数理解析研究所講究録1093 巻 1999 年 81-86

81

部分語計数問題の接尾辞配列を用いた高速アルゴリズム
笠井

透有村博紀

有川節夫

九州大学大学院システム情報科学研究科情報理学専攻
1

対して,

はじめに

大規模テキストデータベースの急速な発展によって,テキストデータから規則性やパタンを発見する研究が注目されている. 従来のパタン発見や文字列解析のアルゴリズムの多くは, 接尾辞木 (suffix)とよばれる索引構造を対象としている. 最近, よりコンパクトなデータ構造である接尾辞配列 (suffix
array) [9] が提案され, 大規模テキストデータベース$\mathrm{t}\mathrm{r}\mathrm{e}\mathrm{e}$$[8]$におけるデータ構造として注目されている. この接尾辞配列は, 実現において接尾辞木の 1/2\sim 1/3 の記憶容量しか使用しない.
本研究では, 大規模テキストデータベースからの効率よいパタン発見を実現するために, 接尾辞配列

上で高速なパタン発見を可能にするための基本的実装法について考察する. 接尾辞配列を左から右へ一度走査するだけで接尾辞木の仮想的巡回をおこない, テキスト中のすべての部分語の頻度を計算する高速なアルゴリズムを提案する. このアルゴリズ
ムの時間計算量は $O(n)$ であり, 2 分探索を繰り返し用いて木の巡回を模倣する素朴なアルゴリズムのに比べるとオーバーヘッドが小さい. したがって, パタン探索問題やテキストデー$O(n\log n)\sim O(n^{2})$タマイニングの高速化に有効である. また, 計算機
実験の結果も示す.

2

準備

と

に共通する最長の接頭辞を最長共通
接頭辞 (longest common prefix) といい, その長さ
. を $lcp(s, t)$ で表す.のテキスト (text) とは, 文字列 $A=$
長さ
-1$である. ここに,であり,
号 $ は$であるような特別な区切り記号である. 本稿では, $n\geq 2$ と常に仮定する. 語 が, ある
整数 $1\leq i,j\leq n,$ $i\leq j$ に対して, $s=a_{i}\cdots a_{j}$ となるとき, は $A$ に出現するといい, を の出現位置(occurrence) という. 任意の $1\leq i\leq n$ に対して,位置 からはじまる $A$ の接尾辞を $A_{i}=a_{i}\cdots a_{n}$ -1$
で表す.
$s$

$t$

$n$

$a_{i}\in\Sigma$$a_{1}a_{2}\cdots a_{n}$$\equiv \mathrm{a}-\mathrm{D}$$\not\in\Sigma$

$s$

$i$

$s$

$s$

$i$

テキスト $A$ め接尾辞木 (suffix tree) とは, つぎのように定義される順序木(1) 各辺は,$A$$T_{A}$である [8]:の空でない部分語\alpha をラベルとしてもつ. ラベルは, その出現位置 と終了位
置 $i+\iota_{e}n(\alpha)-1$ の組 $(i, i+len(\alpha)-1)$ で符号化されている.
$i$$\alpha$(2) 任意の内部節点に対して, その子へと出ていく
すべての辺のラベルは, 先頭の文字が互いに異なる.

(3) 各節点は, 根から へ至る辺のラベルを合併して得られる語を表す. これを, 分岐語(branching subword) とよび, Word $(v)$ と書く.
$v$

$v$

(4) 葉を 個もち, それらの葉が表す分岐語は,の空でない接尾辞である. 各葉は, それが表す接尾辞の中の開始位置をもち, の空でないすべての接尾辞が, 左の葉から右の葉へ\Sigma $\cup\{}$上の辞書式順序で並んでいる.

$A$

$n$

2.1

接尾辞木

本稿では, 記号のアルファベット に対して, 上の任意の文字列を語 (word) とよび, その長さを $len(s)$ で表す. 語 に対して, $s=uvw$ を満
たす語 $u,$を, それぞれ, の接頭辞 (prefix), 部
分語 (subword), 接尾辞 (suffix) とよぶ. 語に$\Sigma$$\Sigma$$s\in\Sigma^{*}$$s$$v,$ $w$

$s$

$s,$

$t$

Virtual suffix trees: fast computation of subword
frequency using suffix arrays, T. Kasai, H. Arimura,
S. Arikawa, Department of Informatics, Kyushu University, Hakozaki 6-10-1, Fhkuoka 812-8581, Japan. {arim,. kyushu-u.
$\mathrm{a}\mathrm{r}\mathrm{i}\mathrm{k}\mathrm{a}\mathrm{w}\mathrm{a}\}@i$$\mathrm{a}\mathrm{c}.\mathrm{j}\mathrm{p}$

$A$

$A$

図 1 の左に, 接尾辞木の例を示す.
接尾辞木は, 個の葉とたかだか $n-1$ 個の内部節点をもち, $O(n)$ 領域を使う. 整数を 4 バイ
トで表現すると, TA は $15n$ バイトの記憶領域を必要とする.
を計算する $(n)$は,.
時間アルゴリズムを与えている.
$T_{A}$$n$$\mathrm{M}\mathrm{c}\mathrm{C}\mathrm{r}\mathrm{e}\mathrm{i}\mathrm{g}\mathrm{h}\mathrm{t}[8]$$T_{A}$

$O$

82
Text

S\mbox{\boldmath $\omega$}面 x tree

Sufffx$:_{\text{図}}1$2.2: 接尾辞木と接尾辞配列

接尾辞配列で表す. $T$ の葉 が, 左から 番目の葉であるならに対して,ば, の順位は であるという. 節点
left $(v)(right(v))$ を を根とする $T$ の部分木の最左の葉の順位 (最右の葉の順位) と定義する.
との最近共通先祖 (nearest com節点 $w$ が,
mon ancestor) とは, 節点 $w=nca(u, v)$ で $w\preceq u$とするすべてかつ $w\preceq v$ であり, $x\preceq u$ かつ
$i$

$l$

テキスト $A$ の接尾辞配列 (suffix array) は,A の各接

尾辞へのポインタを格納した 1 次元配列 $Pos[1..n]$であり, 各ポインタは, それが指し示す接尾辞の辞書式順序でソートされている. 定義より, 任意の$1\leq i\leq n$ に対して, $Pos[i]$ は, 辞書式順序で順位
中での開始位置である. これは,力 s の接尾辞の接尾辞木の葉だけを左から右に–次元整数配列に格納したものに等しい.
図 1 の右側下に, 接尾辞配列の例を示す. 例えば,
左から 2 番目のセルの値 4 は, テキストの 4 文字目
からはじまる順位 2 の接尾辞 A4=ACCA$ を表す.
また, 長さ 1 の文字列 A の出現位置は, 接尾辞配列
め連続したセル [1..3] を占めることもわかる.
$A$

$v$

$i$

$l$

$v$

$u$

$v$

$x\preceq v$の節点 に対して, $x\preceq w$ が成立するものをいう.
リストの連結を で表す. $T$ の後置順巡回 (Postorder traversal) とは, つぎのように再帰的に定義$x$.

される節点のリストである:(1) $.T$ がただ–つの節点 からなるとき, (V) は,の後置順巡回である.
$v$

$T$

$\ldots,v_{m}(m\geq 1)$ をもつ(2) $T$ の根 が, 子の部分木のとし, 各 に対し, を根とする
後置順巡回を とすると,は, $T$ の後置順巡回である.
$v$

に対して,

その逆関数となる配列$Suf[1..n]$ を, $Suf[P_{\mathit{0}}S[i]]=i$ と定義する. $Suf[i]$の順位である. 高さ配列 (hightは, 接尾辞は, 任意の順位 $1\leq i<n$ に対して,$Hgt[i]=lcp(APos[i], A_{P_{\mathit{0}}}[si+1])$ で定義される配列である. ただし, $Hgt[n]=-1$ と定義する.
$Pos[1..n]$$\mathrm{a}\iota\tau \mathrm{a}\mathrm{y}$$v_{1},v_{2},$$i$$v_{i}$$\Gamma_{1}\cdot\Gamma_{2\cdot\cdot m}..\cdot\Gamma\cdot(v)$$\Gamma_{i}$$A_{i}$$T$$\mathrm{a}\mathrm{r}\mathrm{r}\mathrm{a}\mathrm{y})H.gt[i]$2.4パタン探索問題

パタン発見に関わる問題の多くは, 各節点の巡回と接尾辞配列 $Pos$ は, テキストとあわせて $5n$ バイ
トしか使わない. $Pos$ は, いったん接尾辞木を計算することで $O(n)$ 時間で構成できるが, 実用的には,
クィックソートを用いた平均時間 $O(n\log n)$ のア
ルゴリズムを用いることが多い [4].

動的計画法の適用によって効率よく計算できる. このクラスの問題を –般化する.
$D$ を値の集合とし, これを領域 (domain) とよぶ.
演算子 $\oplus:D\mathrm{x}Darrow D$ を, 空要素 をもつ $D$ 上と任意の値の結合的二項演算子とする. ただし,
$e\in D$ に対して, $e\oplus\phi=\phi\oplus e=e$ とする. 初期割り当て $B:\{1, \ldots, n\}arrow D$ を, テキスト $A$ 上の任$\phi$$\phi$

23

順序木と巡回

順序木 $T$ は, そのすべての内部節点が 2 つ以上の子をもつとき, コンパクトであるという. 接尾語木は,コンパクトな順序木である. 木 $T$ の節点を $u,$ $v,$ $w$
とおく. 節点 $u,$ に対して, が の先祖であることを, $u\preceq v$ で表し, 真の先祖であることを $u\prec v$
$v$

$u$

$v$

意の位置への値の割り当てとする. テキスト $A$ のの任意の部分語統計 (subword statistics) とは,
$C$
$D$
への写像
であり, $A$ 中で
から領域
部分語
に対して,
の
の出現位置全体$C(\alpha)=B(i_{1})\oplus\cdots$ \oplus B(娠) と定義する.
$A$’$\alpha$$\alpha$$i\mathrm{l}\leq i_{2}\leq\cdots\leq i_{m}$83

Naive-Traverse
1.
の任意の葉$T_{A}$

ここに,
する.

$P$

. $:=B(p)$ を割り当てる.
に,は v が表す接尾辞の $A$ 中の開始位置と$l_{i}$$C_{l_{*}}$

での分岐を接尾辞配列上での 2 分探索で模倣し, ス
タックを用いて深さ優先探索をおこなう. しかしこの手法の計算時間は $O(n\log n+Q+M(n))$ 時間となる. ここに,は非圧縮接尾辞トライの節
点数 $Q=o(n^{2})$ であり, $M(n)$ は, 図 2 のアルゴリ
ズムにおける\oplus 演算の所要時間の合計である. 次節
以降では, より効率よく接尾辞木の巡回を模倣する方法を与える.
$Q$

2. 葉から根へと走査しながら, 各内部節点に対して, リスト $C_{v}:=C_{v_{1}}\oplus C_{v_{2}}\oplus\cdots\oplus C_{v_{m}}$ を対応づけ$v$

る.

ここに, $m\geq 2$ であり, 任意の $1\leq i\leq m$ に対して, 暁は, のもつ左から 番目の子とする.
$v$

$i$

$\overline{T}_{A}$

図 2: テキストのすべての部分語の部分語統計を, 接尾辞木の深さ優先探索を用いて計算するアルゴリズム

3

部分語統計問題 (subword statistics problem)
入力: テキスト $A$ , 領域 $D$ , 初期の割り当て $B$ ,本節と良禽では, 接尾辞配列上で接尾辞木の巡回を模倣しながら, テキストに現れるすべての部分語の二項演算子\oplus .
問題: $A$ の (出現位置がことなる) すべての部

分語$\alpha$に対して, 部分語統計$C(\alpha)$を出力せよ.

部分語統計問題は, 接尾辞木の深さ優先探索を用いて, 図 2 のように計算できる.
以下の問題は, 上記の部分語統計問題の具体例またはそれに密接に関連した問題の例である:$\bullet$.
$\circ$

部分語頻度計算問題 (String statistics with overlaps) [1]. 入力テキストの (出現位置がことなる) す
べての部分語について, その出現回数を答えよ.
最長反復部分語問題 (Longest repeated substring
problem)[3](pp. 21). 入力テキスト中に 2 回以上出現する最長の文字列をみつけよ.
最長共通部分語問題 (Longest common substring
problem) [3]. つの入力テキスト中に共通して出現する最長の文字列をみつけよ. (一般には, 入力テキストの数が任意の場合も考えられる)$(\mathrm{p}\mathrm{p}.

.

.

20)$

$2$

出現文書数問題 (Color set size ploblem) [6]. 入力
テキストの集合が与えられたとき, (出現位置がことなる) すべての部分語について, それが出現する
文書数 (color set size) を答えよ.

部分語無矛盾性問題 (Characteristic substring
problem) [10]. 入力として, 2 つのテキスト集合$P,$ $N$が与えられたとき, $P$ 中のすべてのテキストに出現し, $N$ 中のどのテキストにも出現しない文字列を見つけよ.

コンパクト順序木のボトムアップ巡回

部分語統計を計算する効率よいアルゴリズムを与える.

まず準備として, 本節では, 一般の順序木において, 葉の左から右への走査と, 最近共通節点の計算,

節点間の先祖関係の計算だけが基本的演算として与えられている場合に, 木の巡回をボトムアップにおこなうアルゴリズムを与える. 次に次節では, このアルゴリズムを接尾辞配列上で実現可能なことを示す. これにより, 接尾辞木の巡回を接尾辞配列を用いて効率よく実現するアルゴリズムを与える.

3.1

図 3 に, 接尾辞木の葉を左から右へ走査することで,

後置順巡回で各節点を巡回するアルゴリズムを示す. アルゴリズムは, スタックを用いて木を巡回$S$する.

本節では, $T$ を, 個の葉をもっコンパクトな順序木とする. 任意の $1\leq i\leq n$ に対して,で $T$の左から 番目の子を表し, ncai で葉 との最近共通先祖 $=nca(l_{i}, l_{i+}1)$ を表す. ただし, 特
別な節点 ，鰺僂い, $nca_{0}=nca_{n}=nca(l_{0}, l_{1})=$$nca(l_{n}, ln+1)=\perp$ と定義する. 根の仮想的な親が$n$$l_{i}$$i$

素朴な模倣アルゴリズム

接尾辞配列をもちいて部分語統計問題を解く方法として, 接尾辞木の深さ優先探索をおこなう図 2 のア
ルゴリズムを, そのまま接尾語配列上で模倣することが考えられる.
このとき, 各節点 を, それが占める順位のなす
区間 (lef.t $(v),$ $right(v)$ ) で表現する. さらに, 節点$v$$l_{i}$$l_{i+1}$

である.

32

25

アルゴリズム

正当性

定義 1(最長最右枝) 順序木 の 番目の葉 に対して, 葉 から根へ進む経路で, 節点の最右辺だけから構成される最長のものを, 最長最右枝といい,
$T$

$i$

$l_{i}$$l_{i}$と書く. ここに,されているとする.

$\Pi_{i}$$\Pi_{i}$は節点のリストとして表現

任意の順序木は, 最長最右枝の集まりとして表現できる. 図 4 に, 順序木の最長最右枝の例を示す.

84

Algorithm Traverse-Tree
1. Compute theand $S:=\phi$ .
Push into .
, do:
2. For each leaf $i=1,$(a) Push .
(b) $w:=nca_{i}$ . Let be the top of .
(c) While $w\prec v$ , do:(i) Report .
(ii) Let be the top of .
(d) If $v=w$ thenDo nothing.
(e) Else if $v\prec w$ thenPush into .
$nca_{i}\mathrm{s}$$S$$\hat{r}$$n$$l_{i},$$\ldots,$$l_{i}$

$S$

$v$

$v$

$S$

$v$

$w$

$S$

図 3: 順序木の葉を左から右へ走査しながら, 後置

順巡回で各節点を巡回するアルゴリズム

補題 1 任意の $1\leq i\leq n$ に対して, 葉 l, から節点

ncai への経路を $v_{1}(=l_{i})v2\ldots vkvk+1(=nca_{i})$ とお
く,. このとき, $\Pi_{i}=v_{12}v\cdots$ 循である.
定理 2 葉数 $n\geq 1$ のコンパクトな順序木を $T$ とおく. このとき, $T$ のすべての最長最右枝を左から右へ連結して得られるリスト
は,$T$ の後置順巡回に等しい.
$\Pi_{1}\cdot\Pi_{2}\cdot\ldots\cdot\Pi_{n}$アルゴリズム Traverse-Tree において, ステップ$2.(\mathrm{a})$からステップ 2(e) の For$\mathrm{K}\mathrm{s}_{-\text{フ^{}\circ}}$

の

$i$

回目の実

行を第 ステージとよぶ. 第 ステージにおいて, ス
テップ 2(a) でスタックへのプッシュを行った直後
とおく. スタックの内容のスタックの内容をは, $S=v_{k}vk-1\ldots$ vl ，里茲Δ, スタックの頂上を左に, 底を右に向けた要素の列として表す.
$i$

$i$

$S_{i-1}$

補題 3 アルゴリズムの第 番目のステージのステッ$i$

プ 2(a) でスタックへのプッシュを行った直後において, スタックの内容 $S_{i-1}=v_{to_{P}}vt_{\mathit{0}}p-1\cdots v1\perp$ は,
つぎの (1) と (2) を満たす:(1) スタックの任意の要素を $v_{j}(0\leq j<top)$ とする.

$-$ つ上の要素 $v_{j+1}$を根とする部分木を考え, その最左の葉を とおく. このとき,$v_{j}=nca(l_{k-}1, \iota k)$ が成立する.
$l_{k}$

図 4: 順序木の各葉$l_{i}$の最長最右枝. 各葉から根へ進む灰色の経路が最長最立枝である.

の最左の葉を とし, 最右の葉を とする $(i\leq j)$ .
とし, の–つ国隣
さらに, l, の–つ左隣の葉をとする. このとき, このとき, の親は,の葉を
$l_{i}$$l_{j}$$l_{i-1}$$l_{j}$$v$$l_{j+1}$$nca(l_{i-1},\iota_{i})=nCai-1$と $nca(l_{j,j1}l+)=nca_{j}$ のど

ちらかに等しい.
補題 5 アルゴリズムの第$i$

回目のステージにおの実行直後には, 最長最右いて, ステップ
枝が, スタックの最上部に積まれている. す$2.(\mathrm{a})$$\Pi_{i}$なわち, スタック Si-l $=v_{top}\cdots v_{1}\perp$ に対して,$\Pi_{i}=v_{top}\cdots v_{k}$となる整数 $0\leq k\leq top$ が存在.
する.
定理 6 コンパクトな順序木 $T$ が与えられたとき,
図 3 のアルゴリズム Traverse-野 ee は, $T$ のすべての節点を後置順巡回で巡回する.

4

接尾辞配列による高速な巡回

本節では, 前節のアルゴリズムを用いて, 接尾辞木の巡回を接尾辞配列を用いて効率よく実現する線
形時間アルゴリズムを与える. さらに, これを用いて, 接尾辞配列からテキストに現れるすべての部分

語の部分語統計を計算する効率よいアルゴリズムを与える.
この節を通して, 長さとおく.
の接尾辞木を$n$のテキストを $A$ とし, $A$$T_{A}$(2) スタック中の節点は, 葉 から根にいたる経
路上に順に並んでいる. すなわち, $v_{0}=\perp\leq\tau$$l_{i}$$v_{1}\leq\tau\cdots\leq\tau v_{tp}O=li$

である.

補題 4 コンパクトな順序木をとし, その任意の$T$ の部分木
を根とする
節点を
節点
とする.
$T$

$v$

$v$

4.1
図5

アルゴリズム

前節のアルゴリズム 升 averse-Zkee
を接尾辞配列上で模倣するアルゴリズム$verse_{-}with_{-}Array$ を示す.
アルゴリズムは, 接尾$\text{に},$.

$\pi_{a-}$85Algorithm $\tau_{rave\Gamma}Se_{-}with_{-}Array$
1. Compute $Hgt[1..n]$ and
$:=$
.
Push
$(\phi, (0, -1))$ into.
2. For each rank $i=1,$, do:(a) Push $(B(PoS[i])),$ $(i, |A_{P_{oS}[]}i|))$ .
(b) $(C_{new}, (L_{new}, H_{ne})w):=(\phi, (i, Hgt[i]))$ . Let$(C, (L, H))$ be the top of .
(c) While $H>H_{new}$ , do:(i) Report $(C\oplus C_{new}, (L, H))$ .
(ii) $C_{new}$ $:=$ $C\oplus C_{new}$ and pop S. Let$(C, (L, H))$ be the top of .
(d) If $H=H_{new}$ then
Pop $(C, (L, H))$ from , and then push
$C_{new},$ $(L, H))$ into.
. (e) Else if $H<H_{new}$ thenPush $(C_{new}, (L_{new}, H_{ne}w))$ into .
$S$$\phi$$S$$\ldots,$

$n$

$S$

$S$

$S$

$(C\oplus$

$S$

$S$

図 5: 接尾辞配列をもちいて, 部分語統計問題を解くア定理 10 長さ のテキスト $A$ および $A$ の接尾辞
配列 $Pos$ が与えられたと仮定する. このとき, 図
3 のアルゴリズム $Traverse_{-}with$-Array は, $O(n)$ 胸
$n$

間で,

$T_{A}$

Proo 丑

のすべての節点を後置順巡回で訪問する.

補題 6 および, 補題 7, 補題 8, 補題 9 から導かれる .

$\square$のテキスト $A$ および, $A$ の接尾辞系 11 長さ
配列 $Pos$ , 部分語統計問題 $(D, B, \oplus)$ が与えられ
$n$

たとする.

このとき, 図 3 のアルゴリズム Tra中のすべての部
は, テキスト
分語の部分語統計を $O(n+M(n))$ 時間で計算する.
ここに, $M(n)$ は,演算の所要時間の総計である.
$verse-wi\theta h_{-}Array$$A$$\oplus$

Proofi定理 10 から,は,アルゴリズム Tra-の後置順巡回を正しく模倣する. 後置順巡回では, ある節点 が訪問される
とき, その子どもはすでに訪問されており, に関連づけられた値
はすでに計算ずみであることが保証される. よってアルゴリズムは, すべての節点に対して正しく $C(word(v))$ を出力する. 計算時間については, Push と Pop 演算は $O(1)$ 時間で実行でき, $len(AP_{oS}[i])=n-i+1$ なのでこれも $O(1)$時間で計算可能である. また, \oplus 演算の実行回数は,
図 2 のアルゴリズム Naive-Traverse でのものと変わらない. よって, 構成より明らか
口$verSe_{-}withArray$$T_{A}$

$v$

ルゴリズム

$v$

辞配列を左から右へ走査しながら木の巡回を模倣
し, テキストに現れるすべての部分語の部分語統計を計算する.

42

正当性の接尾辞木を $T$ とする. 任意の整数の組 $(L, H)$ に対して, つぎの (1) と (2) をみたす節点が存在するとき, node $(L, H)=v$ と定義する:
テキスト

$A$

$v$

(1) left $(v)\leq L\leq right(v)$ .

もし条件をみたす が存在しないなら, node $(L, H)$
は未定義とする.
この定義から node $(L, H)$ が唯– に定まることが容易にわかる. アルゴリズムでは, 節点をnode $(L, H)=v$ となるような組 $(L, H)$ で表す.
$v$

$v$

$\leq$$i$$n$$\leq$$(i,\iota en(A_{P[}i]os))=l_{i}\text{が}\mathfrak{p}\mathrm{X}\text{立す^{る}}$

.

に対して,

$i$

$\leq$

高さ配列 Hgt の線形時間計算

前節のアルゴリズムでは, 高さ配列 Hgt を用いて接尾辞木の仮想的な巡回をおこなった. 本節では, テ
キスト配列と接尾辞配列から Hgt を線形時間で計算するアルゴリズムを与える.
定義から, Hgt はすべての $1\leq i\leq n$ に対して,$Hgt[i]=lCP(A_{Po}A_{Po}i+])S[i]’ s[1$ を計算することで求められる. しかし, 一般に$O(n)$ であるので, この簡単な方法では最悪時に$lcp(AP_{\mathit{0}\mathit{8}}[i], A_{Po}S[i+1])=$

補題 8 任意の整数 1に対して,node( , Hgt[jl)=ncai が成立する.
補題 9 アルゴリズムの第 回目のステージのステップ 2.(c)-ステップ 2(e) において, スタックの頂$\leq$$v$

5(2) $len(word(v))=H$ .

補題 7 任意の整数 1
node$C_{v}$$n$$O(n^{2})$

$i$

$i$

上の要素

$(L, H)=t\varphi(S)$と$(L_{\mathrm{n}ew},Hnew)=$$(i, Hgt[i])$ に対して, つぎの (1) $-(3)$ が成立する.

(1) $H>Hgt[i]\Leftrightarrow node(L, H)\succ nca_{i}$ .
(2) $H=Hgt[i]\Leftrightarrow node(L, H)=nca_{i}$ .

(3) $H<Hgt[i]\Leftrightarrow node(L, H)\prec nca_{i}$ .

時間を要する 1.

図 6 に, 高さ配列 $Hgt[1..n]$ を $O(n)$ 時間で計算するアルゴリズム Fast-Hgt を示す. 次の補題は,アルゴリズムの正当性に本質的である.
補題 12 任意のテキスト $A$ と整数 $1\leq i<n$ に対して, $l\varphi(A_{Ps}[i],A_{PoS}o[i+1])-1\leq lcp(A_{Pos[}i]+1$ ,$A_{PoS[+1]+1}i)$ が成立する.
1

例えば, $A=aaaaaa\cdots a$ の場合,

86

Algorithm Fast-Hgt
1. Compute $Suf[1..n]$ and $h:=0$ .
2. For each position $i=1,2,$ $\ldots,n$ , do:
If $s_{uf}[i]=n$ thencontinue.
(b) $j:=Pos[s_{u}f[i]+1]$ .
(d) If $h=0$ then$\ovalbox{\tt\small REJECT}_{1}^{\mathrm{N}}\mathrm{T}\mathrm{A}\circ \mathrm{r}\mathrm{i}\mathrm{t}\mathrm{h}\mathrm{m}\mathrm{a}\mathrm{i}\mathrm{v}\mathrm{e}\mathrm{i}\mathrm{m}\mathrm{e}(\sec)75-\mathrm{H}\mathrm{g}\mathrm{F}\mathrm{a}\mathrm{S}978\mathrm{l}\mathrm{H}\mathrm{t}_{-}\mathrm{g}\iota$$.(\mathrm{a})$$Hgt[suf[i]]=-1.\mathrm{a}\mathrm{n}\mathrm{d}$$Hgt[Suf[i]]:=l_{C}p(A_{i}, Aj)$

図 7: 計算時間の比較.

イトであり, スタック平均長は よりかなり小さい.
また, アルゴリズムの単純さも長所である.
本アルゴリズムはディスク上での実装にも適す
る. それには, 前処理で計算した Hgt と Pos をディスクにおき, スタックを主記憶上におけばよい. この際, Hgt のアクセスパタンは逐次的である.
$n$(c) Else if $h>0$ then$Hgt[suf[i]]:=h-1+lcp(Ai+h-1, Aj+h-1)$ .
(e) $h:=Hgt[s_{u}f[i]]$ .
図 6: 高さ配列 $Hgt[1..n]$ の線形時間アルゴリズム

Proof: テキスト $A$ において,] の先頭から 1 文字取り除いたものが $A_{poS}[i]+1$ である. 同様に,] の先頭から 1 文字取り除いたものがよって, $A_{p_{oS}}A_{Po}[i]’ s[i+1]$ の] である
共通接頭辞の先頭から 1 文字取り除いたものは,$A_{p_{\mathit{0}\mathit{8}[}}i$$A_{p_{oS[}}i+1$$A_{p_{os}[}i+1$$+1$$A_{poS}[i]+1,$ $A_{ps[+}\mathit{0}i1]+1$の共通接頭辞になる.

とから導かれる

このこ
口

アルゴリズム Fast-Hgt は,ら右へ走査し, 位置

テキストを左かを増加させながら,を計算していく. 上の補題
から, アルゴリズムは, 接尾辞同士の重複部分を利用して文字列比較の回数を減らし, $Hgt$ を高速に計算する.
$Pos[i]$$l\varphi(A_{Ps}iAo[]’ p_{os[+}i1])$

7

おわりに

本稿では, 高速なパタン探索手法について論じ, 接尾辞配列上で接尾辞木の巡回を実現する線形時間ア
ルゴリズムを与えた. ここで略したアルゴリズムと証明の詳細については [7] を参照されたい.
本手法を用いて, 文献 [2] のテキストデータマイ
ニングにおける語相関パタン発見問題が, 接尾辞木を用いた場合と同じ時間計算量で実装可能である.
詳細に関しては, 別の機会に述べたい.

参考文献[1] A. Apostolico, F. P. Preparata, Structural propstatistics problem. JCSS,$\mathrm{e}\mathrm{r}\mathrm{t}\mathrm{i}\mathrm{e}\mathrm{s}.\mathrm{O}3\mathrm{l}(3).394\mathrm{f}\mathrm{t}\mathrm{h}\mathrm{e}-4\mathrm{l}\mathrm{l}(19\mathrm{s}\mathrm{t}\mathrm{r}\mathrm{i}8\mathrm{n}_{5}7$

補題 13 長さとの接尾辞配列$Pos[1..n]$ が与えられたとき, 図 6 のアルゴリズム
Fast-Hgt 1 は, $Hgt[1..n]$ を $O(n)$ 時間で計算する.

6

$n$

のテキスト

$A$

$A$

計算機実験

接尾語木の巡回を 2 分探索によって模倣する素朴なアルゴリズムと今回提案するアルゴリズム
Fas 沖 Traverse (図 7) を, Unix ワークステーション(Sun Enterprise3000,
on Solaris 25) 上に実の英文テキスト [5] を対象として計算
現し, 5.
時間を測定した. 接尾辞配列は主記憶上においた.
次ページの図 7 に計算機実験の結果を示す.
上の 2 つの欄は,素朴な巡回アルゴリズム$Binary-\tau raver^{1}$ seと提案の巡回 7 ルゴリズム
Fast-Traverse について, 巡回の時間を示す (前処理で $Hgt$ を計算する時間は含まない). 下の 2 つの欄は, 前処理における Hgt 配列の計算について, 素朴なアルゴリズム Naive-Hgt と提案のアルゴリズ
ム Fast-Hgt の計算時間を示す.
使用領域は, $Pos$ と $Hgt$ がそれぞれ $4n$ と $2n$ バ$\mathrm{g}++$$3\mathrm{M}\mathrm{B}$[2] H. Arimura, S. Shimozono, Maximizing agreement between a classification and bounded or unbounded number of associated words. In Proc. ISSAC, (1998).
[3] M. Crochemore, W. Rytter, Text Algorithm. Oxford University ress (1994)[4] G. H. Gonnet, R. Baeza-yates, T. Snider, New indices for text: Pat tree and Pat arrays. Information
Retrieval, Prentice Hall (1992).
[5] R. Harris, Abstract Index, Monash Univ. (1998).
[6] L. C. K. Hui, Color set size Problem with aPPlications to string matching. In Proc. of 3rd $CPM$,
230-243 (1992).
[7] 笠井透, 部分語計数問題の接尾辞配列を用いた高速, ステム
アルゴリズム. 修士論 X, fL’f ト|\star \neq \rightarrow ‘‘
情報科学研究科 E 報理学 E 攻, 平或 $11\not\in 2$ 月.
, A space-economical suffix[8] E. M.
tree construction algorithm. JACM, $23(2):262- 272$
(1976).
[9] U. Manber, G. Myers, Suffix arrays: A new method
for on-line string searches. SIAM J. Computing,$22(5):935- 948$ (1993).
M. Hashidume, M. Ito,[10] M. Nakanishi,
A. Hashimoto, A linear-time algorithm for computing characteristic strings. In Proc. 5th ISAAC(1994), 315-323.
$\lambda^{arrow^{\backslash }}\backslash \neq\Re^{-\backslash }\wedge\backslash$$\mathrm{M}\mathrm{c}\mathrm{c}_{\mathrm{r}\mathrm{e}}\mathrm{i}\mathrm{g}\mathrm{h}\mathrm{t}$