string attractors を使った文字列表現

はじめに

string attractors を使った文字列表現について紹介します。

具体的には、明示的に文字列そのものを持たずに、文字列上の任意の位置の文字を取得できるようなデータ構造を string attractors を用いて作る方法を紹介します。

このデータ構造は文字列長が $n$ で string attractor の数が $\gamma$ のときに、空間計算量が $\mathcal{O}(\gamma log(n/\gamma))$ で、文字取得の時間計算量が $\mathcal{O}(log(n/\gamma))$ となっています。
文字列長に比べて string attractor の数が少ないときは有効なデータ構造であると言えます。

また今回紹介するデータ構造は At the Roots of Dictionary Compression: String Attractors の Theorem 14. の実装になります。

string attractors の説明については LZ77 から string attractors を作る を参照してください。

今回の記事の内容を実装したコードは github に置いてあります。

今回扱うサンプルデータ

string attractors とは、ある文字列 $T$ の位置の部分集合です。また $T$ の任意の部分文字列について、その部分文字列と字面が同じ部分文字列のいずれかに string attractors の元が含まれている必要があります。

サンプルとして aaaabbbb という文字列を扱います。

この文字列に対する string attractors の一例は {2, 4} です（先頭の位置を0としています）。

# string attractor の位置を()で示しています
aa(a)a(b)bbb

データ構造の構築

ここで紹介するデータ構造は文字列に対して、階層的に同じような処理を適用していきます。

まずは最初の階層です。とりあえずこれを階層0とします。

文字列 $T$ を $\gamma$ 個の等しいサイズのブロックに分割します。1つのブロックの大きさは $\lceil n/\gamma \rceil$ になります。

今回のサンプルでは $n=8, \gamma=2$ なのでブロックの大きさは4になります。

階層0のブロック [aa(a)a] [(b)bbb]

次にそれぞれのブロックに対して、字面が同じで string attractor を含む部分文字列を探します。ブロックは $T$ の部分文字列なので、条件を満たす string attractor は必ず存在します。

見つけたら、その部分文字列が含む string attractor と string attractor からのオフセットを記録します。この string attractor とオフセットを論文に倣って coordinate と呼びます。coordinate は (string attractor, オフセット) という形式で扱います。

今回は2つのブロックがどちらも既に string attractor を含んでいるので、そのままこれを使います。

階層0のブロック      [aa(a)a] [(b)bbb]
階層0の coordinate (2,2)    (4,0)

ここから階層1です。階層0では文字列　$T$ を分割してブロックを作りました。階層1からはブロックを作る対象が少し変わっています。

まず、それぞれの string attractor の前後に階層0と同じ大きさ（今回の例では4）のブロックをとります。

string attractor は後ろのブロックに含めています。またブロックが文字列をはみ出している場合は * でパディングしています。

階層0のブロック        [aa(a)a]       [(b)bbb]
階層1のブロック      [**aa][(a)abb] [aaaa][(b)bbb]

次にこのブロックを半分に分割します。これが階層1のブロックになります。

階層0のブロック          [aa(a)a]           [(b)bbb]
階層1のブロック      [**][aa][(a)a][bb] [aa][aa][(b)b][bb]

これらのブロックについても coordinate を計算します。パディングしかないブロックは無視します。

階層0のブロック          [aa(a)a]             [(b)bbb]
階層0の coordinate     (2,2)                (4,0)
階層1のブロック      [**][aa][(a)a][bb]   [aa][aa][(b)b][bb]
階層1の coordinate (-,-)(2,0)(2,0)(4,0) (2,0)(2,0)(4,0)(4,0)

階層2以降は階層1と同様にブロックを作っていきます。毎回ブロックサイズが半分になるのでブロックサイズが適当な閾値以下になったら処理を中断してブロックの中身をそのまま保存します。

今回はブロックサイズが1になるまで分割しています。

階層0のブロック          [aa(a)a]             [(b)bbb]
階層0の coordinate     (2,2)                (4,0)
階層1のブロック      [**][aa][(a)a][bb]   [aa][aa][(b)b][bb]
階層1の coordinate (-,-)(2,0)(2,0)(4,0) (2,0)(2,0)(4,0)(4,0)
階層2のブロック      [a][a][(a)][a]       [a][a][(b)][b]
階層2の coordinate (-,-)(2,0)(2,0)(2,0) (2,0)(2,0)(4,0)(4,0)

これで処理は終わりです。最後の階層の中身と、全部の階層の coordinate だけを持っておけばOKです。

階層0の coordinate     (2,2)                (4,0)
階層1の coordinate (-,-)(2,0)(2,0)(4,0) (2,0)(2,0)(4,0)(4,0)
階層2の coordinate (-,-)(2,0)(2,0)(2,0) (2,0)(2,0)(4,0)(4,0)
階層2のブロック      [a][a][(a)][a]       [a][a][(b)][b]

結局何をやっていたかというと、 string attracftor 周辺の部分文字列だけ直接保存し、それ以外の部分は string attractor へのリンク（coordinate）だけ持たせる、ということをしていたのでした。

今回の例だと文字列が短すぎて文字列をそのまま持った方がデータが小さくなっていますが、string attractor が文字列に比べて小さい場合はデータ構造のほうが小さくなります。

データ構造の空間計算量

ここで空間計算量の整理をしておきます。

階層0は $\gamma$ 個の coordinate があります。それ以外の階層は $4\gamma$ 個の coordinate があります（string attractor の前後にブロックをとって、そのブロックを半分に分割しているので4倍になります）。従って各階層での corodinate の計算量は $\mathcal{O}(\gamma)$ です。

階層0はブロックの大きさが $n/\gamma$ でこれがどんどん半分になっていくので階層の数は高々 $log_2(n/\gamma)$ になります。従って階層全体での coordinate の計算量は $\mathcal{O}(\gamma log(n/\gamma))$ です。

最後の階層はブロックの中身も保存していたのですが、これはブロックの大きさが $\log_2(n/\gamma)$ を下回ってから分割をやめるようにすれば計算量は $\mathcal{O}(\gamma log(n/\gamma))$ になり、階層全体の coordinate の計算量と同じになります。

なのでトータルでの空間計算量は $\mathcal{O}(\gamma log(n/\gamma))$ です。

指定した位置の文字の取得

ここからは位置を指定して、その位置の文字を取得する様子を紹介します。

まず、今回作ったデータ構造を再掲します。

階層0の coordinate     (2,2)                (4,0)
階層1の coordinate (-,-)(2,0)(2,0)(4,0) (2,0)(2,0)(4,0)(4,0)
階層2の coordinate (-,-)(2,0)(2,0)(2,0) (2,0)(2,0)(4,0)(4,0)
階層2のブロック      [a][a][(a)][a]       [a][a][(b)][b]

ではこのデータ構造を使って6番目の文字を取得してみます。

まず階層0の対応する coordinate を見つけます。階層0はブロックを $\lceil n/\gamma \rceil$ （今回のサンプルだと4）ごとに分割していました。なので6番目の文字は2つ目のブロックが対応しているはずです。また、6番目の文字は2つ目のブロックでは2番目の文字になっているはずです。

[??(?)?][(?)???]
          ↑
このブロックの2文字目に欲しい文字がある

そしてこのブロックと字面が同じで、かつ string attractor を含んでいる部分文字列の情報は coordinate が持っています。

階層0の coordinate  (2,2) (4,0)
                           ↑
                         こっち

2つ目の coordinate は　(4,0) です。この coordinate から、対応する string attractor は4で、オフセットは0であることがわかります。
これは階層0での2つ目のブロックに字面が一致する部分文字列が文字列 $T$ の4文字目からはじまっていることを意味します（今回の場合 $T$ の4文字目からはじまっている部分文字列は、階層0の2つ目のブロックそのものなのですが）。

階層1のブロックは string attractor の前後に2つずつ持っていました。また string attractor 自身は3つ目のブロックに含めていました。

先ほどの coordinate の情報から string attractor からのオフセットが0であることがわかっています。また階層0でのブロックの先頭から2文字目に欲しい文字があることもわかっています。なので、4つ目のブロックの先頭に欲しい文字があることがわかります。

[??][??][(?)?][??]  [??][??][(?)?][??]
                                    ↑
                  このブロックの0文字目に欲しい文字がある

階層1の coordinate は以下のようになっていました。対応する coordinate は (4,0) です。またしても対応する string attractor は4で、オフセットは0となっていることがわかりました。

階層1の coordinate (-,-)(2,0)(2,0)(4,0) (2,0)(2,0)(4,0)(4,0)
                                                        ↑
                                                       これ！！

string attractor からのオフセットは0で、さらに階層1では欲しい文字はブロックの先頭にあったので、階層2では string attractor がある位置が欲しい文字のある位置になっています。
そして、階層2は最後の階層なので文字列をそのまま持っています！

[a][a][(a)][a]       [a][a][(b)][b]
                             ↑
                           欲しい文字はこれだ！！

というわけで6番目の文字は b であるということがわかりました。めでたしめでたし。

文字取得の時間計算量

文字取得において、各階層での coordinate の決定は定数時間で行うことができます。また階層の数は既に述べたように $\log_2(n/\gamma)$ です。

従って文字取得の時間計算量は $\mathcal{O}(log(n/\gamma))$ となります。

おわりに

この記事では string attractors を使った文字列表現について紹介しました。

基本的には論文の定理に従った実装の具体例となっていますが、いくつか省略した部分もあります。結構複雑なデータ構造なので、少しでも読む敷居を下げたかったからです。

論文では具体例が書かれていないので、理解するのが大変でした。この記事が論文を読む手助けとなれば幸いです。

以上です。