搜索具有误差范围的特定字符串

Question

如何在有误差的情况下搜索特定的 string？

示例：

我有一个 table 具有以下 values:

Brands Table

Brand: Panasonic, Model: 15T

Brand: Apple, Model: IPHONE 7

Brand: Samsung, Model: Galaxy S8

Brand: Microsoft, M15

而且我想找到一个边距为3个错误字符的重合点。例如，我的输入是 M$crosoft，我希望它 return Microsoft row。或者如果我输入 Pnasonic 它应该输入 Panasonic row.

如何在不牺牲性能的情况下实现这一目标？简单的方法是比较每个字符和 3 个错误的计数器，但我需要性能，因为品牌 table 有大约 200K+ rows.

P.S 我在 PHP.

编码

Answer 1

您可能希望结合使用 Metaphone 和 Levenshtein。（拼写错误）

http://php.net/manual/en/function.metaphone.php

和

http://php.net/manual/en/function.levenshtein.php

Metaphone 作用于声音，因此 "poor" 示例是您可以将其视为删除元音并将一些复合声音更改为单个字母（几乎像 shorthand ）。所以使用你的例子

$sound1 = metaphone('M$crosoft');

echo "$sound1\n";

$sound2 = metaphone('Microsoft');

echo "$sound2\n";

产出

MKRSFT
MKRSFT

如您所见，它们是匹配的。

你可以在这里测试

http://sandbox.onlinephpfunctions.com/code/716471f5fed18268a2dc0aea800b3db634d9616f

性能由于运行ning metaphone 的额外开销，我建议预先计算您搜索的词的声音索引之前，并将它们保存在数据库中。然后，当您运行用户搜索您时运行对他们的搜索词使用相同的 metaphone 功能，并使用它来搜索 table 中的声音索引。这样您就可以预先加载构建声音索引的成本，并且只需执行一次（或在编辑记录时）

不过，您可能会觉得搭配过于松散，这时您可以使用Levenshtein。这会根据所需的更改计算 2 个单词之间的差异。比如需要做的insert update和delete，你甚至可以对这些操作进行加权

$len = levenshtein ('M$crosoft', 'Microsoft');

echo "$len\n";

//as you can see the arguments are $str1, $str2, insert cost, replace cost, delete cost
//so we can control what weight we get for each operation.
$len = levenshtein ('M$crosoft', 'Microsoft', 1,2,1);

echo "$len\n";

输出

1
2

现在，如果您需要将它与 "Bunch" 的文本结合起来，这可能会变得非常复杂，因为您必须在 DB 上使用全文搜索。

这不是微不足道的。

可能更好的选择是考虑使用像 Sphinx 这样的全文搜索引擎。让它基本设置起来并不难。但它也不会是灵丹妙药，所以你必须做一些事情，比如词干提取和词形等。

同样重要，但它确实比 Mysql 数据库有更好的全文搜索，

http://sphinxsearch.com/

性能我可以告诉你它很快，在文本搜索方面可能比 MySql 快 20 倍，但它有自己的怪癖。但我强烈推荐它。我们运行每分钟在 1/4 百万行的记录集上通过我们的小型 sphinx 集群进行大约 150k 次搜索。（虽然我们的主服务器是一个 12 核，54GB 的怪物）

这种类型的搜索没有一个万无一失的解决方案，或者至少我还没有找到它（而且我已经做了很多）。

搜索具有误差范围的特定字符串

Search for a Specific String With Error Margin

php

string

margin

find