# String Attractorsを用いたランダムアクセス可能なデータ構造

## 前提
$S$ : テキスト文字列
$n$ : $S$ の文字列長
$\sigma$ : アルファベットサイズ
$\Gamma$ : String Attractorsの要素
$\gamma$ : String Attractorsのサイズ
$w$ : ワードサイズ

とする

$S = s_0s_1 \dots s_{n-1}$ とし、$S[i,j] = s_i s_{i+1} \dots s_j$ とする

## 概要
$\tau \geq 2$ を定数とする
この時、$S$ 中の長さ $l$ の部分文字列の取得を
- 空間 $\mathcal{O} (\gamma \tau \log_{\tau}(n / \gamma))$
- 時間 $\mathcal{O} (\log_{\tau}(n/\gamma)+l \log \sigma / w)$

で行えるデータ構造が構築できる[^1]

以下、$\tau = 2,\ l = 1$ で、複数文字を1wordに詰め込まないような場合を考える
この時、計算量は以下のようになる
- 空間 $\mathcal{O} (\gamma \log (n / \gamma))$
- 時間 $\mathcal{O} (\log (n / \gamma))$

## 構造
以下、$n \equiv 0 \pmod \gamma$ で $\beta = n / \gamma$ を2冪とする(説明の簡略化のため) また、$\alpha = \log_2 \beta$ とする
$\beta/2^i < \alpha$ であるような最小の $i$ を $d$ とする

データ構造の $i$ 段目 $(0 \leq i < d)$ の $j$ ブロック目が表現する文字列を $S_{i,j}$ と表す[^2]

$S_{0, j} = S[j \cdot \beta, (j + 1) \cdot \beta - 1]$ とする
整数の組 $(i, j, k)\ (i \neq 0, 0 \leq j < \gamma, 0 \leq k < 4)$ に対して、$S_{i, 4j+k} = S[\Gamma_j + (k - 2) \times \beta / 2^i, \Gamma_j + (k - 1) \times \beta / 2^i - 1]$ とする[^3]

$S_{i, j} = S[l, r]$ であって $l \leq p \leq r, p \in \Gamma$ であるような任意の $(l, r, p)$ に対して $P_{i, j} = p, O_{i, j} = p - l$ とする[^4]

データ構造では $P, O, S_d$ を保持する

$d$ は $\mathcal{O}(\log(n / \gamma))$ であり、それぞれの段で $P_i, O_i$ は $\mathcal{O}(\gamma)$ 個の要素を保持するため、$P, O$ の空間計算量は $\mathcal{O}(\gamma \log (n / \gamma))$ となる
$S_d$ には $\mathcal{O}(\gamma)$ 個の要素が存在し、それぞれ長さ $\alpha$ の文字列であるため、$S_d$ の空間計算量は $\mathcal{O}(\gamma \alpha) = \mathcal{O}(\gamma \log (n / \gamma))$ となり、全体の空間計算量が $\mathcal{O}(\gamma \log (n / \gamma))$ となる

($\beta/2^i=1$ になるまで分割しても空間 $\mathcal{O}(\gamma \log (n / \gamma))$, 時間 $\mathcal{O} (\log (n / \gamma))$ にはなる)

\
\

## ランダムアクセス
現在の深さを $t$, 現在見ているブロック位置を $u_t$, $S_{t,u_t}$ 中の $v_t$ 文字目に探している文字が存在するとする
$s_x$ を取得したい場合、初期時点では $t=0, u_0=\lfloor x / \beta \rfloor, v_0=x \bmod \beta$ となる

遷移先の $u_{t+1},v_{t+1}$ は $O_{t,u_t},P_{t,u_t}$ を使って定数時間で求める事ができる
遷移を繰り返して最終的に $t=d$ となった時、$S_{d,u_d}$ の $v_d$ 文字目を返せばよい

$d$ は $\mathcal{O}(\log (n / \gamma))$ なため、取得の時間計算量は $\mathcal{O}(\log (n / \gamma))$ になる

## 実装
$n \equiv 0 \pmod \gamma$ でない場合、 $\beta$ が2冪でない場合などでバグる

{%gist shibh308/704a0e88e16fec572db936294b35a113 %}

## 感想など
「データ構造が設計できる」って書いてあるだけで構築計算量が書いてなくて、$(l, r, p)$ の取得を効率的に行う方法が分からない(そもそも存在しなかったりする？)
圧縮全文索引の方は $\mathcal{o}(n^2)$ で構築できるらしいので、後でそっちも読む

[^1]: 初出論文のTheorem 5.3
[^2]: このデータ構造では直接保持しないが、理解のためにあると便利
[^3]: 文字列をはみ出している場合は適当な文字列でパディングする
[^4]: このような $(l, r, p)$ が必ず存在する事はString Attractorsの性質から分かる(パディング文字を含む場合はそのような組が存在しないため無視する)