2

任意の文字列のセットがあると想像してください。ここで、後続のいくつかの文字以外はすべて等しいと仮定します (この仮定が成り立たない場合は、エラーを返しても問題ありません)。ここで、正規表現を導出して、異なる文字列の部分を識別したいと考えています。

入力：
「こんにちはアリス、私はボブです」、「こんにちはジョン、私はボブです」、「こんにちはジョシュ、私はボブです」。

出力：
「こんにちは(.+)、ボブです。」

入力：
「月曜日」「木」「犬」

出力：
エラー

おそらく、最長の共通部分文字列またはレーベンシュタイン距離を見つけることが役立つでしょうか? それらのいずれかが本当に私の問題に当てはまるかどうか、またはそれらを使用して問題を解決する方法はまだわかりません.

4

1 に答える 1

0

あなたは問題を抱えていて、それを解決するために regexp を使用することに決めました - 今、あなたには 2 つの問題があります。:-)

冗談はさておき、これは 2 つのステップに分けることができます。

  1. 文字列間の違いを識別します。
  2. すべての違いを見て、それらに一致する正規表現を見つけてください。

difflib(1) の場合、言語 ( Pythonなど) で差分計算ライブラリを使用して、2 つの文字列間の同一領域のリストを見つけることが問題です。すべての文字列に共通のセグメントがある場合は、string-1 を string-[2..N] のそれぞれと比較して、結果の同一ブロックを分析します (各ブロックの内容と、他の同一ブロックに対する相対的な位置の両方を比較することについて賢くする必要があります)。ブロック）。同じブロック間のテキストも抽出して記録します。

あなたの例では、比較するたびに2つの同一のブロックが得られます:"Hello "と", I'm Bob.". 同一のブロック間のテキストは、次の文字列になります: "Alice", "John", "Josh".

(2) の場合、最も簡単な解決策は、調査結果を次のもので構成される完全に文字通りの正規表現に結合することです。

Hello+ (Alice|John|Josh)+, I'm Bob.

または、すべての文字列で見つかった同じ同一ブロック間のセグメントを に置き換えます.*。それを貪欲でない一致にすることを検討してください -- .*?.

私はオートマトン理論を知りませんし、DFA/NFA についてはあなたを助けることはできませんが、より精度が必要な場合は、それが確かな方向性です。

于 2012-08-31T22:36:23.253 に答える