これらのタイプの正規表現は最適化できますか？

Question

私は、テキストから重要な情報を引き出す必要があるアプリケーションに取り組んでいます。このキャッチは、OCRされたドキュメントから来るテキストであるため、OCR認識エラー、ノイズ、ガベージ文字などが存在する可能性があります。また、ドキュメントのテキストは、ソースに応じて100万種類もあります。

したがって、多くの正規表現を使用してテキストを引き出します。大量になると、サーバー上のCPUが壊れていました。私は正規表現をあらかじめコンパイルして、改善せずにキャッシュしてみました。プロファイラは、ランタイムの65％がRegex.Match（）の呼び出しによるものであることを示しています。

正規表現を読み上げると、壊滅的なバックトラックがパフォーマンス上の問題であることがわかります。

のは、私は（これは私たちの正規表現の一般的なフォーマット説明するために単純なものです - 他の人がより多くのキーワードと形式を含めることができます）このような式があるとしましょう：

(.*) KEYWORD1 AND (.* KEYWORD2) 

私はステップスルー正規表現のコーチと、私はそれが文字列に一致するバックトラックの多くを参照してください。

このタイプの正規表現を概念的に改善できますか？私たちは文書全体（テキストの小塊）のサブセットに対してのみ実行しますが、ブロブを取り出すための前処理は本質的に完璧ではありません。

だから、ええ、ほとんど何が「KEYWORD1」の前に現れることができ、何が「KEYWORD2」の前に現れることができる、など

我々はAZに制限する代わりにすることはできません。*、OCRで以来、文字は時には数字に間違い（Illene = I11ene）したり、OCR認識エラーのためにそこにガベージ文字を入れることがあります。

Answer 1

はい、これらのタイプは簡単に最適化できます。

正規表現を目的のコードに置き換えて最適化します。つまり、2つの部分文字列検索です。 " KEYWORD1 AND "の位置が"KEYWORD2"の位置よりも小さい場合は、一致します。

高速化のために、最適化された部分文字列検索を使用できますが、ほとんど必要ありません。正規表現を削除するだけで、大幅なスピードアップが可能になります。

[編集] [OK]をクリックすると400が表示されます。そのうちいくつかはやや複雑です。パターンは変わっていない実質的な部分文字列で、効果的に配置できます。入力に"PART OF"があることがわかっている場合は、約1ナノ秒で" PART OF"が発生するかどうかを確認できます。そして、PARTF OF_ _doesn't_ occur, you don't need to check at all whetherの部分が発生した場合。

現在、400の正規表現はあまりありません。 40.000の場合は、共通の部分文字列のチェックを自動化する価値があります。現時点では、他の399正規表現の文字列と一致させようとすると、それぞれの正規表現を順番に実行することができます。 .*PART OF.*は".*AS PART OF.*"と一致します。

同じ理由で、他の最適化も必要ありません。 40.000の正規表現をマッチさせると、各文字ペアの頻度が計算されます。私。入力FOO AS PART OF BARは、文字ペアFO, OO, PA, AR (twice), RT, OF, BAを持っています。これは、.*FOR EXAMPLE.*の文字ペアEXと一致しません。右