2

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

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

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

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

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

192.168.12.12：“琼斯”、“莉兹”

12.124.2.1：“吉米”，“乔治”

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

4

2 回答 2

5

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

帕特里夏特里（压缩）

└── [black] 10.10.1
    ├── [black] 0
    │   ├── [white] (0.1) 00.1
    │   └── [white] (1.2) 01.2
    └── [white] (10.3) 10.10.110.3
于 2012-10-03T15:10:56.823 回答
1

Patricia 尝试解决为给定 IP 地址寻找最佳覆盖前缀的问题（例如，路由器使用它们来快速确定 192.168.0.0/16 是 192.168.14.63 的最佳选择）。如果您只是想精确匹配 IP 地址，哈希表是更好的选择。

于 2012-10-03T14:06:01.490 回答