PHP/MySQL - 查找具有相似或匹配属性的项目

Question

我正在尝试开发一种获取具有多个属性的实体并在数据库中搜索类似实体的方法(以正确的顺序匹配尽可能多的属性)。这个想法是它会返回相似度的百分比。

还应考虑属性的顺序，因此开头的属性比结尾的属性更重要。

例如:

Item 1 - A, B, C, D, E

Item 2 - A, B, C, D, E

将是 100% 匹配

Item 1 - A, B, C, D, E

Item 2 - B, C, A, D, E

这不是完美匹配，因为属性的顺序不同

Item 1 - A, B, C, D, E

Item 2 - F, G, H, I, A

将是一个低匹配度，因为只有一个属性相同并且它在位置 5

此算法将运行成千上万条记录，因此需要高性能和高效。关于如何在 PHP/MySQL 中快速高效地执行此操作有什么想法吗？

我正在考虑 levenshtein但据我所知，这也会在拼写方面查看两个完全不同的单词之间的距离。除非我只是以错误的方式使用它，否则似乎不适合这种情况。

它可能只在 MySQL 中完成，也许使用全文搜索或其他东西。

这看起来像一个 nice solution ，虽然不是为这种情况设计的。也许二进制比较可以以某种方式使用？

Answer 1

我要做的是将订单和属性值编码为数字。数字具有快速比较的优势。

这是一个总体思路，可能仍需要一些工作，但我希望它能以某种方式提供帮助。

为每个属性计算一个数字(某种形式的散列)，并将代表该属性在项目中出现的顺序的数字相乘。

假设 item1 有 3 个属性 A、B 和 C。

哈希(A)= 123，哈希(B)= 345，哈希(C)= 456

假设我们有已知数量的属性，然后将其乘以出现顺序:

(哈希(A) * 1,000,00) + (哈希(B) * 1,000) + (哈希(C) * 1) = someval

可以调整乘数的大小以反射(reflect)您的数据集。您必须确定哈希函数。也许是 soundex？

由于散列冲突，问题现在已简化为唯一性问题，但我们可以非常确定不匹配的属性。

另外，通过使用乘数的大小从生成的数字中提取哈希值，可以相对轻松地检查某个属性是否以不同的顺序出现在另一个项目中。

HTH.

编辑:检查匹配的例子

给定 item1(a b c) 和 item2(a b c)。项目的计算哈希值将是相等的。这是最好的情况。不需要进一步的计算。

给定 item1(a b c) 和 item2(d e a)。项目的计算哈希值不相等。继续分解属性哈希...

假设属性 a = 1、b = 2、c = 3、d = 4、e = 5 的哈希表，乘数为 10^n。 item1 的计算哈希为 123，item2 为 451，分解每个属性的计算哈希，并比较每个 item1(变成 item1(1 2 3))和 item2(变成 item2(4 5 1)的所有属性组合))。然后计算分数。

另一种看待它的方法是一个一个地比较属性，除了这次，你在玩数字而不是实际的字符串值