为mysql /模糊搜索实现Levenshtein距离？

我希望能够按照以下方式搜索一个表格,因为它可以获得1个方差范围内的所有内容.

数据:

O'Brien
Smithe
Dolan
Smuth
Wong
Smoth
Gunther
Smiht

我已经研究过使用Levenshtein距离有没有人知道如何实现它？

为了使用levenshtein距离进行有效搜索,您需要一个有效的专用索引,例如bk-tree.不幸的是,我所知道的数据库系统,包括MySQL,都没有实现bk-tree索引.如果您正在寻找全文搜索,而不是每行只有一个术语,这将更加复杂.另一方面,我想不出任何可以以允许基于levenshtein距离进行搜索的方式进行全文索引的方式.

有一个Levenshtein距离函数的mysql UDF实现

https://github.com/jmcejuela/Levenshtein-MySQL-UDF

它在C中实现,并且具有比schnaader提到的"MySQL Levenshtein距离查询"更好的性能

damerau-levenshtein距离的实现可以在这里找到: Damerau-Levenshtein算法:具有转置 的Levenshtein对纯Levenshtein距离的改进是考虑字符的交换.我在schnaader链接的评论中找到了它,谢谢!