问题标签 [trie]

我是 C# 初学者，目前我正在尝试用不同的问题挑战自己。

目前我正在尝试构建一个 Web 应用程序，您可以在其中输入字母和通配符来搜索可能的单词。

通过之前关于此的问题，我决定构建一个包含从 400k+ 单词生成的字母的 Trie。稍后我将根据字母和通配符输入在 Trie 中搜索可能的单词匹配。

我构建了两个类，一个代表 Trie 中的一个节点，另一个代表整个 Trie。

我目前处于停顿状态，我的问题是我想在多个级别向 Trie 添加多个孩子，并且每个孩子都必须是唯一的。

手动执行此操作看起来像这样：

问题是我想添加一个或多个循环的孩子，这样做似乎有点“错误”：

我需要的是一个或多个带有“干净”代码的循环，你能帮我吗？为了让 Trie 稍后可以搜索，我认为这些字母需要按顺序排列。这是我与此相关的其他问题：Question 1，Question 2。

这是我的 TrieNode 类：

……这是我的 Trie 课程：

我试图了解mmo目标文件格式是如何工作的，它用于 Don Knuth 的教育MMIX架构。MMIXware我没买过，所以只能从汇编器和模拟器的文字源文件中猜测大部分细节。

对象格式使用特殊的三元搜索树来存储符号表。看一下代码，我不太明白它是如何工作的。有人可以向我解释一些细节吗？特别是关于树是如何序列化的。

就计算复杂度而言，哪种数据结构最适合实现 (key,val) 项的字典，它必须仅支持以下命令：

1. Insert(key)- 用 val=1 附加一个项目 (key,val)
2. Increment(key)- 增加已存在的 val (key,val)
3. Find(key)- 返回 (key,val) 的 val
4. Select(part_of_key)strstr(key,part_of_key)!=NULL- 如果以相同类型的新字典的形式返回所有项目 (key,val) 的列表（如果可能，不分配新内存）；例如，如果字典是 {(red,3), (blue,4), (green,1)}，则 Select(re)={(red,3), (green,1)}
5. Max(i)- 返回所有项目中具有第 i 个最大值的项目；例如，如果字典是 {(red,3), (blue,4), (green,1)}，则 Max(1)=blue, Max(2)=red, Max(3)=green

键是字符串，值是正整数。字典中的项目数量预计会非常大。

我认为它一定是两种不同数据结构的综合。但它应该是哈希表 + 二叉树还是 trie + 排序数组或其他？

我正在尝试从大量单词中读取并以一种允许我以后快速检索的方式存储它们。我首先想到的是使用 trie，但我承认我的实现很幼稚，它基本上是嵌套的哈希表，每个键都是不同的字母。现在将一个单词插入到 trie 中需要很长时间（运行这个程序需要 20 多秒），我想知道是否有人对我可以做些什么来改进我的插入有任何想法？这不是为了家庭作业。

I am looking to implement a VBA trie-building algorithm that is able to process a substantial English lexicon (~50,000 words) in a relatively short amount of time (less than 15-20 seconds). Since I am a C++ programmer by practice (and this is my first time doing any substantial VBA work), I built a quick proof-of-concept program that was able to complete the task on my computer in about half a second. When it came time to test the VBA port however, it took almost two minutes to do the same -- an unacceptably long amount of time for my purposes. The VBA code is below:

Node Class Module:

Main Module:

My question then is simply, can this algorithm be sped up? I saw from some sources that VBA Collections are not as efficient as Dictionarys and so I attempted a Dictionary-based implementation instead but it took an equal amount of time to complete with even worse memory usage (500+ MB of RAM used by Excel on my computer). As I say I am extremely new to VBA so my knowledge of both its syntax as well as its overall features/limitations is very limited -- which is why I don't believe that this algorithm is as efficient as it could possibly be; any tips/suggestions would be greatly appreciated.

Thanks in advance

NB: The lexicon file referred to by the code, "corncob_caps.txt", is available here (download the "all CAPS" file)

我正在尝试使用 trie 数据结构实现拼写检查器。我目前有以下大纲Node：

我想做的下一件事是编写函数来搜索 astring然后返回一个建议的拼写。( def correct(self, string))。我将如何通过这个尝试来实现搜索？假设我已经通过定义一个 root node 向 trie 添加了一个单词列表root，然后add_item对列表中的每个单词使用。

背景：
我的 CSS360 小组正在尝试创建一个包含自动完成搜索功能的 Android 应用程序。我们将要搜索的数据包含大约 7000 个条目，并将存储在手机本身的 SQLite 数据库中。最明显的方法是在用户键入的每个字符之后对数据库进行线性搜索，然后返回一个建议列表，这些建议是用户查询的潜在字母扩展。但是，这似乎效率很低，我们一直在寻找更好的替代方案。在我今天的另一节课中，我的导师简要讨论了 trie 数据结构，并提到它通常用于存储整个字典。可以在对数时间内检索到 trie 的条目（与常规旧数组的线性时间相反），所以这对我们来说似乎是一个很好的工具！不幸的是，我们已经在这个项目上不知所措了，我们都没有真正知道如何做到这一点。迄今为止，我们任何人都编写过基本的控制台应用程序，用于教我们编程基础知识。我们都试图在一周的时间内通过观看 YouTube 视频来学习 Android 平台，并将数据库内容与我们小组中具有任何 SQL 经验的人区别开来。我们可以认真使用一些指针！所有人都试图在一周的时间内通过观看 YouTube 视频来学习 Android 平台，并将数据库内容与我们小组中具有任何 SQL 经验的人区别开来。我们可以认真使用一些指针！所有人都试图在一周的时间内通过观看 YouTube 视频来学习 Android 平台，并将数据库内容与我们小组中具有任何 SQL 经验的人区别开来。我们可以认真使用一些指针！

问题：

• 创建 trie 时，是否可以预先填充整个结构？IE：为每个使用的节点生成一行代码，这样程序启动时整个结构就已经在内存中了？我的想法是，这将为我们节省每次程序启动时都必须从数据库中重新生成整个 trie 的开销。如果是这样，有没有一种简单的方法可以将这数千行代码放入我们的程序中？IE：某种脚本可以将数据库文件转换为可以复制并粘贴到 Eclipse 中的 java 命令的巨大文本文件？
• 如果我们直接搜索数据库而不是使用某种内部列表或数据结构，会不会有相当大的开销？我们是否应该从数据库中复制名称并在程序中搜索它们以获得我们的自动完成功能？
• 如果这对我们来说在技术上太难了，我们不得不求助于常规的线性搜索，性能会受到明显影响吗？
• 我们目前的计划是在每次用户输入字符时运行自动完成功能，然后等待该功能返回，然后再允许他们继续输入。到目前为止，我们任何人编写的唯一程序都是这样同步运行的。我们需要知道什么才能使这个函数异步？考虑到我们的新手能力，以及我们已经必须满足的要求，这对我们来说在技术上是否太具有挑战性？

可能重复：
在哪里可以找到 Java 中基于标准 Trie 的地图实现？

我想在 Java 中使用 Trie，有没有我可以使用的实现？（我试图寻找一个，但我没有找到它）。

特里的类型是

我想编写一个接收键值对和前缀树的函数。然后我希望它返回包含键值对的符号表。如果键已经存在，则新值应替换旧值。

例子：

我还希望能够在 trie 中搜索并找到以某个前缀开头的键。例子：

任何人都知道 Delphi 中现成的 trie [原文如此] 实现？优化的尝试会更好。

提前致谢！