Here is my Github repository of efficient and read-able Wavelet tree and RRR bit vector implementation. Comparing to SDSL and it got better results.
SuccinctDS – A Succinct Wavleet Tree/RRR bit vector Library
這篇介紹一個神奇的資料結構 Wavelet Tree，又叫做小波樹。
小波樹可以有效率的儲存字串並支援 access, rank, select 三種的二元樹狀資料結構。
對 Wavelet Tree 儲存 S 我們可以支援三種操作：
- Access(p): 讀取位置 p 的字元
- Rank(c, p): 計算字串 S 中 [0, p) 範圍的子字串中字元 c 出現多少次
- c 代表字元（character），p 代表位置（position）
- Select(c, o): 計算字串中第 o 次出現字元 c 的位置
- c 代表字元（character），o 代表出現次數（occurence）
Construction
最樸素版本的 Wavelet Tree 是很直覺的 divide & conquer ，令所有可能組成字元為一個集合，把集合對半切，並把字串依照順序分類到兩邊，再持續把字元集合對切直到末端的葉節點都是同樣的字元。因為知道對切到兩邊的字元集，所以對當前字串，每個字元只需要用 0/1 表示它該往左或右分類。
Wavelet Tree 的操作完全取決於它內部所儲存的 0/1 陣列（bitmap）所支援的 rank/select 速度。我也寫了篇文章在介紹有效的 bitmap rank/select 操作。
以下是 psuedo code 。（但這顯然不是他的最佳儲存方式，花了兩倍的空間在儲存一條字串）
Node* Construct ( s, sigma ) :
if size(sigma) == 1 or size(s) == 0 :
return Self
sigma_L, sigma_R = split(sigma) # split in half
s_L = "", s_R = ""
for all c in S do:
if c belongs to sigma_L :
Self.Bitmap.Append(0)
s_L.append(c)
else:
Self.Bitmap.Append(1)
s_R.append(c)
Self.nodeL = Construct(s_L, sigmaL)
Self.nodeR = Construct(s_R, sigmaR)
return Self
Wavelet Tree – Access
對根節點 root 上儲存的 0/1 陣列，第 p 個位置可以決定要往下看哪個子節點。假設第 p 個位置的值是 b，對葉節點就需要看第 BinaryRank(b, p) 的值。繼續遞迴下去就可以得到葉節點是哪個字元。
Char Access(p) :
if Self.isLeaf == True:
return Self.alphabet
CharBit = Self.Bitmap[p]
o = Self.Bitmap.BinaryRank(CharBit, p)
if CharBit == 0:
return Self.nodeL.Access(o)
else:
return Self.nodeR.Access(o)
Wavelet Tree – Rank
遞迴呼叫 bitmap rank 來得到結果。預處理字元集的切分之後可以很容易算出尋找的字元屬於哪個子節點。
Int Rank(c, p):
if Self.isLeaf:
return p
CharBit = (c belong to Self.NodeR)
o = Self.Bitmap.BinaryRank(CharBit, p)
if CharBit == 0:
return Self.nodeL.Rank(c, o)
else:
return Self.nodeR.Rank(c, o)
Wavelet Tree – Select
比較複雜一點，需要經歷兩倍樹高度的呼叫。先取得這個字元的葉節點。再往上使用 bitmap select 來得到字元在字串中的 select 。
Int Select(c, o):
leafNode = rootNode.getLeaf(c)
if leafNode is a left child:
return leafNode.parentNode.BottomUp(0, o)
else:
return leafNode.parentNode.BottomUp(1, o)
Int BottomUp(CharBit, o):
p = Self.Bitmap.BinarySelect(CharBit, o)
if Self == rootNode :
return p
if Self is a left child:
return Self.parentNode.BottomUp(0, p)
else:
return Self.parentNode.BottomUp(1, p)
Huffman-Shaped Wavelet Tree
上圖：原本的字元集 {adfs} 被切分成 {ad} 與 {fs}，然後再對切一次到葉節點。
因為葉節點都是同一個字元不需要儲存，所以對高度 h 的小波樹，空間複雜度是樹的高度乘上字串長度。
但是如果我們可以改變樹的結構，就可以變得更有效率。把字串做 Huffman encoding ，而字元屬於哪個子節點就是他自己的 Huffman code ，這時同時有效率的儲存與找到子節點。這時儲存的空間就是最小可能的 lossless storage 。
不過有個小隱憂在於，Huffman tree 結構假設字串的存取可能性是它在字串中所佔的比例（期望值）。但是如果資料結構所儲存的資料，在使用中的頻率分布與期望值不同時，比起樸素對分的 Wavelet Tree 就會有較差的 average complexity 。當然樸素做法是一個平衡二元樹有比較好的平均函數呼叫次數，但 tradeoff 就是較差的儲存效率。
小結
如果對詳細實作有興趣可以到我寫的 Wavelet Tree Library 看看。我寫的 Wavelet+RRR 結構比 SDSL 還要快。
圖片 Reference:
- picture from “Engineering Rank and Select Queries on Wavelet Trees”, Jørgen K. H. Knudsen, Roland L. Pedersen Published 2015
如果你覺得有收穫，可以用 30 NTD 來支持我繼續創作更多內容。因為做自己喜歡的事而得到報酬，是再好不過的事了。（街口支付）
eopXD 