python - 在困惑的字母中高效地寻找单词

Question

我想您可以将其归类为拼字游戏风格的问题，但它的起因是一位 friend 提到了英国电视问答节目倒计时。节目中的各个回合都会向参赛者展示一组乱七八糟的字母，他们必须想出他们能想到的最长的单词。我 friend 提到的那个是“RAEPKWAEN”。

在相当短的时间内，我用 Python 编写了一些东西来处理这个问题，使用 PyEnchant 来处理字典查找，但是我注意到它确实不能很好地扩展。

这是我目前拥有的:

#!/usr/bin/python

from itertools import permutations
import enchant
from sys import argv

def find_longest(origin):
    s = enchant.Dict("en_US")
    for i in range(len(origin),0,-1):
        print "Checking against words of length %d" % i
        pool = permutations(origin,i)
        for comb in pool:
            word = ''.join(comb)
            if s.check(word):
                return word
    return ""

if (__name__)== '__main__':
    result = find_longest(argv[1])
    print result

这对于他们在节目中使用的 9 个字母示例来说很好，9 阶乘 = 362,880 和 8 阶乘 = 40,320。在这个规模上，即使它必须检查所有可能的排列和字长，也没有那么多。

但是，一旦您达到 14 个字符，就有 87,178,291,200 种可能的组合，这意味着您只能靠运气快速找到一个 14 个字符的单词。

使用上面的示例词，我的机器需要大约 12 1/2 秒才能找到“reawaken”。对于 14 个字符的乱序词，我们可以在 23 天的范围内讨论，只是为了检查所有可能的 14 个字符排列。

有没有更有效的方法来处理这个问题？

Answer 1

实现Jeroen Coupé创意来自 his answer字母数:

from collections import defaultdict, Counter


def find_longest(origin, known_words):
    return iter_longest(origin, known_words).next()

def iter_longest(origin, known_words, min_length=1):
    origin_map = Counter(origin)
    for i in xrange(len(origin) + 1, min_length - 1, -1):
        for word in known_words[i]:
            if check_same_letters(origin_map, word):
               yield word

def check_same_letters(origin_map, word):
    new_map = Counter(word)
    return all(new_map[let] <= origin_map[let] for let in word)

def load_words_from(file_path):
    known_words =  defaultdict(list)
    with open(file_path) as f:
        for line in f:
            word = line.strip()
            known_words[len(word)].append(word)
    return known_words

if __name__ == '__main__':
    known_words = load_words_from('words_list.txt')
    origin = 'raepkwaen'
    big_origin = 'raepkwaenaqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnm'
    print find_longest(big_origin, known_words)
    print list(iter_longest(origin, known_words, 5))

输出(对于我的 58000 字小字典):

counterrevolutionaries
['reawaken', 'awaken', 'enwrap', 'weaken', 'weaker', 'apnea', 'arena', 'awake',
 'aware', 'newer', 'paean', 'parka', 'pekan', 'prank', 'prawn', 'preen', 'renew',
 'waken', 'wreak']

注意事项:

• 这是没有优化的简单实现。

• words_list.txt - 在 Linux 上可以是 /usr/share/dict/words。

更新

如果我们只需要查找单词一次，并且我们有字典，单词按长度排序，例如通过这个脚本:

with open('words_list.txt') as f:
    words = f.readlines()
with open('words_by_len.txt', 'w') as f:
    for word in sorted(words, key=lambda w: len(w), reverse=True):
        f.write(word)

我们可以找到最长的单词而无需将完整的字典加载到内存中:

from collections import Counter
import sys


def check_same_letters(origin_map, word):
    new_map = Counter(word)
    return all(new_map[let] <= origin_map[let] for let in word)

def iter_longest_from_file(origin, file_path, min_length=1):
    origin_map = Counter(origin)
    origin_len = len(origin)
    with open(file_path) as f:
        for line in f:
            word = line.strip()
            if len(word) > origin_len:
                continue
            if len(word) < min_length:
                return
            if check_same_letters(origin_map, word):
                yield word

def find_longest_from_file(origin, file_path):
    return iter_longest_from_file(origin, file_path).next()

if __name__ == '__main__':
    origin = sys.argv[1] if len(sys.argv) > 1 else 'abcdefghijklmnopqrstuvwxyz'
    print find_longest_from_file(origin, 'words_by_len.txt')