2025/05/09 簡潔データ構造ゼミ

7.4 圧縮接尾辞配列

甲本 健太

7.4   圧縮接尾辞配列
2025/05/09 簡潔データ構造ゼミ

目次

  1. 圧縮接尾辞配列

    1. 圧縮接尾辞配列の概要

    2. 関数 Ψ の性質

    3. 圧縮接尾辞配列上で SA[i] を求める

    4. 圧縮接尾辞配列の計算量

    5. CSA のさらなる省スペース化 / 高速化

    6. CSA の実用上の実装

  2. 自己索引化

7.4   圧縮接尾辞配列
2025/05/09 簡潔データ構造ゼミ

圧縮接尾辞配列の概要 (1/2)

圧縮接尾辞配列 (CSA: compressed suffix array):
→ 接尾辞配列のサイズを小さくしたもの

接尾辞配列との比較

データ構造 サイズ SA[i]\mathit{SA}[i] の計算
接尾辞配列（非圧縮） nlg⁡nn \lg n bits O(1)O(1) 時間
圧縮接尾辞配列 O(nlg⁡σ)O(n \lg \sigma) bits O(lg⁡εn)O(\lg^\varepsilon n) 時間

計算時間について

圧縮接尾辞配列の各要素は polylog(n)\mathrm{polylog}(n) 時間で復元できる[1]．
→ 検索速度はあまり落ちない

[1] polylog(n):=O(lg⁡kn)\mathrm{polylog}(n) := O(\lg^k n)

7.4.1 圧縮接尾辞配列 > 接尾辞配列の圧縮
2025/05/09 簡潔データ構造ゼミ

圧縮接尾辞配列の概要 (2/2)

圧縮接尾辞配列 (CSA) は以下のように実現される．

  1. 接尾辞配列の要素を間引く
    • 任意の自然数 hh に対して，n/hn/h 個の要素のみを格納
    • hh はデータ構造のパラメータ
  2. 間引かれた要素は，関係を用いて表す
    • 残された要素同士の関係を関数 Ψ\mathit{\Psi} で表す

center

7.4.1 圧縮接尾辞配列 > 接尾辞配列の圧縮
2025/05/09 簡潔データ構造ゼミ

関数 Ψ の性質 (1/5)

文字列 TT の接尾辞配列を SA\mathit{SA} とする．このとき Ψ\mathit{\Psi} 関数を次のように定義する．

Ψ[i]:={SA−1[SA[i]+1]if   SA[i]<n,SA−1[1]if   SA[i]=n.\mathit{\Psi}[i] := \begin{cases} \mathit{SA}^{-1}[\mathit{SA}[i] + 1] & \text{if ~ $SA[i] < n$},\\ \mathit{SA}^{-1}[1] & \text{if ~ $SA[i] = n$}. \end{cases}

気持ち

  • SA[i]\mathit{SA}[i]: {T[j..]∣1≤j≤n}\{ T[j..] \mid 1\le j\le n \} を辞書順に並べたとき ii 番目にあたる jj の値
  • SA−1[j]\mathit{SA}^{-1}[j]: T[j..]T[j..] は辞書順で何番目にあたるか

center

  • Ψ[i]\mathit{\Psi}[i]: 辞書順で ii 番目にあたる接尾辞 T[j..]T[j..] から先頭 1 文字を削除した文字列 T[j+1..]T[j+1..] は辞書順で何番目にあたるか
7.4.1 圧縮接尾辞配列 > 接尾辞配列の圧縮
2025/05/09 簡潔データ構造ゼミ

関数 Ψ の性質 (2/5)

T=“banana”T = \text{``banana''} としたときの例．


ii SA[i]\mathit{SA}[i] T[SA[i]..n+1]T[\mathit{SA}[i]..n + 1] SA[i]+1\mathit{SA}[i] + 1 Ψ[i]\mathit{\Psi}[i]
00 77 $ 11 44
11 66 a$ 77 00
22 44 ana$ 55 55
33 22 anana$ 33 66
44 11 banana$ 22 33
55 55 na$ 66 11
66 33 nana$ 44 22
jj SA−1[j]\mathit{SA}^{-1}[j]
11 44
22 33
33 66
44 22
55 55
66 11
77 00
7.4.1 圧縮接尾辞配列 > 接尾辞配列の圧縮
2025/05/09 簡潔データ構造ゼミ

関数 Ψ の性質 (3/5)

関数 Ψ\mathit{\Psi} は補題 7.2 の性質を満たす．

0≤i<j≤n0 \le i < j \le n に対し，T[SA[i]]=T[SA[j]]T[\mathit{SA}[i]] = T[\mathit{SA}[j]] ならば Ψ[i]<Ψ[j]\mathit{\Psi}[i] < \mathit{\Psi}[j]．

定義より Ψ[i]=SA−1[SA[i]+1],Ψ[j]=SA−1[SA[j]+1]\mathit{\Psi}[i] = \mathit{SA}^{-1}[\mathit{SA}[i] + 1], \mathit{\Psi}[j] = \mathit{SA}^{-1}[\mathit{SA}[j] + 1] である．つまり，Ψ[i]\mathit{\Psi}[i] と Ψ[j]\mathit{\Psi}[j] の大小関係は接尾辞 T[SA[i]+1..n+1]T[\mathit{SA}[i] + 1..n + 1] と T[SA[i]+1..n+1]T[\mathit{SA}[i] + 1..n + 1] の辞書順で定義される．
今，T[SA[i]]=T[SA[j]]T[\mathit{SA}[i]] = T[\mathit{SA}[j]] であるため，接尾辞 T[SA[i]+1..n+1]T[\mathit{SA}[i] + 1..n + 1] と T[SA[j]+1..n+1]T[\mathit{SA}[j] + 1..n + 1] の大小関係は T[SA[i]..n+1]T[\mathit{SA}[i]..n + 1] と T[SA[j]..n+1]T[\mathit{SA}[j]..n + 1] の大小関係と等しい． i<ji < j であり，接尾辞配列の定義から T[SA[i]..n+1]<T[SA[j]..n+1]T[\mathit{SA}[i]..n + 1] < T[\mathit{SA}[j]..n + 1] であるため，Ψ[i]<Ψ[j]\mathit{\Psi}[i] < \mathit{\Psi}[j] となる．

気持ち
文字列 S,TS,T について，S<TS < T かつ S[1]=T[1]S[1] = T[1] であるとき，S[2..]<T[2..]S[2..] < T[2..] である．

7.4.1 圧縮接尾辞配列 > 接尾辞配列の圧縮
2025/05/09 簡潔データ構造ゼミ

関数 Ψ の性質 (4/5)


補題 7.2 より，Ψ\mathit{\Psi} 関数は高々 σ\sigma 個の狭義単調増加列に分解できる．
→ 単調増加列の圧縮といえば… Elias-Fano 符号とそれを拡張したデータ構造 GV\mathrm{GV}．

Elias-Fano 符号（イライアス・ファノ符号と読む）は，広義単調増加する非負整数の列に対する符号である．

符号化方法
nn 個の非負整数 0≤x1≤⋯≤xn=u0\le x_1\le \dots\le x_n = u とする．{xi}\{x_i\} の符号は以下のように行う．

  1. xix_i の下位 ss ビットを rir_i，下位 ss ビットを除いたものを qiq_i とする．
  2. {qi}\{q_i\} は広義単調増加になっていることから，
    qiq_i の代わりに直前の値との差分 di:=qi−qi−1d_i := q_i - q_{i - 1} を 1 進数符号で符号化する．
  3. {ri}\{r_i\} は ss ビットの 2 進数で符号化する．

（データ構造 GV は 第 7 回資料 を参照）

7.4.1 圧縮接尾辞配列 > 接尾辞配列の圧縮
2025/05/09 簡潔データ構造ゼミ

関数 Ψ の性質 (5/5)


補題 7.2 より，Ψ\mathit{\Psi} 関数は高々 σ\sigma 個の狭義単調増加列に分解できる．さらに，

Ψ′[i]=T[SA[i]]⋅(n+1)+Ψ[i]\mathit{\Psi}'[i] = T[\mathit{SA}[i]] \cdot (n + 1) + \mathit{\Psi}[i]

と定義すると，Ψ′\mathit{\Psi}' 関数は狭義単調増加関数になる．
（ただし，T[SA[i]]T[\mathit{SA}[i]] は整数にエンコードしてあるものとする．）

center

関数 Ψ′\mathit{\Psi}' はデータ構造 GV を用いて，

  • n(2+lg⁡σ)+O(nlg⁡lg⁡n/lg⁡n)n(2 + \lg\sigma) + O(n\lg\lg n / \lg n) ビットで表現できる．

  • Ψ′[i],Ψ[i],T[SA[i]]\mathit{\Psi}'[i], \mathit{\Psi}[i], T[\mathit{SA}[i]] は定数時間で求まる．

    • Ψ[i]=Ψ′[i] mod (n+1)\mathit{\Psi}[i] = \mathit{\Psi}'[i] \bmod (n + 1)
    • T[SA[i]]=⌊ ⁣Ψ′[i]/(n+1)⌋T[\mathit{SA}[i]] = \lfloor \!\mathit{\Psi}'[i] / (n + 1) \rfloor

    とすればよい．

7.4.1 圧縮接尾辞配列 > 接尾辞配列の圧縮
2025/05/09 簡潔データ構造ゼミ

圧縮接尾辞配列上で SA[i]を求める (1/2)

CSA は，以下の 2 つの情報からなる．

  1. SA の要素で， SA[i]\mathit{SA}[i] が hh の倍数であるもののみからなる配列
  2. 関数 Ψ[i]\mathit{\Psi}[i] を GV で圧縮したもの

このとき，1 に格納されていない SA の要素は次のように求める．

center

例） SA[4]\mathit{SA}[4] を求める

  1. SA[4]\mathit{SA}[4] は格納されている？
    → No.
  2. Ψ[4]=3\mathit{\Psi}[4] = 3，SA[3]\mathit{SA}[3] は格納されている？
    → No.
  3. Ψ[3]=6\mathit{\Psi}[3] = 6，SA[6]\mathit{SA}[6] は格納されている？
    → Yes. SA[6]=3\mathit{SA}[6] = 3
  4. よって，SA[Ψ2[4]]=3\mathit{SA}[\mathit{\Psi}^2[4]] = 3
    SA[Ψ[i]]=SA[i]+1⇒SA[4]=1.\mathit{SA}[\mathit{\Psi}[i]] = \mathit{SA}[i] + 1\Rightarrow \mathit{SA}[4] = 1.
7.4.1 圧縮接尾辞配列 > 接尾辞配列の圧縮
2025/05/09 簡潔データ構造ゼミ

圧縮接尾辞配列上で SA[i]を求める (2/2)


先のページの内容をちゃんと言うと，次のようになる．

配列 SA0\mathit{SA}_0 を用いることで，すべての ii に対して高々 2h−22h - 2 回の Ψ\mathit{\Psi} の計算で SA[i]\mathit{SA}[i] を求めることができる．

j=SA[i]j = \mathit{SA}[i] を求める場合，SA[Ψ[i]]=j+1\mathit{SA}[\mathit{\Psi}[i]] = j + 1 であることから，SA[Ψk[i]]\mathit{SA}[\mathit{\Psi}^k[i]] が hh の倍数である最小の kk を求めればよい．
通常は k≤h−1k \le h - 1 であるが，文字列の末尾で Ψ\mathit{\Psi} を求めると SA\mathit{SA} の値が 11 になるため，さらに h−1h-1 回の Ψ\mathit{\Psi} の計算が必要である．

center

7.4.1 圧縮接尾辞配列 > 接尾辞配列の圧縮
2025/05/09 簡潔データ構造ゼミ

圧縮接尾辞配列の計算量


  • どの要素が SA0\mathit{SA}_0 に格納されているか → 長さ nn のビットベクトル BB で管理
    • B[i]=1B[i] = 1 ならば SA[i]\mathit{SA}[i] が格納されている
    • SA[i]\mathit{SA}[i] は SA0[rank1(B,i)]\mathit{SA}_0[\mathit{rank}_1(B,i)] に格納
  • 計算量:
    h=Θ(lg⁡1+εn)h = \Theta(\lg^{1+\varepsilon}n)（ε\varepsilon は任意の正定数）を仮定すると，
    • Ψ′\mathit{\Psi}' は GV を用いると n(2+lg⁡σ)+O(nlg⁡lg⁡n/lg⁡n)n(2 + \lg\sigma) + O(n\lg\lg n / \lg n) ビットで表現できる
    • BB は FID を用いると B(n/h,n)+O(nlg⁡lg⁡n/lg⁡n)\mathcal{B}(n/h, n)+O(n\lg\lg n/\lg n) ビットで格納可能
      • h=Ω(lg⁡n)h = \Omega(\lg n) より，O(nlg⁡lg⁡n/lg⁡n)O(n\lg\lg n/\lg n) ビット
    • SA0\mathit{SA}_0 は lg⁡n⋅n/h=o(n)\lg n\cdot n/h = o(n) ビットで格納可能
    • SA[i]\mathit{SA}[i] は O(h)=O(lg⁡1+εn)O(h) = O(\lg^{1+\varepsilon} n) 時間で復元可能

以上より，CSA の計算量に関して以下の定理が得られる．

長さ nn ，アルファベットサイズ σ\sigma の文字列の接尾辞配列は，任意の正定数 hh を用いて n(2+lg⁡σ)+O(nlg⁡n/h)+O(nlg⁡lg⁡n/lg⁡n)n(2 + \lg\sigma) + O(n\lg n/h) + O(n\lg\lg n/\lg n) ビットで表現でき，接尾辞配列の 1 つの要素は O(h)O(h) 時間で計算できる．

7.4.1 圧縮接尾辞配列 > 接尾辞配列の圧縮
2025/05/09 簡潔データ構造ゼミ

圧縮接尾辞配列上で SA[i]を求める（疑似コード）

CSA 上で SA[i]SA[i] を求める関数の疑似コードは以下の通り．


アルゴリズム 7.2 csa_lookup(i)\mathit{csa\_lookup}(i): SA[i]\mathit{SA}[i] を求める．

  1. k←0k \leftarrow 0
  2. while B[i]=0B[i] = 0 do
    1. k←k+1k \leftarrow k + 1
    2. i←Ψ[i]i \leftarrow \mathit{\Psi}[i]
  3. end while
  4. j←SA0[rank1(B,i)]−kj \leftarrow \mathit{SA}_0[\mathit{rank}_1(B,i)] - k
  5. if j≤0j \le 0 then
    1. j←j+n+1j \leftarrow j + n + 1
  6. end if
  7. return jj
7.4.1 圧縮接尾辞配列 > 接尾辞配列の圧縮
2025/05/09 簡潔データ構造ゼミ

CSA のさらなる省スペース化 / 高速化

  • 配列 SA0\mathit{SA}_0 をそのまま格納せず，それを再帰的に表現することもできる

    1. SA0\mathit{SA}_0 は長さ n/hn/h の別の文字列 T′T' の接尾辞配列になっている

    2. T′T' の圧縮接尾辞配列を再帰的に作成する

  • これにより，SA[i]\mathit{SA}[i] の復元速度を O(lg⁡n)O(\lg n) 時間から O(lg⁡εn/ε)O(\lg^\varepsilon n / \varepsilon) 時間にすることができる．（ε\varepsilon は任意の定数）

    • h=O(lg⁡n)h = O(\lg n) を仮定？

  • データ構造のサイズは O(nlg⁡σ/ε)O(n\lg\sigma / \varepsilon) ビットになる．

7.4.1 圧縮接尾辞配列 > 接尾辞配列の圧縮
2025/05/09 簡潔データ構造ゼミ

CSA の実用上の実装 (1/2)

※ 1 枚前のスライドとは関係ないです


今までは，SA[i]\mathit{SA}[i] が hh の倍数のときに SA0\mathit{SA}_0 に格納していた
→ ii が hh の倍数のときに SA0′\mathit{SA}_0' に格納するよう，修正

  • メリット:

    • ビットベクトル BB を保持する必要がなくなるため，省スペース
    • B[i]B[i] を求める操作も不要になるため，その分高速になる

  • デメリット:

    • ii が hh の倍数になるまでに Ψ\mathit{\Psi} を計算する回数の上限値が抑えられない
    • 期待値としても，回数が Ψ\mathit{\Psi} の計算回数が 2 倍になる

次ページに，この方針で実装した場合のアルゴリズムを示す．

7.4.1 圧縮接尾辞配列 > 接尾辞配列の圧縮
2025/05/09 簡潔データ構造ゼミ

CSA の実用上の実装 (2/2)

  • SA0′\mathit{SA}_0' : ii が hh の倍数である SA[i]\mathit{SA}[i] のみを格納した配列

アルゴリズム 7.3 csa_lookup2(i)\mathit{csa\_lookup2}(i): SA[i]\mathit{SA}[i] を求める．

  1. k←0k \leftarrow 0
  2. while i mod h≠0i \bmod h \neq 0 do
    1. k←k+1k \leftarrow k + 1
    2. i←a[i]i \leftarrow \mathit{a}[i]
  3. end while
  4. j←SA0′[i/h]−kj \leftarrow \mathit{SA}'_0[i/h] - k
  5. if j≤0j \le 0 then
    1. j←j+n+1j \leftarrow j + n + 1
  6. end if
  7. return jj
7.4.1 圧縮接尾辞配列 > 接尾辞配列の圧縮
2025/05/09 簡潔データ構造ゼミ

自己索引化 (1/4)

7.4.1 項で扱った CSA と通常の SA の比較は以下の通り．

接尾辞配列 圧縮接尾辞配列
配列のサイズ nlg⁡nn\lg n ビット O(nlg⁡σ)O(n\lg\sigma) ビット
SA[i]\mathit{SA}[i] を求める O(1)O(1) 時間 O(lg⁡εn)O(\lg^\varepsilon n) 時間
パタン PP の出現頻度クエリ O(∣P∣lg⁡n)O(|P|\lg n) 時間 O((∣P∣+lg⁡εn)lg⁡n)O((|P| + \lg^\varepsilon n)\lg n) 時間

自己索引とは

  • CSA を用いると配列のサイズは元のテキストと同じオーダーになった
  • 一方，検索のためには元のテキスト TT を保持する必要がある
    → CSA を自己索引化すれば，元のテキストを保持しなくてよい

自己索引:
データを検索するための索引構造で，検索時に元データを必要としないデータ構造

7.4.2 圧縮接尾辞配列 > 自己索引化
2025/05/09 簡潔データ構造ゼミ

自己索引化 (2/4)

復習: SA でのパタン PP の検索

  • SA の 2 分探索で求める．

    1.  接尾辞配列の中央の要素 j=SA[n/2]j = \mathit{SA}[n/2] を求める
    2.  T[j..j+∣P∣−1]T[j..j + |P| - 1] と PP を比較する
       ︙

    ステップ 2 で元のテキスト TT を参照する必要があった．

CSA からの部分文字列の復元

  • 実は，TT の部分文字列 T′(≔T[j..j+∣P∣−1])T' (\coloneqq T[j..j + |P| - 1]) は Ψ′\mathit{\Psi}' 関数から復元できる

    1.  T′T' の 1 文字目 T[j]=T[SA[i]]=⌊ ⁣Ψ′[i]/(n+1)⌋T[j] = T[\mathit{SA}[i]] = \lfloor \!\mathit{\Psi}'[i]/(n + 1) \rfloor
    2.  T′T' の 2 文字目 T[j+1]T[j+1]:
      • Ψ[i]\mathit{\Psi}[i] が T[j+1..n+1]T[j+1..n+1] を表すことを利用する．
      • 疑似コードを次ページに示す．
7.4.2 圧縮接尾辞配列 > 自己索引化
2025/05/09 簡潔データ構造ゼミ

自己索引化 (3/4)


アルゴリズム 7.4 csa_substring(i,ℓ)\mathit{csa\_substring}(i, \ell): 部分文字列 T[SA[i]..SA[i]+ℓ+1]T[\mathit{SA}[i]..\mathit{SA}[i] + \ell + 1] を求める．

  1. for k←1,ℓk\leftarrow 1, \ell do
    1. S[k]←⌊ ⁣Ψ′[i]/(n+1)⌋S[k] \leftarrow \lfloor \!\mathit{\Psi}'[i] / (n + 1) \rfloor T[SA[i]]T[\mathit{SA}[i]]
    2. i←Ψ′[i] mod (n+1)i\leftarrow \mathit{\Psi}'[i] \bmod (n + 1) T[ ⁣Ψ[i]]T[\!\mathit{\Psi}[i]]
  2. end for
  3. return SS

center

7.4.2 圧縮接尾辞配列 > 自己索引化
2025/05/09 簡潔データ構造ゼミ

自己索引化 (4/4)

TT の部分文字列 T[s..t]T[s..t] の復元

  • csa_substring(i,ℓ)\mathit{csa\_substring}(i,\ell) を用いて TT の部分文字列 T[s..t]T[s..t] を復元したい
  • 接尾辞 T[s..n+1]T[s..n + 1] の辞書順が必要
    → 接尾辞配列の逆関数 i=SA−1[s]i = \mathit{SA}^{-1}[s] を計算する必要がある
    • SA−1\mathit{SA}^{-1} も CSA と同様に値を間引いて格納する
    • SA0−1[1..n/h]\mathit{SA}_0^{-1}[1..n/h] を SA0−1[i]=SA−1[ih]\mathit{SA}_0^{-1}[i] = \mathit{SA}^{-1}[ih] とする
      → 高々 2h−22h-2 回 Ψ\mathit{\Psi} 関数を計算すれば SA−1[s]\mathit{SA}^{-1}[s] が求まる
    • 配列 SA0−1\mathit{SA}_0^{-1} は nlg⁡n/hn\lg n/h ビット

自己索引化のまとめ

文字列 TT 中のパタン P[1..m]P[1..m] の存在または頻度問い合わせは，TT の Ψ′\mathit{\Psi}' 関数のみを用いて O(mlg⁡n)O(m\lg n) 時間で行える．また，O(nlg⁡n/h)O(n\lg n/h) ビットの補助データ構造を追加することで（hh は任意の正定数），TT の接尾辞配列の 1 つの要素は O(h)O(h) 時間で計算でき，TT の任意の位置の長さ ℓ\ell の部分文字列は O(ℓ+h)O(\ell + h) 時間で復元できる．

7.4.2 圧縮接尾辞配列 > 自己索引化