在python中从随机输入字母中查找单词。已经有了什么算法/代码?

Trie 。这是Python中的一个实现: http://jtauber.com/2005/02/trie.py (归功于詹姆斯·陶伯)

我可能对游戏缺乏了解,但除非规则中出现一些复杂情况,例如引入“joker”(通配符)字母、缺少或额外的字母、多个单词等……我认为以下想法将有助于将问题变成一个相对无趣的问题。 :-(

主要思想 索引词 有序的 他们字母的顺序 .
例如,“computer”被键入为“cemobrtu”。随机图纸提供的是实物排序,并用作找到可能匹配项的关键。 使用 trie 查找可以在O(n)时间内完成 ,其中n是字母数(或者更好,由于不存在单词,平均而言)。

为了进一步帮助索引,我们可以有几个表/字典,每个字母对应一个。同样,根据统计数据,元音和辅音可以分开处理。另一个技巧是使用自定义排序顺序,将最有选择性的字母放在第一位。

游戏中的其他转折(例如找到由字母子集组成的单词)主要是 迭代 power set 并检查字典中的每个组合。

可以引入一些启发式方法 为了帮助修剪一些组合(例如,没有元音[和给定长度]的组合是不可能的解决方案等。人们应该仔细管理这些启发式方法,因为查找成本相对较小。

对于字典索引,构建一个映射(map[Bag[Char],List[String]])。它应该是一个哈希映射,这样你就可以得到O(1)个单词的查找。Bag[Char]是一个单词的标识符,按照字符顺序是唯一的。它基本上是一个从Char到Int的哈希映射。Char是单词中的一个给定字符,Int是该字符在单词中出现的次数。

例子:

{'a'=>3, 'n'=>1, 'g'=>1, 'r'=>1, 'm'=>1} => ["anagram"]
{'s'=>3, 't'=>1, 'r'=>1, 'e'=>2, 'd'=>1} => ["stressed", "desserts"]

要查找单词,请从输入字符串中提取每个字符组合,并在该映射中查找。该算法的复杂度在输入字符串的长度上为O(2^n)。值得注意的是,复杂度不取决于字典的长度。

这听起来像 Rabin-Karp string search 这将是一个不错的选择。如果你使用滚动哈希函数,那么在每个位置都需要一次哈希值更新和一次字典查找。您还需要创建一种很好的方法来处理不同的单词长度,比如将所有单词截断为集合中最短的单词,并重新检查可能的匹配。将单词集拆分为单独的长度范围将减少误报的数量,但代价是增加了哈希工作。

有两种方法可以做到这一点。一种方法是检查单词中每个候选字母的排列,看看候选字母是否在你的词典中。这是一个O(N!)操作,取决于单词的长度。

因此,首先构建一个字典,其关键字是一个排序的字母串,其值是关键字的字谜单词列表:

>>> from collections import defaultdict
>>> d = defaultdict(list)
>>> with open(r"c:\temp\words.txt", "r") as f:
        for line in f.readlines():
            if line[0].isupper(): continue
            word = line.strip()
            key = "".join(sorted(word.lower()))
            d[key].append(word)

现在我们需要一个函数来查看一个单词是否包含候选词。此函数假设单词和候选词都已排序,因此它可以逐个字母地遍历它们,并在发现它们不匹配时迅速放弃。

>>> def contains(sorted_word, sorted_candidate):
        wchars = (c for c in sorted_word)
        for cc in sorted_candidate:
            while(True):
                try:
                    wc = wchars.next()
                except StopIteration:
                    return False
                if wc < cc: continue
                if wc == cc: break
                return False
        return True

现在,在字典中找到单词包含的所有候选键,并将它们的所有值聚合到一个列表中:

>>> w = sorted("mythopoetic")
>>> result = []
>>> for k in d.keys():
        if contains(w, k): result.extend(d[k])
>>> len(result)
429
>>> sorted(result)[:20]
['c', 'ce', 'cep', 'ceti', 'che', 'chetty', 'chi', 'chime', 'chip', 'chit', 'chitty', 'cho', 'chomp', 'choop', 'chop', 'chott', 'chyme', 'cipo', 'cit', 'cite']

在我的笔记本电脑上,最后一步大约需要四分之一秒;我的字典里有195K个键(我使用的是BSD Unix单词文件)。