2

我正在尝试在这里编写一个像这样的单词解扰器，并且想知道我应该使用什么算法来实现它。此外，如果有人能找到现有的代码，那也很好。基本上，该功能将像一个 boggle 求解器，但不是矩阵，只是从字符串中搜索所有单词的可能性。我已经有足够的字典了。

我打算在 python 或 ruby​​ 中执行此操作。提前感谢您的帮助！

4

5 回答 5

3

我会使用Trie。这是 Python 中的一个实现：http: //jtauber.com/2005/02/trie.py（感谢 James Tauber）

于 2009-10-15T04:17:00.703 回答
2

我可能缺少对游戏的理解，但除非规则中出现一些复杂情况，例如引入“joker”（通配符）字母、缺少或额外的字母、多个单词等......我认为以下想法将有助于转变问题出在一件比较无趣的事情上。:-(

主要思想按字母顺序排列词索引。
例如，“计算机”被键入为“cemoprtu”。随机图纸提供的任何东西都是实物排序，并用作查找可能匹配项的关键。使用perimosocordiae 建议的trie结构，作为“叶”节点中这些排序键和相关单词/wordIds 的底层存储，单词查找可以在 O(n) 时间内完成，其中 n 是字母的数量（或者更好，平均而言，由于不存在的单词）。

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

游戏的其他转折（例如查找由字母子集组成的单词）主要是迭代 这些字母的幂集 并检查每个组合的字典。

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

于 2009-10-15T05:08:19.377 回答
2

对于您的字典索引，构建一个地图 (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)。值得注意的是，复杂性不取决于字典的长度。

于 2009-10-15T05:43:39.093 回答
1

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

于 2009-10-15T11:58:10.903 回答
1

有两种方法可以做到这一点。一种是检查单词中每个候选字母的排列，以查看该候选是否在您的单词词典中。这是一个 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 单词文件）。

于 2009-10-15T20:52:16.610 回答