标签: radix-tree

是特里和基数特里数据结构是一回事吗？

如果它们相同,那么radix trie(AKA Patricia trie)的含义是什么？

我试图在Java中实现一个非常简单的Trie,支持3个操作.我希望它有一个insert方法,一个has方法(即trie中的某个单词),以及一个以字符串形式返回trie的toString方法.我相信我的插入工作正常,但是并且toString被证明是困难的.这是我到目前为止所拥有的.

特里班.

public class CaseInsensitiveTrie implements SimpleTrie {

    //root node
    private TrieNode r;

    public CaseInsensitiveTrie() {
        r = new TrieNode();
    }

    public boolean has(String word) throws InvalidArgumentUosException {
        return r.has(word);
    }

    public void insert(String word) throws InvalidArgumentUosException {
        r.insert(word);
    }

    public String toString() {
        return r.toString();
    }

    public static void main(String[] args) {

        CaseInsensitiveTrie t = new CaseInsensitiveTrie();

        System.out.println("Testing some strings");
        t.insert("TEST");
        t.insert("TATTER");
        System.out.println(t.has("TEST"));
    }
}

和节点类

public class TrieNode {

    //make child nodes
    private TrieNode[] c;
    //flag for end …

我需要获取打开文件的页面缓存统计信息.文件结构中有一个address_space指针(f_mapping),它又具有名为page_tree的基数树的根.我需要遍历该树以获取有关该打开文件的所有缓存页面的信息.

有一些函数,如radix_tree_for_each_chunk(迭代块),radix_tree_for_each_chunk_slot(迭代一个块中的插槽)等,使用这些功能可以实现.我不确定它的正确用法(参数).如果发布任何示例,将会很有帮助.

虽然很难找到"基数树"的一致定义,但大多数公认的基数树定义表明它是一个压缩的前缀树.我正在努力理解的是在这种情况下术语"基数"的重要性.为什么压缩的前缀树如此命名(即Radix Tree),而非压缩的前缀树不称为Radix Tree？

我对使用基数树（或Patricia trie）存储的哈希/字典/数组感兴趣strings -> values。但是，我发现我有太多的字符串无法容纳到内存中。

我发现Algolia撰写了一篇文章，介绍了他们如何通过搜索索引解决此问题，他们谈论了我正在尝试做的事情：在构建每个分支时将基数树刷新到磁盘上，并且仅读回所需的分支。

但是，他们没有提及他们如何做到这一点。我想到存储基数树的唯一方法是作为完整的（序列化的）对象或作为简单的键/值存储的哈希/数组。

例如，使用键/值存储

SET smile:  [...values...]
SET smiled: [...values...]
SET smiles:  [...values...]
SET smiling: [...values...]

然后进行前缀扫描以提取出的键/值MATCH smil*。但是，这种损失失去了基数树的节省空间的好处，另外，它还需要在负载下重建至少一部分基数树。

我一直关注基数树的空间使用,但我没有找到任何有用的讨论.

现在假设我们有一个与linux radix-tree.c相同的基数树实现,它接受一个整数并使用每6位来索引树中的下一个位置.我可以很容易地想到基数树的空间使用远远超过二叉搜索树的情况.如果我错了,请纠正我:

使用案例:(0,1,1,1,1),(1,1,1,1,1),(2,1,1,1,1),......(63,1,1,1) ,1).

这里只是为了方便起见,我使用(a,b,c,d,e)来表示一个30位整数键,每个元素代表一个6位值.a是MSB,e是LSB.

基数树:

对于这个用例,基数树的高度为5,每个密钥将占用4个独立的节点,因为它们位于根的不同子树上.所以会有((5-1)*64 + 1)= 257个节点.

每个节点包含2 ^ 6 = 64个指针,因此它将使用257*64*4Byte = 65KB

二叉搜索树

我们只关心有多少钥匙.在这种情况下,它有64个键.

假设每个BST节点每个节点使用3个指针,它将使用64*3*4Byte = 768字节.

对照

看起来基数树空间效率很低.在给定相同数量的节点的情况下,它比二叉搜索树使用~100倍的空间!我不明白为什么它甚至在linux内核中使用.

我错过了什么吗？谢谢.

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

huffman-code | symbol
------------------------------------
00           | _
01           | E
100          | THE
101          | A
1100         | UP
1101         | DOWN
11100        | .
11101        |
1111...
(etc...)

如何构建频率表？显然存在一些重叠问题，序列_TH出现的频率几乎与 一样THE，但在表中毫无用处（_和THE都有短霍夫曼代码）。

这样的算法存在吗？它有一个特殊的名字吗？生成频率表有哪些技巧？我需要对输入进行标记吗？我在文献/网络中没有找到任何内容。（所有这些让我也想到了基数树）。

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

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

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

我正在尝试决定使用哪种数据结构.

假设我有1000万个键,其中包含指向包含某些数据的唯一对象的指针.

密钥是UUID将它们视为16字节二进制数组.UUID是使用高质量的随机数生成器生成的.

我一直在考虑以下内容,但想知道速度和内存消耗方面的优缺点是什么.一些公平的估计,64位平台上的最佳/最差/平均情况会很好.

我需要能够插入几乎无限的项目.

二叉树哈希表基数树(基于位或2位多路)

我需要的操作是:插入,删除,搜索

我喜欢基数树的想法,但它被证明是最难实现的,我没有找到一个合适的实现,我可以将其纳入商业产品.

我正在用 C++ 编写一个程序，该程序需要以快速方式查找和存储 IP 地址（所有 IPv4）。每个 IP 地址都有与之关联的数据。如果它已经存在于树中，我打算将树中的 IP 地址数据与新地址数据合并。如果它不存在，我打算将它作为新条目添加到树中。不需要删除 IP 地址。

为了实现这一点，我需要设计一个 Patricia Trie。但是，我无法想象除此之外的设计。我似乎很天真，但我想到的唯一想法是将 IP 地址更改为二进制形式，然后使用特里树。然而，我对如何实现这一点一无所知。

如果你能帮助我解决这个问题，我将非常感谢你。请注意，我确实在这里找到了类似的问题。问题或更具体的答案超出了我的理解，因为 CPAN 网站中的代码对我来说不够清楚。

另请注意，我的数据格式如下

10.10.100.1：“汤姆”、“杰克”、“史密斯”

192.168.12.12：“琼斯”、“丽兹”

12.124.2.1：“吉米”、“乔治”

10.10.100.1：“迈克”、“哈利”、“詹妮弗”