1

私はUdacityコースを受講していますが、講義の1つ（https://www.youtube.com/watch?v=gPQ-g8xkIAQ&feature=player_embedded）で、教授はhigh_common_bits（講義から逐語的に）次のような機能を提供します。これを擬似コードで：

function high_common_bits(a,b):
   return:
     - high order bits that a+b in common
     - highest differing bit set
     - all remaining bits clear

例として：

a = 10101
b = 10011
high_common_bits(a,b) => 10100

次に彼は、この関数は高度に最適化された試行の実装で使用されると述べています。誰かが彼が参照している正確な実装を知っていますか？

4

3 に答える 3

5

高度に最適化されたビットごとに圧縮されたトライ (別名基数ツリー) を探している場合。BSD ルーティング テーブルは、その実装で 1 つを使用します。ただし、コードは読みにくいです。

于 2013-02-17T23:56:00.570 に答える
1

彼は簡潔な試行について話していました。これは、各ノードが格納するのに 2 ビットしか必要としない(理論上の最小値)試行です。

Steve Hanov は、Succinct Tries に関する非常に親しみやすいブログ記事をここに書いています。それらを紹介した Guy Jacobson による元の論文(最近では 1989 年に書かれたもの)もここで読むことができます。

于 2015-07-10T22:27:41.320 に答える
0

圧縮されたトライは、1 つのノードにプレフィックスを格納し、そのノードから、そのプレフィックスで始まる、見られた可能性のある各アイテムに分岐します。

この場合、彼は明らかにビット単位のトライを行っているため、ビットのプレフィックスを格納しています。つまり、アイテムが共通に持っている先頭のビットが 1 つのノードに入り、そのノードから 2 つの分岐があり、1 つは次のビットのノードは 0 で、次のビットのノードは 1 です。おそらく、これらのノードも同様に圧縮されるため、次の 1 ビットを格納するだけでなく、次のビット数を格納します。これまでにトライに挿入されたアイテムはすべて一致しました。

実際、特定のノードに続く次のビットは、後続のノードにまったく格納されない場合があります。そのビットは、たどるリンクに暗黙的に含まれている可能性があるため、次のノードはその後のビットのみを保存します。

于 2013-02-17T23:31:42.553 に答える