java - 如何有效地计算数百万个字符串之间的余弦相似度

Question

我需要计算列表中字符串之间的余弦相似度。例如，我有一个超过 1000 万个字符串的列表，每个字符串都必须确定其自身与列表中每个其他字符串之间的相似性。我可以用来高效快速地完成此类任务的最佳算法是什么？分治算法是否适用？

编辑

我想确定哪些字符串与给定字符串最相似，并且能够拥有与相似度相关的度量/分数。我认为我想做的事情与最初不知道集群数量的集群一致。

Answer 1

你可以试试SimString。

它是一个用于近似字符串匹配的 C++ 库（带有 Python 或 Ruby 绑定）。

它声称可以在 1 毫秒内为 1300 万个字符串的数据库找到具有高余弦相似度的字符串。

这里使用的算法是基于倒排列表的修剪来描述的。

Answer 2

使用转置矩阵。这就是 Mahout 在 Hadoop 上所做的以快速完成此类任务（或仅使用 Mahout）。

本质上，以天真的方式计算余弦相似度是不好的。因为你最终会计算很多 0 * 的东西。相反，您最好在列中工作，并在此处保留所有 0。