拼字机:建立一个trie，存储一个trie，使用trie？

Question

我想做的是：

• 构建了一个移动web应用程序，用户在玩拼字游戏时可以通过输入任意数量的字母和0或更多的通配符(

)获得单词建议。

我是怎么做的：

使用包含400多个单词的字典的

• 使用MySQL数据库
• 使用ASP.NET作为服务器端编程MySQL HTML5、CSS和Javascript

我现在的计划：

• 用数据库中的所有单词构建Trie，以便根据用户字母/通配符输入

快速准确地搜索单词

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

• 如何从数据库构建Trie？(更新:我想使用数据库中已经存在的单词生成Trie，在完成之后，我将不再使用数据库进行单词匹配)
• 如何存储Trie以方便快速访问？(更新:这样我就可以毁掉我的database)
• How了，我用C#根据字母和通配符搜索单词吗？

终于：

任何帮助都是非常感谢的，我仍然是C#和MySQL的初学者，所以请温柔一点

非常感谢你！

Answer 1

首先，让我们来看看问题的制约因素。您希望在有效支持"anagram“问题的数据结构中存储游戏的单词列表。也就是说，给定n个字母的“行”，那么单词列表中所有的n字母或较少字母的单词都可以由该字条构成。单词列表将是大约400 K的单词，所以当未压缩时可能是大约1到10兆字节的字符串数据。

trie是解决这一问题的经典数据结构，因为它将内存效率和搜索效率结合起来。有了一个大约400 K字的合理长度的单词列表，你应该能够将trie保存在记忆中。(与使用b树的解决方案不同，在这种解决方案中，大多数树都保存在磁盘上，因为它太大，无法同时放进内存中。)

trie基本上只是一个26进制的树(假设您使用的是罗马字母)，其中每个节点都有一个字母，每个节点上有一个额外的位，表示它是否是单词的结尾。

让我们来描述一下数据结构：

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

当然，这只是一个草图；您可能希望使这些具有适当的属性、访问器和构造函数等等。此外，也许平面列表不是最好的数据结构；也许某种字典更好。我的建议是，首先让它发挥作用，然后衡量它的性能，如果这是不可接受的，然后尝试作出改变，以提高其性能。

您可以从一个空的trie开始：

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.”您将编写一个循环，搜索trie以查看您想要的节点是否存在，如果不存在，则创建它。

要将您的trie存储在磁盘上--坦率地说，我只需将单词列表存储为纯文本文件，并在需要时重新构建trie。它不应该超过30秒左右，然后你可以在内存中重复使用trie。如果您确实希望以更像trie的格式存储trie，那么应该不难找到序列化格式。

为了寻找匹配机架的trie，想法是探索trie的每一个部分，但是修剪出机架不可能匹配的区域。如果你没有任何"A“在机架上，就没有必要下降任何”A“节点。我在你上一个问题中勾勒出了搜索算法。

我已经实现了一个功能风格的持久trie，我已经有一段时间想在博客上写了，但一直没有找到它。如果我最终发布，我会更新这个问题。