减少字谜词搜索的计算时间

Question

下面的代码是搜索单词列表和创建任何字谜的子列表的暴力方法。你知道吗

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

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

通过使用字典检查成员身份而不是进行线性搜索，可以大大加快速度。唯一的“诀窍”是设计一种方法来为它创建键，这样它将是相同的语法词（而不是其他）。你知道吗

在下面的代码中，这是通过从每个单词中的字母创建一个排序元组来完成的。你知道吗

def anagramtastic(words):
    dct = {}
    for word in words:
        key = tuple(sorted(word))  # Identifier based on letters.
        dct.setdefault(key, []).append(word)

    # Return a list of all that had an anagram.
    return [words for words in dct.values() if len(words) > 1]

wordlist = ['act', 'cat', 'binary', 'brainy', 'case', 'aces',
            'aide', 'idea', 'earth', 'heart', 'tea', 'tee']

print('result:', anagramtastic(wordlist))

产出：

result: [['act', 'cat'], ['binary', 'brainy'], ['case', 'aces'], ['aide', 'idea'], ['earth', 'heart']]

Answer 2

用一本冻疮辞典怎么样？Frozensets是不可变的，这意味着您可以对它们进行散列以进行常量查找。当涉及到字谜时，两个单词之间的字谜是因为它们有相同的字母和相同的计数。因此，您可以构造一个{（letter，count），…}对的冻结集，并对其进行散列以实现高效的查找。你知道吗

下面是一个使用collections.Counter将单词转换为多集的快速小函数：

from collections import Counter, defaultdict

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

现在，给定一个单词列表，按如下方式填充你的字谜字典：

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'}})

Answer 3

除非我误解了这个问题，否则简单地通过对单词的字符进行排序来对单词进行分组应该是一个有效的解决方案，正如您已经意识到的那样。诀窍是避免将每个单词与其他所有单词进行比较。以字符排序的字符串为关键字的dict可以快速找到每个单词的正确组；查找/插入将是O（logn）。你知道吗

#!/usr/bin/env python3
#coding=utf8

from sys import stdin

groups = {}

for line in stdin:
    w = line.strip()
    g = ''.join(sorted(w))
    if g not in groups:
        groups[g] = []
    groups[g].append(w)

for g, words in groups.items():
    if len(words) > 1:
        print('%2d %-20s' % (len(words), g), ' '.join(words))

在我的words文件（99171个单词）上测试，似乎效果不错：

anagram$ wc /usr/share/dict/words
 99171  99171 938848 /usr/share/dict/words
anagram$ time ./anagram.py < /usr/share/dict/words | tail
 2 eeeprsw              sweeper weepers
 2 brsu                 burs rubs
 2 aeegnrv              avenger engrave
 2 ddenoru              redound rounded
 3 aesy                 ayes easy yeas
 2 gimnpu               impugn umping
 2 deeiinsst            densities destinies
 2 abinost              bastion obtains
 2 degilr               girdle glider
 2 orsttu               trouts tutors

real    0m0.366s
user    0m0.357s
sys     0m0.012s