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

Question

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

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

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

这样做合适吗？或者你有什么建议？

- Martin Cup

---

如果你想要高效率，首先你应该避免对一个表中所有记录应用无法使用索引解析的 WHERE 条件，除非那个表相当小。 - millimoose

另外，请注意，生成的模式长度将为O(nCd)，其中n是字符串的长度，d是您的距离。这可能会导致非常大的模式。例如，对于一个长度为80个字符的字符串，希望距离为5，您将向数据库发送约2GB的正则表达式。（这仅考虑字符替换，不包括转位。）但是，如果您确定字符串将很短和/或d非常小或非常接近n，那么这可能是可行的。 - millimoose

这意味着如果字符串是由用户输入的，你需要确保长度在一定限制内，否则会创建一个DoS漏洞（就像任何使用用户输入参数的非常非常低效的算法一样）。 - millimoose

Answer 1

你可以在Mysql中存储一个Levenshtein函数。之后，你只需像这样进行搜索：

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

- enrico.bacis

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

- durron597

---

我注意到这个解决方案的唯一问题是，对于长度较长且编辑距离大于2的单词，SQL查询非常冗长和缓慢。 - Martin Cup

我认为Levenshtein函数的解决方案可能比我的更好（由enrico.bacis提供），你应该去看看。 - durron597

Answer 3

您需要实现Levenshtein Distance（或类似的算法）。这里提供了一个适用于MySQL的函数定义。

- diolemo

---

修改该算法，当确定的编辑距离超过所需的阈值时立即停止计算，相比于无谓地计算出精确结果，这样可能会更高效。 - millimoose

谢谢。问题是，在我想使用它的服务器上，我没有使用存储函数和过程的权限...所以我必须用php来实现它... - Martin Cup