这个问题之前在这里被问过
但没有明确的答案说明如何“分组”项目。基于difflib的解决方案基本上是搜索，对于给定的项目，difflib可以从列表中返回最相似的词。但是如何将其用于分组呢？
我想将
['ape', 'appel', 'apple', 'peach', 'puppy']减少到
['ape', 'appel', 'peach', 'puppy']或者
['ape', 'apple', 'peach', 'puppy']我尝试的一个想法是，对于每个项目，遍历列表，如果get_close_matches返回多个匹配项，则使用它，如果没有，则保持原词不变。这部分有效，但它可能会建议apple对应appel，然后appel对应apple，这些词只是交换位置而没有任何变化。
我希望能得到任何建议、库名称等。
注意：在性能方面，我们有一个包含300,000个项目的列表，get_close_matches似乎有点慢。有人知道有基于C/++的解决方案吗？
谢谢，
注意：进一步的调查显示，kmedoid是正确的算法（以及层次聚类），因为kmedoid不需要“中心”，它使用数据点本身作为中心（这些点被称为medoids，因此得名）。在词语分组的情况下，medoid将是该组/簇的代表元素。
回答：
你需要对组进行标准化。在每个组中，选择一个词或编码来代表该组。然后根据它们的代表进行分组。
一些可能的方法：
- 选择遇到的第一个词。
- 选择字典顺序的第一个词。
- 为所有词派生一个模式。
- 选择一个唯一的索引。
- 使用soundex作为模式。
将词进行分组可能很困难。尽管A与B相似，B与C相似，A和C不一定彼此相似。如果B是代表，A和C都可以被包含在组中。但如果A或C是代表，另一个可能无法被包含。
按照第一个替代方案（遇到的第一个词）：
class Seeder: def __init__(self): self.seeds = set() self.cache = dict() def get_seed(self, word): LIMIT = 2 seed = self.cache.get(word,None) if seed is not None: return seed for seed in self.seeds: if self.distance(seed, word) <= LIMIT: self.cache[word] = seed return seed self.seeds.add(word) self.cache[word] = word return word def distance(self, s1, s2): l1 = len(s1) l2 = len(s2) matrix = [range(zz,zz + l1 + 1) for zz in xrange(l2 + 1)] for zz in xrange(0,l2): for sz in xrange(0,l1): if s1[sz] == s2[zz]: matrix[zz+1][sz+1] = min(matrix[zz+1][sz] + 1, matrix[zz][sz+1] + 1, matrix[zz][sz]) else: matrix[zz+1][sz+1] = min(matrix[zz+1][sz] + 1, matrix[zz][sz+1] + 1, matrix[zz][sz] + 1) return matrix[l2][l1]import itertoolsdef group_similar(words): seeder = Seeder() words = sorted(words, key=seeder.get_seed) groups = itertools.groupby(words, key=seeder.get_seed) return [list(v) for k,v in groups]示例：
import pprintprint pprint.pprint(group_similar([ 'the', 'be', 'to', 'of', 'and', 'a', 'in', 'that', 'have', 'I', 'it', 'for', 'not', 'on', 'with', 'he', 'as', 'you', 'do', 'at', 'this', 'but', 'his', 'by', 'from', 'they', 'we', 'say', 'her', 'she', 'or', 'an', 'will', 'my', 'one', 'all', 'would', 'there', 'their', 'what', 'so', 'up', 'out', 'if', 'about', 'who', 'get', 'which', 'go', 'me', 'when', 'make', 'can', 'like', 'time', 'no', 'just', 'him', 'know', 'take', 'people', 'into', 'year', 'your', 'good', 'some', 'could', 'them', 'see', 'other', 'than', 'then', 'now', 'look', 'only', 'come', 'its', 'over', 'think', 'also', 'back', 'after', 'use', 'two', 'how', 'our', 'work', 'first', 'well', 'way', 'even', 'new', 'want', 'because', 'any', 'these', 'give', 'day', 'most', 'us']), width=120)输出：
[['after'], ['also'], ['and', 'a', 'in', 'on', 'as', 'at', 'an', 'one', 'all', 'can', 'no', 'want', 'any'], ['back'], ['because'], ['but', 'about', 'get', 'just'], ['first'], ['from'], ['good', 'look'], ['have', 'make', 'give'], ['his', 'her', 'if', 'him', 'its', 'how', 'us'], ['into'], ['know', 'new'], ['like', 'time', 'take'], ['most'], ['of', 'I', 'it', 'for', 'not', 'he', 'you', 'do', 'by', 'we', 'or', 'my', 'so', 'up', 'out', 'go', 'me', 'now'], ['only'], ['over', 'our', 'even'], ['people'], ['say', 'she', 'way', 'day'], ['some', 'see', 'come'], ['the', 'be', 'to', 'that', 'this', 'they', 'there', 'their', 'them', 'other', 'then', 'use', 'two', 'these'], ['think'], ['well'], ['what', 'who', 'when', 'than'], ['with', 'will', 'which'], ['work'], ['would', 'could'], ['year', 'your']]