问题标签 [radix-tree]

我正在创建一个二叉基数树（最长的公共前缀树）。数据仅存储在叶节点中。树层次结构具有内部节点，每个内部节点都有两个子节点。子节点可以是叶节点或内部节点。叶节点和内部节点都存储对父节点的引用。

叶节点存储在一个数组中。内部节点存储在另一个数组中。根节点是内部节点数组的第一个元素

假设树结构现在填充为内部节点数组，如果我现在选择树的任何内部节点，我怎么知道内部节点的子节点是内部节点还是叶节点？为此，我正在考虑为每个子节点存储一个布尔变量，以将其标记为前导节点或内部节点。但这在我看来并不是一个好的解决方案。

谁能建议我一个更好的方法来做到这一点？

我需要根据大量数据进行查找。该数字可能在 1 - 2^32 范围内。根据输入，我需要返回一些其他数据结构。我的问题是我应该使用什么数据结构来有效地保存它？

如果数字在 1 到 5000 的范围内，我会使用一个给我 O(1) 查找的数组。但是当我的输入数字变大时，使用数组变得不切实际，因为内存需求会很大。

因此，我试图研究一种能够快速产生结果并且不是很重的数据结构。

任何线索任何人？

编辑：

使用数组是没有意义的，因为我可能只有 100 或 200 个索引要存储。

阿布舍克

这是一个关于在实践中通常会做什么的问题。

假设我们有一个带有一个条目的基数树（无论出于何种原因，将其视为一个用于演示的条目）：

然后我们要输入第二个条目

我们希望最终得到来自根的边缘

和两个边缘的，一个与

和一个

天真地，我们可以为“te”和“sts are really...”创建新的字符串（字符数组等）。这需要很多操作，即使我们的新词“团队”很短。

或者，我们可以让“te”和“sts are really...”标签可以包含对相同原始字符串的引用，以及开始/结束值，即：

和

这样我们就避免了任何复制，并且“team”的插入时间仅取决于“team”的长度，而不取决于其他字符串的长度，即“tests are really...”在这种情况下。

所以问题在于kinO(k)是指插入的字符串的长度，还是迄今为止最长的字符串。

显然，后一种实现更难，并且在实践中可能会使用更多内存（因为存储端点），但似乎理论上最坏情况的时间得到了改善。

我想知道是否有人知道在实践中通常会做什么？

谢谢

编辑：我想后一种实现的一个问题会随着删除而出现。如果您稍后插入“心灵感应”，但随后删除了“测试真的很难......”，则“te”边缘将保留，并且仍然对字符串的引用比需要的要长得多。

我正在考虑使用霍夫曼代码来压缩文本，但使用可变长度的符号（字符串）。例如（使用下划线作为空格）：

如何构建频率表？显然存在一些重叠的问题，序列_TH会出现的频率接近THE，但在表中是无用的（两者_都有THE短的霍夫曼代码）。

这样的算法存在吗？它有一个特殊的名字吗？生成频率表的技巧是什么？我需要标记输入吗？我没有在文学/网络中找到任何东西。（这一切都让我想起了基数树）。

我正在考虑使用迭代过程：

1. 为长度为 1 到 N 的所有符号生成霍夫曼树
2. 从树中删除所有 N>1 且低于某个计数阈值的符号
3. 重新生成第二个霍夫曼树，但这次用前一个对输入进行标记（可能使用基数树进行查找）
4. 重复 1 直到我们收敛（或几次）

但我不知道如何防止重叠（_THvs THE）的问题。

为了让事情变得更简单但也更复杂，我尝试实现“组合/简洁标签”的概念，该概念进一步扩展到多种基本标签形式。

在这种情况下，标签由（一个或多个）“子标签”组成，用分号分隔：

斜线表示“子标签”可互换性。因此，解释器将它们翻译成这样：

使用的代码（不完美，但有效）：

问题：我怎样才能恢复这个过程？出于可读性的原因，我需要这个。

我想在 linux 页面缓存中添加我的变量。页面缓存由基数树管理。

我想在基数树节点中添加我的变量“X”。但是，当填充 radix_tree_root 的“X”时它不起作用。

有一个名为根的基数树根。// struct radix_tree_root* root; root 有 rnode，它是 radix_tree_node 的指针。

它失败了，我不知道为什么它不起作用。

Inspired by iOS7 iMessage's next-word-prediction, I've decided to try to write a script that will learn, based on user input, which words / letters are most likely wanted to complete the user's current word or which word might most likely be desired next.

To do this, I'm going to use a data structure very similar to a Radix Tree (AKA a Patricia Trie).

Take this user input for example:

I like icecream

From that, my goal is to generate the following data structure:

This is essentially a Radix Tree, with some extra information, allowing me to weigh the probability of the learned possibilities that the user might want to type next.

From the above extremely limited data set, when the user types an "I", our best (and only) guess is that the next character will be a " ".

So now that I've explained my goal and method, here's my question:

How can I build this data structure from any given user input?

This is as far as I've gotten, but I'm not sure how to insert the next values at the proper positions recursively.

我需要获取打开文件的页面缓存统计信息。文件结构中有一个地址空间指针（f_mapping），它又具有名为page_tree的基数树的根。我需要遍历该树以获取有关该打开文件的所有缓存页面的信息。

有一些函数，如radix_tree_for_each_chunk（迭代块）、radix_tree_for_each_chunk_slot（迭代一个块中的槽）等，使用这些功能可以实现。我不确定是否正确使用（参数）。如果发布任何示例将会很有帮助。

我的结构定义遇到了很大的麻烦。我尝试了几种不同的方法来定义它们，但似乎无法摆脱错误。

我的代码可能还有很多其他问题，但如果不通过运行我认为的代码找到它们，我实际上无法解决这些问题。这就是为什么我需要先解决这个问题。

这是完整的代码：

这是我得到的错误：

我的基数树实现有问题。这个想法是我创建第一个节点，然后输入一些二进制数。二进制数确定是创建左节点 (0) 还是创建右节点 (1)。一旦我到达二进制数的末尾，我将一个节点设置为“活动”。

然后我在树中搜索找到一个活动节点，并通过检查我必须朝哪个方向到达活动节点来再次输出原始二进制数。

这是完整的代码：

这是输出：

（和无限继续）

显然我在insert()函数的递归中有一个问题，但考虑到我在执行递归时删除了二进制数字符串的第一个字符，我不明白它是如何无限运行的。