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] の計算
接尾辞配列(非圧縮) nlgnn \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(lgkn)\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]:={SA1[SA[i]+1]if   SA[i]<n,SA1[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..]1jn}\{ T[j..] \mid 1\le j\le n \} を辞書順に並べたとき ii 番目にあたる jj の値
  • SA1[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 SA1[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 の性質を満たす.

0i<jn0 \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]=SA1[SA[i]+1],Ψ[j]=SA1[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 個の非負整数 0x1xn=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:=qiqi1d_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(nlglgn/lgn)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] = 3SA[3]\mathit{SA}[3] は格納されている?
    → No.
  3. Ψ[3]=6\mathit{\Psi}[3] = 6SA[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]+1SA[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 に対して高々 2h22h - 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 を求めればよい.
通常は kh1k \le h - 1 であるが,文字列の末尾で Ψ\mathit{\Psi} を求めると SA\mathit{SA} の値が 11 になるため,さらに h1h-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=Θ(lg1+εn)h = \Theta(\lg^{1+\varepsilon}n)ε\varepsilon は任意の正定数)を仮定すると,
    • Ψ\mathit{\Psi}' は GV を用いると n(2+lgσ)+O(nlglgn/lgn)n(2 + \lg\sigma) + O(n\lg\lg n / \lg n) ビットで表現できる
    • BB は FID を用いると B(n/h,n)+O(nlglgn/lgn)\mathcal{B}(n/h, n)+O(n\lg\lg n/\lg n) ビットで格納可能
      • h=Ω(lgn)h = \Omega(\lg n) より,O(nlglgn/lgn)O(n\lg\lg n/\lg n) ビット
    • SA0\mathit{SA}_0lgnn/h=o(n)\lg n\cdot n/h = o(n) ビットで格納可能
    • SA[i]\mathit{SA}[i]O(h)=O(lg1+εn)O(h) = O(\lg^{1+\varepsilon} n) 時間で復元可能

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

長さ nn ,アルファベットサイズ σ\sigma の文字列の接尾辞配列は,任意の正定数 hh を用いて n(2+lgσ)+O(nlgn/h)+O(nlglgn/lgn)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. k0k \leftarrow 0
  2. while B[i]=0B[i] = 0 do
    1. kk+1k \leftarrow k + 1
    2. iΨ[i]i \leftarrow \mathit{\Psi}[i]
  3. end while
  4. jSA0[rank1(B,i)]kj \leftarrow \mathit{SA}_0[\mathit{rank}_1(B,i)] - k
  5. if j0j \le 0 then
    1. jj+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 の別の文字列 TT' の接尾辞配列になっている

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

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

    • h=O(lgn)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 に格納していた
→ iihh の倍数のときに SA0\mathit{SA}_0' に格納するよう,修正

  • メリット:

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

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

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

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

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

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

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

  1. k0k \leftarrow 0
  2. while imodh0i \bmod h \neq 0 do
    1. kk+1k \leftarrow k + 1
    2. ia[i]i \leftarrow \mathit{a}[i]
  3. end while
  4. jSA0[i/h]kj \leftarrow \mathit{SA}'_0[i/h] - k
  5. if j0j \le 0 then
    1. jj+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 の比較は以下の通り.

接尾辞配列 圧縮接尾辞配列
配列のサイズ nlgnn\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(Plgn)O(|P|\lg n) 時間 O((P+lgεn)lgn)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+P1]T[j..j + |P| - 1]PP を比較する
       ︙

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

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

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

    1. TT' の 1 文字目 T[j]=T[SA[i]]= ⁣Ψ[i]/(n+1)T[j] = T[\mathit{SA}[i]] = \lfloor \!\mathit{\Psi}'[i]/(n + 1) \rfloor
    2. TT' の 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 k1,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=SA1[s]i = \mathit{SA}^{-1}[s] を計算する必要がある
    • SA1\mathit{SA}^{-1} も CSA と同様に値を間引いて格納する
    • SA01[1..n/h]\mathit{SA}_0^{-1}[1..n/h]SA01[i]=SA1[ih]\mathit{SA}_0^{-1}[i] = \mathit{SA}^{-1}[ih] とする
      → 高々 2h22h-2Ψ\mathit{\Psi} 関数を計算すれば SA1[s]\mathit{SA}^{-1}[s] が求まる
    • 配列 SA01\mathit{SA}_0^{-1}nlgn/hn\lg n/h ビット

自己索引化のまとめ

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

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