2

ドキュメント内の複数のn-gramに一致する正規表現を実行しようとしています。最初にn-gramのリストを取得し、次のように正規表現にコンパイルします。

sNgrams = '|'.join(('\s+'.join(re.escape(gram) for gram in nGram.split())) for nGram in aNgrams)

（n-gramを任意の空白文字のトークンに分割し、これらのトークンを再エスケープして'\ s +'-esで結合します（改行、ダブルスペース、タブなどでngramを一致させることができます）。正規表現に「|」が付いたn-gram）

私の正規表現は次のようになります。

reNgram = re.compile('(\A|\W+)(' + sNgrams + ')(?=\W+|\Z)',flags=re.UNICODE|re.IGNORECASE)

現在、これはほとんどの場合に正常に機能しますが、n-gramが別のn-gramとオーバーラップする場合、一致するものは1つだけです。

doc = 'aap noot mies'

aNgrams = ['aap','noot','aap noot']
sNgrams = 'aap|noot|aap\\s+noot'
re.findall(reNgram,doc)
[('', 'aap'), (' ', 'noot')]

aNgrams = ['mies','aap noot']
re.findall(reNgram,doc)
[('', 'aap noot'), (' ', 'mies')]

  • これを解決する方法はありますか？ドキュメント内で一致するすべての（サブ）文字列を返すには？

  • さらに、速度/効率は非常に重要です（私はこれらの正規表現を何万も発射しています）、最適化するために私ができることはありますか？「オンザフライ」でコンパイルされた正規表現はとにかくキャッシュされるため、正規表現の事前コンパイルはあまり効果がないことを読みましたが、これらの式を高速化するために実行できる（他の）明らかな手順はありますか？

4

1 に答える 1

4

単一の正規表現でそれを行うことはできないと思います。

あなたは少し近づくことができます

  • 先読みアサーションを使用して、少なくとも同じ位置から開始しない重複する一致を見つける
  • nグラムを長さで降順に並べ替えて、より大きな一致が最初に見つかるようにします

これで、実際の重複一致 (noot開始後app noot) を見つけることができます。

>>> sNgrams = '|'.join(('\s+'.join(re.escape(gram) 
...                    for gram in nGram.split())) 
...                    for nGram in reversed(sorted(aNgrams, key=len)))
>>> sNgrams
'aap\\s+noot|noot|aap'
>>> reNgrams = re.compile(r"(?<!\w)(?=(" + sNgrams + r")(?!\w))",
...                         flags=re.UNICODE|re.IGNORECASE)
>>> reNgrams.findall(doc)
['aap noot', 'noot']

しかし、まだ と の両方aapを見つけることができませんaap noot。正規表現は、文字列内の位置ごとに 1 つの一致しか報告できないため、2 つのうちの 1 つに一致する必要があります。

これを回避するには、n-gram のリストを、どの文字列も同じ単語で始まらないリストに分割し、それらの正規表現を順番に適用する必要があります。それはあまりパフォーマンスが高くないと思いますが、他の方法は見当たりません（独自の正規表現で各単語をチェックする以外に、それも非常に高速ではありません）。

于 2012-10-23T09:02:48.403 に答える