高效寻词于混乱字母中

Question

我想这可以算是一种类似拼字游戏的问题，但最开始是因为一个朋友提到了英国的电视问答节目《Countdown》。节目中的几个回合会给参赛者一组打乱的字母，他们需要想出能拼出的最长单词。我朋友提到的例子是“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.5秒才能找到“reawaken”。如果是14个字母的打乱单词，检查所有可能的14个字母排列可能需要23天的时间。

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

Answer 1

这和我之前做过的一个字谜问题有点像。我是通过用质数来表示每个字母来解决这个问题的。每个单词的字母乘起来会得到一个数字。要判断一组输入的字符是否足够组成一个单词，只需将输入字符的乘积除以你想检查的单词的乘积。如果没有余数，那就说明输入的字符是足够的。我在下面实现了这个方法。输出结果是：

$ python longest.py rasdaddea aosddna raepkwaen
rasdaddea -->  sadder
aosddna -->  soda
raepkwaen -->  reawaken

你可以在这里找到更多细节和关于字谜案例的详细解释： http://mostlyhighperformance.blogspot.com/2012/01/generating-anagrams-efficient-and-easy.html

这个算法在建立字典时需要一点时间，但之后检查每个字典中的单词就简单多了，只需要进行一次除法运算。如果字典中缺少某个字母，可能会有更快的方法来排除字典的某些部分，但如果输入的字母数量很大，这些方法可能效果反而不好，因为它实际上无法排除字典的任何部分。

import sys


def nextprime(x):
    while True:
        x += 1
        for pot_fac in range(2,x):
            if x % pot_fac == 0:
                break
        else:
            return x

def prime_generator():
    '''Returns a generator that produces the next largest prime as
    compared to the one returned from this function the last time
    it was called. The first time it is called it will return 2.'''
    lastprime = 1
    while True:
        lastprime = nextprime(lastprime)
        yield lastprime


# Assign prime numbers to each lower case letter
gen = prime_generator()
primes = dict( [ (chr(x),gen.next()) for x in range(ord('a'),ord('z')+1) ] )


product = lambda x: reduce( lambda m,n: m*n, x, 1 )
make_key = lambda x: product( [ primes[y] for y in x ] )


try:
    words = open('words').readlines()
    words = [ ''.join( [ c for c in x.lower() \
                if ord('a') <= ord(c) <= ord('z') ] ) \
            for x in words ]
    for x in words:
        try:
            make_key(x)
        except:
            print x
            raise

except IOError:
    words = [ 'reawaken','awaken','enwrap','weaken','weaker', ]

words = dict( ( (make_key(x),x,) for x in words ) )


inputs = sys.argv[1:] if sys.argv[1:] else [ 'raepkwaen', ]
for input in inputs:
    input_key = make_key(input)
    results = [ words[x] for x in words if input_key % x == 0 ]

    result = reversed(sorted(results, key=len)).next()
    print input,'--> ',result

Answer 2

你想避免进行排列组合。你可以计算一下一个字符在两个字符串中出现的次数（一个是原始字符串，另一个是字典里的字符串）。如果字符出现的频率不一样，就可以把字典里的这个单词排除掉。

所以，要检查字典中的一个单词，你最多需要计算字符出现的次数，次数不会超过 MAX（26, n）。

Answer 3

这是对Jeroen Coupé在他的回答中提出的一个想法的实现，主要是用来计算字母的数量：

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