按字符串相似性分组搜索结果的最有效方法

Question

我正在处理一个sql server 2008数据库和asp.net mvc网络电商应用程序。

我有不同的用户向数据库提供其产品，并希望比较具有相似名称的产品的价格。 我知道字符串匹配是与领域相关的，但我仍然需要最好的通用解决方案。

什么是最有效的方式来分组搜索结果？ 我应该递归地使用Levenshtien Distance算法比较每个记录吗？ 我是在DB中还是在代码中执行它？ 有没有一种方法可以实时实现SSIS模糊分组来完成此任务？ 是否可以使用Sql server 2008全文搜索以高效的方式进行？

编辑1： 那么网络图分析呢？如果我使用Levenshtien Distance算法定义矩阵，我可以使用聚类算法（例如：clauset newman moore）并分离彼此没有语音路径的组。 我已经为Nick Johnson（请参见评论）附上了猫狗示例（红线是聚类），通过使用clauset newman moore，我创建了2个不同的聚类并将猫与狗分开。

你觉得呢？

- Gidon

---

我会在数据库中完成它，参见这个帖子：http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=66781 和这个：https://dev59.com/3nRB5IYBdhLWcg3wpopm 关于Levenshtein距离算法。 - Magnus

这很困难 - 你如何将产品'cat'、'car'、'bar'、'bag'、'bog'、'dog'分组？每个产品之间只有1的距离，但是'cat'和'dog'没有任何相似之处。 - Nick Johnson

那么有什么替代方案吗？也许是某种语义词典？还有其他想法吗？ - Gidon

@NickJohnson：嗯... cat 和 car 的距离为1。car 和 bar 的距离也是1。但是这说明了 cat 和 bar 的距离是2而不是1。你需要从 cat 跳两次才能到达 bar，对吧？从 cat 到 dog 需要5步。所以它们相当远。虽然在图中添加其他单词会导致 cat 和 dog 仅相隔3步... - Robert Koritnik

@RobertKoritnik 那么你会将这组单词分成哪些类别，为什么呢？（另外，注意从'cat'到'dog'的编辑距离是3。:)) - Nick Johnson

Answer 1

这是一个聚类问题，因此在计算上比较困难，但已知有大量算法可用于解决这些问题，包括精确和近似算法。请查看维基百科关于聚类分析和这个答案的页面。

一旦您实现了聚类算法，您可以将聚类存储在数据库中，但我怀疑每添加一个项目重新计算聚类会太昂贵。最好是每小时或每天运行一次聚类算法。

- Vic Smith

Answer 2

如果你能找到一个合适的同义词词典/本体论，基本上提供了最佳的聚类 - 因为单词是概念树中的叶子，树中的距离就是语义上的单词之间的距离。因此，猫和狗并不像虎斑猫和三花猫那样接近，但它们比猫和香蕉更接近，而猫（名词）和跳（动词）之间的距离则更近。

允许存在小的拼写错误（通过查找在同义词词典中与非目标词相似拼写的单词）可以增加鲁棒性，但也可能由于同音异义词而产生意外结果。

至于在数据库还是代码中进行操作，建议选择代码。在尽可能缓存的情况下，速度会更快。

- DRVic