如何有效分组相似单词？

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

我觉得其实有两个不同的问题。

第一个是拼写纠正。你可以在Python中实现一个拼写纠正的功能，这里有个链接可以参考：

http://norvig.com/spell-correct.html

第二个问题更实用。在拼写纠正之后，我会做一个关系函数。

这个关系函数可以这样定义：当且仅当句子1和句子2有一些不常见的共同词时，才认为它们是相关的。这里的“不常见”是指那些常见的词，比如“the”、“what”、“is”等等。你可以看看TF/IDF这个系统，它可以用来判断两个文档是否相关，主要是通过它们的词汇来判断。稍微搜索一下，我找到了这个链接：

https://code.google.com/p/tfidf/

Answer 2

你可能会发现一些相似的字符串之间有很大的共同部分，比如：

"Bla bla bLa" 和 "Bla bla bRa" => 共同部分是 "Bla bla ba"（注意第三个词）

要找到这些共同部分，你可以使用一种叫做动态规划的算法。其中一种算法的变种是Levenshtein距离（最相似的字符串之间的距离很小，而差异较大的字符串之间的距离则较大） - http://en.wikipedia.org/wiki/Levenshtein_distance。

为了提高效率，你还可以尝试使用Soundex算法 - http://en.wikipedia.org/wiki/Soundex。

在计算完所有字符串之间的距离后，你需要对它们进行聚类。最简单的方法是k-means聚类（但你需要先确定聚类的数量）。如果你不知道聚类的数量，就需要使用层次聚类。请注意，在你的情况下，聚类的数量是不同电影标题的数量 + 1（用于完全拼写错误的字符串）。

Answer 3

看看“模糊匹配”。下面的讨论中有一些很棒的工具，可以计算字符串之间的相似度。

我特别喜欢 difflib 这个模块。

>>> get_close_matches('appel', ['ape', 'apple', 'peach', 'puppy'])
['apple', 'ape']
>>> import keyword
>>> get_close_matches('wheel', keyword.kwlist)
['while']
>>> get_close_matches('apple', keyword.kwlist)
[]
>>> get_close_matches('accept', keyword.kwlist)
['except']

https://stackoverflow.com/questions/682367/good-python-modules-for-fuzzy-string-comparison