IPv4アドレスと衛星データの高速検索のためのPatricia Trie

Question

IPアドレス（すべてのIPv4）を必要とするC ++でプログラムを作成しています。すべてのIPアドレスには、データが関連付けられています。トライにすでに存在している場合は、新しいアドレスデータとともに、IPアドレスのデータをTRIE内のデータをマージするつもりです。存在しない場合は、Trieへの新しいエントリとして追加するつもりです。 IPアドレスの削除は不要です。

これを実装するためには、Patricia Trieを設計する必要があります。しかし、私はこれを超えてデザインを視覚化することができません。それは私にとってとても素朴そうですが、私の心にやって来た唯一の考えはIPアドレスを彼らのバイナリ形式に変更してからTRIEを使うことでした。しかし、私は を正確に実装しています。

あなたがこれを使って私を助けることができれば私はあなたに本当に感謝します。 私は似たような質問を見つけました。 a>。 CPAN Webサイトのコードが私にとって十分に明確ではなかったので、質問またはより具体的な答えは私の理解を超えていました。

また、私のデータは次の形式

です。

10.10.100.1： "Tom"、 "Jack"、 "Smith"

192.168.12.12： "Jones"、 "Liz"

12.124.2.1：「ジミー」、「ジョージ」

10.10.100.1：「マイク」、「ハリー」、「ジェニファー」

Answer 1

Patriciaは、特定のIPアドレスについて最良のカバープレフィックスを見つけるという問題を解決します（たとえば、192.168.0.0/16は、例えば192.168.14.63の最良の選択であることを迅速に決定するためにルータによって使用されます）。IPアドレスを正確に一致させようとしている場合は、ハッシュテーブルがより良い選択肢です。

Answer 2

あなたは Radixtrie Javaでは、それを開始点として使用する場合は、実際のキーを値にします。それは 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

.