アルゴリズムを最長の接頭辞を検索パトリシア-Trie

StackOverflow https://stackoverflow.com/questions/911947

  •  06-09-2019
  •  | 
  •  

質問

私の実施圧縮のためのIP接頭辞のルックアップの方々かに コード作業のための完全なキーが面した問題に前方一致検索の場合 鍵である接頭辞のキーのように:

1.2.3.0
1.2.0.0

誰でもできるので助けてくれるアルゴリズムのための接頭辞を検索では、上記の場合 るべきと考えるこれらのキーとしての長いてe/24 16)?

役に立ちましたか？

解決

しくは当期純-タカヤマさん。この実装は、パトリシア-trieを見上げの全てのIPアドレスを使います。ユーザーインターフェイスはperl、基になるコードはC.こちらのリンクですが、多くのCPANアーカイブしてい:

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

他のヒント

あなたは、固定長の要素としてIP番号を格納するために、このトライを使用する場合は、

それは間違いなく正しい方法ではありません。ここでのポイントは、PTは、可変長データを格納するために特に有用であることです。

あなたがIP番号の一部を保存する場合、可変長の接頭辞として、その後PTは良い選択です。
この場合はそうあなたの鍵は、異なる長さであるべきです。
あなたが最初のキーとしてこれを追加し、あなたがバイナリ0xC0の0xA8に接頭辞「192.168」を記憶しているとしましょう。
192.168.1.1のようなIPを検索する際に続いて、あなたはあなたのトライは、あなたが探して何の接頭辞である192.168が含まれている情報を得ることができます。

あなたがしなければならないのは、トライを横断しながら、「共通部分」を格納することです。
これは、このを実装noreferrer"> ロバート・セッジウィックのアルゴリズム帳を読んでお勧めします知識の源ます。

編集：PTでのCの文字列を格納する際に一つの問題があります。このトライは、バイナリデータを格納するために設計されていますが、あなただけの全体のバイト数を得ることに興味を持っているされています。 あなたはビットでその大きさは8の倍数である場合にのみプレフィックスの共通部分を格納していることを確認します。 間違った例：あなたは、あなたのツリーにキーを持っている：0xC0の0xA5のあなたは0xC0のは0xA6あちこち探しています。 共通部分「0xC0の0xAが」、しかし、あなたは唯一の「0xC0の」を取ってに興味があるとき、あなたのトラバーサルが停止します。だから、普通のバイトではなく、ビットを格納することを確認します。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top