什么是一个好的策略来分组相似的词？

Question

假设我有一个电影名字的列表，上面有拼写错误和类似这样的小变化-

 "Pirates of the Caribbean: The Curse of the Black Pearl"
 "Pirates of the carribean"
 "Pirates of the Caribbean: Dead Man's Chest"
 "Pirates of the Caribbean trilogy"
 "Pirates of the Caribbean"
 "Pirates Of The Carribean"

如何分组或查找这样的单词集，最好使用python和/或redis？

Answer 1

您可能会注意到类似的字符串有很大的公共子字符串，例如：

"Bla bla bLa" and "Bla bla bRa" => common substring is "Bla bla ba" (notice the third word)

要查找公共子串，可以使用动态编程算法。算法的变化之一是Levenshtein距离（大多数相似字符串之间的距离很小，而更多不同字符串之间的距离更大）-http://en.wikipedia.org/wiki/Levenshtein_distance。

此外，为了提高性能，您可以尝试调整Soundex算法-http://en.wikipedia.org/wiki/Soundex。

所以在计算完所有弦之间的距离后，必须对它们进行聚类。最简单的方法是k-means（但它需要定义集群的数量）。如果您实际上不知道集群的数量，则必须使用分层集群。请注意，在您的情况下，集群的数量是不同电影标题的数量+1（对于拼写完全错误的字符串）。