如何高效计算数百万字符串的余弦相似度

Question

我需要计算一个列表中字符串之间的余弦相似度。比如说，我有一个包含超过1000万个字符串的列表，每个字符串都要和列表中的其他所有字符串进行相似度比较。我可以用什么算法来高效快速地完成这个任务呢？分治算法适用吗？

编辑

我想找出哪些字符串和给定的字符串最相似，并且能够给出一个相似度的评分。我觉得我想做的事情和聚类有关，但聚类的数量一开始并不知道。

Answer 1

你可以试试 SimString。

这是一个用C++写的库（也有Python和Ruby的接口），主要用于模糊字符串匹配。

它声称可以在不到1毫秒的时间内，在1300万个字符串的数据库中找到相似度很高的字符串。

这个算法的具体原理可以在 这里 找到，主要是通过修剪倒排列表来实现的。

Answer 2

处理转置矩阵。这就是Mahout在Hadoop上快速完成这类任务的方法（或者直接使用Mahout）。

其实，用简单的方法计算余弦相似度并不好。因为你会计算很多0乘以某个数。相反，你最好在列上进行操作，并且把所有的0都去掉。