7

私はパトリシアがIPプレフィックスルックアップを試みて実装しています。完全なキー一致のためにコードを機能させることができましたが、次のような他のキーのプレフィックスであるキーがある場合、プレフィックス検索で問題に直面しています。

1.2.3.0
1.2.0.0

上記の場合のプレフィックス検索のアルゴリズムを誰かが手伝ってくれますか？これらを別々の長さ（つまり、/ 24と16）のキーと見なす必要がありますか？

4

3 に答える 3

5

Net-Patriciaをご覧ください。これは、IPアドレスを検索するためのPatriciaトライの実装です。インターフェイスはperlですが、基礎となるコードはCです。ここにリンクがありますが、多くのCPANアーカイブには次のリンクが必要です。

http://cpansearch.perl.org/src/PHILIPP/Net-Patricia-1.15_07/libpatricia/​​patricia.c

于 2009-12-18T08:51:53.180 に答える
3

このトライを固定長の要素としてIP番号を格納するために使用する場合、それは間違いなく正しい方法ではありません。ここでのポイントは、PTは可変長データの格納に特に役立つということです。

IP番号の一部を可変長のプレフィックスとして格納する場合は、PTが適しています。
この場合、はい、キーの長さを変える必要があります。
プレフィックス「192.168」をバイナリ0xC00xA8に格納しているとすると、これを最初のキーとして追加します。
次に、192.168.1.1のようなIPを検索すると、検索対象のプレフィックスである192.168がトライに含まれているという情報を取得できます。

あなたがしなければならないのは、トライを横断しながら「共通部分」を保存することです。 これはこれ
へのマイナーな追加です実装。トライを下るときに、再帰関数のパラメーターのどこかに共通部分を格納することを確認してください。
Patricia trieをよく理解するには、優れた知識源であるRobertSedgewickのAlgorithms本を読むことをお勧めします。

編集：PTにC文字列を格納するときに1つの問題があります。このトライはバイナリデータを格納するように設計されていますが、関心があるのはバイト全体を取得することだけです。ビット単位のサイズが8の倍数である場合にのみ、プレフィックスの共通部分を格納していることを確認してください。間違った例：ツリーにキーがあります：0xC0 0xA5で、0xC00xA6を探しています。共通部分が「0xC00xA」になるとトラバーサルは停止しますが、「0xC0」のみを取得することに関心があります。したがって、ビットではなく、共通のバイトを格納するようにしてください。

于 2009-11-04T21:27:55.580 に答える
0

LLVMのテストコードにはかなり読みやすいC実装があります：https ：//llvm.org/svn/llvm-project/test-suite/trunk/MultiSource/Benchmarks/MiBench/network-patricia/

于 2014-11-23T20:07:27.677 に答える