问题标签 [trie]

我正在使用大量（5-20​​00 万）字符串键（平均长度为 10 个字符），我需要将它们存储在内存数据结构中，该结构支持在恒定时间或接近恒定时间的以下操作：

事实证明，Java 的 Hashmap 就吞吐量而言非常令人满意，但它占用了大量内存。我正在寻找一种内存高效的解决方案，并且仍然支持不错的吞吐量（与散列相当或几乎一样好）。

我不在乎插入/删除时间。在我的应用程序中，我将只执行插入（仅在启动时），随后将只contains在应用程序的生命周期内使用该方法查询数据结构。

我读到 HAT-Trie 数据结构最适合我的需要。我想知道是否有一个有实现的库。

欢迎其他带有实现指针的建议。

谢谢你。

我正在尝试用 Java 实现一个非常简单的 Trie，它支持 3 个操作。我希望它有一个 insert 方法、一个 has 方法（即 trie 中的某个单词）和一个 toString 方法以字符串形式返回 trie。我相信我的插入工作正常，但 has 和 toString 被证明是困难的。这是我到目前为止所拥有的。

trie 类。

和节点类

因此，基本上，在创建 Trie 时，会创建一个 TrieNode 作为具有 26 个子节点的根。当尝试插入时，会在该根节点上调用 insert，它会在正确的位置递归地创建一个新节点，并继续直到单词完成。我相信该方法工作正常。

我的 has 函数非常糟糕，因为出于某种原因，我必须在括号外加上 return 语句。我不能将它包含在 else 子句中，否则编译器会抱怨。除此之外，我认为该方法应该进行一些调整，但我无法终生解决。

toString 是我试图解决的野兽，但我扔给它的任何东西都不起作用，所以我会保留它，直到我解决问题。如果我有工作，我可能会想办法将它重新格式化为 toString 函数。

int val = word.charAt(0) - 64; 的目的 是因为输入的每个字符串都必须全部大写（我将创建一个字符串格式化函数来确保这一点）所以第一个字母的 int 值 - 64 将是它在数组中的位置。即数组索引0是A，所以A = 64，A - 64 = 0。B = 65，B - 64 = 1，依此类推。

我正在开发一个Trie数据结构，其中每个节点代表一个单词。所以单词st,stack和将被安排为stackoverflowoverflow

我的 Trie 在HashTable内部使用，因此所有节点查找都需要固定时间。以下是我想出的将项目插入特里树的算法。

1. 检查 trie 中是否存在项目。如果存在，则返回，否则转到步骤2。
2. 迭代中的每个字符key并检查单词是否存在。这样做直到我们得到一个可以将新值添加为子节点的节点。如果没有找到节点，它将被添加到根节点下。
3. 插入后，重新排列插入新节点的节点的兄弟姐妹。这将遍历所有兄弟节点并与新插入的节点进行比较。如果任何节点以与新节点相同的字符开头，它将从那里移动并添加为新节点的子节点。

我不确定这是实现 trie 的正确方法。欢迎任何建议或改进。

使用语言：C++

今天参加了一家公司的笔试。整个测试集中在数据结构上。我遇到了一个我认为我解决了的问题。但是我在计算数据结构的大 O 函数时遇到了困难。我将提供我想出的问题和答案。

给定您需要存储的文档和文档中的单词，并且应该能够在输入任何单词时返回计数。为您提供char* GetNextWord().

1. 你会选择什么数据结构
2. 给出算法
3. 你的算法的顺序是什么

对于问题 1，我写了我会选择 TRIE 数据结构。对于问题 2，我给出了一个简短的算法。我写道，我将构建 TRIE 数据结构如下。

我有方法可以为每个单词constructTrie()做一个。addToTrie()

我写的顺序addToTrie()是 O( k )，其中k是长度。的顺序constructTrie()是N *O( k )，其中N是单词的数量。

现在我的问题是：我提到的命令是否正确？如果没有，将来如何解决这样的问题（给定一个 ds 查找命令）。使用 O( k )后我真的很困惑。它让我假设 O(1)。

提示/提示/建议是敞开的！

编辑：更正了清楚地提到应该为所有唯一单词存储字数的问题。

我正在尝试使用 , 和 方法实现 Patricia Trie addWord()，isWord()并将isPrefix()其作为一种存储大型单词字典以便快速检索（包括前缀搜索）的方法。我已经阅读了这些概念，但它们只是没有阐明实现。我想知道（在 Java 或 Python 代码中）如何实现 Trie，尤其是节点（或者我应该递归地实现它）。我看到一个人用一组 26 个子节点设置为 null/None 来实现它。是否有更好的策略（例如将字母视为位）以及您将如何实施？

哪种结构提供了最好的性能结果；trie（前缀树）、后缀树还是后缀数组？还有其他类似的结构吗？这些结构的良好 Java 实现是什么？

编辑：在这种情况下，我想在大型名称字典和大量自然语言文本之间进行字符串匹配，以便识别文本上字典的名称。

我计划在 TRIE 数据结构中工作，我需要一个字典数据库或一个包含整个英语单词列表的文本或单词文件。大小是否巨大无关紧要。越大越好。

I have a trie which I am using to do some string processing. I have a simple compiler which generates trie from some data. Once generated, my trie won't change at run time.

I am looking for an approach where I can persist the trie in a file and load it effectively. I have looked at sqllite to understand how they are persisting b-treebut their file format looks bit advanced and I may not need all of those.

It'd be helpful if someone can provide some ideas to persist and read the trie. I am programming using C.

我希望使用以下代码不检查 Trie 中是否存在匹配的单词，而是返回以用户输入的前缀开头的所有单词的列表。有人可以指出我正确的方向吗？我根本无法让它工作......

为方便起见，该表包含英语词典中的所有单词。

我想做的是能够将数据存储为 trie。这样我可以遍历 trie 的不同分支并返回最相关的结果。

首先，如何将表中的数据存储为 trie？

其次，如何遍历树？

如果它有帮助，那么上一个问题中的建议就是引发这个问题的地方。

请确保它是我们正在谈论的 SQL。由于指针，我理解了Mike Dunlavey 的 C 实现，但看不到这部分（特里树本身）在 SQL 中是如何工作的。

谢谢，
马特