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

Question

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

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

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

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

10.10.100.1: "Tom","Jack","Smith"

192.168.12.12: "Jones","Liz"

12.124.2.1: "Jimmy","George"

10.10.100.1: "Mike","Harry","Jennifer"

Answer 1

我认为您指的是 RadixTree .我有一个 RadixTrie 的实现在 Java 中，如果您想将其用作起点，它会进行实际的键值映射。它使用 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