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

Question

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

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

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

这是一个很好的方法吗？或者你会推荐什么？

Answer 1

您可以在 Mysql中存储Levenshtein 函数。之后，您可以像这样简单地进行搜索：

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

Answer 2

您需要Levenshtein Distance的实现（或非常类似的东西）。这是一个用于 MySQL的函数定义。

Answer 3

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

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