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

Question

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

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

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

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

10.10.100.1:"；Tom"Jack"Smith"；

192.168.12.12："；Jones"Liz"；

12.124.2.1："；Jimmy"乔治；

10.10.100.1："；Mike"Harry"詹妮弗">

Answer 1

我认为您指的是RadixTree。我有一个Java中RadixTrie的实现，如果你想把它作为一个起点，它可以进行实际的键到值映射。它使用PatriciaTrie作为其背衬结构。

使用以下字符串的示例。

1. 10.10.101.2
2. 10.10.100.1
3. 10.10.110.3

尝试示例(未压缩)

└── 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

Answer 2

Patricia试图解决为给定IP地址找到最佳覆盖前缀的问题(例如，路由器使用这些前缀来快速确定192.168.0.0/16是192.168.14.63的最佳选择)。如果你只是想精确匹配IP地址，哈希表是一个更好的选择。