X高速トライ
| X高速トライ | ||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| タイプ | トライ | |||||||||||||||||||||||
| 発明された | 1982 | |||||||||||||||||||||||
| 発明者 | ダン・ウィラード | |||||||||||||||||||||||
| ||||||||||||||||||||||||
コンピュータサイエンスにおいて、x-高速トライは、境界付きドメインの整数を格納するためのデータ構造です。x-高速トライは、 O (log log M )の時間で、O ( n log M )の空間を使用して、正確なクエリと先行クエリ、または後続クエリをサポートします。ここで、nは格納されている値の数、Mはドメイン内の最大値です。この構造は、1982年にダン・ウィラード[1]によって、より複雑なy-高速トライと共に提案されました。これは、ファン・エムデ・ボアズ木の空間使用率を改善しつつ、O (log log M )のクエリ時間を維持する方法として提案されました。
構造
x-fastトライはビット単位のトライです。つまり、各サブツリーが共通のプレフィックスで始まるバイナリ表現を持つ値を格納するバイナリツリーです。各内部ノードは、そのサブツリー内の値の共通プレフィックスでラベル付けされ、通常、左の子ノードはプレフィックスの末尾に0を追加し、右の子ノードは1を追加します。0からM − 1までの整数のバイナリ表現は⌈log 2 M ⌉ビットを使用するため、トライの高さはO (log M )です。
x-fast トライのすべての値は、リーフに格納されます。内部ノードは、サブツリーにリーフがある場合にのみ格納されます。内部ノードに左の子がない場合、代わりに右のサブツリーの最小のリーフへのポインター (子孫ポインター) が格納されます。同様に、右の子がない場合、左のサブツリーの最大のリーフへのポインターが格納されます。各リーフには、先行リーフと後続リーフへのポインターが格納され、これによって双方向リンク リストが形成されます。最後に、各レベルにハッシュ テーブルがあり、そのレベルのすべてのノードが含まれます。これらのハッシュ テーブルが一緒になってレベル検索構造 (LSS) を形成します。最悪の場合のクエリ時間を保証するには、これらのハッシュ テーブルで動的完全ハッシュまたはカッコウ ハッシュを使用する必要があります。
各要素のルートからリーフへのパスの長さはO ( log M ) なので、総スペース使用量はO ( n log M ) です。[要引用]
オペレーション
ファン・エムデ・ボアズ木と同様に、x-fastトライは順序付き連想配列の演算をサポートします。これには、通常の連想配列演算に加えて、SuccessorとPredecessor という2つの順序演算が含まれます。
- Find ( k ): 指定されたキーに関連付けられた値を見つける
- 後継者（k）：指定されたキー以上の最小のキーを持つキー/値のペアを見つける
- 先行キー（k）：指定されたキー以下の最大のキーを持つキー/値のペアを見つける
- 挿入( k , v ): 指定されたキー/値のペアを挿入する
- 削除( k ): 指定されたキーのキー/値のペアを削除します。
探す
データ構造内のキーkに関連付けられた値を見つけることは、すべてのリーフ上のハッシュテーブルであるLSS [0]でkを検索することによって定数時間で行うことができます。 [2]
たとえば、上のグラフで 4 を探している場合は、次の手順を実行します。
- ステップ 1: 10 進数の 4 を 2 進数の 100 に変換します。
- ステップ2：ルートから始めて、各レベルへのパスをたどってみましょう。100の最初の数字は1なので、ルートの右パス（1）をたどってノード「1」まで進みます。
- ステップ 3: ステップ 2 を繰り返します。100 の 2 番目の数字は 0 なので、ノード「1」の左のパス (0) をたどってノード「10」まで進みます。
- ステップ 4: ステップ 3 を繰り返します。100 の 3 番目の数字は 0 なので、ノード「10」の左のパス (0) をたどってノード「100」まで進みます。
後継者と前任者
キーkの後継または先行するキーを見つけるには、まずkの最下位の祖先であるA k を見つけます。これは、 kと最長の共通プレフィックスを持つトライ内のノードです。 A kを見つけるには、レベルでバイナリ検索を実行します。レベルh /2 から開始します。ここで、hはトライの高さです。各レベルで、レベル検索構造の対応するハッシュ テーブルを、適切な長さのkのプレフィックスを使用して照会します。そのプレフィックスを持つノードが存在しない場合、 A k は上位レベルにあるはずなので、検索をそれらのレベルに制限します。そのプレフィックスを持つノードが存在する場合、A k は上位レベルにはないはずなので、検索を現在のレベルとそれより低いレベルに制限します。
kの最下位の祖先を見つけると、その部分木の1つに葉があることがわかります（そうでなければトライツリーには含まれません）。そして、k はもう一方の部分木に含まれるはずです。したがって、子孫ポインタはkの後継者または先行者を指します。どちらを探しているかによって、リンクリスト内で次の葉または前の葉まで1ステップ進む必要がある場合があります。
トライの高さはO (log M )なので、最下位の祖先を探す二分探索にはO (log log M )の時間がかかります。その後、後継者または先行者は定数時間で見つかるため、合計の探索時間はO (log log M )となります。[1]
たとえば、上のグラフで 3 の前身を探す場合は、次の手順を実行します。
- ステップ 1: 10 進数の 3 を 2 進数の 011 に変換します。
- ステップ2：ルートから始めて、各レベルへのパスを辿ってみましょう。011の最初の数字は0なので、ルートの左パス（0）を辿ってノード「0」まで進みます。
- ステップ3：ステップ2を繰り返します。011の2桁目は1なので、正しいパス（1）をたどってみます。ただし、ノード「0」には正しいパスがないため、ポインタをたどってノード「001」に進みます。
- ステップ 4: 001 は 011 より小さいため、011 の前の数字を表します。したがって、3 の前数字は 1 (001) です。
入れる
キーと値のペア ( k , v ) を挿入するには、まずkの先行ノードと後続ノードを見つけます。次に、 kの新しいリーフノードを作成し、それを後続ノードと先行ノードの間のリーフノードのリンクリストに挿入し、 vへのポインタを設定します。次に、ルートノードから新しいリーフノードまで移動し、必要なノードを作成してそれぞれのハッシュテーブルに挿入し、必要に応じて子孫ノードのポインタを更新します。
トライの高さ全体を歩いていく必要があるため、このプロセスにはO（log M）の時間がかかります。[3]
消去
キーkを削除するには、葉のハッシュテーブルを使ってその葉を見つけます。リンクリストから k を削除しますが、どの葉が後続ノードと先行ノードであったかは記憶しておきます。次に、葉からトライのルートまで移動し、kのみを含むサブツリーを持つすべてのノードを削除し、必要に応じて子孫ポインタを更新します。 k を指していた子孫ポインタは、どのサブツリーが欠落しているかに応じて、 kの後続ノードまたは先行ノードを指すようになります。
挿入と同様に、トライのすべてのレベルを調べる必要があるため、O（log M ）の時間がかかります。 [3]
議論
ウィラードは主にy高速トライの導入としてx高速トライを導入しました。y高速トライは同じクエリ時間を提供しながら、O ( n )のスペースしか使用せず、O (log log M )の時間で挿入と削除を可能にします。[1]
パトリシアトライに似た圧縮技術は、実際にはx-fastトライのスペース使用量を大幅に削減するために使用できます。[4]
レベル間のバイナリ検索の前に指数検索を使用し、現在のプレフィックスxだけでなくその後続のプレフィックスx + 1も照会することで、x高速試行は先行クエリと後続クエリにO (log log Δ )の時間で応答できます。ここで、Δはクエリ値とその先行または後続クエリの差です。[2]
参考文献
- ^ abc Willard, Dan E. (1983). 「対数対数最悪ケース範囲クエリは空間Θ( N )で可能である」. Information Processing Letters . 17 (2). Elsevier: 81– 84. doi :10.1016/0020-0190(83)90075-3. ISSN 0020-0190.
- ^ ab Bose, Prosenjit ; Douïeb, Karim ; Dujmović, Vida ; Howat, John ; Morin, Pat (2010)、「境界付き宇宙における高速局所探索と更新」(PDF)、第22回カナダ計算幾何学会議(CCCG2010)の議事録、pp. 261– 264
- ^ ab Schulz, André; Christiano, Paul (2010-03-04). 「Lecture 9 of Advanced Data Structures (Spring '10, 6.851) の講義ノート」(PDF) . 2011-04-13閲覧。
- ^ Kementsietsidis, Anastasios; Wang, Min (2009), Provenance Query Evaluation: What's so special about it? , Proceedings of the 18th ACM conference on Information and knowledge management, pp. 681– 690
外部リンク
- オープンデータ構造 - 第13章 - 整数のデータ構造
