减少字词搜索的计算时间

Question

下面的代码是搜索单词列表和创建任何Anagram的子列表的蛮力方法。

搜索整个英语词典是令人望而却步的时间，所以我很好奇有谁有方法来降低代码的计算复杂度呢？

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

用一本冷冻词典怎么样？Frozenset是不可变的，这意味着您可以散列它们以进行常量查找。说到字谜，两个字相互暗喻的原因是，它们有相同的字母和相同的计数。因此，您可以构造一个{(字母，计数)，.}对的冻结集，并对它们进行散列以进行有效的查找。

下面是一个使用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'}})

Answer 3

除非我误解了这个问题，通过对单词的字符排序来组合单词应该是一个有效的解决方案--正如你已经意识到的。诀窍是避免把每一个单词与所有其他单词进行比较。以字符排序字符串为键的块将使快速查找每个单词的正确组；查找/插入将是O(log )。

#!/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))

测试我的文字档案(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