7

我正在尝试做的事情：

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

我是如何尝试这样做的：

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

我目前的计划：

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

如果您无法执行计划，那就没有好处了，这是我需要帮助的：

  • 如何从数据库构建 Trie？（更新：我想使用数据库中已有的单词生成一个 Trie，完成后我将不再使用数据库进行单词匹配）
  • 如何存储 Trie 以便快速方便地访问？（更新：所以我可以丢弃我的数据库）
  • 如何使用 C# 根据字母和通配符使用 Trie 搜索单词？

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

十分感谢！

4

1 回答 1

17

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

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

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

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

要搜索树以匹配机架，其想法是探索树的每个部分，但修剪掉机架不可能匹配的区域。如果机架上没有任何“A”，则无需关闭任何“A”节点。我在你之前的问题中勾勒了搜索算法。

我有一个函数式持久性 trie 的实现，我一直想写博客一段时间，但一直没有解决。如果我最终发布，我会更新这个问题。

于 2011-09-16T15:13:11.443 回答