algorithm - 按字符串相似性对搜索结果进行分组的最有效方法

Question

我正在开发 sql server 2008 数据库和 asp.net mvc web 电子商务应用程序。

我有不同的用户将他们的产品提供给数据库，我想比较具有相似名称的产品的价格。 我知道字符串匹配是特定领域的，但我仍然需要最好的通用解决方案。

对搜索结果进行分组的最有效方法是什么？ 我应该使用 Levenshtien 距离算法递归地比较每条记录吗？ 我应该在数据库中还是在代码中进行？ 有没有办法为此任务实时实现 SSIS 模糊分组？ 有没有使用 Sql server 2008 自由文本搜索的有效方法？

编辑 1: 网络图分析呢？如果我将使用 Levenshtien 距离算法定义矩阵，我可以使用聚类算法(例如:clauset newman moore)和单独的组，它们之间没有语音路径。 例如，我附上了 Nick Johnson(见评论)cat-dog(红线是簇)- 通过使用 newman moore 子句，我创建了 2 个不同的簇并将猫与狗分开。

你怎么看？

Answer 1

如果你能找到一个合适的同义词库/本体，它基本上可以提供最好的聚类——因为单词是概念树中的叶子，树中的距离就是语义意义上单词之间的距离。因此，cat 和 dog 不像 tabby 和 calico (cat) 那样接近，但它们比 cat 和 banana 更接近，而 cat 和 banana 本身又比 cat(n.) 和 jump(v.) 更接近。

允许小的拼写错误(通过寻找同义词库中拼写相似的词来寻找不存在的词)可以提高稳健性，但也可能由于同音异义词而产生意想不到的结果。

至于在数据库里做还是在代码里做，就在代码里做。在可以缓存的范围内，速度会更快。