様々な操作を高速にサポートするデータ圧縮法に関する論文を公開しました。

様々な操作を高速にサポートするデータ圧縮法に関する論文を公開しました。本論文はデータ圧縮に関する国際会議 Data Compression Conference (DCC2015)に採択された論文でarXivから入手出来ます。

Djamal Belazzougui, Travis Gagie, Paweł Gawrychowski, Juha Kärkkäinen, Alberto Ordóñez, Simon J. Puglisi, Yasuo Tabei: Queries on LZ-Bounded Encodings, Data Compression Conference (DCC), 2015. 論文へのリンク(arXiv)

提案法はLempel-Ziv(LZ)法に類似性がありその簡易版になっています。LZ法では各テキスト上の位置より前に出現する部分文字列の最長一致文字をテキスト上の位置と一致した部分文字列の長さで表現することに圧縮を行います。一方、提案法では入力テキストを固定長の部分文字列にチャンク分割したあとで、各チャンクに対して一致する部分列を探して、その位置を記録することにより圧縮を行います。このようにすると圧縮率は低下してしまいますが、提案手法では一致する部分列が見つからなかったチャンクに対して、チャンクをさらに短いチャンクに分割して一致する部分列を発見します。これをチャンクの最小単位まで再帰的に繰り返すことにより圧縮率の低下を抑えます。大きいチャンクからより小さいチャンクに一致文字列が見つからなかったチャンクを再帰的に分割することを繰り返すので、最終的には各ノードがチャンクをもつ木構造が出来上がり、これを保存します。木が持つノード数に対する圧縮率の上限を保証することもできます。

圧縮率に対する保証を持たせることができることの利点に加えて、提案法ではrank/select/access/LCAなどのFM-indexやcompressed suffix tree(CST)などの圧縮データ構造を実装するのに欠かせない操作を定数時間でサポートします。文法圧縮でも、これらの操作をサポートする方法が最近提案されていいますが、構文木の高さ(バランスされている場合、高さlog n, n : テキスト長)の時間がかかってしまうことを考えると、定数時間でこれらの操作をサポートしていることは、提案法のメリットと言えます。

提案法はチャンクをノードにもつ木ですので実装は比較的簡単で、ベンチマークデータ上でも実際に有用性が確認されています。ソースコード整理の都合上、実装の公開はもう少し後になりそうです。