Scrabble word finder:使用trie构建trie,存储trie？

Question

我正在做的事情:

我是怎么做的:

我目前的计划:

如果你不能执行它,有一个计划是不好的,这是我需要帮助的:

最后:
非常感谢任何帮助,我仍然是C#和MySQL的初学者,所以请保持温和

非常感谢!

Answer 1

首先,让我们看看问题的限制.您希望在有效支持"anagram"问题的数据结构中存储游戏的单词列表.也就是说,给定一个n个字母的"机架",单词列表中可以从该机架制作的所有n个或更少字母的单词是什么.单词列表将是大约400K字,因此在未压缩时可能大约有一到十兆字符串数据.

trie是用于解决此问题的经典数据结构,因为它结合了内存效率和搜索效率.使用大约400K字合理长度的单词列表,您应该能够将trie保留在内存中.(与使用b-tree类型的解决方案相反,在这种解决方案中,您将大部分树保留在磁盘上,因为它太大而无法同时存储在内存中.)

trie基本上只是一个26-ary树(假设你使用的是罗马字母),每个节点都有一个字母,每个节点上有一个额外的位,表示它是否是单词的结尾.

那么让我们勾勒出数据结构:

class TrieNode
{
    char Letter;
    bool IsEndOfWord;
    List<TrieNode> children; 
}

这当然只是一个草图; 你可能想让它们具有适当的属性访问器和构造函数等等.也许,平面列表可能不是最好的数据结构; 也许某种字典更好.我的建议是先让它工作,然后测量它的性能,如果它是不可接受的,那么试着做一些改进以改善它的性能.

你可以从一个空的特里开始:

TrieNode root = new TrieNode('^', false, new List<TrieNode>());

也就是说,这是表示单词开头的"根"trie节点.

如何添加单词"AA",拼字游戏字典中的第一个单词？好吧,首先为第一个字母创建一个节点:

root.Children.Add('A', false, new List<TrieNode>());

好的,我们的特里现在

^
|
A

现在为第二个字母添加一个节点:

root.Children[0].Children.Add(new trieNode('A', true, new List<TrieNode>()));

我们的特里现在

^
|
A
|
A$   -- we notate the end of word flag with $

大.现在假设我们想要添加AB.我们已经有一个"A"节点,所以添加"B $"节点:

root.Children[0].Children.Add(new trieNode('B', true, new List<TrieNode>());

现在我们有

    ^
    |
    A
   / \
  A$   B$

继续这样.当然,不是编写"root.Children [0] ..."而是编写一个循环来搜索trie以查看是否存在所需的节点,如果不存在,则创建它.

将你的trie存储在磁盘上 - 坦率地说,我只是将单词列表存储为纯文本文件,并在需要时重建trie.它不应该超过30秒左右,然后你可以在内存中重复使用trie.如果你想以某种更像trie的格式存储trie,那么编写序列化格式应该不难.

要搜索trie以匹配机架,我们的想法是探索trie的每个部分,但要删除机架无法匹配的区域.如果机架上没有任何"A",则无需关闭任何"A"节点.我在上一个问题中概述了搜索算法.

我已经实现了一个功能风格的持久性trie,我一直想写博客一段时间,但从未接触过它.如果我最终发布,我会更新这个问题.