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

Question

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

phpmysqlcompare

8

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

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

例如：

项目1 - A，B，C，D，E 项目2 - A，B，C，D，E

将是100％匹配

项目1 - A，B，C，D，E 项目2 - B，C，A，D，E

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

项目1 - A，B，C，D，E 项目2 - F，G，H，I，A

只有一个属性相同且位于第5个位置，因此匹配度较低

这个算法需要处理成千上万条记录，因此需要高性能和高效率。有什么想法可以在PHP/MySQL中以快速和高效的方式实现吗？

我正在考虑 levenshtein，但据我所知，它也会考虑拼写方面两个完全不同单词之间的距离。除非我使用方法错误，否则似乎并不理想。

也许可以仅使用MySQL来完成，可能使用全文搜索或其他方法。

这似乎是一个不错的解决方案，尽管不是为这种情况设计的。也许可以以某种方式使用二进制比较？

- RichW

1

你忘记告诉我们A/B/C/D/E是否是同一张表中的字段，还是分别在不同的表中，或者全部都是一个大的varchar/text/其他类型。请提供一些表定义来更新信息。 - Khez

目前，它完全处于理论阶段，因此可以接受建议（它将根据效率来确定）。实际属性将是字符串，但可以使用它们的数字ID进行比较。它们可以存储在单独的表中，并作为连接处理，但这样做效率会相当低下，所以我想知道它们是否也可以作为字符串缓存在同一张表中，并且在比较时将其视为一个整体字符串。另一个想法是为每个项目创建某种指纹，并基于该指纹进行搜索（如果这样更快的话）。 - RichW

你想要什么精确的输出？只要完美的结果吗？ - Bibhas Debnath

不，只是列出所有部分或完全匹配的结果列表，按其匹配百分比排序。 - RichW

所有属性值都已知吗？所有实体的属性数量都相同吗？ - AnaZgombic

很遗憾，字符串可能相当随机。不过如果需要的话，这些值可以被缓存在另一张表中。属性数量将是相同的。 - RichW

2个回答

1

你可以从各种序列比对算法（例如Smith-Waterman）中获得启发（或直接采用算法）。实际上，你正在寻找的非常类似于序列比对的描述。然而，我不确定这是否可能作为一个SQL查询来完成。

- aterimperator

1

确实，这是一个序列比对问题。 - AnaZgombic

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- AnaZgombic · Accepted Answer

我会将订单和属性值编码为数字。数字具有快速比较的优点。

这是一个普遍的想法，可能仍需要一些改进，但我希望它能在某种程度上有所帮助。

为每个属性计算一个数字（某种哈希形式），并将出现顺序的数字代表相应的乘积。

例如，item1有3个属性A、B和C。

hash(A) = 123, hash(B) = 345, hash(C) = 456

然后将其乘以出现顺序的数字，因为我们知道属性的数量：

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

乘数的大小可以调整以反映您的数据集。您必须确定哈希函数。Soundex或许可以？

现在问题被简化为哈希冲突的唯一性问题，但我们可以非常确定不匹配的属性。

此外，这样做的优点是相对容易检查属性是否以不同的顺序出现在另一个项目中，只需使用乘数的数量来从生成的数字中提取哈希值即可。

希望对你有帮助。

编辑：检查匹配的示例

给定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））的每个属性组合，然后计算得分。

另一种看待它的方法是逐个比较属性，这次您正在玩数字而不是实际的字符串值。