式の長いリストの正規表現の最適化

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文字とca.のリスト5000語であり、これは遅すぎる。 tの各用語については、テキストを一度スキャンする必要があるため、この時間の複雑さはO(t * n)であるようです。ここに明白なパフォーマンスバグはありますか？可能な最適化お​​よび/またはより良いアルゴリズムは何ですか？

Answer 1

これは、n O（t * log（n））で動作するようにすることができます。純粋なPythonで完了

：私は現在、生産

実装＃1に、このランニングの2つの実装を持っています。私はツリーの各ノードが可能な次の文字のハッシュにリンクする文字である（より小さい）パターンファイルから検索ツリーを構築しました。たとえば、猫、犬、ドッジの3つのパターンがあります。以下のツリーは自動的にO（n）の中で構築されている：

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

あなたはできるようになりましたスキャンのテキストと（）N（ログ）Oでこのルックアップツリー内のすべての単語（またはすべての文字）を検索します。

私はこのソリューションの正規表現をサポートしませんでしたが、可能です。欠点は、Pythonがこれに対して優れた性能を持たず、ハッシュツリーが消費するメモリ量が非効率的であることです。私はPypyを使ってPerlやCで書き直し、マルチプロセッシングをすることを考えました。

実装＃2：grep呼ば

Aよく知られているツールは、すでに上記のすべてを行います。正規表現をサポートし、パターンのファイルを受け入れることができます。なんらかの理由で、パターンの大きなファイルが気に入らず、パターンファイルの増加に伴ってパフォーマンスが急激に低下します。これは、私が正規表現を頻繁に使用するためである可能性があります。パターンファイルを複数のスライスに分割して並列処理でgrepに渡すことになりました。私のアプリケーションでは、grepは10倍速く動作します。注意：環境変数$ LANGを ''に設定すると、grepは深刻なローカリゼーションの遅さによって妨げられます。

結論：

はCで目標とエンジンを構築するには理想的であるが、作業を取り、広く利用可能なGPLツールにより、数ヶ月にあなたの命を救うことができます。