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

Question

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

为了实现这一点，我需要设计Patricia Trie。但是，我无法以超越这个设计。我似乎很天真，但唯一来到我脑海的想法是将IP地址改为他们的二进制形式，然后使用Trie。然而，我对如何为如何实现这一目标。

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

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

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

192.168.12.12：“琼斯”，“liz”

12.124.2.1：“吉米”，“乔治”

10.10.100.1：“Mike”，“Harry”，“Jennifer”

Answer 1

Patricia尝试解决给定IP地址找到最佳覆盖前缀的问题（路由器用于快速确定192.168.0.0/16是192.168.14.63的最佳选择）。如果您只是尝试匹配IP地址，则哈希表是一个更好的选择。

Answer 2

我认为你指的是a 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

.