Оптимизация соответствия регулярных выражений для длинного списка выражений

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 

Теперь это занимает около 6 секунд для текста длиной ок 35000 символов и список ок. 5000, что слишком медленно. Похоже, что временная сложность этого составляет O(t * n), потому что для каждого из условий t текст нужно сканировать один раз. Есть ли очевидная ошибка производительности здесь? Каковы возможные оптимизации и/или лучшие алгоритмы?

Answer 1

Это может быть сделано для работы в n O (t * log (n)). Я в настоящее время есть две реализации этого хода в производстве

Осуществление # 1:

Совершено в чистом Python. Я построил дерево поиска из файла (меньшего) шаблона, где каждый узел дерева является буквой, которая ссылается на хэш возможных следующих букв. Например, у вас есть три шаблона: кошка, собака и уловка. Следующее дерево быть автоматически построено в О (п):

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

Вы можете теперь текст сканирования и искать каждое слово (или каждый символ) в этом дереве поиска в O (журнал (п)).

Я не поддерживаю регулярное выражение для этого решения, хотя это возможно. Недостатком является то, что Python не обладает хорошей производительностью для этого, и хеш-дерево неэффективно в том, сколько памяти он потребляет. Я предполагал использовать Pypy, переписывая его в Perl или C и делая многопроцессорную обработку.

Осуществление # 2:

Хорошо известный инструмент под названием grep уже делает все выше. Он поддерживает регулярные выражения и может принимать файл шаблонов. По какой-то причине он не любит большие файлы шаблонов, и его производительность экспоненциально ухудшается с увеличением файла шаблона. Это может быть связано с тем, что я сильно использую регулярное выражение. Я закончил разбиение файла шаблона на несколько фрагментов и подал их в grep в параллельных процессах. Для моих приложений grep работает на 10X быстрее. Примечание: установите переменную окружения $ LANG на '', поскольку grep затрудняется из-за сильной локализации.

Вывод:

Построение целевой двигатель в C было бы идеально, но принимая рабочее и широко доступный инструмент GPL может сэкономить вам несколько месяцев своей жизни.