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

PHP/MySQL - find items that have similar or matching properties

提问人：RichW 提问时间：4/22/2011 最后编辑：CommunityRichW 更新时间：4/25/2011 访问量：1062

问：

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

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

例如：

项目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中完成，也许使用全文搜索或其他东西。

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

php mysql 比较

评论

1赞 Khez 4/22/2011
你忘了告诉我们 A/B/C/D/E 是否是同一个表中的字段，在不同的表中，都是一个大的 varchar/text/something。请使用一些表定义进行更新。
0赞 RichW 4/22/2011
它目前完全处于理论阶段，因此可以提出建议（这将由效率决定）。实际属性将是字符串，但可以使用它们的数字 ID 进行比较。它们可以存储在单独的表中并作为连接处理，但这效率非常低，所以我想知道它们是否可以缓存为同一表中的字符串，并且在比较时它只是将字符串视为一个整体。另一个想法是，它可以为每个项目创建某种指纹，并基于此进行搜索（如果这样会更快）
0赞 Bibhas Debnath 4/23/2011
您想要的确切 o/p 是什么？只有完美的结果？
0赞 RichW 4/23/2011
不，只是部分或完全匹配的所有结果的列表，按匹配百分比排序
0赞 AnaZgombic 4/24/2011
所有属性值都是已知的吗？是否所有实体都具有相同数量的属性？

答：

2赞 AnaZgombic 4/25/2011 #1

我要做的是将 Order 和 Property 值编码为一个数字。数字具有快速比较的优点。

这是一个一般的想法，可能还需要一些工作，但我希望它能在某种程度上有所帮助。

计算每个属性的数字（某种形式的哈希），并将表示项目属性的出现顺序的数字相乘。

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

哈希 （A） = 123， 哈希 （B） = 345， 哈希 （C） = 456

然后将其乘以外观顺序，假设我们有已知数量的属性：

（哈希 （A） * 1,000,00） + （哈希 （B） * 1,000） + （哈希 （C） * 1） = 某个值

可以调整乘数的大小以反映您的数据集。您必须识别哈希函数。也许是Soundex？

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

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

HTH。

编辑：检查匹配项的示例

给定项目 1（a、b、c）和项目 2（a、b、c）。计算出的项哈希值将相等。这是最好的情况。无需进一步计算。

给定项目 1（a、b、c） 和项目 2（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））。然后计算分数。

另一种查看方式是逐个比较属性，但这次您使用的是数字而不是实际的字符串值

评论

0赞 RichW 4/25/2011
非常有趣的概念，我真的很喜欢比较数字的想法。我刚刚将其作为电子表格进行了尝试，我认为缺陷在于哈希。在此示例中，哈希只是属性的增量 ID - 1、2、3 等。产生的问题出在乘数上，如果 ID 是一个高数字，则计算出的数字会变得非常高。查看 s4.postimage.org/5f0kogg2x/...，看看实体 1、2 和 3 之间的区别 - 与没有类似值的实体 4 相比，实体 3 的最终值非常高。
0赞 AnaZgombic 4/25/2011
预计这些数字会相对较高。对于 8 THO 的样本集，乘数可以是 10 的幂增量。因此，最高的哈希结果将低于 1000。沿着任意精度 （Bigints） 数字的思路思考，而不仅仅是 32 或 64 位 int。
0赞 RichW 4/25/2011
对不起，我只是不明白它是如何工作的..在实体 4 的示例中，乘以 4 x 10 总是大于 1 x 10（实体 1），而实体 3 应该更接近，但实际上是 8 x 10（使其比实体 4 离实体 1 更远）。看看这张图中的“与实体 1 的差异”和“顺序”，根据实体 -img683.imageshack.us/img683/7570/screenshot20110425at131.png 的性质，顺序是完全错误的
0赞 AnaZgombic 4/25/2011
无需道歉。如果我不能更清楚地解释它，那将是我的错。您仍然需要遍历计算出的单个哈希值以进行比较。
0赞 RichW 4/25/2011
在循环过程中，你会做什么比较？你能举个例子吗？
1赞 aterimperator 4/25/2011 #2

您可以从各种序列比对算法（如 Smith-Waterman）中汲取灵感（或平坦的算法）。事实上，你正在寻找的似乎是对序列比对的描述。但是，我不确定是否可以将其作为 SQL 查询来执行。

评论

1赞 AnaZgombic 4/25/2011
事实上，这是一个序列比对问题

上一个：浮雕堆积条形图不堆积

下一个：PHP 包含在 cron 作业中