【圧縮文字列索引連載part1】圧縮文字列索引って？

はじめに

本記事から、連載という形で圧縮文字列索引についての現状を紹介しようと思う。

本エントリは、アルゴリズムの詳細には踏み込まずに、圧縮文字列索引とは何か、そしてその研究の経緯について紹介する。加えて、今後書いていく各エントリへのリンクハブという形で運用するつもりである。

はじめに
圧縮文字列索引って？
何に役立つ？
研究の系譜
新たな地平へ
おわりに

圧縮文字列索引って？

圧縮文字列索引とは、文字列を取り扱うデータ構造で、以下の二つの特徴を満たすものである。

サイズが圧縮されており、元の文字列に比べて十分に小さい。
高速な文字列への操作をサポートしている。
- (例)パターンの検索、部分文字列へのアクセス

何に役立つ？

実世界での応用で最も特筆すべきものは、バイオインフォマティクスである。

例えばヒトゲノムは1人あたり30億塩基という巨大なサイズであり、圧縮しつつ高速に解析できることには応用上の意義がある。実際にBowtie*1などのソフトウェアが生み出されている。

他にも巨大な文書集合に対する高速な全文検索エンジンの構築などが挙げられるだろう。

並列化やスケールアップで計算資源を盛ることで解決できてしまうケースも多いので、実世界の問題に対する最適解となることはなかなか難しいというのも現状である。研究の原動力となっているのは、やはり生物学分野との協同、および文字列の圧縮可能性に対する理論的な興味である。

研究の系譜

どういう経緯で研究が進められてきたのかにも言及しておく(自分の理解なので誤りがあるかもしれない)。アルゴリズムの詳細には言及しない。

文字列索引の夜明け

まず、最も多機能でいろんな問題を解ける「接尾辞木」*2が1973年に提案された。ただ、この木構造を素直にポインタで表現すると、索引サイズが元の文字列よりもはるかに大きくなってしまう問題があった。(ノード数が文字列長nに近いので、ポインタで各ノードの親と子を格納するとnlognビットのオーダーになる。接尾辞リンクというものも含めるとさらに大きくなる。)

つまり、最初から多機能性は極まっていたが、もう一方の要件であるサイズがよろしくなかった。

そこで、接尾辞木の機能性を減らす代わりに、構造をシンプルにしつつサイズを大幅に削減した「接尾辞配列(Suffix Array)」*3が1993年に提案された。(ただ、これでもnlognビットであり、巨大な文字列を取り扱う際にはやはりサイズが大きい。)

簡潔データ構造の利用

接尾辞木、接尾辞配列は検索機能こそ優秀だが、どうしても巨大なDNAや文書に構築するには重すぎる。どうにかして機能性を維持しつつ、主記憶に載るぐらいまで圧縮できないものか。

そこで着目されたのが1989年に初めて提案された「簡潔データ構造(Succinct Data Structure)」*4の概念である。簡単に要約すると、「その情報源を表すのに必要な最低限のサイズで、検索操作もサポートする構造」というものである。

それ以来、例えば

ビットベクトル (0と1からなる配列)
順列
木構造

などといったデータに対する簡潔データ構造が研究、提案されてきた。

その成果として生まれたデータ構造たちをコンポーネントとして利用することで、圧縮文字列索引が生み出された。

例えば接尾辞配列を圧縮した「圧縮接尾辞配列(Compressed Suffix Array)」*5、接尾辞木を圧縮した「圧縮接尾辞木(Compressed Suffix Tree)」*6、接尾辞配列と同様の機能を実現するがBurrows-Wheeler Transformという別の概念を用いた「FM-index」*7がこの時期の主要な成果だろう。

より高度な圧縮へ

上に記してきた圧縮文字列索引たちは、従来の文字列索引と比較するとはるかにコンパクトで操作も高速である。

ただ、反復が多い冗長なデータに対しては圧縮効率が頭打ちになることが知られていた。

例えば、1GBの文書を100個くっつけた100GBの文書を考えよう。これは全く同じ情報が100回繰り返されていて非常に冗長であり、その分は圧縮できてほしい。が、上の索引たちはこの冗長性を検出することができず、だいたい100GBの文書に対する索引になる。言い換えると、索引サイズが文字列サイズに比例して大きくなってしまう。

これを検出して圧縮したい、1GBの文書に対する索引と同等にしたい、というのが新たな研究のモチベーションとなった。「反復の多い文字列に対し、劣線形な索引サイズを実現する圧縮文字列索引」が現在の主要な研究対象になっているわけである。

劣線形な圧縮を実現するためのアプローチは複数試されてきた。実用性の評価まで包括的になされている代表例が以下のアプローチである。

Lempel-Ziv圧縮 ( $z$ )
Burrows-Wheeler Transform(BWT)の連長圧縮 ( $r$ )
文法圧縮 ( $g$ )
Compacted Directed Acyclic Word Graph (CDAWG) ( $e$ )

ここで、括弧で付記している記号たちは、その圧縮を施したときの辞書サイズを表すために一般的に使われるものである。

この他にも、文字列の圧縮可能性に対する理論的な興味から出発して（実用性はともかくとして）索引が提案されているアプローチもあり、例としては

String Attractors ( $\gamma$ )*8
( $\delta$ )*9

がある。こちらに付記している記号は、その概念を用いて計算した文字列の冗長性であり、具体的な圧縮手法に基づく数である $z,r,g,e$ とは少し意味が異なる。これらの数の間の関係についてはまた別のエントリで言及する。（結論から言うと、現状提案されているものの中で $\delta$ が最も小さく、その次に $\gamma$ が小さい。 $\delta$ は線形時間計算可能だが、それをベースにした索引は実用性は獲得しておらず、実用性能における最先端はBurrows-Wheeler Transform(BWT)の連長圧縮に基づく索引だろう。）

このように、単一の圧縮手法を洗練させていくのみならず、圧縮手法間での比較、関係の理論的な解明まで含めて「文字列の圧縮可能性」をコミュニティ全体が突き詰めているのが圧縮文字列索引の今というわけだ。

新たな地平へ

導入用エントリの最後の締めとして、この分野における研究の方向性をリストアップしていこうと思う。

索引の検索アルゴリズムの改良。実用的に有用、かつ理論的にも興味深い。
索引の構築アルゴリズムの改良。パターンの検索だけでなく、索引の構築段階も重要である。特に、線形時間で構築できることは一つの重要な基準となる。
数値実験による性能評価・比較。
- 理論的にはとてもコンパクト・高速な索引でも、実際に構築してみると意外に大きい、意外に時間がかかるということは起こりうるので、まだ実装されていない索引を実装してみるだとか、包括的な評価をしてみることには想像以上の実りがある。
計算機向けの最適化。
- 前項にも共通するところだが、計算機の特性(キャッシュなど)を活かしたり、理論的には劣るが実用的には高速な実装をあえて採用したりすることもよく行われている。
理論を進める。
- 新たな反復性の指標の提案。そんなものが存在するのかも分からない難しいトピック。
- 反復性の指標間の関係の証明。ある程度進んでいるが、知り尽くされてはいない。

おわりに

この分野、最初はとっつきにくいのだが、文字列やデータ構造へのイメージが頭の中に定着してくると次第に楽しくなる。興味を持ったらぜひ足を踏み入れてみてほしい。

次回、part2では、接尾辞配列（Suffix Array)について解説しようと思う。

これ自体は圧縮文字列索引ではないが、多くの索引のベースになっている重要な基礎概念なので、最初に理解しておく価値がある。

u-ar.hatenablog.com

*1:http://bowtie-bio.sourceforge.net/index.shtml

*2:Weiner, Peter. "Linear pattern matching algorithms." 14th Annual Symposium on Switching and Automata Theory (swat 1973). IEEE, 1973.

*3:Manber, Udi, and Gene Myers. "Suffix arrays: a new method for on-line string searches." siam Journal on Computing 22.5 (1993): 935-948.

*4:Jacobson, Guy. "Space-efficient static trees and graphs." 30th annual symposium on foundations of computer science. IEEE Computer Society, 1989.

*5:Sadakane, Kunihiko. "New text indexing functionalities of the compressed suffix arrays." Journal of Algorithms 48.2 (2003): 294-313.

*6:Sadakane, Kunihiko. "Compressed suffix trees with full functionality." Theory of Computing Systems 41.4 (2007): 589-607.

*7:Ferragina, Paolo, and Giovanni Manzini. "Indexing compressed text." Journal of the ACM (JACM) 52.4 (2005): 552-581.

*8:Kempa, Dominik, and Nicola Prezza. "At the roots of dictionary compression: string attractors." Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. 2018.

*9:Kociumaka, T., Navarro, G., Prezza, N. (2020). Towards a Definitive Measure of Repetitiveness. In: Kohayakawa, Y., Miyazawa, F.K.