数理解析研究所講究録
第 1849 巻 2013 年 18-21

18

部分文字列最大密度索引

Indexing maximum densities of characters in substrings of asparse string
酒井義文*
東北大学大学院農学研究科

Yoshifumi Sakai
Graduate School of Agricultural Science, Tohoku University,
Sendai 981-8555, Japan
最近，Moosa と Rahman [3] は，2 値アルファ

概要を記号が回現れる長さ の文字列とする．
$S$ 中の各にはやに依存しない整数の重みが与えられているとする．1 からまでの各区間幅
重み$w$ に対する $S$ の幅 $w$ の連続領域におけるの総和の最大値をすべて求めるアルゴリズムを提案する．このアルゴリズムの実行時間は， の重み$S$$\sigma$

$k$

$n$

$k$

$n$

$\sigma$$n$$\sigma$$\sigma$がすべて 1 である場合，$O(n+ \min(k^{2}/\log k,$ $(n-$の重みがすべて自然数である$O(n+k^{2}/\logk),$の重みがすべて整数で場合，$k)^{2}/\log(n-k))),$$\sigma$$\sigma$ある場合， (
$O$

1$n+k^{2}$log log ) である．
$k$

はじめにを記号 が 回現れる長さ の任意の文字列$S$ に現れる各にはやに依存しないとする．
任意の整数の重みが与えられているとする．1 から$S$ の幅
$W_{S,\sigma}(w)$までの各区間幅 $w$ に対して，で，$w$ の連続領域におけるの重みの総和の最大値を$[W_{S,\sigma}(1), W_{S,\sigma}(2), \ldots, W_{S,\sigma}(n)]$要素配列表す．
$S$$\sigma$

$k$

$n$

$\sigma$

$n$

$k$

$n$

$\sigma$$n$を，$W_{S,\sigma}$索引とよぶ．本稿では，与えられた文字索引を求める問題について考える．この問題を解くアルゴリズムは，たとえば区間幅に依存する閾値よりも大きな重みつき出現頻度で特定の記号が現れる最大区間幅をもつ連続領域を見つけ出すことに利用できるため，データマイニン
グやパターン認識、 分子生物学などの様々な分野において多くの応用をもつと考えられる．たとえば，
図 1 を見られたい．

列 $S$ に対して

$W_{S,\sigma}$

ベット文字列の置換マッチング問題を解くための索引を求める
前処理アルゴリズムとして，$W_{S,\sigma}$$O(n^{2}/\log n)$

時間アルゴリズムを提案した．このアルゴリズムは，再帰的に 2 つの部分問題と 1 つの和最小値畳込み計算に分割することで問題を解く．ここで，2 つの $m$ 要素ベクトル$\langle a0,$$a_{1},$$\ldots,$$a_{m-1}\rangle.$に対する和最小値畳込みは，$c_{j}=$ mino $\leq j\leq\iota(a_{j}+b_{i-j})$ である $m$ 要素ベクト
ノレ...
であり，Bremner ら [1] の方$O(n^{2}/\logn)$ 時間で得ることができ法を用いるとる．本稿では，ベクトルの要素の順番を入れ替えた$m$ 要素ベクト
り添え字を変更することによって，ノレに対する和最$\langle b_{0},$$b_{m-1}\rangle$$b_{1},$$\ldots,$$\langle c_{0},$$c_{1},$$\langle a_{1},$$a_{2},$$c_{m-1}\rangle$$a_{m}\rangle,$$\langle b_{1},$$\ldots,$$b_{2},$$b_{m}\rangle$$\ldots,$小値畳込みを，$c_{\dot{\eta}}= \min_{i\leq j\leq m}(oj+b_{j-i+1})$

る $m$ 要素ベクトル$\langle c_{1},$$c_{2},$$c_{m}\rangle$$\ldots,$と扱う．また，．

$c_{i}= \max_{i\leq j\leq m}(aj+b_{J-i+1),\mathcal{C}_{i}}=\min_{i\leq j\leq m}(aj-$$b_{j-i+1})$, $ci= \max_{i\leq J\leq m}(a-b)$ である $m$ 要,,をそれぞれ，和最大値畳込み，差最小値畳込み，差最大値畳込みとよぶ．
ただし，これらを求める計算を一括して和最小値畳込み計算とよび，Bremner ら [1] の方法を用いて素ベクトル$\langle c_{1}$$c_{2},$$\ldots$$c_{m}\rangle$$O(m^{2}/\log m)$ 時間で実行されるものと仮定する．

本稿では，索引を求める単純なアルゴリ
ズムを提案する．このアルゴリズムは，Moosa とRahman[3] のアルゴリズムと同様に Bremner ら$W_{S,\sigma}$$\backslash$[1] の方法を用いるものの，和最小値畳込み計算を再帰的に何度も実行するのではなく，高々 1 回しか実行しない．提案するアルゴリズムの漸近的な実行時間は， の重みがすべて 1 である場合，$\sigma$$O(n+ \min(k^{2}/\log k, (n-k)^{2}/\log(n-k)))$“Email: sakai@biochem.tohoku.ac jp

であ.

$\sigma$の19$1 2 3 4 5 6 7 8 9 1011 121314151617181920212223242526$

AGTTACTGGCAAAGTGACATGACGTG
ATTTGCTGGTCTAGTTACTTCGCGAG

$A$

$B$

$S A\star TT\star CTGG_{1}^{\star} \star \star AGT\star AC\star T\star \star c1G\star G$

図 1 2 本の文字列 $A,$ $B$ のコンセンサス文字列 $S$ の例．ただし，$A$ と $B$の対応する位置の記号が不一致であることを $S$ では記号 で表す．もしも $S$ において区間幅 $w$ に対して $w^{0.75}$ を超える個数の を$\star$$\star$含む最大区間幅の連続領域をと $B$ の非類似領域として求めたいならば，見つけなければならないのは$A$

下カッコで示された $1O$ 番目の文字から 22 番目の文字までの区間幅 13 の領域である．2 番目に広い区間幅をもつ領域は，9 番目，10 番目，19 番目の文字を左端とする幅 4 の 3 つの領域である．記号 に対索引が利用可能ならば，これらの領域を の長さの線形時間で$\star$する重みをすべて 1 とした場合の$S$$W_{S,\star}$求めることができる．

重みがすべて自然数である場合，$O(n+k^{2}/\log k),$log log )の重みがすべて整数である場合， ($\sigma$$O$$n+k^{2}$$k$である．したがって， に が疎にしか現れない場
合 (あるいは， の重みがすべて 1 であるときは，$S$$\sigma$

補題 2$1\leq w\leq n$である任意の区間幅$w$

に対しはまたは $W_{S,\sigma}(w-1)+1$て，のどちらかに等しい．ただし，$W_{S,\sigma}(0)=0$ とする．
$W_{S,\sigma}(w-1)$$W_{S,\sigma}(w)$$\sigma$$S$に$\sigma$が密に現れる場合においても), 提案するア

ルゴリズムを用いることで，Moosa と Rahman[3]のアルゴリズムと比較して高速に恥，。索引を求め

証明 長さがちょうど 1 だけ異なり一方がもう．一方の接頭辞あるいは接尾辞である任意の 2 つの文字列において， が現れる回数の差は また 1 である．
$0$$\sigma$

ることができる．

したがって，補題は成立する．口2

アルゴリズム

この補題と $W_{S,\sigma}(n)=k$ より，索引は 要
素配列 $[w(1), w(2), \ldots, w(k)]$ として表せる．ただ2. 1

単純な $O(n^{2}/\log n)$ 時間アルゴリズム$k$$W_{S,\sigma}$$w(i)$ は $W_{S,\sigma}(w)=i$ である最小のし，索引は，以下の補題より， 要素ベクトルに対する 1 回の和最小値畳込み計算にょり得られる．
$W_{S,\sigma}$

この $k$ 要素配列を $n$ 要素配列である$n$$O(n)$である任意の添え字 に対して， が $S$ の長さ である接頭辞における の重みの総和に等しく， が $S$ の長さ1 である
接頭辞における2 つの$1\leq i\leq n$$i$

次の補題より，索引を求める $O(n+k^{2}/\log k)$

時間アルゴリズムを直ちに得ることができる．

$\sigma$$\sigma$

要素ベクトルの重みの総和に等しい-$\langle a_{1)}a_{2},$$a_{n}\rangle,$$\ldots,$$\langle b_{1},$$n$$b_{2},$$b_{n}\rangle$$\ldots,$の差$\langle W_{S,\sigma}(1),$$W_{S,\sigma}(2),$$\ldots,$の区間幅が $w$ である任意の連続領域に対し
$i$

$i$

$S$

$j$の接頭辞を削除することで得られるから，この領-域に現れる$i$$w$の重みの総和は $aJ-b_{j-w+1}$ に等しい．
したがって，補題は成立する．口2.2 単位重みの場合$\sigma$

中の$S$$k$個の$\sigma$$\sigma$の重みをすべて 1 とする．

$W_{S,\sigma}$

$i$

索引を求

める $O(n+k^{2}/\log k)$ 時間アルゴリズムと $O(n+$$(n-k)^{2}/\log(n-k))$ 時間アルゴリズムを与える．

これらのアルゴリズムは以下の補題に基づく．

を先頭から順に$1\leq i\leq k$ である任意とする．

$\sigma_{k}$$\ldots,$の添え字に対して， と $b_{i}+1$ がどちらも$a_{i}$の出現位置に等しい 2 つのは，$\langle w(1),$$w(2),$ $\ldots,$ $w(k)\rangle$

要素ベクトル,の差最小値畳込みに等しい．

証明$w(i)$

は， においてがちょうど$(a_{1},$ $a_{2},$$w+1$ 文字目から 文字目て，この領域が の$w-\leq i\leq n$はまでの範囲ならば，を満たす．また，この領域は の長さ の接頭辞から長さ$i$$\sigma_{2},$$W_{S,\sigma}(n)\rangle$に等しい．

$S$$\sigma_{1},$$\sigma_{i}$最大値畳込みは，$S$

補題 3

$i$

$b_{i}$

記号

索引に

$i$

$a_{i}$

証明である．

時間で変換することは容易である．よって，$W_{S,\sigma}$

補題 1

$w$

$W_{S,\sigma}$$a_{k}\rangle,$$\langle b_{1},$$\ldots,$$b_{2},$$\ldots$$S$$\sigma$$k$$b_{k}\rangle$$i$回現れる連続領域の最小区間幅に等しい．$i\leq i\leq k$ である
任意の添え字 に対して， におけるから$S$$i$のまでのちょうど 個の$\sigma j-i+1$を含む最小区間幅の連$S$ の長さ$b_{j-i+1}$ のの接頭辞から長さ$aJ$続領域は，$i$$\sigma$接頭辞を削除することで得られる．この連続領域の区間幅は $aj-b\prime J-i+1$ に等しい．よって補題は成立する．口$n-k$ 個の要素からなる配索引は，
列 $[w’(1), w’(2), \ldots, w’(n-k)]$ として表せる．ただ同様に，$W_{S,\sigma}$$w’(i)$ は $w-W_{S,\sigma}(w)=i-1$ である最大のし，ある．この $n-k$ 要素配列を$W_{S,\sigma}$$w$で索引に $O(n)$ 時20間で変換することは容易である．よって，次の補題

より，$W_{S,\sigma}$索引を求める $O(n+(n-k)^{2}/\log(n-k))$$\langle a_{1},$$a_{2},$

和が$\tau_{1},$$\tau_{2},$$\ldots,$$\tau_{n-k}$

$1$

$i$

$\tau_{i}$$\langle a_{1},$$a_{2},$$a_{n-k+1}\rangle$$\ldots,$$\tau_{i-1}$$\langle b_{1},$$b_{2},$$\langle w’(1),$$\ldots,$$b_{n-k+1}\rangle$$n\rangle$$\ldots,$$\tau_{0},$$0,$$w’(i)$

は， において$S$$\tau$がちょうど $i-1$ 回$i\leq j\leq$現れる連続領域の最大区間幅に等しい．
$S$ にお$k+1$ である任意の添え字 $j$ に対して，$n$までのちょうど $i-1$ 個の$S$ の長さ$aj$ の接を含む最大区間幅の連続領域は，$-\tau_{j-\ovalbox{\tt\small REJECT}+1}$

けるから$\tau$$\tau_{j-1}$

頭辞から長さ $b_{j-i+1}$ の接頭辞を削除することで得に等られる．この連続領域の区間幅は $a-b$
しい．よって補題は成立する．口2.3 自然数重みの場合$S$ 中の各の重みを や に依存しない任意の索引を求めることのでき自然数である場合にる $O(n+k^{2}/\log k)$ 時間アルゴリズムを与える．
$n$$\sigma$$k$$W_{S,\sigma}$$\sigma$$0\leq W_{S,\sigma}(1)\leq$の重みが正であることから，が成立する．
$l=W_{S,\sigma}(n)$ とすると，
索
このことから，$[w(1),w(2),\ldots,w(l)]$として表要素配列
引は，$S$ においての重みの総$w(i)$ は，せる．ここで，$W_{S,\sigma}$$b_{l}\rangle$$\ldots,$$k$個の$l$の差最小値畳込みは，して， の定義より， の$S$である．このを$\sigma$以上である連続領域の最小区間幅である．
この要素配列は，前節で導入した 要素配列$[w(1), w(2), \ldots, w(k)]$ の自然な拡張になっている．
$k$

$l$

$W_{S,\sigma}$$W_{S,\sigma}$である任意の添え字 に対して， が $S$ において の重みの総和が 以上である接頭辞の最小区間幅に等しい 要素ベクトル$1\leq i\leq l$

$i$

$i$

$\sigma$$l$$\sigma$とする．このとき，$1=$$S$$\sigma$である．この$\sigma$を$\sigma_{y(i)}$とする．
$i$$w(i)$$1\leq i\leq l$ である任意の添え字とする．
を，は $S$ において$\sigma$の重みの総和が$i$以上である連続領域の最小区間幅であるから，$1\leq y\leq x\leq k$ある添え字 $y,$が存在して， における
$S$

$x$

$\sigma_{y}$でからまでの連続領域の区間幅は $w(i)$ であり，この領の重みの総和は 以上である． を域における$\backslash$$\sigma_{x}$$i$$\sigma$$i$$x(j)=x$ である最大の添え字とする．したがって，$S$ のを末尾とする接頭辞における の重みの総和はちょうど である．
$y(j-i+1)=y$ であ$\sigma$$\sigma_{x(j)}$$i$

ることを以下に示す．定義より， の $b_{j-i+1}+1$$S$$b_{j-i+1}$
文字目の記号は $\sigma_{y(j-1+1)}$ である．また，$S$ においての重みの総和が $j-i$ 以下であは，$\sigma$る接頭辞の最大区間幅に等しい．したがって， の$S$$\sigma_{y(j-i+1)}$

から重みの総和は$S$

る$S$までの連続領域における$\sigma_{x(j)}$$\sigma$$\sigma$の$i-(j-i)=i$ 以上である．一方，の $\sigma_{y(j-i+1)+1}$ からの重みの総和がまでの連続領域におけ以上であると仮定すると，$\sigma_{x(j)}$$i$の $\sigma_{y(j-i+1)}$ を末尾とする接頭辞における重みの総和は $j-i$ 以下であるから．
義に矛盾する．したがって， の$b_{j-i+1}$$S$$aj^{-}-b_{j-i+1}=w(i)$$i$に対文字目の記号は$a_{i}$$b_{i}$

るとは限らない．もしも $w(i-1)=w(i)$ ならば，$w$$\sigma_{k}$$i$$\sigma_{x(j)}$を満たす区間幅 は存在しない．
$w(i-1)<w(i)$ を満たす添え字 にのみ注
しかし，索引に $O(n)$目することで，この 要素配列を時間で変換することも容易にできる．よって，次の補題より， 索引を求める $O(n+k^{2}/\log k)$ 時間アルゴリズムを直ちに得ることができる．

$i$$2\leq i\leq l$ である任意の添え字に対して，た，$x(i)=x(i-1)$ , そうでないなら$a_{i}=a_{i-1}$ ならば，$x(i)=x(i-1)+1$ である． の定義より，
ば，$w(i-1)\leq w(i)$ ではあるものの，前節のただし，場合と異なり，必ずしも $w(i-1)<w(i)$ が成立す$l$$\sigma_{x(i)}$$\ldots,$$x(1)\leq x(2)\leq\cdots\leq x(l)=k$ が成立する．ま$i$$W_{S,\sigma}(w)=i-1$$\sigma_{1},\sigma_{2},$$\sigma$$a_{i}$$\sigma$$a_{i}$の重みの総を先頭から順に$1\leq i\leq l$ である任意の添え字とする．

証明 $S$ 中の$l$

補題 5$\sigma$$w(2),$ $\ldots,$ $w(l)\rangle$ に等しい．

$W_{S,\sigma}(2)\leq\cdots\leq W_{S,\sigma}(n)=O(k)$

和が$(b_{1},$$b_{2},$の $b_{i}+1$ 文字目の記号もをそれぞれ， $n+1$ とする．
証明

において

$\sigma$$\tau$$b_{i}$$S$未満である接頭辞の最大区間幅に等しい$i$$\langle w(1),$中の以外の記号をすべて同一の記補題 4と号とみなし，先頭から順にする． $\leq i\leq n\backslash -k+1$ である任意の添え$a_{i}+1$ がの出現位置に等しい
字 に対して，と，$\backslash n-k+1$ 要素ベクトルがの出現位置に等しい $n-k+1$ 要素ベの差最大値畳込みは．
クトル$w’(2),$$w’(n-k),$に等しい．ただし，$\tau_{n-k+1}$ の出現位置
便宜的に，存在しない記号と，b が$,$要素ベクトル

時間アルゴリズムが直ちに得られる．
$S$$a_{l}\rangle$$\ldots,$までの連続領域における$\sigma_{y(\dot{g}-i+1)+1}$$\sigma$$\sigma$のの定からの重みの総和は$i$$y(j i+1)=y$ が成立する．このことは，よって，であることを意味する．

$i\leq i\leq l$ であより，る任意の添え字 に対して，$a-b\geq w(i)$ で$w(1)\leq w(2)\leq\cdots\leq w(l)$$j$あることも容易に確認できる．よつで，補題は成立する．口2.4 整数重みの場合
中の各 の重みを や に依存しない任意の索引を求めることのできる整数である場合に$S$$n$$\sigma$$k$$W_{S,\sigma}$$O$( $n+k^{2}$ log log ) 時間アルゴリズムを与える．単$k$

純な $O(nk)$ 時間アルゴリズムをはじめに与え，後

21に，これを ( $n+k^{2}$ log log ) 時間で動作するよう$O$べて削除する．
中の $u(i,j)$ 未満の最大の要素 $w$ を探し，そ3.

$k$に変形する．
$S$ 中の個の$\mathcal{W}$$k$$\sigma$

を先頭から順に$\sigma_{1},$$\sigma_{2},$$\ldots,$のような $w$ が存在しない，あるいは $W(w)<$$\sigma_{k}$文字目に現れるととする． は において
$a0=0,$ $a_{k+1}=n+1$ とする． の連続する．
$S$$\sigma_{i}$$W(i,j)$ ならば，$W(i,j)$ をラベル付けされた$a_{i}$$u(i,j)$ を$S$領域を，以下のような $k(k+1)$ 個のグループに$0\leq i\leq k$ である任意の添え字分類する．

$i$と，である任意の添え字 に対して，$S(i,j)$の連続領域でで，からのまでのちょう
ど $j-i$ 個の を含むすべてからなる集合を表す．
$1\leq i\leq k$

$i$

$S$

$\sigma_{i+1}$$\sigma$$W(i,j)$ で，$\sigma_{i+1},$$\sigma_{i+2},$$\ldots$,$\sigma j$の重みの総和を表す．

$u(i,j)= \max(1, a_{i}- (a_{j+1} 1))$ , $v(i,j)=$
また，とする．この定義-より，$(a_{i+1}-1)-aj$$\mathcal{S}(i,j)$含まれる $S$ の各連続領域におけるにの重みの総和はすべて $W(i,j)$ に等しい．更に，$S(i, j)$ に含まれる $S$ の連続領域の区間幅は $u(i,j)$ 以上かつ $v(i,j)$$\sigma$$S(i,j)$ 中にこの範囲の任意の区間幅を以下であり，もつ $S$ の連続領域が少なくとも 1 つ以上存在する．

$\mathcal{W}$に新しい要素として加える．

上記のアルゴリズムの実行時間を以下に与える．
を走査することで，1 から までのすべての添
え字 に対するの重みの総和と，

$S$

$k$

$i$

$a_{i}$$\sigma_{1},$$\sigma_{2},$$\ldots,$$\sigma_{i}$$W(0, のを O(n)$ 時間で求めることができる．アルゴリズムは，これらの値を保持し，任意の添え字対$(i, j)$ に対する$W(i,j),$$v(i,j)$ を定数時間の整数ソートアルで求めるために用いる．Han[2]$k(k+1)$ 個の添え字対
ゴリズムを用いることで，$(i, j)$ すべてに対する $2k(k+1)$ 個の整数 $u(i,j)$ ,$v(i, j)$

を $O$ ($k^{2}$$u(i,|j),$log log ) 時間で昇順に並べること$k$ができる．この $2k(k+1)$ 個の整数のみを要素としてもつことのできる van Emde Boas[4] のデー
タ構造を用いてを実装することで，先に述べた
各添え字対 $(i,j)$ に対するの要素に関するなら$\mathcal{W}$$S$の任意の連続領域はいずれかの$\delta(i,j)$に属する$\mathcal{W}$から，$W_{S,\sigma}$

索引を $[W(1),$ $W(2),$$\ldots,$$W(n)1$ として求める以下の単純な $O(nk)$ 時間アルゴリズムが直ちに得られる．

1: For each from 1 to $n,$ $W(w)arrow 0$ ;2: for each from 1 to3:for each from to $n,$4:
for each $w$ from $u(i, j)$ to $v(i, j)$ ,$w$

$j$

5:

$O$

$0$

$W(w) arrow\max(W(w), W(i, j))$ .

順に変更する．この変更により，5 行目では $W(w)$と(的) の比較をすることなしに，常に $W(i,j)$$W$を $W(w)$ に代入することができる．このことは，

もしもアルゴリズムが $[W(1), W(2), \ldots, W(n)]$ をである $(W(w)$ をラベル付けられた) $w$ すべてからなる集合

4, 5 行目の実行を$\mathcal{W}$としてもつならば，の要素に関する以下のならし$\mathcal{W}\backslash$

定数回の操作により完了することができることを意$\mathcal{W}$

中に $u(i, j)$ 以上かつ $v(i, j)+1$ 以下である要素が存在するならば，そのような最大のを$w$$W(w)<W(i, j)$ なから削除した後に，$W(w)$をラベル付けられた $v(i,j)+1$ をらば，に新しい要素として加える．
中の u(的) 以上かつ $v(i, j)$ 以下の要素を，2.
最小のもの (あるいは最大のもの) から順にす$\mathcal{W}$$\mathcal{W}$$\mathcal{W}$$k$$W_{S,\sigma}$$k$

ことができる．

参考文献[1] D. Bremner, T.M. Chan, E.D. Demaine,
J. Erickson, F. Hurtado, J. Iacono,
S. Langerman, P. Taslakian, Necklaces,
convolutions, and $X+Y$ , in: Y. Azar,
T. Erlebach (Eds.), ESA 2006, LNCS 4168,

pp. 160-171, 2006.
[2] Y.
Han,
Deterministic sorting in( log log ) time and linear space,
J. Algorithms 50 (2004) 96-105.
[3] T.M. Moosa, M.S. Rahman, Indexing permutations for binary strings, Inform. Process. Lett. 110 (2010) 795-798.
[4] . van Emde Boas, Preserving order in a forest in less than logarithmic time and linear
space, Inform, Process. Lett. 6 (1977) 80-82.
$O$

味する．

1.

$k$

$W_{S,\sigma}$

このアルゴリズムを高速化するため，2,3 行目で指定される添え字対 $(i, j)$ の順序を，$W(i,j)$ の昇$W(w)\neq W\backslash (w+1)$$k^{2}$$\mathcal{W}$$n_{\rangle}$$i$

し定数回の操作を，ならし (log log k) 時間で実行できる．また，Han[2] の整数ソートアルゴリズム$k(k+1)$ 個の添え字対 $(i,j)$ をを用いることで，( log log ) 時間で $W(i,j)$ の昇順に並べることができる． を $O$ ( $n+k^{2}$ log log ) 時間で索引に変換することも容易である．
以上より，提案したアルゴリズムを用いること
で， 索引を $O$ ( $n+k^{2}$ log log ) 時間で求める
$O$

$P$

$n$

$n$