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

Question

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

我的想法是生成一个正则表达式，将所有字符串与编辑距离 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。

这样做有什么好的方法吗？或者您会推荐什么？

Answer 1

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

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