Scrabble word finder：使用trie构建trie，存储trie？
我想做什么：
- 构建一个移动Web应用程序，用户可以在玩拼字游戏时寻求帮助
- 用户通过键入任意数量的字母和0个或更多通配符来获得单词建议
我是怎么做的：
- 将MySQL数据库与包含超过400k字的字典一起使用
- 使用ASP.NET和C＃作为服务器端编程语言
- 使用HTML5，CSS和Javascript
我目前的计划：
- 使用数据库中的所有单词构建Trie，以便根据用户字母/通配符输入快速准确地搜索单词
如果你不能执行它就有一个计划是不好的，这是我需要帮助的：
- 如何从数据库构建Trie？ （更新：我想使用我的数据库中已有的单词生成一个Trie，完成之后我不再使用数据库进行单词匹配了）
- 如何存储Trie以便快速方便地访问？ （更新：所以我可以删除我的数据库）
- 如何使用C＃根据字母和通配符使用Trie搜索单词？
最后：
非常感谢任何帮助，我仍然是C＃和MySQL的初学者，所以请保持温和
非常感谢！
首先，让我们看看问题的限制。 您希望在有效支持“anagram”问题的数据结构中存储游戏的单词列表。 也就是说，给定n个字母的“机架”，单词列表中可以从该机架制作的所有n个或更少字母的单词是什么。 单词列表将是大约400K字，因此在未压缩时可能大约有一到十兆字符串数据。
trie是用于解决此问题的经典数据结构，因为它将内存效率与搜索效率相结合。 使用大约400K字合理长度的单词列表，您应该能够将trie保留在内存中。 （与使用b-tree类型的解决方案相反，您可以将大部分树保留在磁盘上，因为它太大而无法同时存储在内存中。）
trie基本上只是一个26-ary树（假设你使用的是罗马字母），每个节点都有一个字母，每个节点上有一个额外的位，表示它是否是单词的结尾。
那么让我们勾勒出数据结构：
class TrieNode { char Letter; bool IsEndOfWord; List children; } 这当然只是一个草图; 你可能想让它们具有适当的属性访问器和构造函数等等。 也许，平面列表可能不是最好的数据结构; 也许某种字典更好。 我的建议是先让它工作，然后测量它的性能，如果它是不可接受的，那么试着做一些改进来改善它的性能。
你可以从一个空的特里开始：
TrieNode root = new TrieNode('^', false, new List());
也就是说，这是表示单词开头的“根”trie节点。
如何添加单词“AA”，拼字游戏字典中的第一个单词？ 好吧，首先为第一个字母创建一个节点：
root.Children.Add('A', false, new List());
好的，我们的特里现在
^ | A
现在为第二个字母添加一个节点：
root.Children[0].Children.Add(new trieNode('A', true, new List()));
我们的特里现在
^ | A | A$ -- we notate the end of word flag with $
大。 现在假设我们想要添加AB。 我们已经有一个“A”节点，所以添加“B $”节点：
root.Children[0].Children.Add(new trieNode('B', true, new List());
现在我们有了
^ | A / \ A$ B$
继续这样。 当然，不是编写“root.Children [0] …”而是编写一个循环来搜索trie以查看您想要的节点是否存在，如果不存在，则创建它。
将你的trie存储在磁盘上 – 坦率地说，我只是将单词列表存储为纯文本文件，并在需要时重建trie。 它不应该超过30秒左右，然后你可以在内存中重新使用trie。 如果你想以某种更像trie的格式存储trie，那么编写序列化格式应该不难。
要搜索trie以匹配机架，我们的想法是探索trie的每个部分，但要删除机架无法匹配的区域。 如果机架上没有任何“A”，则无需关闭任何“A”节点。 我在上一个问题中概述了搜索算法。
我有一个函数式持久trie的实现，我一直想写博客一段时间，但从来没有解决它。 如果我最后发布，我会更新这个问题。