正則表達式中的Levenshtein距離

Question

有沒有可能在正則表達式查詢中如何包含levenshtein距離？

除了在排列之間進行聯合之外。喜歡用L.d.搜索「hello」。 1

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

這是一個很大的愚蠢和不可用的L.d.較大的數字。

Answer 1

是否有可能如何在正則表達式查詢中包含levenshtein距離？

不，不是一種健全的方式。實現 - 或使用現有的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，你得到了一個與給定單詞Damerau-Levenshtein距離爲1的任何單詞的匹配器。

（2 Damerau-的Levenshtein距離是複雜得多。）

注意使用（>非回溯構建體，它的意思是個體的量級|？「。d表達式在於輸出物質

我想不出辦法「緊湊」那表情

編輯：我得到它的工作，至少在藥劑https://github.com/pmarreck/elixir-snippets/blob/master/damerau_levenshtein_distance_1.exs

我不一定會推薦這雖然（除教育！ PU因爲它只會讓你的距離爲1;一個合法的DL庫可以讓你計算距離大於1.儘管由於這是正則表達式，它可能會工作得很快，一旦構建（注意，你應該在某處保存「編譯」正則表達式，因爲這個代碼目前在每次比較時都重構它）。