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

问题描述

我希望能够按如下方式在表中搜索 smith，以获取它在 1 个方差范围内的所有内容.

数据:

奥布莱恩史密斯多兰斯穆斯黄斯莫斯冈瑟史密斯

我已经研究过使用 Levenshtein distance 有人知道如何用它来实现吗?

解决方案

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

I would like to be able to search a table as follows for smith as get everything that it within 1 variance.

Data:

O'Brien
Smithe
Dolan
Smuth
Wong
Smoth
Gunther
Smiht

I have looked into using Levenshtein distance does anyone know how to implement this with it?

解决方案

In order to efficiently search using levenshtein distance, you need an efficient, specialised index, such as a bk-tree. Unfortunately, no database system I know of, including MySQL, implements bk-tree indexes. This is further complicated if you're looking for full-text search, instead of just a single term per row. Off-hand, I can't think of any way that you could do full-text indexing in a manner that allows for searching based on levenshtein distance.

这篇关于为 mysql/模糊搜索实现 Levenshtein 距离?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！