为给定的字符串和编辑距离生成正则表达式

Question

我有一个问题，我想匹配数据库中的所有字符串与给定的字符串一定的编辑距离。

我的想法是生成一个正则表达式，将所有字符串与编辑距离d与字符串s。

匹配。

因此，例如，我想以：r = 'abc|.abc|.bc|a.c|ab.|abc.'等形式生成d = 1和s = 'abc'的REGEX r。但是我不确定这是非常有效的还是已经有一些好算法了？我想考虑在编辑距离中的字符交换。因此，'acb'也应该是r的一部分。我想在PHP中意识到它，然后进行SQL查询：SELECT * FROM table WHERE name RLIKE TheRegularExpression。

是这样做的好方法吗？或您推荐什么？

Answer 1

您可以将Levenshtein函数存储在MySQL中。之后，您可以简单地进行搜索：

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

Answer 2

可能要做的最好的事情是为所有可能性建立一个迭代过程。换句话说，类似的东西：

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);

Answer 3

您需要实现Levenshtein距离（或非常相似的东西）。这是用于MySQL的函数定义。