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

Question

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

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

因此，例如，我希望为d = 1和s = 'abc'生成一个：r = 'abc|.abc|.bc|a.c|ab.|abc.'等形式的正则表达式r。但我不确定这是否非常有效，或者已经有一些好的算法来解决这个问题？我想考虑编辑距离内的字符交换。所以'acb'也应该是r的一部分。我想用PHP实现它，然后执行一个SQL查询：SELECT * FROM table WHERE name RLIKE TheRegularExpression。

这样做是个好方法吗？或者你会推荐什么？

Answer 1

也许最好的做法是为所有的可能性建立一个迭代过程。换句话说，就像这样：

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 2

您可以在Mysql中存储Levenshtein function。在此之后，您可以简单地执行如下搜索：

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

Answer 3

你需要一个Levenshtein Distance (或者非常类似的东西)的实现。这是一个与MySQL一起使用的function definition。