3

複数のファイルがあり、それぞれのファイルで一連の単語を検索しています。

私の正規表現は基本的に、単語 1 の後に単語 2 が続き、単語 3 が続くシーケンスを検索します。したがって、式は次のようになります。

strings = re.findall('word1.*?word2.*?word3', f.read(), re.DOTALL)

20kb 未満のファイルの場合、式はかなりうまく実行されます。ただし、20 kb を超えるファイルでは実行時間が指数関数的に増加し、100 kb に近いファイルではプロセスが完全にハングします。(以前のスレッドを読んだ後) 問題は .* を re.DOTALL と組み合わせて使用​​することに関係しているように見えます-「壊滅的なバックトラッキング」につながります。推奨される解決策は、ファイル全体を 1 つのメモリ バッファーに読み込むのではなく、1 行ずつ入力ファイルを提供することでした。

しかし、私の入力ファイルはランダムな空白と "\n" 改行文字でいっぱいです。私の単語シーケンスも長く、複数の行にまたがっています。したがって、ファイル全体を re.DOTALL と組み合わせて正規表現に入力する必要があります。そうしないと、行ごとの検索でシーケンスが見つかりません。

それを回避する方法はありますか？

4

3 に答える 3

2

正規表現パターンがまったくない3つの単語の出現を文字通り検索している場合、正規表現を使用する必要はまったくありません-私がこの回答を書いたときに@Bartが示唆したように:)。このようなものはうまくいくかもしれません（テストされておらず、おそらくもっときれいかもしれません）：

with open('...') as f:
    contents = f.read()

words = ['word1', 'word2', 'word3']
matches = []
start_idx = 0
try:
    while True:
        cand = []
        for word in words:
            word_idx = contents.index(word, start_idx)
            cand.append(word_idx)
            start_idx = word_idx + len(word)
        matches.append(cand)
except ValueError:  # from index() failing
    pass

これにより、インデックスが に配置されmatchesます。findall と同等の結果が必要な場合は、次のようにします。

found = [contents[match[0]:match[-1]+len(words[-1]] for match in matches]

indexの呼び出しをファイルの同等の関数に置き換えることで、事前にファイル全体を読み込むことなく、この種のアプローチを機能させることもできます。stdlib にそのような関数が含まれているとは思いません。おそらく、ファイル オブジェクトに対してreadline()および/または 同様のメソッドを手動で使用する必要があります。tell()

于 2013-04-04T21:24:55.277 に答える
1

これが発生する理由は、python の正規表現エンジンがバックトラッキングを使用しているためです。ごと.*に、次の単語が見つからない場合、エンジンは文字列の最後 (100kb) まで移動してからバックトラックする必要があります。ここで、最後の一致の後に「ほぼ一致」が多数ある場合にどうなるかを考えてみましょう。エンジンは、試合の開始から文字列の終わりまで前後にジャンプし続けます。

バックトラッキングではなく、NFA に基づく正規表現エンジンを使用して修正できます。これにより、使用できる正規表現の種類が制限されることに注意してください (バックトラッキングや任意のゼロ幅アサーションは使用できません) が、ユース ケースには問題ありません。

そのようなエンジンはここにあります。nfa エンジンがどのように機能するかは、www.debuggex.comで視覚化できます。

于 2013-04-04T21:07:11.950 に答える
0

ループを使用して、一度に 1 つの単語を検索できます。単純な部分文字列検索の方が高速なので、ここを使用str.find()していますが、このコードをre.search()代わりに使用するように調整することもできます。

def findstrings(text, words):
    end = 0
    while True:
        start = None
        for word in words:
            pos = text.find(word, end) #starts from position end
            if pos < 0:
                return
            if start is None:
                start = pos
            end = pos + len(word)
        yield text[start:end]


#usage in place of re.findall('word1.*?word2.*?word3', f.read(), re.DOTALL)
list(findstrings(f.read(), ['word1', 'word2', 'word3']))
于 2013-04-05T05:46:40.653 に答える