c# - 拼字游戏查找器 : building a trie, 存储一个 trie，使用一个 trie？

Question

我正在尝试做的事情:

• 构建一个移动网络应用程序，用户可以在玩拼字游戏时获得帮助找到要玩的单词
• 用户通过输入任意数量的字母和 0 个或多个通配符来获得单词建议

我是如何尝试做到这一点的:

• 使用 MySQL 数据库和包含超过 40 万个单词的字典
• 使用 ASP.NET 和 C# 作为服务器端编程语言
• 使用 HTML5、CSS 和 Javascript

我目前的计划:

• 用数据库中的所有单词构建一个 Trie，这样我就可以根据用户字母/通配符输入快速准确地搜索单词

有计划如果不能执行就白搭，这就是我需要帮助的地方:

• 如何从数据库构建 Trie 树？ (更新:我想使用我数据库中已有的单词生成一个 Trie，完成之后我将不再使用该数据库进行单词匹配)
• 如何存储 Trie 以便快速轻松地访问？ (更新:这样我就可以丢弃我的数据库了)
• 如何使用 C# 根据字母和通配符使用 Trie 搜索单词？

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

非常感谢!

Answer 1

首先，让我们看看问题的约束条件。您希望在有效支持“字谜”问题的数据结构中存储游戏的单词列表。也就是说，给定一个 n 个字母的“架子”，可以从该架子组成的单词列表中的所有 n 个或更少字母的单词是什么。单词列表大约有 400K 个单词，因此在未压缩时可能有大约 1 到 10 兆的字符串数据。

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

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

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

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

这当然只是一个草图；您可能想让它们具有适当的属性访问器和构造函数等等。另外，也许平面列表不是最好的数据结构；也许某种字典更好。我的建议是先让它工作，然后衡量它的性能，如果 Not Acceptable ，然后尝试进行更改以提高其性能。

你可以从一个空的 trie 开始:

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

也就是说，这是表示单词开头的“根”特里树节点。

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

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

OK，我们的 trie 是现在

^
|
A

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

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

现在我们的 trie 是

^
|
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”节点。我在您之前的问题中勾勒出了搜索算法。

我有一个函数式持久性特里树的实现，我一直想在博客上讨论它一段时间，但一直没有时间去做。如果我最终发布了这个问题，我会更新这个问题。