python - 优化长表达式列表的正则表达式匹配

Question

问题定义:给定长度为 n 个字符的文本和长度为 t 的术语列表(可以是正则表达式)，找到并计算所有出现的次数文本中的术语。

这是一个简单的实现:

class WordFrequency(TextAnalysis):
    """Determines the frequency of words from a vocabulary in a given text"""

    def __init__(self, vocabulary, text):
        """
        :param vocabulary: contains the words (e.g. list)
        :param text: the analysed text
        """
        self.text = text
        self.vocabulary = vocabulary
        self.matches = {}

    def run(self):
        """
        :return: self for method chaining
        """

        ltext = self.text.lower()
        self.freq = {} # word -> absolute frequency
        for word in self.vocabulary:
            matches = re.findall(r'\b' + word + r'\b', ltext)
            self.matches[word] = [match for match in matches]  #.lstrip() for match in matches]
            self.freq[word] = len(matches)
        return self

现在，对于长度为 ca 的文本，这大约需要 6 秒。 35000 个字符和一个 ca 列表。 5000 条，太慢了。看起来它的时间复杂度是 O(t * n)，因为对于每个 t 术语，文本都必须被扫描一次。这里有明显的性能错误吗？有哪些可能的优化和/或更好的算法？

Answer 1

这可以在 n O(t * log(n)) 中工作。我目前有两个在生产中运行的实现

实现#1:

用纯 Python 完成。我从(较小的)模式文件构建了一个搜索树，其中树的每个节点都是一个链接到可能的下一个字母的散列的字母。例如，您有三种模式:cat、dog 和 dodge。以下树在 O(n) 中自动构建:

{
    'c': {'a': {'t': 'cat'}},
    'd': {'d': {'g': {'e': 'dodge'}},
          'o': {'g': 'dog'}}
}

您现在可以扫描文本并在 O(log(n)) 的查找树中查找每个单词(或每个字符)。

我不支持此解决方案的正则表达式，尽管它是可能的。缺点是 Python 对此没有很好的性能，哈希树在消耗多少内存方面效率低下。我考虑使用 Pypy，用 Perl 或 C 重写它并进行多处理。

实现#2:

一个名为 grep 的著名工具已经完成了上述所有工作。它支持正则表达式并且可以接受模式文件。由于某种原因，它不喜欢大文件的模式，并且其性能随着模式文件的增加呈指数级下降。这可能是因为我大量使用正则表达式。我最终将模式文件分成多个片段，并将它们提供给并行进程中的 grep。对于我的应用程序，grep 的运行速度提高了 10 倍。注意:将环境变量 $LANG 设置为 ' '，因为严重的本地化缓慢阻碍了 grep。

结论:

用 C 构建一个目标引擎是理想的，但是通过使用一个有效且广泛可用的 GPL 工具可以为您节省几个月的时间。