爲給定的字符串和編輯距離生成正則表達式

我有一個問題，我想匹配數據庫中與給定字符串具有一定編輯距離的所有字符串。爲給定的字符串和編輯距離生成正則表達式

我的想法是生成一個正則表達式，它可以將編輯距離爲d的所有字符串匹配到字符串s。

因此，例如，我想生成d = 1和s = 'abc'的形式正則表達式r：r = 'abc|.abc|.bc|a.c|ab.|abc.'等。但我不確定這是否非常有效，或者是否已經有一些針對該問題的良好算法？我甚至想在編輯距離中考慮字符交換。所以'acb'也應該是r的一部分。我想在PHP中實現它，然後進行SQL查詢：SELECT * FROM table WHERE name RLIKE TheRegularExpression。

它是一個很好的方式來做到這一點？或者你會推薦什麼？

來源

2012-11-02 Martin Cup

如果你想效率，首先要避免應用的WHERE條件不能在表中使用索引的所有記錄得到解決，除非該表是相當小。 – millimoose

另外，考慮結果模式的長度將是'O（nCd）'，其中'n'是字符串的長度，'d'是您的距離。這可能會導致非常大的模式。例如，對於一個'80'字符串，所需的距離爲'5'，您將向數據庫發送一個約2千兆字節的RE。（這只是考慮字符替換，而不是換位。）但是，如果您確定字符串將會短並且/或者'd'非常小或非常接近'n'，則可能是可行的。 – millimoose

另一個含義是，如果用戶輸入字符串，則需要確定長度是否在一定限度內，否則會創建DoS漏洞。（與使用用戶輸入參數的任何非常非常低效的算法一樣）。 – millimoose

可能最好的事情是建立一個迭代過程的所有可能性。換句話說，這樣的事情：

function findall($startString) { 
    // create an array of all strings that are distance one away 
    // each element would be $returnArray["abc"] = "abc"; 
} 

$d = 2; // distance 
$myArray[$startString] = $startString; 

for($i = 0; $i < $d; $i++) { 
    $newCombos = array_merge(array(), $myArray); 
    foreach($myArray as $element) { 
     $newCombos = array_merge($newCombos, findall($element)); 
    } 
    $myArray = array_merge(array(), $newCombos); 
} 

$myRegex = implode("|", $myArray);

來源

2012-11-02 17:38:53 durron597

謝謝！奇蹟般有效！ –

我唯一注意到的解決方案是，對於較長的單詞和編輯距離高於2的sql查詢非常長且很慢。 –

我實際上認爲Levenshtein函數解決方案可能比我的更好（通過enrico.bacis），你應該檢查一下 – durron597

您需要執行Levenshtein Distance（或類似的東西）。這裏是用於MySQL的function definition。

來源

2012-11-02 17:37:05 diolemo

一旦確定的編輯距離超過了所需的閾值，修改該算法可能會更有效，而不是不必要地計算確切的結果。 – millimoose

謝謝。問題是，在我想使用它的服務器上，我沒有權利使用存儲的函數和過程...所以我必須用PHP實現它... –

您可以在Mysql中存儲Levenshtein function。之後，你可以簡單地做這樣的搜索：

mysql_qery("SELECT `term` FROM `words` WHERE levenshtein('$word', `term`) BETWEEN 0 AND '$d'");

來源

2012-11-02 17:38:29

爲給定的字符串和編輯距離生成正則表達式

回答

相關問題