LZ77 + Hybrid Indexing - m-shijou’s diary

Hybrid Indexing Revisited (ALENEX2018) で用いられているアルゴリズムについて説明します。

この論文の筆者らは、先行研究においてHybrid Indexingという圧縮全文索引を提案していました。
[1306.4037] Hybrid Indexes for Repetitive Datasets
https://royalsocietypublishing.org/doi/abs/10.1098/rsta.2013.0137
ALENEX2018の論文では、その提案手法が他のいくつかの索引手法と比べて優れていることを様々な実データで定量的に実証しています。実装は以下のリポジトリにあります。
github.com

この記事では準備としてLZ圧縮について述べたあと、Hybrid Indexingそのものについて説明します。

LZ圧縮(or LZ分解)

LZ圧縮は辞書式圧縮という文字列圧縮手法の一つです。（LZ圧縮とLZ分解は異なる概念ですが、以降の文では気にせず全てLZ圧縮と書いています）具体的には、文字列を頭から順番に見ていって、以前に登場した部分文字列を見つけたら、その部分文字列の開始位置と長さで置き換えます。詳しく言うと、ある文字iから始まるsuffixが、j<iなるjから始まるsuffixと長さkのcommon prefixを持つとき、部分文字列[i,i+k)をタプル(j,k)で置き換えます。jが存在しない場合は(文字、0)としたり置き換えなかったりします。jが存在しない場合の具体的な扱いによってLZ77の他にLZSSなどいろいろなバリエーションがありますが、今回は特に気にせずに説明します。以下の説明では文字の添字は0-originとします。

例えば"abcabcd"をLZ圧縮すると、"(a,0),(b,0),(c,0),(0,3),(d,0)"となります。最初の3文字は初出なのでそのまま出力しています。3番目からのsuffixは0番目からのsuffixと長さ3のcommon prefixを持つので、第4項でそれを表しています。6文字目は初出なのでそのまま出力しています。

（論文中の例ですが）例えば"zzzzzapzap"をLZ圧縮すると、"(z,0),(0,4),(a,0),(p,0),(4,3)"となります。この例のポイントは第2項で、置き換えが発生する際に自分自身の一部を参照するような置き換えが許されています。もしそのような置き換えが許されないならば、"(z,0),(0,1),(0,2),(0,1),(a,0),(p,0),(4,3)"などとせざるを得ず、圧縮効率が悪くなります。（ちなみにLZ系の他の亜種ではこれの扱いが色々異なります）とはいえ、Hybrid IndexingにおいてはLZ77圧縮がどんなに非効率な形であっても全文検索の出力は等価で計算時間と索引の大きさが変わるだけです。

Observation

以降、リファレンス文字列Rにおけるクエリ文字列Qの完全一致検索クエリを考えます。複数の完全一致があるとき、一致箇所がオーバーラップしているものも含めて全て報告するとします。（例えばR="zzzzzapzap"、Q="zzz"のとき、[0,3),[1,4),[2,5)の3箇所で一致するとします。）クエリ文字列の長さは一定値とし、Mとします。M>1とします。ここでObservationとして、R上でEから始まる部分文字列[E,E+M)がQと完全一致するとき

[E,E+M)はRをLZ圧縮したときの項と項の境界をまたがない ⇒ Eより前に他の完全一致箇所が存在する

が成り立ちます。これは自明でして、LZ圧縮の2文字以上の項は、それより前の文字列との完全一致箇所だからです。

そして、このObservationの対偶は

[E,E+M)はR上で最初に出現する完全一致である ⇒ [E,E+M)はRをLZ圧縮した時の項と項の境界をまたぐ

となります。

例えばリファレンス文字列"abcabcd"からクエリ文字列"ab"を探したいとします。リファレンス文字列をLZ圧縮すると"(a,0),(b,0),(c,0),(0,3),(d,0)"となります。[3,5)は完全一致であり、LZ圧縮の第4項に完全に含まれますが、実は[3,5)より前にも完全一致箇所[0,2)が存在します。[0,2)は最初の完全一致ですが、LZ圧縮の第1項と第2項にまたがっています。

ちなみに逆は成り立ちません。例えばR="faabcdefcdefabcd"とすると、LZ圧縮は(f,0),(a,0),(1,1),(b,0),(c,0),(d,0),(e,0),(0,1),(4,4),(2,4)となります。ここでQ="fa"とすると完全一致箇所は[0,2),[11,13)の2つですが、両方とも境界をまたいでいます。

Kernel Sequence

LZ圧縮の項のうち、(M*2-1)文字以上の項に関して、両端(M-1)文字だけを残して真ん中はダミー文字で置き換えた文字列をKernel Sequenceと呼びます。

例えばR="abcdefghijabcdefghij"でM=3のとき、ダミー文字を#とするとK="abcdefghijab#ij"となります。リファレンス文字列の中に完全な長い反復が大量に存在するとき、Kernel Sequenceは非常に短くなり得ます。

Kernel Sequence上で既存の（FM-indexなどを使った）完全一致検索を行うと、RとQの完全一致箇所が1つ以上存在するならば、少なくとも最初の完全一致は必ず見つかることが前述のObservationにより言えます。ここで見つかった一致箇所をPrimary Matchと呼ぶことにします。

Secondary Match

少なくとも最初の完全一致は必ず見つかりますが、2つ目以降の完全一致(Secondary Match)は見つからない場合があります。それは完全一致箇所がダミー文字で潰された領域を含む場合です。ここで追加のデータ構造としてRMQを使えばSecondary Matchを高速に全て見つけられます。

(M*2-1)文字以上の各項[i,j)について、開始位置と終端位置の組(i,j)を集めたとします。（ここでi,jと言っているのは参照している先の番号です。例えばR="abcdefghijabcdefghij"でM=3のとき、(i,j)=(0,10)のことです。(10,20)ではありません）ここで高速に実行したいクエリは、既に見つかっている完全一致箇所[s,e)に対して、 $i \leq s \lt e \leq j$ なる項(i,j)を全て見つけることです。それができれば、項[i,j)には完全一致箇所が含まれることがわかります。見つけた(i,j)で再帰的に同じクエリを投げて深さ優先探索的なことをやれば、全ての完全一致箇所を得ることができます。

方法ですが、まずすべての(i,j)をiで昇順にソートします。iが同じ場合のjの順番は気にしなくても良いです。RMQを使えば、 $0 \leq i \leq s$ の範囲内におけるjの最大値とそのときの(i,j)のインデックスを高速に得られます。得た(i,j)のjがe以上ならば、インデックスの前後で区切って再帰的にRMQを投げることで、 $i \leq s \lt e \leq j$ なる項(i,j)を全て見つけられます。

まとめ

Kernel Sequence上のFM-index（あるいは他の既存の全文索引）とRMQ用のデータ構造を組み合わせることで、完全一致検索を行えます。LZ圧縮がうまく働くような文字列に対して、もともとの文字列でFM-indexを作るよりも索引の容量が小さくなる利点があります。また計算時間も（ALENEX2018の論文によると）低く抑えられます。