ウェーブレットツリー

ウェーブレットツリーは、圧縮されたスペースに文字列を格納するための簡潔なデータ構造です。これは、ビットベクトルで定義されたおよび操作を任意のアルファベットに一般化します。 ${\displaystyle \mathbf {rank} _{q}}$${\displaystyle \mathbf {select} _{q}}$

もともとは圧縮された接尾辞配列を表すために導入されましたが、^[1]いくつかのコンテキストで応用されています。^{[2] [3]}ツリーは、アルファベットをサブセットのペアに再帰的に分割することによって定義されます。葉はアルファベットの個々の記号に対応し、各ノードのビットベクトルは文字列の記号がどちらのサブセットに属しているかを格納します。

この名前は、信号を低周波成分と高周波成分に再帰的に分解する信号の ウェーブレット変換との類似性から由来しています。

を の有限アルファベットとします。ノードで簡潔な辞書を使用することで、文字列を に格納できます。ここで、は の0 次経験的エントロピーです。 ${\displaystyle \Sigma }$${\displaystyle \sigma ={|\Sigma |}}$${\displaystyle s\in \Sigma ^{*}}$${\displaystyle {|s|}H_{0}(s)+o({|s|}\log \sigma )}$${\displaystyle H_{0}(s)}$${\displaystyle s}$

ツリーがバランスが取れている場合、操作、、 は時間 内にサポートできます。${\displaystyle \mathbf {アクセス} }$${\displaystyle \mathbf {rank} _{q}}$${\displaystyle \mathbf {select} _{q}}$${\displaystyle O(\log \sigma )}$

ウェーブレット ツリーには、文字列のビットマップ表現が含まれています。アルファベット セットがわかっていれば、ツリーのビットを追跡することで正確な文字列を推測できます。文字列の i 番目の位置にある文字を見つけるには、 ^{次のようにします。}

アルゴリズムアクセス
  入力：-文字を知りたい文字列内の
    位置i。1から始まります。-文字列を表すウェーブレットツリーの
    最上位ノードW出力: iの
  位置にある文字

     W.isLeafNode の場合はW.letterを返し、  W.bitvector[i] = 0 の場合はaccess( i - rank( W.bitvector , i ), W.left )
    を返し、それ以外の場合はaccess(rank( W.bitvector , i ), W.right )
を返します。
      

この文脈では、ビットベクトル内の位置のランクは、の最初の位置に現れる1の数です。ランクは簡潔な辞書を使用してO(1)で計算できるため、ツリーがバランスが取れている限り 、文字列S内の任意のS[i]に^[3]時間でアクセスできます。${\displaystyle i}$${\displaystyle b}$${\displaystyle i}$${\displaystyle b}$${\displaystyle O(\log \sigma )}$

文献では、基本構造に対するいくつかの拡張が発表されています。木の高さを減らすために、バイナリノードの代わりに多項ノードを使用できます。^[2]データ構造を動的にすることができ、文字列の任意のポイントでの挿入と削除をサポートします。この機能により、動的なFMインデックスの実装が可能になります。^[4]これはさらに一般化され、更新操作で基礎となるアルファベットを変更できるようになります。ウェーブレットトライ^{[5]は、文字列のアルファベット上の}トライ構造を利用して、動的な木の変更を可能にします。

• ウェーブレット ツリー。ウェーブレット ツリーの構築を例とともに説明するブログ投稿。

• ウィキメディア・コモンズのウェーブレットツリーに関連するメディア