python - 有效地寻找乱码中的单词

Question

我想你可以把它归类为拼字游戏风格问题，但它是由于一位朋友提到英国电视问答节目倒计时而开始的。节目中的多轮比赛涉及向参赛者展示一组乱七八糟的字母，他们必须想出他们能想到的最长的单词。我朋友提到的那个是“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 秒才能找到“重新唤醒”。使用 14 个字符打乱的单词，我们可以在 23 天的范围内讨论，只是为了检查所有可能的 14 个字符排列。

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

Answer 1

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- 可以/usr/share/dict/words在 Linux 上。

更新

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

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

Answer 2

你想避免做排列。您可以计算一个字符在两个字符串（原始字符串和字典中的字符串）中出现的次数。排除字典中字符频率不同的所有单词。

因此，要从字典中检查一个单词，您最多需要计算字符数 MAX (26, n) 时间。

Answer 3

1. 将字典预解析为 sorted(word)、单词对。（例如 giilnstu，语言学家）
2. 对字典文件进行排序。

然后，当您搜索给定的一组字母时：

1. 对字典中的字母进行二进制搜索，首先对字母进行排序。

您需要为每个字长单独执行此操作。

编辑：应该说您正在搜索目标字长（range(len(letters), 0, -1)）的排序字母的所有唯一组合

Answer 4

这类似于我之前研究过的一个字谜问题。我通过使用素数来表示每个字母来解决这个问题。每个单词的字母乘积产生一个数字。要确定一组给定的输入字符是否足以完成一项工作，只需将输入字符的乘积除以您要检查的数字的乘积即可。如果没有余数，则输入字符就足够了。我在下面实现了它。输出是：

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

您可以在以下位置找到有关 anagrams 案例的更多详细信息和详尽解释：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 5

我昨晚在你问这个问题后不久就开始了这个，但直到现在才开始完善它。这是我的解决方案，它基本上是一个修改过的 trie，直到今天我才知道！

class Node(object):
    __slots__ = ('words', 'letter', 'child', 'sib')

    def __init__(self, letter, sib=None):
        self.words = []
        self.letter = letter
        self.child = None
        self.sib = sib

    def get_child(self, letter, create=False):
        child = self.child
        if not child or child.letter > letter:
            if create:
                self.child = Node(letter, child)
                return self.child
            return None
        return child.get_sibling(letter, create)

    def get_sibling(self, letter, create=False):
        node = self
        while node:
            if node.letter == letter:
                return node
            sib = node.sib
            if not sib or sib.letter > letter:
                if create:
                    node.sib = Node(letter, sib)
                    node = node.sib
                    return node
                return None
            node = sib
        return None

    def __repr__(self):
        return '<Node({}){}{}: {}>'.format(chr(self.letter), 'C' if self.child else '', 'S' if self.sib else '', self.words)

def add_word(root, word):
    word = word.lower().strip()
    letters = [ord(c) for c in sorted(word)]
    node = root
    for letter in letters:
        node = node.get_child(letter, True)
    node.words.append(word)

def find_max_word(root, word):
    word = word.lower().strip()
    letters = [ord(c) for c in sorted(word)]
    words = []
    def grab_words(root, letters):
        last = None
        for idx, letter in enumerate(letters):
            if letter == last: # prevents duplication
                continue
            node = root.get_child(letter)
            if node:
                words.extend(node.words)
                grab_words(node, letters[idx+1:])
            last = letter
    grab_words(root, letters)
    return words

root = Node(0)
with open('/path/to/dict/file', 'rt') as f:
    for word in f:
        add_word(root, word)

测试：

>>> def nonrepeating_words():
...     return find_max_word(root, 'abcdefghijklmnopqrstuvwxyz')
... 
>>> sorted(nonrepeating_words(), key=len)[-10:]
['ambidextrously', 'troublemakings', 'dermatoglyphic', 'hydromagnetics', 'hydropneumatic', 'pyruvaldoxines', 'hyperabductions', 'uncopyrightable', 'dermatoglyphics', 'endolymphaticus']
>>> len(nonrepeating_words())
67590

我想我更喜欢 dermatoglyphics 最长的词不可版权，我自己。性能方面，使用约 500k 单词词典（来自此处），

>>> import timeit
>>> timeit.timeit(nonrepeating_words, number=100)
62.8912091255188
>>> 

因此，平均而言，6/10 秒（在我的 i5-2500 上）可以找到所有 67000 个不包含重复字母的单词。

这个实现和 trie 之间的最大区别（这使得它比一般的 DAWG 更远）是：单词存储在 trie 中，与它们的排序字母相关。所以'dog'这个词和'god'存储在同一个路径下：dgo。第二位是find_max_word算法，它通过不断地砍掉它的头并重新运行搜索来确保访问每个可能的字母组合。

哦，只是为了咯咯笑：

>>> sorted(tree.find_max_word('RAEPKWAEN'), key=len)[-5:]
['wakener', 'rewaken', 'reawake', 'reawaken', 'awakener']

Answer 6

另一种方法，类似于@market 的答案，是为字典中的每个单词预先计算一个“位掩码”。如果字包含至少一个 A，则设置位 0，如果它包含至少一个 B，则设置位 1，依此类推，直到 Z 的位 25。

如果您想在字典中搜索所有可以由字母组合组成的单词，您首先要为字母集合形成位掩码。wordBitmask & ~lettersBitMask然后，您可以通过检查是否为零来过滤掉所有使用其他字母的单词。如果为零，则该单词仅使用集合中可用的字母，因此可能是有效的。如果它不为零，则它使用集合中不可用的字母，因此是不允许的。

这种方法的优点是按位运算速度很快。字典中的绝大多数单词将至少使用 17 个或更多字母中的一个，这些字母不在给定的集合中，您可以快速将它们全部打折。但是，对于通过过滤器的少数单词，您仍然需要进行另一项检查。您仍然需要检查单词使用字母的频率是否高于它们在集合中出现的频率。例如，必须禁止使用单词“weakener”，因为它有三个“e”，而字母 RAEPKWAEN 的集合中只有两个。单独的按位方法不会过滤掉这个单词，因为单词中的每个字母都出现在集合中。

Answer 7

1. 从您的字典中构造一个trie（前缀树） 。您可能想要缓存它。
2. 走在这个树上，移除不适合你的信袋的整个树枝。

在这一点上，你的 trie 是字典中所有单词的表示，这些单词可以从你的字母包中构造出来。

1. 只需要更长的时间:-)

编辑：您也可以使用具有较少顶点的DAGW（有向无环字图） 。虽然我还没有读过，这篇维基百科文章有一个关于世界上最快的拼字游戏程序的链接。

Answer 8

当寻找超过 10 个字母的单词时，您可能会尝试迭代超过 10 个字母的单词（我认为 10 个字母的单词并不多），并检查您的集合中是否有所需的字母。

问题是您必须首先找到所有这些 len(word) >= 10 个单词。

所以，我会做什么：在阅读字典时，将单词分为两类：shorts 和 longs。您可以通过迭代每个可能的排列来处理短裤。比你可以通过迭代来处理多头并检查它们是可能的。

当然，两条路径都可以进行许多优化。

Answer 9

DAWG (Directed Acyclic Word Graph) Mark Wutka 很友好地在这里提供了一些帕斯卡代码。

• http://www.wutka.com/dawg.html
• http://www.wutka.com/DictConvert.ZIP

Answer 10

如果您有一个带有排序单词的文本文件。只需这段代码进行数学运算：

UsrWrd = input()      #here you Enter scrambled letters
with open('words.db','r') as f:
   for Line in f:
       for Word in Line.split():
           if len(Word) == len(UsrWrd) and set(Word) == set(UsrWrd):
               print(Word)
               break
           else:continue       `