文字列を正規表現に一致するように変換する編集操作の最小数

Question

いくつかの文字列を正規表現に一致させるために、最小限の操作数（挿入、削除、置換）を計算する方法はありますか？例えば

、正規表現(ab)+と一致する文字列babaに変換する操作の最小数は2である：それはどちらかababab（+2文字）またはab（-2文字）に変えることが必要です。

Answer 1

文字列と正規表現の間でLevenshtein distanceを計算できますが、これは2つの生の文字列の類似性を測定するため意味がありません。

おそらく、文字列がパターンと一致するために受ける必要がある操作の数を測定することです。

ここではグラフ理論に基づいた解決法があります。

まず、正規表現で定義された言語を表すオートマトンを構築する必要があります。 Thompson's algorithmがお手伝いします。

このオートマトンを構築したら、式が一致するように最善の努力をして、それがオフになるたびに修正することができます。 修正の数は、文字列から正規表現で記述された言語までの距離になります。

ここでは、正規表現の例を示します：.*a.*。 対応するオートマトンは次のとおりです。

だがbbb文字列の距離を確認してみましょう。

1. 最初の文字がbあるので、我々は再び
2. b1にとどまるので、私たちは1
まだ
3. bに滞在、我々は1
4. 文字列が空に滞在し、我々はしていますまだ最終状態ではない2。 aを追加しましょう。さて、2に行くことができます。
5. 私たちは2です。文字列に文字が残っていないので、よかったです。

私たちは、元の文字列に1つの修正をしたので、bbbから.*a.*正規表現までの距離は1です。 実際には、任意の単語とその言語との距離は、または1のいずれかです。これは、その単語がa（バイナリ）であるためです。

これは単なるアイデアであり、欠陥があるかもしれませんが、あなたはそれを使って何かできると思います。