ビットマップ付きビット単位トライ

コンテンツへジャンプ

メインメニュー

メインメニュー

サイドバーへ移動非表示

ナビゲーション

• メインページ
• 目次
• 最新ニュース
• ランダム記事
• Wikipediaについて
• お問い合わせ

寄稿する

• ヘルプ
• 編集方法を学ぶ
• コミュニティポータル
• 最近の変更
• ファイルをアップロード
• 特別ページ

検索

検索

外観

• 寄付する
• アカウントを作成
• ログイン

個人用ツール

• 寄付する
• アカウントを作成
• ログイン

目次

サイドバーへ移動非表示

• （上）
• 1トライとビット単位のトライ
• 2ビットマップを使ったビット単位のトライ
  ビットマップサブセクションを含むビット単位トライの切り替え
  • 2.1ノードトラバーサル
• 3セット実装例
  トグルセットの実装例のサブセクション
  • 3.1物理データ構造
  • 3.2集合演算
    • 3.2.1キーを含む
    • 3.2.2キーの設定（追加）
    • 3.2.3クリア（削除）キー
  • 3.3集合演算子
    • 3.3.1フライウェイトインターフェース
    • 3.3.2交差（AND）
    • 3.3.3結合（OR）
    • 3.3.4差（マイナス）
    • 3.3.5範囲
  • 3.4使用例
• 4参考文献

目次を切り替える

言語を追加

リンクを追加

• 記事
• トーク

英語

• 読む
• 編集する
• 履歴を見る

ツール

ツール

サイドバーへ移動非表示

アクション

• 読む
• 編集する
• 履歴を見る

一般

• ここからリンクされているもの
• 関連する変更
• ファイルをアップロード
• パーマリンク
• ページ情報
• このページを引用
• 短縮URLを取得
• QRコードをダウンロード

印刷/エクスポート

• PDFとしてダウンロード
• 印刷可能なバージョン

他のプロジェクトで

• ウィキデータ項目

外観

サイドバーへ移動非表示

フリー百科事典『ウィキペディア（Wikipedia）』より

ビット単位トライは、各ノードとその子枝がキーの1つ以上のビットのビット列を表す特殊な形式のトライです。ビットマップ付きビット単位トライは、ビットマップを使用して有効な子枝を示します

試行とビット単位の試行

[編集]

トライ木は、例えばB木とは異なり、キーがノードではなく葉へのパスに格納される探索木の一種です。キーは木構造全体に分散されています。「典型的な」トライ木では、各ノードとその子枝は、キーの1つの位置（文字）に対応するアルファベットの1つの記号を表します。

ビット単位の試行では、キーは何らかのバイナリ表現のビット シーケンスとして扱われ、子ブランチを持つ各ノードは、このビット シーケンスのサブシーケンスの値を表し、バイナリ ツリー (サブシーケンスには 1 ビットのみが含まれる) または n 進ツリー (サブシーケンスには複数のビットが含まれる) を形成します。

「クラシック」トライとビット単位のトライの違いを説明する例を挙げます。キーとして数値を使用する場合、トライのアルファベットは 10 進法の数値の桁を表す記号 '0' ～ '9' で構成され、ノードには最大 10 個の子ノードが存在する可能性があります。

キーが「07」と「42」のトライ木。「0」や「07」といったノードラベルは読みやすさのために追加されたものであり、実際にはノードに格納されていないことに注意してください。

トライを物理データ構造として実装するには、複数の直接的なアプローチがあります。そのうちの2つを挙げると、

• ノードは、アルファベットの各記号に対応する子ポインタの配列（10進数の例では、ノードあたり10個のポインタの配列）で表現できます。これにより、キーの長さに応じた検索時間が得られます。しかし、各ノードは、そのパスを実現するキーがない場合でも、すべての可能な子シンボルのためのスペースを確保するため、これは空間効率が良くありません。 ${\displaystyle \Sigma }$ ${\displaystyle O(|M|)}$ ${\displaystyle |M|}$
• ノードには、シンボル順に並べられた（シンボル、子ポインタ）タプルの二分木が含まれます。これにより空間効率は向上しますが、検索時間は になります。理想的なトライでは、アクセス時間は格納されているキーの数に依存しません。 ${\displaystyle O(|M|\cdot \log |\Sigma |)}$

これらのアプローチは、例えばキーがUnicode文字列である場合など、アルファベットが大きい場合にはさらに悪化します。キーをビット列として扱うことで、ノードごとに固定のカーディナリティを持つことができます。

ビットマップ付きビット単位トライ

[編集]

Bagwell ^{[ 1 ]}は、Array Mapped Tree (AMT)という時間と空間を効率的に利用したトライのソリューションを発表しました。HAMT ( Hash array mapped trie )はAMTに基づいています。コンパクトなトライノード表現では、ビットマップを使用してすべての有効なブランチをマークします。つまり、ビットマップを使用したビット単位のトライです。AMTは、ノードごとに8つの32ビットのビットマップを使用して、ノードごとに8ビットのシーケンスを表現できる256進トライを表します。64ビットCPU ( 64ビットコンピューティング)では、バリエーションとして、ノードごとに1つの64ビットのビットマップのみを使用して6ビットのシーケンスを表現できる64進トライがあります。

有効な子ブランチをマークするビットマップを持つトライノード。

与えられた6ビット値に対応するノードの子ポインタのインデックスを決定するには、先行する子ポインタの数を計算する必要があります。これは非常に効率的に実装できることがわかります。

ノードトラバーサル

[編集]

long bitMap = mem [ nodeIdx ] ; long bitPos = 1L << value ; // 6ビット値if (( bitMap & bitPos ) == 0 ) return false ; // 見つかりませんlong childNodeIdx = mem [ nodeIdx + 1 + Long . bitCount ( bitMap & ( bitPos - 1 )) ] ;                           

現在のノードインデックスに基づいてインデックスを見つけるためのオフセットは、ビットマップ内でターゲット位置の前に設定されている最下位ビットの数にビットマップのビット数を1加えた値です。設定されている最下位ビットの数は、単純なビット演算と、設定されているビット数を決定するCTPOP（カウントポピュレーション）演算（JavaではLong.bitCount()として利用可能）を使用することで、定数時間計算量で効率的に計算できます。CTPOP自体は「ビットハック」 ^{[ 2 ]}を使用して非常に効率的に実装でき、多くの最新のCPUでは、CTPOPをコンパイラによって組み込み関数として扱われる専用命令として提供しています。

int CTPOP ( long x ) { // 人口カウント関数の「ビットハック」実装。x -= (( x >>> 1 ) & 0x5555555555555555L ); x = ( x & 0x3333333333333333L ) + (( x >>> 2 ) & 0x3333333333333333L ); x = ( x + ( x >>> 4 )) & 0x0f0f0f0f0f0f0f0fL ; x += ( x >>> 8 ); x += ( x >>> 16 ); x += ( x >>> 32 ); return x & 0x7f ; }                                          

セット実装例

[編集]

物理データ構造

[編集]

このビットマップを用いたビット単位トライの実装例では、ノードはlong（64ビット）整数の配列に配置されます。ノードは配列内の位置（インデックス）によって識別されます。ルートノードのインデックスは、トライのルートを表します。

ノードは配列内の未使用領域から割り当てられ、必要に応じて配列を拡張します。さらに、置換されたノードはフリーリストに集められ、その領域は再利用されます。この再利用を行わない場合、このデータ構造は、以前のルートインデックスのみを保持し、既存のノードを上書きすることなく、変更されたノードのコピーを常に作成することで、永続的なデータ構造を実装できます。

リーフ ノードはインライン化されます。つまり、リーフ ノードへの子ポインターを持つ代わりに、リーフ ノード自体のビットマップが格納されます。

パブリッククラスBBTrieSet {    long [] mem ; long [] freeLists ; long freeIdx ;      長いルート;長いカウント;    // 配列はゼロベースなので、最大ノード サイズは 1 (ビットマップ) + 64 (子ポインターまたはリーフ値) + 1 です。final static int FREE_LIST_SIZE = 1 + 64 + 1 ;       最終的な静的int KNOWN_EMPTY_NODE = 0 ;最終的な静的int KNOWN_DELETED_NODE = 1 ;最終的な静的int HEADER_SIZE = 2 ; // KNOWN_EMPTY_NODE、KNOWN_DELETED_NODE                   public BBTrieSet ( int size ) { mem = new long [ size ] ; freeLists = new long [ FREE_LIST_SIZE ] ; freeIdx = HEADER_SIZE ; root = KNOWN_EMPTY_NODE ; count = 0 ; }                      private long allocate ( int size ) { long free = freeLists [ size ] ; if ( free != 0 ) { // 要求されたサイズはフリーリストで使用可能です。再リンクしてヘッドを返します。freeLists [ size ] = mem [ ( int ) free ] ; return free ; } else { // 拡張が必要か? if ( freeIdx + size > mem . length ) { // 25% 増やして、十分であることを確認します。int currSize = mem . length ; int newSize = currSize + Math . max ( currSize / 4 , size ); mem = Arrays . copyOf ( mem , newSize ); }                                                   long idx = freeIdx ; freeIdx += size ; return idx ; } }           プライベートlong allocateInsert ( long nodeIdx 、int size 、int childIdx ) { long newNodeRef = allocate ( size + 1 );               int a = ( int ) newNodeRef ; int b = ( int ) nodeIdx ;          // 子のギャップ付きコピーfor ( int j = 0 ; j < childIdx ; j ++ ) mem [ a ++] = mem [ b ++] ; a ++ ; // 挿入済みfor ( int j = childIdx ; j < size ; j ++ ) mem [ a ++] = mem [ b ++] ;                           deallocate ( nodeIdx , size );  newNodeRefを返します。} private long allocateDelete ( long nodeIdx , int size , int childIdx ) { long newNodeRef = allocate ( size - 1 );                   // 子要素を削除してコピーしますint a = ( int ) newNodeRef ; int b = ( int ) nodeIdx ; for ( int j = 0 ; j < childIdx ; j ++ ) mem [ a ++] = mem [ b ++] ; b ++ ; // 削除しましたfor ( int j = childIdx + 1 ; j < size ; j ++ ) mem [ a ++] = mem [ b ++] ; deallocate ( nodeIdx , size );                                          newNodeRefを返します。   private void deallocate ( long idx , int size ) { if ( idx == KNOWN_EMPTY_NODE ) return ; // 既知の空ノードを保持する             // フリーリストの先頭に追加mem [ ( int ) idx ] = freeLists [ size ] ; freeLists [ size ] = idx ; }         private long createLeaf ( byte [] key , int off , int len ) { long newNodeRef = allocate ( 2 ); int a = ( int ) newNodeRef ; mem [ a ++] = 1L << key [ len - 2 ] ; mem [ a ] = 1L << key [ len - 1 ] ; // value len -= 3 ; while ( len >= off ) { long newParentNodeRef = allocate ( 2 ); a = ( int ) newParentNodeRef ; mem [ a ++] = 1L << key [ len --] ; mem [ a ] = newNodeRef ; newNodeRef = newParentNodeRef ; } return newNodeRef ; }                                                                private long insertChild ( long nodeRef , long bitMap , long bitPos , int idx , long value ) { int size = Long . bitCount ( bitMap ); long newNodeRef = allocateInsert ( nodeRef , size + 1 , idx + 1 ); mem [ ( int ) newNodeRef ] = bitMap | bitPos ; mem [ ( int ) newNodeRef + 1 + idx ] = value ; return newNodeRef ; } private long removeChild ( long nodeRef , long bitMap , long bitPos , int idx ) { int size = Long . bitCount ( bitMap ); if ( size > 1 ) { // ノードにはまだ他の子ノードや葉ノードがありますlong newNodeRef = allocateDelete ( nodeRef , size + 1 , idx + 1 ); mem [ ( int ) newNodeRef ] = bitMap & ~ bitPos ; return newNodeRef ; } else { // ノードは空になったので削除しますdeallocate ( nodeRef , size + 1 ); return KNOWN_DELETED_NODE ; } }                                                                                                パブリックlong size () {戻り値 count ; }      }

集合演算

[編集]

キーを含む

[編集]

getメソッドは、キーが集合の一部であるかどうかをテストします。キーはbyte[]として渡され、各バイトはキーの6ビットのビットシーケンスを表します。したがって、1バイトあたり8ビットのうち6ビットのみが使用されます

 public boolean get ( byte [] key , int len ) { if ( root == KNOWN_EMPTY_NODE ) return false ;             long nodeRef = root ; int off = 0 ; for (;;) { long bitMap = mem [ ( int ) nodeRef ] ; long bitPos = 1L << key [ off ++] ; // ++ に注意してください if (( bitMap & bitPos ) == 0 ) return false ; // 見つかりません                                  long値= mem [ ( int ) nodeRef + 1 + Long . bitCount ( bitMap & ( bitPos - 1 )) ] ;             if ( off == len - 1 ) { // リーフlong bitPosLeaf = 1L << key [ off ] ; return (( value & bitPosLeaf ) != 0 ); } else { // 子ポインターnodeRef = value ; } } }                             

キーを設定（追加）する

[編集]

 public boolean set ( byte [] key , int len ) { long nodeRef = set ( root , key , 0 , len ); if ( nodeRef != KNOWN_EMPTY_NODE ) { // 変更回数を表す++ ; root = nodeRef ; trueを返す; } else falseを返す; }                               private long set ( long nodeRef , byte [] key , int off , int len ) { long bitMap = mem [ ( int ) nodeRef ] ; long bitPos = 1L << key [ off ++] ; // ++ に注意してくださいint idx = Long . bitCount ( bitMap & ( bitPos - 1 ) );                                if (( bitMap & bitPos ) == 0 ) { // 子はまだ存在しませんlong value ; if ( off == len - 1 ) value = 1L << key [ off ] ; else value = createLeaf ( key , off , len ); return insertChild ( nodeRef , bitMap , bitPos , idx , value ); } else { // 子が存在しますlong value = mem [ ( int ) nodeRef + 1 + idx ] ; if ( off == len - 1 ) { // リーフにありますlong bitPosLeaf = 1L << key [ off ] ; if (( value & bitPosLeaf ) == 0 ) { // リーフのビットマップを更新しますmem [ ( int ) nodeRef + 1 + idx ] = value | bitPosLeaf ; return nodeRef ; } else // キーが既に存在しますreturn KNOWN_EMPTY_NODE ; } else { // リーフではない、再帰long childNodeRef = value ; long newChildNodeRef = set ( childNodeRef , key , off , len ); if ( newChildNodeRef == KNOWN_EMPTY_NODE ) return KNOWN_EMPTY_NODE ; if ( newChildNodeRef != childNodeRef ) mem [ ( int ) nodeRef + 1 + idx ] =                                                                                                                     newChildNodeRef ; nodeRefを返します; } } }      

キーをクリア（削除）する

[編集]

 public boolean clear ( byte [] key , int len ) { long nodeRef = clear ( root , key , 0 , len ); if ( nodeRef != KNOWN_EMPTY_NODE ) { count -- ; if ( nodeRef == KNOWN_DELETED_NODE ) root = KNOWN_EMPTY_NODE ; else root = nodeRef ; return true ; } else return false ; }                                      public long clear ( long nodeRef 、byte [] key 、int off 、int len ) { if ( root == KNOWN_EMPTY_NODE ) return KNOWN_EMPTY_NODE ;                 long bitMap = mem [ ( int ) nodeRef ] ; long bitPos = 1L << key [ off ++] ; // ++ に注意してくださいif (( bitMap & bitPos ) == 0 ) { // 子要素が存在せず、キーが見つかりませんreturn KNOWN_EMPTY_NODE ; } else { // 子要素が存在しますint idx = Long . bitCount ( bitMap & ( bitPos - 1 )); long value = mem [ ( int ) nodeRef + 1 + idx ] ; if ( off == len - 1 ) { // リーフにありますlong bitPosLeaf = 1L << key [ off ] ; if (( value & bitPosLeaf ) == 0 ) // キーが存在しませんreturn KNOWN_EMPTY_NODE ; else { // リーフのビットをクリアしますvalue = value & ~ bitPosLeaf ; if ( value != 0 ) { // リーフにはまだいくつかのビットが設定されているため、リーフを保持しますが、mem [ ( int ) nodeRef + 1 + idx ] = value ; return nodeRef ; } else return removeChild ( nodeRef , bitMap , bitPosLeaf , idx ); } } else { // リーフではありませんlong childNodeRef = value ; long newChildNodeRef = clear ( childNodeRef , key , off , len ); if ( newChildNodeRef ==                                                                                                                    KNOWN_EMPTY_NODE )を返しますKNOWN_EMPTY_NODE ; if ( newChildNodeRef == KNOWN_DELETED_NODE )を返しますremoveChild ( nodeRef 、bitMap 、bitPos 、idx ) ; if ( newChildNodeRef != childNodeRef ) mem [ ( int ) nodeRef + 1 + idx ] = newChildNodeRef ; return nodeRef ; } } }                             }

集合演算子

[編集]

積（and）、和（or）、差（minus）の集合演算子は、以下に示すフライウェイトパターンを使用して実行可能です

インターフェースは、演算子の物理ノードと「仮想」結果ノードを表します。このインターフェースのインスタンスは、トライの走査中に必要に応じて作成されます。複数の演算子を含む複合式は、これらの演算子を組み合わせることで直接表現できます。つまり、ある演算子を別の演算子の引数（入力）として使用することができます。

フライウェイトインターフェース

[編集]

パブリックインターフェースBBTrieNode { public long getBitMap (); public long getBitMapLeaf ( long bitPos ); public BBTrieNode getChildNode ( long bitPos ); }パブリック静的クラスBBTrieNodeMem はBBTrieNodeを実装します{                       long nodeRef ; long [] mem ;    BBTrieNodeMem子;  パブリックBBTrieNodeMem ( long nodeRef 、long [] mem ) { this . nodeRef = nodeRef ; this . mem = mem ; }             @Override public long getBitMap () { return mem [ ( int ) nodeRef ] ; }         @Override public long getBitMapLeaf ( long bitPos ) { int idx = Long . bitCount ( getBitMap () & ( bitPos - 1 )); long value = mem [ ( int ) nodeRef + 1 + idx ] ;戻り値; }                          @Override public BBTrieNode getChildNode ( long bitPos ) { int idx = Long . bitCount ( getBitMap () & ( bitPos - 1 )); long value = mem [ ( int ) nodeRef + 1 + idx ] ; return new BBTrieNodeMem ( value , mem ); } }                             

積集合（AND）

[編集]

積集合演算子は、部分式に対しても自動的に枝刈りを行うため、非常に効率的です。ビットマップとビット単位のAND演算によって結果を事前に決定できるため、無関係な子ノードにアクセスする必要はありません。例えば、を計算する場合、部分式は中間結果として具体化されません ${\displaystyle \{1,2,3\}\cap (\{2,3,4\}\cup \{5,6,7\})=\{2,3\}}$ ${\displaystyle \{2,3,4\}\cup \{5,6,7\}=\{2,3,4,5,6,7\}}$

 パブリック静的クラスBBTrieAnd はBBTrieNodeを実装します{ BBTrieNode nodeA ; BBTrieNode nodeB ; long bitMapA ; long bitMapB ;                public BBTrieAnd ( BBTrieNode nodeA , BBTrieNode nodeB ) { this . nodeA = nodeA ; this . nodeB = nodeB ; bitMapA = nodeA . getBitMap (); bitMapB = nodeB . getBitMap (); } public long getBitMap () { return bitMapA & bitMapB ; // これにより、適切な最適化 (プルーニング) が行われます} public long getBitMapLeaf ( long bitPos ) { return nodeA . getBitMapLeaf ( bitPos ) & nodeB . getBitMapLeaf ( bitPos ); } public BBTrieNode getChildNode ( long bitPos ) { BBTrieNode childNodeA = nodeA . getChildNode ( bitPos ); BBTrieNode childNodeB = nodeB . getChildNode ( bitPos ); return new BBTrieAnd ( childNodeA , childNodeB ); }                                                           }

和集合（OR）

[編集]

public static class BBTrieOr implements BBTrieNode { BBTrieNode nodeA ; BBTrieNode nodeB ; long bitMapA ; long bitMapB ;                public BBTrieOr ( BBTrieNode nodeA 、BBTrieNode nodeB ) { this . nodeA = nodeA ; this . nodeB = nodeB ; bitMapA = nodeA . getBitMap (); bitMapB = nodeB . getBitMap (); } public long getBitMap () { return bitMapA | bitMapB ; } public long getBitMapLeaf ( long bitPos ) { return nodeA . getBitMapLeaf ( bitPos ) | nodeB . getBitMapLeaf ( bitPos ); } public BBTrieNode getChildNode ( long bitPos ) { if (( bitMapA & bitPos ) != 0 ) { BBTrieNode childNodeA = nodeA . getChildNode ( bitPos ); if (( bitMapB & bitPos ) != 0 ) { BBTrieNode childNodeB = nodeB . getChildNode ( bitPos ); return new BBTrieOr ( childNodeA , childNodeB ); } else return childNodeA ; // 最適化。これ以上の or ノードは不要} else { BBTrieNode childNodeB = nodeB . getChildNode ( bitPos ); return childNodeB ; // 最適化。これ以上の or ノードは不要} }                                                                                        }

差（マイナス）

[編集]

public static class BBTrieMinus implements BBTrieNode { BBTrieNode nodeA ; BBTrieNode nodeB ; long bitMapA ; long bitMapB ; public BBTrieMinus ( BBTrieNode nodeA , BBTrieNode nodeB ) { this.nodeA = nodeA ; this.nodeB = nodeB ; bitMapA = nodeA.getBitMap ( ); bitMapB = nodeB.getBitMap ( ) ; } public long getBitMap ( ) { return bitMapA ; // bitMapBはここでは役に立ちません} public long getBitMapLeaf ( long bitPos ) { long childBitMapA = nodeA.getBitMapLeaf ( bitPos ) ; if ( ( bitMapB & bitPos ) == 0 ) return childBitMapA ; long childBitMapB = nodeB.getBitMapLeaf ( bitPos ) ; return childBitMapA & ~ childBitMapB ; } public BBTrieNode getChildNode ( long bitPos ) { BBTrieNode childNodeA = nodeA . getChildNode ( bitPos ); if (( bitMapB & bitPos ) == 0 ) return childNodeA ; // 最適化、マイナスノードは不要BBTrieNode childNodeB = nodeB . getChildNode ( bitPos ); return new BBTrieMinus ( childNodeA , childNodeB ); }                                                                                                     }

範囲

[編集]

仮想ノードアプローチを用いると、範囲を生成する仮想トライ（下記参照）を別の演算子と交差させることで範囲クエリを実現できます。つまり、例えば集合 のどの数値が特定の範囲（例えば [10..50]）に含まれるかを判断するには、集合全体を反復処理して各エントリをチェックする代わりに、 を評価することで実行します。 ${\displaystyle \{10,20,30,40,50,60,61,62,63\}}$ ${\displaystyle \{10,20,30,40,50,60,61,62,63\}\cap \{10,..,50\}}$

パブリックスタティッククラスBBTrieIntRange はBBTrieNode を実装します{ private long bitMap ; private int a , b ; private int x , y ; private int level ; public BBTrieIntRange ( int a , int b ) { this ( a , b , 5 ); }                                 private BBTrieIntRange ( int a , int b , int level ) { this . a = a ; this . b = b ; this . level = level ; x = ( int ) ( a >>> ( level * 6 )) & 0x3F ; y = ( int ) ( b >>> ( level * 6 )) & 0x3F ; // ビット ハック for: for (int i = x; i <= y; i++) bitSet |= (1L << i); bitMap = 1L << y ; bitMap |= bitMap - 1 ; bitMap &= ~ (( 1L << x ) - 1 ); }                                                          public long getBitMap () { return bitMap ; } public long getBitMapLeaf ( long bitPos ) { // 読みやすさのためのシンプルなソリューション (呼び出しごとに子ノードが再度作成されるため、それほど効率的ではありません) return getChildNode ( bitPos ). getBitMap (); }                 public BBTrieIntRange getChildNode ( long bitPos ) { int bitNum = Long . numberOfTrailingZeros ( bitPos ); if ( x == y ) return new BBTrieIntRange ( a , b , level - 1 ); else if ( bitNum == x ) return new BBTrieIntRange ( a , ~ 0x0 , level - 1 ); else if ( bitNum == y ) return new BBTrieIntRange ( 0 , b , level - 1 ); else return new BBTrieIntRange ( 0 , ~ 0x0 , level - 1 ); }                                                    }

使用例

[編集]

この例では、32ビット整数をキーとして使用した使用方法を示しています

パブリッククラスBBTrieSetSample {    public interface Visitor { public void visit ( byte [] key , int keyLen ); } public static void visit ( BBTrieNode node , Visitor visitor , byte [] key , int off , int len ) { long bitMap = node . getBitMap (); if ( bitMap == 0 ) return ; long bits = bitMap ; while ( bits != 0 ) { long bitPos = bits & - bits ; bits ^= bitPos ; // 右端のビットを取得してクリアしますint bitNum = Long . numberOfTrailingZeros ( bitPos ); key [ off ] = ( byte ) bitNum ; if ( off == len - 2 ) { long value = node . getBitMapLeaf ( bitPos ); long bits2 = value ; while ( bits2 != 0 ) { long bitPos2 = bits2 & - bits2 ; bits2 ^ = bitPos2 ; int bitNum2 = Long.numberOfTrailingZeros ( bitPos2 ) ; key [ off + 1 ] = ( byte ) bitNum2 ; visitor.visit ( key , off + 2 ) ; } } else { BBTrieNode childNode = node.getChildNode ( bitPos​​​                                                                                                              ); visit ( childNode 、visitor 、key 、off + 1 、len ); } } } public static int set6Int ( byte [] b 、int value ) { int pos = 0 ; b [ pos ] = ( byte ) (( value >>> 30 ) & 0x3F ); b [ pos + 1 ] = ( byte ) (( value >>> 24 ) & 0x3F ); b [ pos + 2 ] = ( byte ) (( value >>> 18 ) & 0x3F ); b [ pos + 3 ] = ( byte ) (( value >>> 12 ) & 0x3F ); b [ pos + 4 ] = ( byte ) (( value >>> 6 ) & 0x3F ); b [ pos + 5 ] = ( byte ) ( value & 0x3F ); 6を返す; }                                                                                     パブリック静的int get6Int ( byte [] b ) { int pos = 0 ; return (( b [ pos ] & 0x3F ) << 30 ) | (( b [ pos + 1 ] & 0x3F ) << 24 ) | (( b [ pos + 2 ] & 0x3F ) << 18 ) | (( b [ pos + 3 ] & 0x3F ) << 12 ) | (( b [ pos + 4 ] & 0x3F ) << 6 ) | ( b [ pos + 5 ] & 0x3F ); }                                                        パブリック静的void main （String [] args ）{ BBTrieSet trie1 =新しいBBTrieSet （100 ）; BBTrieSet trie2 =新しいBBTrieSet （100 ）;                byte [] key =新しいbyte [ 64 ] ; int len ; final int KEY_LEN_INT = set6Int ( key , 1 ); // 6              int [] test = new int [] { 10 , 20 , 30 , 40 , 50 , 30 , 60 , 61 , 62 , 63 }; for ( int i = 0 ; i < test . length ; i ++ ) { len = set6Int ( key , test [ i ] ); boolean change = trie1 . set ( key , len ); System . out . println ( "set: " + test [ i ] + ", " + change ); } System . out . println ( "trie1 size: " + trie1 . size ());                                               BBTrieSetOps.visit ( new BBTrieNodeMem ( trie1.root , trie1.mem ) , new BBTrieSetOps.Visitor ( ) { @Override public void visit ( byte [ ] key , int keyLen ) { System.out.println ( " Visitor : " + get6Int ( key ) + " , " + keyLen ) ; } } , key , 0 , KEY_LEN_INT ) ;​                          test = new int [] { 10 , 25 , 30 , 40 , 45 , 50 , 55 , 60 }; for ( int i = 0 ; i < test . length ; i ++ ) { len = set6Int ( key , test [ i ] ); boolean contains = trie1 . get ( key , len ); System . out . println ( "contained: " + test [ i ] + ", " + contains ); }                                          test = new int [] { 10 , 20 , 30 , 40 , 45 , 50 , 55 , 60 , 61 , 62 , 63 }; for ( int i = 0 ; i < test . length ; i ++ ) { len = set6Int ( key , test [ i ] ); boolean change = trie1 . clear ( key , len ); System . out . println ( "cleared: " + test [ i ] + ", " + change ); BBTrieSetOps . visit ( new BBTrieNodeMem ( trie1 . root , trie1 . mem ), new BBTrieSetOps . Visitor () { @Override public void visit ( byte [] key , int keyLen ) { System . out . print ( get6Int ( key ) + " " ); } }, key , 0 , KEY_LEN_INT ); System . out . println ();                                                                   } System.out.println ( " trie1のサイズ:" + trie1.size ( ) ) ;     for ( int i = 0 ; i <= 50 ; i ++ ) { len = set6Int ( key , i ); trie1 . set ( key , len ); System . out . println ( "set: " + i ); } System . out . println ( "trie1 size: " + trie1 . size ());                       for ( int i = 25 ; i <= 75 ; i ++ ) { len = set6Int ( key , i ); trie2 . set ( key , len ); System . out . println ( "set: " + i ); } System . out . println ( "trie2 size: " + trie2 . size ());                       // AND の例BBTrieNode result = new BBTrieAnd ( new BBTrieNodeMem ( trie1 . root , trie1 . mem ), new BBTrieNodeMem ( trie2 . root , trie2 . mem ));            BBTrieSetOps.visit ( result , new BBTrieSetOps.Visitor ( ) { @Override public void visit ( byte [ ] key , int keyLen ) { System.out.println ( " Visitor AND result: " + get6Int ( key ) ) ; } } , key , 0 , KEY_LEN_INT ) ;                     } }

参考文献

[編集]

1. フィル・バグウェル (2000)。高速でスペース効率の高いトライ検索 (PDF) (レポート)。ローザンヌ連邦エコール工科大学情報科学部。
2. ウォーレン・ジュニア、ヘンリー・S. (2013). Hacker's Delight (第2版). Addison Wesley - Pearson Education, Inc. ISBN  978-0-321-84268-8。

「 https://en.wikipedia.org/w/index.php?title=Bitwise_trie_with_bitmap&oldid=1319374920」より取得

• このページの最終更新日時は 2025年10月29日 (火) 12:17  (UTC)です。
• テキストはクリエイティブ・コモンズ 表示-継承4.0ライセンスの下で利用可能です。追加の条件が適用される場合があります。このサイトを利用することにより、利用規約とプライバシーポリシーに同意したことになります。Wikipedia®は、非営利団体であるウィキメディア財団の登録商標です

• プライバシーポリシー
• Wikipediaについて
• 免責事項
• Wikipediaへのお問い合わせ
• 法的および安全に関する連絡先
• 行動規範
• 開発者
• 統計
• クッキーに関する声明
• モバイルビュー

• 
• 

検索

検索

目次を切り替える

ビットマップ付きビット単位トライ

言語を追加トピックを追加

ビット単位トライは、各ノードとその子枝がキーの1つ以上のビットのビット列を表す特殊な形式のトライです。ビットマップ付きビット単位トライは、ビットマップを使用して有効な子枝を示します

試行とビット単位の試行

トライ木は、例えばB木とは異なり、キーがノードではなく葉へのパスに格納される探索木の一種です。キーは木構造全体に分散されています。「典型的な」トライ木では、各ノードとその子枝は、キーの1つの位置（文字）に対応するアルファベットの1つの記号を表します。

ビット単位の試行では、キーは何らかのバイナリ表現のビット シーケンスとして扱われ、子ブランチを持つ各ノードは、このビット シーケンスのサブシーケンスの値を表し、バイナリ ツリー (サブシーケンスには 1 ビットのみが含まれる) または n 進ツリー (サブシーケンスには複数のビットが含まれる) を形成します。

「クラシック」トライとビット単位のトライの違いを説明する例を挙げます。キーとして数値を使用する場合、トライのアルファベットは 10 進法の数値の桁を表す記号 '0' ～ '9' で構成され、ノードには最大 10 個の子ノードが存在する可能性があります。

キーが「07」と「42」のトライ木。「0」や「07」といったノードラベルは読みやすさのために追加されたものであり、実際にはノードに格納されていないことに注意してください。

トライを物理データ構造として実装するには、複数の直接的なアプローチがあります。そのうちの2つを挙げると、

• ノードは、アルファベットの各記号に対応する子ポインタの配列（10進数の例では、ノードあたり10個のポインタの配列）で表現できます。これにより、キーの長さに応じた検索時間が得られます。しかし、各ノードは、そのパスを実現するキーがない場合でも、すべての可能な子シンボルのためのスペースを確保するため、これは空間効率が良くありません。 ${\displaystyle \Sigma }$ ${\displaystyle O(|M|)}$ ${\displaystyle |M|}$
• ノードには、シンボル順に並べられた（シンボル、子ポインタ）タプルの二分木が含まれます。これにより空間効率は向上しますが、検索時間は になります。理想的なトライでは、アクセス時間は格納されているキーの数に依存しません。 ${\displaystyle O(|M|\cdot \log |\Sigma |)}$

これらのアプローチは、例えばキーがUnicode文字列である場合など、アルファベットが大きい場合にはさらに悪化します。キーをビット列として扱うことで、ノードごとに固定のカーディナリティを持つことができます。

ビットマップ付きビット単位トライ

Bagwell ^[1]は、 Array Mapped Tree (AMT)という時間と空間を効率的に利用したトライのソリューションを発表しました。HAMT ( Hash array mapped trie )はAMTに基づいています。コンパクトなトライノード表現では、ビットマップを使用してすべての有効なブランチをマークします。つまり、ビットマップを使用したビット単位のトライです。AMTは、ノードごとに8つの32ビットのビットマップを使用して、ノードごとに8ビットのシーケンスを表現できる256進トライを表します。64ビットCPU ( 64ビットコンピューティング)では、バリエーションとして、ノードごとに1つの64ビットのビットマップのみを使用して6ビットのシーケンスを表現できる64進トライがあります。

有効な子ブランチをマークするビットマップを持つトライノード。

与えられた6ビット値に対応するノードの子ポインタのインデックスを決定するには、先行する子ポインタの数を計算する必要があります。これは非常に効率的に実装できることがわかります。

ノードトラバーサル

long bitMap = mem [ nodeIdx ] ; long bitPos = 1L << value ; // 6ビット値if (( bitMap & bitPos ) == 0 ) return false ; // 見つかりませんlong childNodeIdx = mem [ nodeIdx + 1 + Long . bitCount ( bitMap & ( bitPos - 1 )) ] ;                           

現在のノードインデックスに基づいてインデックスを見つけるためのオフセットは、ビットマップ内でターゲット位置の前に設定されている最下位ビットの数にビットマップのビット数を1加えた値です。設定されている最下位ビットの数は、単純なビット演算と、設定されているビット数を決定するCTPOP（count population）演算（JavaではLong.bitCount()として利用可能）を使用することで、定数時間計算量で効率的に計算できます。CTPOP自体は「ビットハック」 ^{[2]を使用することで非常に効率的に実装でき、多くの最新のCPUでは、CTPOPをコンパイラによって}組み込み関数として扱われる専用命令として提供しています。

int CTPOP ( long x ) { // 人口カウント関数の「ビットハック」実装。x -= (( x >>> 1 ) & 0x5555555555555555L ); x = ( x & 0x3333333333333333L ) + (( x >>> 2 ) & 0x3333333333333333L ); x = ( x + ( x >>> 4 )) & 0x0f0f0f0f0f0f0f0fL ; x += ( x >>> 8 ); x += ( x >>> 16 ); x += ( x >>> 32 ); return x & 0x7f ; }                                          

セット実装例

物理データ構造

このビットマップを用いたビット単位トライの実装例では、ノードはlong（64ビット）整数の配列に配置されます。ノードは配列内の位置（インデックス）によって識別されます。ルートノードのインデックスは、トライのルートを表します。

ノードは配列内の未使用領域から割り当てられ、必要に応じて配列を拡張します。さらに、置換されたノードはフリーリストに集められ、その領域は再利用されます。この再利用を行わない場合、このデータ構造は、以前のルートインデックスのみを保持し、既存のノードを上書きすることなく、変更されたノードのコピーを常に作成することで、永続的なデータ構造を実装できます。

リーフ ノードはインライン化されます。つまり、リーフ ノードへの子ポインターを持つ代わりに、リーフ ノード自体のビットマップが格納されます。

パブリッククラスBBTrieSet {    long [] mem ; long [] freeLists ; long freeIdx ;      長いルート;長いカウント;    // 配列はゼロベースなので、最大ノード サイズは 1 (ビットマップ) + 64 (子ポインターまたはリーフ値) + 1 です。final static int FREE_LIST_SIZE = 1 + 64 + 1 ;       最終的な静的int KNOWN_EMPTY_NODE = 0 ;最終的な静的int KNOWN_DELETED_NODE = 1 ;最終的な静的int HEADER_SIZE = 2 ; // KNOWN_EMPTY_NODE、KNOWN_DELETED_NODE                   public BBTrieSet ( int size ) { mem = new long [ size ] ; freeLists = new long [ FREE_LIST_SIZE ] ; freeIdx = HEADER_SIZE ; root = KNOWN_EMPTY_NODE ; count = 0 ; }                      private long allocate ( int size ) { long free = freeLists [ size ] ; if ( free != 0 ) { // 要求されたサイズはフリーリストで使用可能です。再リンクしてヘッドを返します。freeLists [ size ] = mem [ ( int ) free ] ; return free ; } else { // 拡張が必要か? if ( freeIdx + size > mem . length ) { // 25% 増やして、十分であることを確認します。int currSize = mem . length ; int newSize = currSize + Math . max ( currSize / 4 , size ); mem = Arrays . copyOf ( mem , newSize ); }                                                   long idx = freeIdx ; freeIdx += size ; return idx ; } }           プライベートlong allocateInsert ( long nodeIdx 、int size 、int childIdx ) { long newNodeRef = allocate ( size + 1 );               int a = ( int ) newNodeRef ; int b = ( int ) nodeIdx ;          // 子のギャップ付きコピーfor ( int j = 0 ; j < childIdx ; j ++ ) mem [ a ++] = mem [ b ++] ; a ++ ; // 挿入済みfor ( int j = childIdx ; j < size ; j ++ ) mem [ a ++] = mem [ b ++] ;                           deallocate ( nodeIdx , size );  newNodeRefを返します。} private long allocateDelete ( long nodeIdx , int size , int childIdx ) { long newNodeRef = allocate ( size - 1 );                   // 子要素を削除してコピーしますint a = ( int ) newNodeRef ; int b = ( int ) nodeIdx ; for ( int j = 0 ; j < childIdx ; j ++ ) mem [ a ++] = mem [ b ++] ; b ++ ; // 削除しましたfor ( int j = childIdx + 1 ; j < size ; j ++ ) mem [ a ++] = mem [ b ++] ; deallocate ( nodeIdx , size );                                          newNodeRefを返します。   private void deallocate ( long idx , int size ) { if ( idx == KNOWN_EMPTY_NODE ) return ; // 既知の空ノードを保持する             // フリーリストの先頭に追加mem [ ( int ) idx ] = freeLists [ size ] ; freeLists [ size ] = idx ; }         private long createLeaf ( byte [] key , int off , int len ) { long newNodeRef = allocate ( 2 ); int a = ( int ) newNodeRef ; mem [ a ++] = 1L << key [ len - 2 ] ; mem [ a ] = 1L << key [ len - 1 ] ; // value len -= 3 ; while ( len >= off ) { long newParentNodeRef = allocate ( 2 ); a = ( int ) newParentNodeRef ; mem [ a ++] = 1L << key [ len --] ; mem [ a ] = newNodeRef ; newNodeRef = newParentNodeRef ; } return newNodeRef ; }                                                                private long insertChild ( long nodeRef , long bitMap , long bitPos , int idx , long value ) { int size = Long . bitCount ( bitMap ); long newNodeRef = allocateInsert ( nodeRef , size + 1 , idx + 1 ); mem [ ( int ) newNodeRef ] = bitMap | bitPos ; mem [ ( int ) newNodeRef + 1 + idx ] = value ; return newNodeRef ; } private long removeChild ( long nodeRef , long bitMap , long bitPos , int idx ) { int size = Long . bitCount ( bitMap ); if ( size > 1 ) { // ノードにはまだ他の子ノードや葉ノードがありますlong newNodeRef = allocateDelete ( nodeRef , size + 1 , idx + 1 ); mem [ ( int ) newNodeRef ] = bitMap & ~ bitPos ; return newNodeRef ; } else { // ノードは空になったので削除しますdeallocate ( nodeRef , size + 1 ); return KNOWN_DELETED_NODE ; } }                                                                                                パブリックlong size () {戻り値 count ; }      }

集合演算

キーを含む

getメソッドは、キーが集合の一部であるかどうかをテストします。キーはbyte[]として渡され、各バイトはキーの6ビットのビットシーケンスを表します。したがって、1バイトあたり8ビットのうち6ビットのみが使用されます

 public boolean get ( byte [] key , int len ) { if ( root == KNOWN_EMPTY_NODE ) return false ;             long nodeRef = root ; int off = 0 ; for (;;) { long bitMap = mem [ ( int ) nodeRef ] ; long bitPos = 1L << key [ off ++] ; // ++ に注意してください if (( bitMap & bitPos ) == 0 ) return false ; // 見つかりません                                  long値= mem [ ( int ) nodeRef + 1 + Long . bitCount ( bitMap & ( bitPos - 1 )) ] ;             if ( off == len - 1 ) { // リーフlong bitPosLeaf = 1L << key [ off ] ; return (( value & bitPosLeaf ) != 0 ); } else { // 子ポインターnodeRef = value ; } } }                             

キーを設定（追加）する

 public boolean set ( byte [] key , int len ) { long nodeRef = set ( root , key , 0 , len ); if ( nodeRef != KNOWN_EMPTY_NODE ) { // 変更回数を表す++ ; root = nodeRef ; trueを返す; } else falseを返す; }                               private long set ( long nodeRef , byte [] key , int off , int len ) { long bitMap = mem [ ( int ) nodeRef ] ; long bitPos = 1L << key [ off ++] ; // ++ に注意してくださいint idx = Long . bitCount ( bitMap & ( bitPos - 1 ) );                                if (( bitMap & bitPos ) == 0 ) { // 子はまだ存在しませんlong value ; if ( off == len - 1 ) value = 1L << key [ off ] ; else value = createLeaf ( key , off , len ); return insertChild ( nodeRef , bitMap , bitPos , idx , value ); } else { // 子が存在しますlong value = mem [ ( int ) nodeRef + 1 + idx ] ; if ( off == len - 1 ) { // リーフにありますlong bitPosLeaf = 1L << key [ off ] ; if (( value & bitPosLeaf ) == 0 ) { // リーフのビットマップを更新しますmem [ ( int ) nodeRef + 1 + idx ] = value | bitPosLeaf ; return nodeRef ; } else // キーが既に存在しますreturn KNOWN_EMPTY_NODE ; } else { // リーフではない、再帰long childNodeRef = value ; long newChildNodeRef = set ( childNodeRef , key , off , len ); if ( newChildNodeRef == KNOWN_EMPTY_NODE ) return KNOWN_EMPTY_NODE ; if ( newChildNodeRef != childNodeRef ) mem [ ( int ) nodeRef + 1 + idx ] =                                                                                                                     newChildNodeRef ; nodeRefを返します; } } }      

キーをクリア（削除）する

 public boolean clear ( byte [] key , int len ) { long nodeRef = clear ( root , key , 0 , len ); if ( nodeRef != KNOWN_EMPTY_NODE ) { count -- ; if ( nodeRef == KNOWN_DELETED_NODE ) root = KNOWN_EMPTY_NODE ; else root = nodeRef ; return true ; } else return false ; }                                      public long clear ( long nodeRef 、byte [] key 、int off 、int len ) { if ( root == KNOWN_EMPTY_NODE ) return KNOWN_EMPTY_NODE ;                 long bitMap = mem [ ( int ) nodeRef ] ; long bitPos = 1L << key [ off ++] ; // ++ に注意してくださいif (( bitMap & bitPos ) == 0 ) { // 子要素が存在せず、キーが見つかりませんreturn KNOWN_EMPTY_NODE ; } else { // 子要素が存在しますint idx = Long . bitCount ( bitMap & ( bitPos - 1 )); long value = mem [ ( int ) nodeRef + 1 + idx ] ; if ( off == len - 1 ) { // リーフにありますlong bitPosLeaf = 1L << key [ off ] ; if (( value & bitPosLeaf ) == 0 ) // キーが存在しませんreturn KNOWN_EMPTY_NODE ; else { // リーフのビットをクリアしますvalue = value & ~ bitPosLeaf ; if ( value != 0 ) { // リーフにはまだいくつかのビットが設定されているため、リーフを保持しますが、mem [ ( int ) nodeRef + 1 + idx ] = value ; return nodeRef ; } else return removeChild ( nodeRef , bitMap , bitPosLeaf , idx ); } } else { // リーフではありませんlong childNodeRef = value ; long newChildNodeRef = clear ( childNodeRef , key , off , len ); if ( newChildNodeRef ==                                                                                                                    KNOWN_EMPTY_NODE )を返しますKNOWN_EMPTY_NODE ; if ( newChildNodeRef == KNOWN_DELETED_NODE )を返しますremoveChild ( nodeRef 、bitMap 、bitPos 、idx ) ; if ( newChildNodeRef != childNodeRef ) mem [ ( int ) nodeRef + 1 + idx ] = newChildNodeRef ; return nodeRef ; } } }                             }

集合演算子

積（and）、和（or）、差（minus）の集合演算子は、以下に示すフライウェイトパターンを使用して実行可能です

インターフェースは、演算子の物理ノードと「仮想」結果ノードを表します。このインターフェースのインスタンスは、トライの走査中に必要に応じて作成されます。複数の演算子を含む複合式は、これらの演算子を組み合わせることで直接表現できます。つまり、ある演算子を別の演算子の引数（入力）として使用することができます。

フライウェイトインターフェース

パブリックインターフェースBBTrieNode { public long getBitMap (); public long getBitMapLeaf ( long bitPos ); public BBTrieNode getChildNode ( long bitPos ); }パブリック静的クラスBBTrieNodeMem はBBTrieNodeを実装します{                       long nodeRef ; long [] mem ;    BBTrieNodeMem子;  パブリックBBTrieNodeMem ( long nodeRef 、long [] mem ) { this . nodeRef = nodeRef ; this . mem = mem ; }             @Override public long getBitMap () { return mem [ ( int ) nodeRef ] ; }         @Override public long getBitMapLeaf ( long bitPos ) { int idx = Long . bitCount ( getBitMap () & ( bitPos - 1 )); long value = mem [ ( int ) nodeRef + 1 + idx ] ;戻り値; }                          @Override public BBTrieNode getChildNode ( long bitPos ) { int idx = Long . bitCount ( getBitMap () & ( bitPos - 1 )); long value = mem [ ( int ) nodeRef + 1 + idx ] ; return new BBTrieNodeMem ( value , mem ); } }                             

積集合（AND）

積集合演算子は、部分式に対しても自動的に枝刈りを行うため、非常に効率的です。ビットマップとビット単位のAND演算によって結果を事前に決定できるため、無関係な子ノードにアクセスする必要はありません。例えば、を計算する場合、部分式は中間結果として具体化されません ${\displaystyle \{1,2,3\}\cap (\{2,3,4\}\cup \{5,6,7\})=\{2,3\}}$ ${\displaystyle \{2,3,4\}\cup \{5,6,7\}=\{2,3,4,5,6,7\}}$

 パブリック静的クラスBBTrieAnd はBBTrieNodeを実装します{ BBTrieNode nodeA ; BBTrieNode nodeB ; long bitMapA ; long bitMapB ;                public BBTrieAnd ( BBTrieNode nodeA , BBTrieNode nodeB ) { this . nodeA = nodeA ; this . nodeB = nodeB ; bitMapA = nodeA . getBitMap (); bitMapB = nodeB . getBitMap (); } public long getBitMap () { return bitMapA & bitMapB ; // これにより、適切な最適化 (プルーニング) が行われます} public long getBitMapLeaf ( long bitPos ) { return nodeA . getBitMapLeaf ( bitPos ) & nodeB . getBitMapLeaf ( bitPos ); } public BBTrieNode getChildNode ( long bitPos ) { BBTrieNode childNodeA = nodeA . getChildNode ( bitPos ); BBTrieNode childNodeB = nodeB . getChildNode ( bitPos ); return new BBTrieAnd ( childNodeA , childNodeB ); }                                                           }

和集合（OR）

public static class BBTrieOr implements BBTrieNode { BBTrieNode nodeA ; BBTrieNode nodeB ; long bitMapA ; long bitMapB ;                public BBTrieOr ( BBTrieNode nodeA 、BBTrieNode nodeB ) { this . nodeA = nodeA ; this . nodeB = nodeB ; bitMapA = nodeA . getBitMap (); bitMapB = nodeB . getBitMap (); } public long getBitMap () { return bitMapA | bitMapB ; } public long getBitMapLeaf ( long bitPos ) { return nodeA . getBitMapLeaf ( bitPos ) | nodeB . getBitMapLeaf ( bitPos ); } public BBTrieNode getChildNode ( long bitPos ) { if (( bitMapA & bitPos ) != 0 ) { BBTrieNode childNodeA = nodeA . getChildNode ( bitPos ); if (( bitMapB & bitPos ) != 0 ) { BBTrieNode childNodeB = nodeB . getChildNode ( bitPos ); return new BBTrieOr ( childNodeA , childNodeB ); } else return childNodeA ; // 最適化。これ以上の or ノードは不要} else { BBTrieNode childNodeB = nodeB . getChildNode ( bitPos ); return childNodeB ; // 最適化。これ以上の or ノードは不要} }                                                                                        }

差（マイナス）

public static class BBTrieMinus implements BBTrieNode { BBTrieNode nodeA ; BBTrieNode nodeB ; long bitMapA ; long bitMapB ; public BBTrieMinus ( BBTrieNode nodeA , BBTrieNode nodeB ) { this.nodeA = nodeA ; this.nodeB = nodeB ; bitMapA = nodeA.getBitMap ( ); bitMapB = nodeB.getBitMap ( ) ; } public long getBitMap ( ) { return bitMapA ; // bitMapBはここでは役に立ちません} public long getBitMapLeaf ( long bitPos ) { long childBitMapA = nodeA.getBitMapLeaf ( bitPos ) ; if ( ( bitMapB & bitPos ) == 0 ) return childBitMapA ; long childBitMapB = nodeB.getBitMapLeaf ( bitPos ) ; return childBitMapA & ~ childBitMapB ; } public BBTrieNode getChildNode ( long bitPos ) { BBTrieNode childNodeA = nodeA . getChildNode ( bitPos ); if (( bitMapB & bitPos ) == 0 ) return childNodeA ; // 最適化、マイナスノードは不要BBTrieNode childNodeB = nodeB . getChildNode ( bitPos ); return new BBTrieMinus ( childNodeA , childNodeB ); }                                                                                                     }

範囲

仮想ノードアプローチを用いると、範囲を生成する仮想トライ（下記参照）を別の演算子と交差させることで範囲クエリを実現できます。つまり、例えば集合 のどの数値が特定の範囲（例えば [10..50]）に含まれるかを判断するには、集合全体を反復処理して各エントリをチェックする代わりに、 を評価することで実行します。 ${\displaystyle \{10,20,30,40,50,60,61,62,63\}}$ ${\displaystyle \{10,20,30,40,50,60,61,62,63\}\cap \{10,..,50\}}$

パブリックスタティッククラスBBTrieIntRange はBBTrieNode を実装します{ private long bitMap ; private int a , b ; private int x , y ; private int level ; public BBTrieIntRange ( int a , int b ) { this ( a , b , 5 ); }                                 private BBTrieIntRange ( int a , int b , int level ) { this . a = a ; this . b = b ; this . level = level ; x = ( int ) ( a >>> ( level * 6 )) & 0x3F ; y = ( int ) ( b >>> ( level * 6 )) & 0x3F ; // ビット ハック for: for (int i = x; i <= y; i++) bitSet |= (1L << i); bitMap = 1L << y ; bitMap |= bitMap - 1 ; bitMap &= ~ (( 1L << x ) - 1 ); }                                                          public long getBitMap () { return bitMap ; } public long getBitMapLeaf ( long bitPos ) { // 読みやすさのためのシンプルなソリューション (呼び出しごとに子ノードが再度作成されるため、それほど効率的ではありません) return getChildNode ( bitPos ). getBitMap (); }                 public BBTrieIntRange getChildNode ( long bitPos ) { int bitNum = Long . numberOfTrailingZeros ( bitPos ); if ( x == y ) return new BBTrieIntRange ( a , b , level - 1 ); else if ( bitNum == x ) return new BBTrieIntRange ( a , ~ 0x0 , level - 1 ); else if ( bitNum == y ) return new BBTrieIntRange ( 0 , b , level - 1 ); else return new BBTrieIntRange ( 0 , ~ 0x0 , level - 1 ); }                                                    }

使用例

この例では、32ビット整数をキーとして使用した使用方法を示しています

パブリッククラスBBTrieSetSample {    public interface Visitor { public void visit ( byte [] key , int keyLen ); } public static void visit ( BBTrieNode node , Visitor visitor , byte [] key , int off , int len ) { long bitMap = node . getBitMap (); if ( bitMap == 0 ) return ; long bits = bitMap ; while ( bits != 0 ) { long bitPos = bits & - bits ; bits ^= bitPos ; // 右端のビットを取得してクリアしますint bitNum = Long . numberOfTrailingZeros ( bitPos ); key [ off ] = ( byte ) bitNum ; if ( off == len - 2 ) { long value = node . getBitMapLeaf ( bitPos ); long bits2 = value ; while ( bits2 != 0 ) { long bitPos2 = bits2 & - bits2 ; bits2 ^ = bitPos2 ; int bitNum2 = Long.numberOfTrailingZeros ( bitPos2 ) ; key [ off + 1 ] = ( byte ) bitNum2 ; visitor.visit ( key , off + 2 ) ; } } else { BBTrieNode childNode = node.getChildNode ( bitPos​​​                                                                                                              ); visit ( childNode 、visitor 、key 、off + 1 、len ); } } } public static int set6Int ( byte [] b 、int value ) { int pos = 0 ; b [ pos ] = ( byte ) (( value >>> 30 ) & 0x3F ); b [ pos + 1 ] = ( byte ) (( value >>> 24 ) & 0x3F ); b [ pos + 2 ] = ( byte ) (( value >>> 18 ) & 0x3F ); b [ pos + 3 ] = ( byte ) (( value >>> 12 ) & 0x3F ); b [ pos + 4 ] = ( byte ) (( value >>> 6 ) & 0x3F ); b [ pos + 5 ] = ( byte ) ( value & 0x3F ); 6を返す; }                                                                                     パブリック静的int get6Int ( byte [] b ) { int pos = 0 ; return (( b [ pos ] & 0x3F ) << 30 ) | (( b [ pos + 1 ] & 0x3F ) << 24 ) | (( b [ pos + 2 ] & 0x3F ) << 18 ) | (( b [ pos + 3 ] & 0x3F ) << 12 ) | (( b [ pos + 4 ] & 0x3F ) << 6 ) | ( b [ pos + 5 ] & 0x3F ); }                                                        パブリック静的void main （String [] args ）{ BBTrieSet trie1 =新しいBBTrieSet （100 ）; BBTrieSet trie2 =新しいBBTrieSet （100 ）;                byte [] key =新しいbyte [ 64 ] ; int len ; final int KEY_LEN_INT = set6Int ( key , 1 ); // 6              int [] test = new int [] { 10 , 20 , 30 , 40 , 50 , 30 , 60 , 61 , 62 , 63 }; for ( int i = 0 ; i < test . length ; i ++ ) { len = set6Int ( key , test [ i ] ); boolean change = trie1 . set ( key , len ); System . out . println ( "set: " + test [ i ] + ", " + change ); } System . out . println ( "trie1 size: " + trie1 . size ());                                               BBTrieSetOps.visit ( new BBTrieNodeMem ( trie1.root , trie1.mem ) , new BBTrieSetOps.Visitor ( ) { @Override public void visit ( byte [ ] key , int keyLen ) { System.out.println ( " Visitor : " + get6Int ( key ) + " , " + keyLen ) ; } } , key , 0 , KEY_LEN_INT ) ;​                          test = new int [] { 10 , 25 , 30 , 40 , 45 , 50 , 55 , 60 }; for ( int i = 0 ; i < test . length ; i ++ ) { len = set6Int ( key , test [ i ] ); boolean contains = trie1 . get ( key , len ); System . out . println ( "contained: " + test [ i ] + ", " + contains ); }                                          test = new int [] { 10 , 20 , 30 , 40 , 45 , 50 , 55 , 60 , 61 , 62 , 63 }; for ( int i = 0 ; i < test . length ; i ++ ) { len = set6Int ( key , test [ i ] ); boolean change = trie1 . clear ( key , len ); System . out . println ( "cleared: " + test [ i ] + ", " + change ); BBTrieSetOps . visit ( new BBTrieNodeMem ( trie1 . root , trie1 . mem ), new BBTrieSetOps . Visitor () { @Override public void visit ( byte [] key , int keyLen ) { System . out . print ( get6Int ( key ) + " " ); } }, key , 0 , KEY_LEN_INT ); System . out . println ();                                                                   } System.out.println ( " trie1のサイズ:" + trie1.size ( ) ) ;     for ( int i = 0 ; i <= 50 ; i ++ ) { len = set6Int ( key , i ); trie1 . set ( key , len ); System . out . println ( "set: " + i ); } System . out . println ( "trie1 size: " + trie1 . size ());                       for ( int i = 25 ; i <= 75 ; i ++ ) { len = set6Int ( key , i ); trie2 . set ( key , len ); System . out . println ( "set: " + i ); } System . out . println ( "trie2 size: " + trie2 . size ());                       // AND の例BBTrieNode result = new BBTrieAnd ( new BBTrieNodeMem ( trie1 . root , trie1 . mem ), new BBTrieNodeMem ( trie2 . root , trie2 . mem ));            BBTrieSetOps.visit ( result , new BBTrieSetOps.Visitor ( ) { @Override public void visit ( byte [ ] key , int keyLen ) { System.out.println ( " Visitor AND result: " + get6Int ( key ) ) ; } } , key , 0 , KEY_LEN_INT ) ;                     } }

参考文献

1. フィル・バグウェル (2000)。高速でスペース効率の高いトライ検索(PDF) (レポート)。ローザンヌ連邦エコール工科大学情報科学部。
2. ウォーレン・ジュニア、ヘンリー・S. (2013). Hacker's Delight (第2版). Addison Wesley - Pearson Education, Inc. ISBN  978-0-321-84268-8。

「https://en.wikipedia.org/w/index.php?title=Bitwise_trie_with_bitmap&oldid=1319374920」から取得

Original text

Rate this translation

Your feedback will be used to help improve Google Translate