2

IPアドレス（すべてIPv4）をすばやく検索して保存する必要があるC ++でプログラムを書いています。すべての IP アドレスには、関連付けられたデータがあります。トライに既に存在する場合は、トライの IP アドレスのデータを新しいアドレス データとマージするつもりです。存在しない場合は、新しいエントリとしてトライに追加するつもりです。IPアドレスの削除は不要です。

これを実装するには、パトリシア トライを設計する必要があります。しかし、これ以上のデザインを視覚化することはできません。私には非常に素朴に思えますが、頭に浮かんだ唯一のアイデアは、IP アドレスをバイナリ形式に変更してからトライを使用することでした。ただし、これを正確に実装する方法についてはわかりません。

この件でお役に立てましたら、本当にありがとうございます。ここで同様の質問を見つけたことに注意してください。CPAN Web サイトのコードが私にとって十分に明確ではなかったため、質問またはより具体的には回答は私の理解を超えていました。

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

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

トライ例（非圧縮）

└── 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 に答える