regex - 正規表現でのレーベンシュタイン距離

Question

正規表現クエリにレーベンシュタイン距離を含めることは可能ですか？

（レーベンシュタイン距離1で「こんにちは」を検索するためにこのように順列を結合することを除いて。

.ello | h.llo | he.lo | hel.o | hell.

これは愚かで、レーベンシュタイン距離が長い場合は使用できないためです。）

Answer 1

プログラムで正規表現を生成できます。これは読者の練習問題として残しておきますが、この架空の関数の出力（「単語」の入力が与えられた場合）には、次の文字列のようなものが必要です。

"^(?>word|wodr|wrod|owrd|word.|wor.d|wo.rd|w.ord|.word|wor.?|wo.?d|w.?rd|.?ord)$"

英語では、最初に単語自体、次にすべての可能な単一の転置、次にすべての可能な単一の挿入、次にすべての可能な単一の省略または置換（同時に実行可能）を一致させようとします。

長さnの単語が与えられた場合、その文字列の長さはnに対して線形（特に指数関数的ではない）です。

これは合理的だと思います。

これを正規表現ジェネレーター（RubyではRegexp.new（str）のように）とbamに渡すと、特定の単語からダメラウ・レーベンシュタイン距離が1の任意の単語のマッチャーが得られます。

（ダメラウ・レーベンシュタイン距離2は、はるかに複雑です。）

（？>非バックトレース構造の使用に注意してください。これは、その出力マター内の個々の|'d式の順序を意味します。

その表現を「コンパクト」にする方法が思いつかなかった。

編集：少なくともElixirでは動作するようになりました！https://github.com/pmarreck/elixir-snippets/blob/master/damerau_levenshtein_distance_1.exs

ただし、これは（教育目的を除いて）必ずしも1の距離にしか到達しないため、お勧めしません。正当なDLライブラリを使用すると、距離> 1を計算できます。これは正規表現であるため、構築するとかなり高速に動作する可能性があります（このコードは現在、すべての比較で再構築されているため、「コンパイル済み」の正規表現をどこかに保存する必要があります）。

Answer 2

近似一致機能を備えた正規表現方言がいくつかあります。つまり、TREライブラリとregexPython用のPyPIモジュールです。

TREの近似一致構文については、 https：//laurikari.net/tre/documentation/regex-syntax/の「近似一致設定」セクションで説明されています。レーベンシュタイン距離1内のものと一致するTRE正規表現は次のhelloようになります。

(hello){~1}

モジュールのregex近似一致構文は、https：//pypi.org/project/regex/のテキストで始まる箇条書きで説明されていますApproximate “fuzzy” matching。regexレーベンシュタイン距離1内のものと一致する正規表現は次のhelloようになります。

(hello){e<=1}

おそらく、これらの構文のいずれかが他の正規表現の実装で採用されることになるでしょうが、現時点では、これら2つしか知りません。

Answer 3

正規表現クエリにレーベンシュタイン距離を含める方法はありますか？

いいえ、正気ではありません。レーベンシュタイン距離アルゴリズムを実装するか、既存のアルゴリズムを使用するのが最善の方法です。