正規表現のLevenshtein距離

Question

正規表現のクエリにlevenshtein距離を含める方法はありますか？

置換の間で和集合を作ることを除いて。 L.dで "hello"を検索するのと同じように。 1

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

これは非常に愚かであり、多くのL.d。

Answer 1

正規表現のクエリにlevenshtein distanceを含める方法はありますか？

いいえ、まともな方法ではありません。既存のアルゴリズムを実装するか、既存のアルゴリズムを使用することで、Levenshtein距離アルゴリズムが実現します。

Answer 2

プログラムで正規表現を生成できます。まず、あなたが合うようにしようと、英語で

"^(?>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のDamerau-Levenshteinの距離を持つ任意の単語のマッチャーを取得しました。その出力物の「D式

|

（2のDamerau・レーベンシュタイン距離ははるかに複雑である。）個々のオーダーを意味します（>非バックトレース構築物の

注意使用？。

は、私は「コンパクト」という表現方法を考えることができませんでした

EDITを：。私はそれが、少なくともエリクサーで、動作するようになったhttps://github.com/pmarreck/elixir-snippets/blob/master/damerau_levenshtein_distance_1.exs

私は必ずしも教育を除いて（このかかわらをお勧めしません！ puあなたは1の距離にあなたを得ることができるので、正規のDLライブラリはあなたが距離> 1を計算させるでしょう。これは正規表現なので、一度構築するとかなり速く動作するでしょう（このコードは現在、すべての比較で再構築されているので、 "コンパイルされた"正規表現はどこかで保存してください）。