用于快速检索 IPv4 地址和卫星数据的 Patricia Trie

Question

我正在用 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：“迈克”、“哈利”、“詹妮弗”

Answer 1

我认为您指的是RadixTree。我在 Java中有一个RadixTrie的实现，如果你想使用它作为起点，它执行实际的键值映射。它使用PatriciaTrie作为它的支持结构。

使用以下字符串的示例。

1. 10.10.101.2
2. 10.10.100.1
3. 10.10.110.3

Trie 示例（未压缩）

??? 1
    ??? 0
        ??? .
            ??? 1
                ??? 0
                    ??? .
                        ??? 1
                            ??? 0
                            ?   ??? 1
                            ?   ?   ??? .
                            ?   ?       ??? (2) 10.10.101.2
                            ?   ??? 0
                            ?       ??? .
                            ?           ??? (1) 10.10.100.1
                            ??? 1
                                ??? 0
                                    ??? .
                                        ??? (3) 10.10.110.3

帕特里夏·特里（Patricia Trie）（压缩）

??? [black] 10.10.1
    ??? [black] 0
    ?   ??? [white] (0.1) 00.1
    ?   ??? [white] (1.2) 01.2
    ??? [white] (10.3) 10.10.110.3