Discovery Sagaサイレントキーワード俯瞰

文字列の高速検索のために用いられるデータ構造である接尾辞木について,それを圧縮したデータ構造を開発した.このデータ構造は従来の接尾辞木でできる操作は全て可能であり,その計算量もほとんどの操作では圧縮前と同じである.このデータ構造により,多くの文字列処理問題を解くために必要なメモリを削減することができる.
Rank/Select辞書とは,順序集合$S in {0,1,...,m-1}$において${it rank}(x,S)=|{y in S|y le x }|$と${it select}(i,S)$($S$の中で$i$番目に小さい要素)を返すデータ構造である.これは文字列,木,グラフなどの圧縮データ構造の基本構成要素であり,多くのデータ構造が提案されている.しかしそれらは漸近的な性能のみを考えており,実データに対する性能は良くない.本研究では単純なRank/Select辞書を提案する.特徴としては,集合$S$の要素数が小さい場合にデータ構造のサイズを縮小できることと,データ構造が単純であるために実装が容易で,実データに対する性能(データ構造のサイズと問い合わせ時間)が良い.実験により,既存の実装よりも速度,サイズともに優れていることを示した.集合$S$は長さ$m$の${0,1}$のベクトル$B[0,m-1]$を用いて表現できる.しかしベクトル$B$をそのまま格納するデータ構造は,$S$の要素数$n$が小さい場合,または多い場合にはサイズに無駄が多い.なぜなら$B$は$m choose n$通りしかないため,$B(n,m)=log{m choose n}approx n log frac{m}{n}+(m-n)log frac{m}{m-n}$ビットで表現できるからである.Ramanら$rank$と$select$を定数時間で求める$B(n,m)+Order(m log log m/log m)$ビットのデータ構造を提案した.本研究で提案するデータ構造は,疎なベクトルに対してデータ構造のサイズが小さくなり,問い合わせ時間は既存のどのデータ構造よりも高速である.