6

重複の可能性：
指定された文字列のリストから正規表現を自動生成するにはどうすればよいですか？

ListAとListBの文字列の2つのリストがあります。ListAのすべての文字列に一致し、 ListBのどの文字列にも一致しない正規表現を生成する必要があります。

  • 文字列には、文字、数字、句読点の任意の組み合わせを含めることができます。
  • 文字列がListAに表示される場合、その文字列がListBに含まれないことが保証されます。
  • 文字列がこれら2つのリストのいずれにも含まれていない場合、マッチングの結果がどうなるかは関係ありません。

リストには通常、数千の文字列が含まれており、文字列は互いにかなり似ています。

私はこの質問に対する簡単な答えを知っています。それは、ListAからの文字列(Str1)|(Str2)|(Str3)であるフォームの正規表現を生成するだけです。StrNしかし、私はこれを行うためのより効率的な方法を探しています。

理想的な解決策は、2つのリストを取得し、このためのJava正規表現を生成するある種のツールです。

更新1：「効率的」とは、自明な解よりも短い式を生成することを意味します。理想的なアルゴリズムは、短縮された可能な式を生成します。下記は用例です。

ListA = { C10 , C15, C195 }
ListB = { Bob, Billy }

理想的な表現は

/^C1.+$/

別の例として、ListBの3番目の要素に注意してください

ListA = { C10 , C15, C195 }
ListB = { Bob, Billy, C25 }

理想的な表現は 

/^C[^2]{1}.+$/

最後の例

ListA = {A、D、E、F、H} ListB = {B、C、G、I}

理想的な表現は、簡単な解決策と同じです。

/^(A|D|E|F|H)$/

また、私は理想的な解決策を探していません。些細なことよりも優れたものが役立つでしょう。私は、些細な解決策のリストを生成するという方針に沿って考えていました。次に、ListBの領域に迷わないように注意しながら、共通のサブストリングをマージしようとしました。

**アップデート2*：正規表現の生成にかかる時間については特に心配していません。最新のマシンでは10分未満であれば問題ありません。

4

1 に答える 1

0

両方のリストに文字列が含まれないことが保証されていて、どちらのリストにも含まれていない文字列を気にしない場合は、ListAの文字列と一致させる必要があります。ListBは完全に無視できます。

あなたが言及した「些細な答え」は完全に合理的な解決策です。「より効率的な」方法が必要だと言うとき、それは正規表現自体を生成する効率的な方法を意味しますか、それとも文字列により効率的に一致する正規表現を生成する方法を意味しますか？

  • 正規表現を効率的に生成したい場合、ほとんどの言語の文字列機能は、文字列のリストを区切り文字列（コンマなど）で結合して単一の文字列を生成する方法を提供します。それ以上に効率的になることはできません。
  • 式を効率的に一致させたい場合は、使用する前に必ず「コンパイル」してください。（ほとんどの正規表現ライブラリにはこのための関数があります。）正規表現をコンパイルするということは、正規表現ライブラリが実際にマッチング操作に使用する有限状態マシンを生成することを意味します。適切な正規表現ライブラリは、FSMを最適化する適切な仕事を行う必要があります。たとえば、可能な場合は、共通のサブストリングを同じFSM状態にマッピングします。

または、正規表現を完全に省略して、ListAを繰り返し処理し、その各文字列を候補の文字列と比較することもできます。この場合、完全に一致する文字列を探すと4バイトまたは8バイトのチャンクの文字列を比較できるため、個々の比較はより高速になる可能性がありますが、正規表現では各文字を個別に調べる必要があります。ただし、比較する文字列がたくさんある場合は、メモリ内で候補の文字列を何度もトラバースすることになります。逆に、正規表現は候補文字列を1回トラバースして、一致するかどうかを確認できます。

両方のアプローチを試してください。どちらが速いかを確認してください。

于 2012-10-14T22:23:37.027 に答える