让正则表达式尝试运行更快？

Question

我有一个 50mb 的正则表达式特里树，我用它来拆分短语。

相关代码如下：

import io
import re

with io.open('REGEXES.rx.txt', encoding='latin-1') as myfile:
        regex = myfile.read()


while True == True:
    Password = input("Enter a phrase to be split: ")

    Words = re.findall(regex, Password)

    print(Words)

由于正则表达式太大，这需要很长时间！

这是我现在正在尝试的代码，使用 re.compile(TempRegex):

import io
import re

with io.open('REGEXES.rx.txt', encoding='latin-1') as myfile:
        TempRegex = myfile.read()

regex = re.compile(TempRegex)

while True == True:
    Password = input("Enter a phrase to be split: ")

    Words = re.findall(regex, Password)

    print(Words)

我想做的是检查输入的短语是否是名称的组合。例如，短语 "johnsmith123" 到 return ['john', 'smith', '123']。正则表达式文件是由一个工具根据来自 Facebook 的每个名字和姓氏的单词列表创建的。我想看看输入的短语是否本质上是该单词列表中单词的组合......如果 johns 和 mith 是列表中的名字，那么我想要 "johnsmith123" 到 return ['john', 'smith', '123', 'johns', 'mith']。

Answer 1

如果编译它，正则表达式模式将被编译成字节码，然后运行由匹配引擎编译。如果你不编译它，它会在调用时为同一个正则表达式一遍又一遍地加载它。这就是为什么如果您对多个不同的记录使用相同的正则表达式，编译的速度会更快。

Answer 2

Python 的正则表达式引擎实际上不是正则表达式，因为它包括后向、捕获组、反向引用等功能，并使用回溯来匹配最左边的有效分支而不是最长的分支。

如果您使用真正的正则表达式引擎，并且您的正则表达式不需要这些功能，您几乎总能获得更好的结果。

真正的正则表达式最重要的品质之一是它将总是return结果的时间与输入的长度成正比，而无需使用任何内存。

我自己用 C 实现的 DFA 写了一个（但可以通过 cffi 从 python 中使用），它将具有最佳的渐近性能，但我没有尝试过矢量化等常数因子改进和装配一代。我没有制作普遍可用的 API，因为我只需要从我的库中调用它，但从示例中应该不难理解。（请注意，搜索可以实现为先与 .* 匹配，然后再向后匹配，但出于我的目的，我宁愿 return 单个字符作为错误标记）。 Link to my project

您也可以考虑离线构建 DFA 并将其用于程序的多次运行 - 但这是 flex 所做的，所以我对我的项目这样做没有意义，所以也许只是使用如果您对 C 感到满意？当然，无论如何您几乎肯定必须编写一些自定义 C 代码才能使用我的项目...

Answer 3

我认为正则表达式不是解决问题的方法。在我看来，您要做的就是找到给定字符串中恰好是名称的所有子字符串的列表。

如果用户输入的是密码或口令，则表示字符串相对较短。很容易将该字符串分解为一组可能的子字符串，然后针对包含名称的另一组测试该组。

长度为n的字符串中子串的个数为n(n+1)/2。假设没有人会输入超过 40 个字符，您只会看到 820 个子字符串，其中许多可能会因为太短而被删除。这是一些代码：

def substrings(s, min_length=1):
    for start in range(len(s)):
        for length in range(min_length, len(s)-start+1):
            yield s[start:start+length]

所以问题是将名称加载到 suitable 数据结构中。您的正则表达式为 50MB，但考虑到您在其中一条评论中显示的片段，由于正则表达式语法的开销，实际数据量将比实际数据量小很多。

如果您只是使用每行一个名称的文本文件，您可以这样做：

names = set(word.strip().lower() for word in open('names.txt'))

def substrings(s, min_length=1):
    for start in range(len(s)):
        for length in range(min_length, len(s)-start+1):
            yield s[start:start+length]

s = 'johnsmith123'
print(sorted(names.intersection(substrings(s)))

可能给出输出：

['jo', 'john', 'johns', 'mi', 'smith']

考虑到可能的小数据集，我怀疑是否会出现内存问题，但是如果您发现没有足够的内存来一次加载完整的数据集，您可以考虑使用 sqlite3 和一个简单的table 存储名称。这样查询起来会比较慢，但它适合内存。

另一种方法是使用 shelve 模块创建一个以名称作为键的持久字典。

让正则表达式尝试运行更快？

Getting a regex trie to run faster?

python

regex

python-3.x

trie

让正则表达式尝试 运行 更快？

Getting a regex trie to run faster?

python

regex

python-3.x

trie

让正则表达式尝试运行更快？