为单词列表拟合正则表达式Fitting a regular expression to a list of words

假设你想搜索一个单词列表。如果你使用的是 grep，可以添加 -f 标志来提供一个正则表达式文件，并添加 -F 标志来告诉它这些正则表达式实际上只是普通单词。几天前我在搜索诊断代码时就是这么做的。

grep -w -F -o -f icd10codes.txt notes.txt

现在你可能出于效率或其他原因，想把这个单词列表合并成一个单一的正则表达式。显然 ripgrep 就是这么做的，因为当我尝试在上面的命令中用 ripgrep 替换 grep 时，我收到了一个错误提示：“Compiled regex exceeds size limit of 104857600 bytes.”

胜过暴力匹配

假设你想搜索字符串“bluecross”、“blueshield”和“bluey”。你可以简单地构造一个暴力匹配的正则表达式

bluecross|blueshied|bluey

但这并没有利用这三个字符串都以“blue”开头这一事实。一个更小的正则表达式应该是

blue(shield|cross|y)

寻找匹配单词列表的最短正则表达式是一个难题，但寻找一个比暴力匹配更短的正则表达式并不难。Python 包 trieregex 就能做到这一点。根据文档说明，

trieregex 通过将单词列表存储在字典树（trie）结构中，并将该字典树转换为更紧凑的模式，从而创建高效的正则表达式（regexes）。

让我们用 trieregex 试一下前面的 blue 例子。

import re
from trieregex import TrieRegEx as TRE

words = ['bluecross', 'blueshield', 'bluey']
tre = TRE(*words) 
print(tre.regex())

这会生成与上面相同的正则表达式，只是它添加了 ?: 使括号变为非捕获组。

blue(?:shield|cross|y)

前缀与后缀

该库利用公共前缀构建字典树数据结构。这在上述例子中效果很好，但当我们有公共后缀而不是公共前缀时，结果就令人失望了。以下代码

words = ['javascript', 'typescript']
tre = TRE(*words) 
print(tre.regex())

生成的正则表达式

(?:javascript|typescript)

这并不比暴力匹配好多少，而我们原本可能期望的是

(?:java|type)script

HCPCS 示例

正如文章开头提到的，ripgrep 无法搜索 ICD-10 代码列表。HCPCS 代码列表的大小约为前者的十分之一，且更具可压缩性。Ripgrep 能够将所有 HCPCS 代码放入单个正则表达式中，并且搜索测试文件的速度比 grep 快得多。该命令

grep -w -F -o -f hcpcs.txt notes.txt

执行耗时 73.426 秒，而命令

rg -w -F -o -f hcpsc.txt notes.txt

耗时 0.078 秒，快了三个数量级。

以下代码将从文件中读取 HCPCS 代码列表并创建一个正则表达式。

tre = TRE()
with open('hcpcs.txt', 'r') as file:
    for line in file:
        tre.add(line.strip())
print(len(tre.regex()))

结果显示生成的正则表达式有 17,198 个字符。代码文件包含 8725 个五个字符的代码，因此该正则表达式将代码字符压缩了大约 5:2 的比例。