python - 减少 Anagram 词搜索的计算时间

Question

下面的代码是一种搜索单词列表并创建任何 Anagrams 子列表的蛮力方法。

搜索整个英语词典非常耗时，所以我很好奇有人有降低代码计算复杂性的技巧吗？

def anogramtastic(anagrms):
    d = []
    e = []
    for j in range(len(anagrms)):
        if anagrms[j] in e:
            pass
        else:
            templist = []
            tester = anagrms[j]        
            tester = list(tester)
            tester.sort()
            tester = ''.join(tester)
            for k in range(len(anagrms)):
                if k == j:
                    pass
                else:
                    testers = anagrms[k]        
                    testers = list(testers)
                    testers.sort()
                    testers = ''.join(testers)
                    if testers == tester:
                        templist.append(anagrms[k])
                        e.append(anagrms[k])
            if len(templist) > 0:
                templist.append(anagrms[j])
                d.append(templist)
    d.sort(key=len,reverse=True) 
    return d

print(anogramtastic(wordlist))

Answer 1

使用卡住集字典怎么样？ Frozensets 是不可变的，这意味着您可以对它们进行哈希处理以进行持续查找。当谈到变位词时，使两个词彼此变位词的原因是它们具有相同的字母和相同的计数。因此，您可以构造一个由 {(letter, count), ...} 对组成的卡住集，并对它们进行哈希处理以进行高效查找。

这是一个使用 collections.Counter 将单词转换为多重集的快速小函数:

from collections import Counter, defaultdict

def word2multiset(word):
    return frozenset(Counter(word).items())

现在，给定一个单词列表，像这样填充你的 Anagram 字典:

list_of_words = [... ]

anagram_dict = defaultdict(set)
for word in list_of_words:
    anagram_dict[word2multiset(word)].add(word)

例如，当list_of_words = ['hello', 'olleh', 'test', 'apple']时，这是anagram_dict运行后的输出上面的循环:

print(anagram_dict)
defaultdict(set,
            {frozenset({('e', 1), ('h', 1), ('l', 2), ('o', 1)}): {'hello',
              'olleh'},
             frozenset({('e', 1), ('s', 1), ('t', 2)}): {'test'},
             frozenset({('a', 1), ('e', 1), ('l', 1), ('p', 2)}): {'apple'}})