问题标签 [trie]

我已经实现了一个基本的前缀树或“trie”。特里树由这样的节点组成：

假设我在我的 trie 中添加了以下词：“Apple”、“Ark”和“Cat”。现在，当我查找诸如“Ap”和“Ca”之类的前缀时，我的 trie 的“bool containsPrefix(string prefix)”方法将正确返回 true。

现在我正在实现方法“bool containsWholeWord(string word)”，它将为“Cat”和“Ark”返回true，但为“App”返回false（在上面的示例中）。

trie 中的节点具有某种“endOfWord”标志是否很常见？ 这将有助于确定要查找的字符串是否实际上是输入到 trie 中的整个单词，而不仅仅是前缀。

干杯!

我正在尝试用 Javascript 实现 Trie，这很容易，但我的对象似乎遇到了障碍。

节点结构如下：

Children 是一个由字符串中的字母映射的节点数组。所以字符串“Test”看起来像这样：

所以每个子数组的长度应该为 1，但如果做类似alert(this._root.children.length);我得到零的事情。关于为什么会发生这种情况的任何想法？

这是我实现的其余部分：

我正在寻找一个好的数据结构来表示形式的字符串：

• 每个“域”可以包含以下模式字符 - *, ?( *- 0 或多个字符, ?- 0 或 1 个字符)

• 每个“Key”可以包含以下模式字符 - *, ?( *- 0 或多个字符, ?- 0 或 1 个字符)

• 每个“值”可以包含以下模式字符 - *, ?( *- 0 或多个字符, ?- 0 或 1 个字符)

例子：

如果您熟悉 JMX ObjectName，那么本质上这就是 ObjectName 模式。

我正在寻找方法来轻松存储与每个模式相对应的规则，并能够快速删除、更新和添加新规则。

*我开始使用 Prefix Trie，但被模式字符,卡住了?。

我有一个生成大约 600 万个唯一数组的 C 函数。这些数组每个总是有 17 个元素，每个元素都是从 0 到 16 的整数。我还有一个稍微修改过的函数版本，它也将生成大约 600 万个相同类型的唯一数组。我的问题是第二个产生的结果比第一个少大约 45,000 个，我想看看这些结果是什么。

所以我的方法是简单地存储第二个函数的所有结果（计算器告诉我这不应该超过 400 mb，这可以保存在内存中）然后查找第一个函数的结果，打印出那些不存在。

假设一般方法是有意义的（如果没有，请告诉我），我正在寻找的是一个合适的数据结构（最好在 C 中具有良好的实现），它可以容纳大约 600 万个独特的排列

（或其一些转换），然后对它们执行快速成员资格测试。正如标题所说，我确实怀疑哪些数据结构可以完成这项工作，但我不确定尝试或哈希图是最好的选择。

这是一种用于检测另一个算法中的缺陷的算法，而不是在生产中使用的东西。我有兴趣以一种可以编码并以人类术语相对快速地返回结果的方式来执行此操作，不一定要减少毫秒，因此存在可以完成大部分工作的易于 grok 库绝对是一个加分项。

有谁知道我在哪里可以找到如何在 C# 中构建 trie 的示例？我正在尝试获取字典/单词列表并用它创建一个 trie。

编辑 ：

我听从了你的好建议，并使用了 trie 数据结构来包含我的字典。我为感兴趣的人选择了这个结构。

但是现在我还有另一个问题：每次启动应用程序时构建的 trie 数据结构都非常长！也许我的字典太大了，或者我选择的 trie 的实现对于简单的字典来说太不合适了。

那么有没有办法在关闭应用程序（如注册数据库）之后保存这种结构，或者如果您认为问题是由实施引起的，您可以推荐我另一个吗？

我的android项目有一个严重的问题。

这里的目标是计算可以用一系列 6 个字母组成的所有单词

为此，我的 BDD 中有两个表：

• 'words' 有两列：'_id' 和 'mots'
• 和 'temp' 具有相同列的临时表。

'words' 包含词汇表中的所有单词（它很大），'temp' 包含可以用 6 个字母组成的所有可能的字母组合（至少使用 3 个字母）。

我正在尝试在“temp”表中选择真实的单词，以便在“words”表中选择单词。这是我的代码：

我首先选择包含好字母的单词（至少使用 3 个字母）

（lettre.tab_char 是一个 ArrayList(Character)，其中包含用于在 temp 中进行组合的字母）

我在表 'temp2' 和 'temp' 之间进行连接：

之后，我将我的值放入列表视图中。

它有效，但它真的很慢：你能帮帮我吗？

我正在尝试在 C 中实现空间高效的 trie。这是我的结构：

当我添加一个节点时，它的索引是字符的无符号字符转换。例如，如果我想添加“c”，那么

是指向新添加节点的指针。然而，这个实现需要我声明一个包含 256 个元素的 node* 数组。我想做的是：

然后在添加节点时，只需为节点分配空间并拥有

指向新节点。问题是如果我不首先为孩子分配空间，那么我显然不能引用任何索引，否则这是一个很大的错误。

所以我的问题是：我如何实现一个 trie，使其只存储指向其子级的非空指针？

我在这里找到了一篇关于使用 Tries 修复拼写错误的很酷的博客文章，但是它是用旧版本的 F# 编写的。
http://blog.lab49.com/archives/2841 我已经修复了大部分问题，除了最后我在我认为出现问题的所有大写字母中发表了评论。基本上在一些地方需要一个 Set 并给出一个 Map<> ，反之亦然。我已经盯着这段代码几个小时了，似乎无法弄清楚事情在哪里变得不匹配。

提前致谢，

鲍勃

我不太精通字符串匹配中使用的实际算法。

我想知道为什么似乎更关注字符串匹配的后缀尝试而不是前缀尝试。我们也可以不使用前缀尝试进行子字符串匹配吗？换句话说，后缀尝试比前缀尝试有什么优势？

我目前正在努力在 Scala 中实现我自己的Trie（出于学习/爱好目的），并且我正在尝试保持它的通用性（以便它可以存储任何可迭代的内容，而不仅仅是字符串）。我的班级签名看起来像

我已经实现了包含、+= 和 -=（它扩展了 Set 的可变版本），但是我在使用迭代器时遇到了一些问题。我目前的方法让我挠头寻找一个优雅的实现。我有一种方法可以遍历所有的 TrieNode，并且只释放那些被标记为“有效结尾”的节点。从那里我计划按照父链接获取各个部分。（例如，树中的“hello”将存储为标记为结尾的“o”节点，父节点为“l”->“l”->“e”->“h”）

现在我的问题。由于我试图保持通用性，我无法从其“部件”中重建“项目”。所以我向 SO 的人们提出的问题是，处理这个问题的最优雅的方式是什么？我应该在构造函数参数中添加重建函数吗？应该Item有不同的界限以强制功能的存在吗？还是完全是别的东西？