DEIM Forum 2016 C6-2

非同期に文字が入力される複数ストリームに対する一般化接尾辞木の線
形時間構築アルゴリズム
高木 拓也†

稲永俊介††

有村 博紀†† 北海道大学大学院情報科学研究科 〒 060–0814 北海道札幌市北区北 14 条西 9 丁目†† 九州大学 大学院システム情報科学研究院 情報学部門 〒 819-0395 福岡県福岡市西区元岡 744
E-mail: †{tkg,arim}@ist.hokudai.ac.jp, ††inenaga@inf.kyushu-u.ac.jp
あらまし

本稿では，非同期に文字が入力される複数ストリームに対する索引構築を考察する．総文字数 n からなる

K 本の文字列の集合を S = {T1 , ..., TK } とする．本問題は，新たな入力文字が任意の文字列 Ti の末尾に追加される文字列集合 S に対して，パターンマッチングなどを高速に実行する索引である一般化接尾辞木をオンライン構築する問題である．これは，マルチセンサーデータ等，複数のクライアントからデータが非同期に到着する状況に対する索引構築問題を想定している．本稿では，入力に対する有向語グラフを並列に構築することによって非同期入力される複数ストリームに対して，一般化接尾辞木を線形時間と領域で構築するアルゴリズムを提案する．
キーワード

テキスト索引，オンライン構築，Suﬃx Tree，DAWG

1. は じ め に

般化接尾辞木完全のオンライン構築アルゴリズムを与える．部
分語グラフと比べ，一般化接尾辞木の完全オンライン構築は難テキスト索引のオンライン構築問題は，コンピュータサイエ

しい．その理由を説明した後で，部分語グラフと並列に一般化

ンスにおける基本的な問題の一つである．文字列集合索引とは，接尾辞木を構築するアルゴリズムを示す．最後の節では，まとK 本の文字列からなる集合 S = {T1 , . . . , TK } が与えられたとめを与える．

き，S に対する文字列照合クエリを高速に答えるためのデータ構造である．最近，多数のセンサーからのセンサーログや，都

2. 準

備

市中を走行する車から送られる位置情報 （注 1） など，複数のクラ

本節では，以降の節で必要な用語と定義を与える．また，本

イアントから非同期に到着するストリームデータが増大してい論文で扱う主要なデータ構造である部分語グラフと一般化接尾る．そのため，文字列集合に対する索引の需要が高まっている．

辞木を導入する．

本稿では，オンライン文字列集合索引構築問題 (online con-

2. 1 基本的な定義

struction probelm for multiple texts indices) を考察する．こ文字の集合 Σ = {a, b, · · ·} をアルファベット (alphabet) とれは，文字列集合 S の文字列すべてが空文字列の状況からス

いい，Σ の要素数 |Σ| = σ をアルファベットのサイズという．

タートし，各時刻ごとにどれか一つの文字列の末尾に新しく文アルファベット Σ 上の長さ n の文字列は，Σ の要素の有限字が付け加えられるたびに，S の最新の索引を構築する問題で

列 T = a1 · · · an , (ai ∈ Σ, i = 1, . . . , n) である．各文字 aiある．これまで，i 番目の文字列 Ti の末尾に新たな文字が加えを T [i] と表記する．長さが 0 の空文字列を ε で表す．各添字られた場合，文字列 T1 , . . . , Ti−1 はそれ以上新たな文字が末尾

1<
=i<
=j<
= n に対して，添字の区間 [i, j] を {x | i <
=x<
= j}

に追加されないことを仮定する準オンライン (semi-online) なと定め，対応する部分文字列を T [i, j] = T [i]T [i + 1] · · · T [j] と設定での文字列集合索引構築として，一般化接尾辞木 (general-

する．もし i > j ならば T [i, j] = ε と定める．

ized suﬃx tree, GST) や部分語グラフ (directed acyclic word

与えられた文字列 T に対して，ある文字列 X, Y, Z ∈ Σ∗ がgraph, DAWG) に対する研究が行われてきた [1–3]．しかしな

存在して T = XY Z と分解できるとき，それぞれ X を T のがら，常に任意の文字列の末尾に新たな文字が追加可能な完全接頭辞 (prefix)，Y を部分語 (factor)，Z を接尾辞 (suﬃx) とオンライン (fully-online) 状況下での索引構築アルゴリズムはいう．

知られていない．そこで，我々は，部分語グラフと一般化接尾2. 2 接尾辞トライ

辞木に対する完全オンライン構築アルゴリズムを提案する．

文字列集合 S = {T1 , . . . , TK } に対する接尾辞トライ (suﬃx

初めに，2. 節で必要な定義を準備する．次に 3. 節では，部分trie)STrie(S) は，各文字列のすべての接尾辞の集合を格納す

語グラフの完全オンライン構築アルゴリズムを考察する．これるトライ構造である．接尾辞トライは辺ラベルとして S の文字

は Blumer らによる準オンライン構築アルゴリズムを拡張するを持つ．S に対する接尾辞トライの領域は O(n2 ) 語であるこことにより得られることを示す．4. 節では，left-to-right な一とが知られている．ここで n は S の総文字列長である．トラ（注 1）：http://cabspotting.org/

までのパス上のラベル文字を連結した文字列（パスラベル）でイ上のあるノード v が表現する文字列 x とは，根ノードから v

尾辞木と呼ぶ．一般化接尾辞木の任意の位置 w は，w の直上にSuffix Trie
c
b

a
b

c

1,3

1

c

る．この組 ϕ を参照 (reference) と呼ぶ．オフセット ℓ = 0 のaとき，参照 ϕ は実ノードを表すとみなすことができる．逆に，

2a b a c1

w までのパスの長さ ℓ の３つ組 ϕ = (u, a, ℓ) で表すことができ

1,3

a

b

ある実ノード u と u から w までのパスの最初の文字 a，u から
2

b
3

2

b

ℓ=
| 0 の位置を仮想ノードと呼ぶ．接尾辞木のノードにも，接尾辞トライと同様に接尾辞リンクを定義できる．

c2

2. 4 部分語グラフ
文 字 列 集 合 S = {T1 , . . . , TK } に 対 す る 部 分 語 グ ラ フ

2(DAWG)DAWG(S) とは，S のすべての接尾辞を格納する
DAG 構造である [2, 5]．部分語グラフは，接尾辞トライにおいて接尾辞リンクで接続された同一の部分木を統合したものであSuffix Tree

c

1,3

b a

c

b

1

2

1

c

a

b

2

ている終端位置が同一の場合，f と g は同じノードで表現され

1,3

b

a

る．より具体的には，S 中のある部分文字列 f と g が，出現しcbaる．図 1 の例では，部分文字列 aaab と部分文字列 aab の出現

a

位置は，それぞれ T1 [1, 4] と T1 [2, 4] であり，終端出現位置が一2b

致しているため同一のノードで表現されている．しかし，部分
文字列 ab は T1 [3, 4] 以外にも T2 [1, 2] や T2 [3, 4]，T3 [2, 3] でも

c2表現されているため，異なるノードで表現される．したがって，
接尾辞木と違い，各辺ラベルは単一文字を表現する．Blumer

2らによって，DAWG のノード数と枝数は O(n) 個であることが示されている．根ノードから各文字列 Ti で遷移した先のノー
ドが，子ノードを持たない時，そのノードを sink ノードと呼DAWG

ぶ．DAWG(S) の根からあるノード v に到達するパスを考え

a

b

a b
a
b

b

る．このとき v への最長パスを構成する枝とそうでない枝に分1,3類され，それぞれを primary な枝と secondary な枝と呼ぶ．

a
c

a
b

1,3

c

b
c
c

3

同一の文字列集合に対する接尾辞トライと接尾辞木，部分語
グラフそれぞれの例を図 1 に示す．

2. 5 オンライン入力
次に，索引の完全オンライン構築を定義するために，いくつ

1cかの概念を準備する．任意の正整数を K >= 1 とおく．非負整2

図 1 文字列集合 S = {T1 = aaab, T2 = ababc, T3 = bab} に対す数t>= 0 を時刻とし，初期状態を t = 0 で表す．このとき，完
全オンライン入力とは，長さ n の列る，接尾辞トライ (Suﬃx Trie) と接尾辞木 (Suﬃx Tree)，部分S = (k1 , a1 ), · · · , (kt , at ), · · · , (kn , an ) (1 <
=t<
= n)

語グラフ (DAWG) の例．実線と破線はそれぞれ枝と接尾辞リンクを表している．

である．ここに，各 1 <=t<= n に対して，(kt , at ) ∈ [1, K] × Σ
ある．この時，v を位置 x のノード，または単にノード x と書いて表現する．S のすべての接尾辞は根からのパスラベルで表現される．ノード ax から x へのポインタ slink (ax) = x を接尾辞リンク (suﬃx link) と呼ぶ．

2. 3 一般化接尾辞木
接尾辞トライから，分岐のないパスを辺におきかえ，ラベル
として文字列をもたせたものを接尾辞木 STree(S) という [4]．
このような内部ノードがすべて分岐を持つトライはコンパクト
トライと呼ばれる．n 個の葉をもつコンパクトトライは，高々n − 1 個の内部ノードしかもたないことが保証される．各ラベ
ル文字列 x = TK [i..j] を，整数の三つ組 ⟨k, i, j⟩ で表現することにより，接尾辞木は O(n2 ) 文字ある接尾辞集合を O(n) 語領
域で表現できる．文字列集合に対する接尾辞木を特に一般化接

は時刻 t に受けとった組である．すなわち，1 <= kt <= K は任意の文書番号であり，at ∈ Σ は任意の文字である．各時刻 t >
=0
(t)

(t)

での K-文字列集合 S (t) = {S1 , . . . , SK } を次のように帰納的に定める：•

時刻 t = 0 の時，S (0) は空文字だけからなる K-文字列(t)集合である．すなわち，任意の文書番号 i に対して，Ti

=ε

である．

•

時刻 t >= 1 の時，入力の組 (k, a) = (kt , at ) にたいして，集合 S (t) は前の時刻の集合 S (t−1) から，選ばれた文字
列 Tk の末尾に新しい文字 a を連結して得られる．すなわち，
(t)

Tk

(t−1)

= Tk

(t)

(t−1)

· a かつ Tk′ = Tk′, k′ ̸= k である．

また，準オンライン入力とは，長さ n の列

S = (k1 , a1 ), · · · , (kt , at ), · · · , (kn , an ) (1 <=t<= n, kt <= kt+1 )

1
1

T1
T2

5

T3

6

a
a
a

2
2

8

7

3
3

b

9

b

10

b

a
a
b

4

12

4

5

6

b

…

…

b

11

a

13

c

…

…

…

a

Tk

a

a

lrsT ’ (Tk)lrsT (Tk a)

図 2 オンライン一般化接尾辞木問題における多重ストリームからの(4,T1, b), (5,T2, a), (6,T3, a), (7,T3, b), (8,T2, b), (9,T2,aaa

文字列集合 S = {T1 = abab, T2 = abab, T3 = abba} の入力
例．完全オンラインテキスト (1,T1, a), (2,T1, b), (3,T1, a),aa}Type-1}

Type-2}Type-3図 3 Tk a の接尾辞の分類．lrs τ (Tk ) は文字列集合 τ 上で２回以上出現している最長の Tk の接尾辞を表す．

a), (10,T3, b), (11,T3, a), (12,T2, b), (13,T2, c) からの入力を示す．ここで，時刻 t の入力 (k, a) を三つ組 (t, k, a) で示している．図の左上の数字は入力順である．

の文書番号 k (1 <=k<
= K) と文字 a の組 (k, a) を受け取り Tkの末尾に文字 a を追加した場合，文字列 T1 , . . . , Tk−1 はそれである．すなわち，ある時刻 t で文字列 Tkt の末尾に文字が追加された時，k1 . . . kt−1 番目の文字列が確定する．
図 2 に，完全オンライン入力における文字列集合の入力例を示す．

以上文字が追加されることはなく，また，文字列 Tk+1 , . . . , TK
は空文字列のままである．
文字列集合 S ′ に対する部分語グラフ DAWG(S ′ ) が構築されていることを仮定し，入力 (k, a) を受け取り，文字列 Tk に文字a を追加した後の文字列集合 S の DAWG(S) を構築すること

2. 6 オンライン索引構築問題
以下に，文字列集合索引の準オンライン構築問題と完全オンライン構築問題を定義する．

を考える．すなわち，DAWG(S ′ ) に Tk a の接尾辞を挿入する．
このとき，Tk a の各接尾辞は以下の 3 つのタイプに分類される．S 中に２回以上出現する Tk の最も長い接尾辞を lrs S (Tk )とする．

文字列集合索引の準オンライン構築問題
入力： 正整数 K >= 1 と Σ 上の長さ n の準オンライン入力

タイプ 1: lrs s (Tk )a よりも長い Tk a の接尾辞.

S = (k1 , a1 ), · · · , (kt , at ), · · · , (kn , an )タイプ 2: lrs s (Tk )a よりも短く，lrs S (Tk a) よりも長い Tk a

(1 <
= t <
= n, kt <=の接尾辞.

kt+1 ).
出力： 各 t = 1, . . . , n に対して，K-文字列集合 S

(t)

に対す

タイプ 3: lrs S (Tk a) よりも短い Tk a の接尾辞.

) を出力する．ただし，任意の時

図 3 に上記の分類を図示する．Blumer らのアルゴリズは Tk a

点でパターン照合クエリ P ∈ Σ∗ が与えられたとき，これに正の接尾辞を長いものから順に挿入していく．すなわち，まずはしく答えられる必要がある．

じめにタイプ１の接尾辞から挿入され，次にタイプ２接尾辞がるテキスト索引 I

(t)

= I(S

(t)

挿入される．タイプ３の接尾辞は，定義より既に DAWG(S ′ )
文字列集合索引の完全オンライン構築問題

で表現されているため，挿入する必要はない．

入力： 正整数 K >= 1 と Σ 上の長さ n の完全オンライン入力

準オンライン構築アルゴリズムは，位置 Tk を表現する活性S = (k1 , a1 ), · · · , (kt , at ), · · · , (kn , an ) (1 <
=t<
= n).
出力： 各 t = 1, . . . , n に対して，K-文字列集合 S (t) に対す点 (active point) と呼ばれる参照から始まる．この活性点を位るテキスト索引 I (t) = I(S (t) ) を出力する．ただし，任意の時

新たな文字 a を挿入していくことで Tk a のすべての接尾辞を挿

点でパターン照合クエリ P ∈ Σ∗ が与えられたとき，これに正入する．活性点から文字 a を挿入するとき，以下の２つの場合

しく答えられる必要がある．

に分類できる．いま活性点が表現しているノードを v とする．

3. 部分語グラフの完全オンライン構築

置 Tk から１つずつ短い接尾辞を表す位置に遷移させながら，（ 1 ） 位置 v から文字 a で遷移できるパスが既に存在している場
合，va のすべての接尾辞はタイプ３に分類される．この場

本節では，一般化接尾辞木の完全オンライン構築に必要な，合，以下の２つに細分化される．場合１の手続きを終了し文字列集合に対する部分語グラフの完全オンライン構築アルゴ

たとき，新たな文字 a の DAWG(S ′ ) への挿入は終了する．

リズムについて考察する．はじめに Blumer らによって提案された準オンライン構築アルゴリズムを紹介する．次に，そのアルゴリズムを拡張した完全オンライン構築アルゴリズムを提案
する．

3. 1 Blumer らによる準オンライン構築アルゴリズム
Blumer らによって提案された，文字列集合 S = {T1 , . . . , TK }に対する部分語グラフ DAWG(S) の準オンライン構築アルゴ
リズムを導入する [2]．準オンラインの状況下では，もし入力（ a ） v から伸びる a のラベルがついた枝が primary な枝である場合，部分語グラフの構造に更新はない．このとき位置 va は lrs S (Tk a) を表現している．場合２により新たな sink ノード s を作成している場合は，s の接尾辞リンクを va に設定する．また，もし v が位置 Tkを表現していたならば，新たな活性点は va になる．
（ b ） v から伸びる a のラベルがついた枝が secondry な枝である場合は部分語グラフの構造の更新が必要である [2]．v から a で到達したノードを u とする．まず，新たなノード w を作成する．次に，u に入る secondry
な枝で u のタイプ３接尾辞を表しているものをすべて

w への入力辺として付け替える．これは，v から接尾辞リンクをたどることで実行できる．次に，u からの得る．
定理 1. K 本の文字列の集合 S に対して n 個の完全オンライ
ン入力が与えられたとき，O(n log σ) 時間かつ O(n) 語領域でDAWG(S) を更新可能である．

出辺をすべて w にコピーする．最後に，w の接尾辞

各文字列の先頭に，他のどの場所にも出現しない特別な区切

リンクを，u の接尾辞リンク先に設定し，u の接尾辞

り文字 #k がついていることを仮定する．その時，部分語グラリンクは w へのポインタへと変更する．このとき位フ DAWG(S) の（逆）接尾辞リンクが，接尾辞木 STree(S) に置 va = w は lrs S (Tk a) を表現している．場合２によなることが知られている [2]．ここに，S は S の各文字列をす

り新たな sink ノード s を作成している場合は，s の接べて反転したものである．これにより，定理 1 から，文字列が尾辞リンクを w に設定する．もし v が位置 Tk を表現

右から左に伸長する right-to-left 完全オンライン接尾辞木構築

していたならば，新たな活性点の位置は w となる．

についての以下の系が導かれる．

（ 2 ） v から a の出辺がない場合，v が sink ノードなら新たな系 2. K 本の文字列の集合 S に対して n 個の完全オンライ

sink ノード s を作成する．次に v からシンク s へ文字 a

ン入力が与えられたとき，O(n log σ) 時間かつ O(n) 語領域での辺で接続する．活性点を v の接尾辞リンク先に変更し，STree(S) を更新可能である．

もう一度文字 a の挿入を試みる．新たな sink ノード s は

Tk a を表現している．そのため，場合１により部分語グラフの更新が終了した場合は，活性点を s に設定する．

4. 一般化接尾辞木のオンライン構築
本節では，文字列集合に対する一般化接尾辞木の完全オンラ

新たに作成したノードと枝，接尾辞リンクの数を q とする場

イン構築アルゴリズムを提案する．初めに，Ukkonen によっ合，明らかに上記の手続きは O(q log σ) 時間かかる．ここでて提案された left-to-right 準オンラインアルゴリズムを導入す

log σ は文字 a ではじまる出辺を見つけるのにかかる時間である．次に，Ukkonen によるアルゴリズムが，部分語グラフのよる．DAWG(S) のノードと枝，接尾辞リンクの数は O(n) 個でうに簡単に拡張することができない理由を示す．最後に一般化あるため, １文字挿入するのにかかる時間はならし O(log σ) 時

接尾辞木の left-to-right 完全オンライン構築アルゴリズムを提間である. 以上により，DAWG(S) は O(n log σ) 時間と O(n)案する．

4. 1 Ukkonen の Left-To-Right 準オンライン一般化接

語領域で準オンライン構築可能である．
事実 1. Blumer らによるアルゴリズムは，総文字列長 n の文字列集合 S に対して，O(n log σ) 時間と O(n) 語領域で準オンライン構築可能である．

尾辞木構築アルゴリズム
文字列集合 S ′ に対する一般化接尾辞木 STree(S ′ ) が構築されていることを仮定し，入力 (k, a) を受け取り，文字列 Tk に
文字 a を追加した後の文字列集合 S の STree(S) を構築するこ

3. 2 完全オンライン構築アルゴリズムとを考える．準オンラインの状況下では，もし入力の文書番号

次に，上で説明した Blumer らの準オンラインアルゴリズム

k (1 <=k<= K) と文字 a の組 (k, a) を受け取り Tk の末尾に文を基に，完全オンライン状況下での構築アルゴリズムを提案

字 a を追加した場合，文字列 T1 , . . . , Tk−1 はそれ以上文字が追する．

加されることはなく，また，文字列 Tk+1 , . . . , TK は空文字列の部分語グラフの完全オンライン構築は，準オンライン構築時ままである. このとき，静的な文字列 T1 , . . . , Tk−1 の末尾に，に管理していた活性点を１つではなく，すべてのテキストに他のどの場所にも出現しない特別な区切り文字 $k がついてい′対し持つことで可能である．再び，文字列集合 S に対する部′ることを仮定する．Ukkonen による接尾辞木のオンライン構

分語グラフ DAWG(S ) が構築されていることを仮定し，入力

築では，位置 lrs S (Tk ) から始まる活性点を１つずつ短い接尾辞(k, a) を受け取り，文字列 Tk に文字 a を追加した後の文字列集を表す位置に遷移させながら，新たな文字 a を挿入していくこ

合 S の DAWG(S) を構築することを考える．部分語グラフのとで Tk a のすべての接尾辞を挿入する．このとき，葉ノードの更新は，k 番目の文字列の活性点 vk = [T ]から始まり，それ更新を省略することで，接尾辞木全体を O(n) 時間で構築する．

以後は 3. 1 節で示した準オンラインアルゴリズムの動作とまっ

位置 v に新たな文字 a の挿入を行う時， 3. 1 節で導入した挿入k S′

たく同様である．図 4 に完全オンラインでの更新例を図示すする Tk a の接尾辞の分類に従って次の 3 通りの場合がある．

る．新たに作成したノードと枝，接尾辞リンクの数を q とする

タイプ１

場合，明らかに上記の手続きは O(q log σ) 時間かかる．ここで葉ノードへ向かう枝のラベルを更新する必要があるが，後述す

位置 v は既に他の枝と重ならない単独の葉である．

log σ は文字 a ではじまる出辺を見つけるのにかかる時間である方法で省略可能である．

る．DAWG(S) のノードと枝，接尾辞リンクの数は O(n) 個でタイプ２あるため, １文字挿入するのにかかる時間はならし O(log σ) 時

木に含まれない．従って v で分岐し，新しい葉を追加する．

位置 v から文字 a で遷移できない．すなわち Tk a は間である. 以上により，DAWG(S) は O(n log σ) 時間と O(n)タイプ３

語領域で準オンライン構築可能である．ここで以下の定理を含まれている．木の更新の必要はない．

挿入点 v から文字 a で延長された点は，すでに木に図 4

完全オンライン部分語グラフにおける更新．S ′ = {T1 = abab, T2 = aaab} から

S = {T1 b, T2 } へ更新する．T1 の sink ノードから順に新しい文字 b を挿入していく．

Blumer らによる部分語グラフの準オンライン構築と同様に，性点を用意する方法を考える．各活性点 vk は準オンラインの

Tk a の接尾辞を長いもの（タイプ１）から降順に挿入してい設定と同じく，２回以上出現している Tk の接尾辞の中で最もく．ここで，葉へ向かうラベルを (k, i, ∞) の三組で表現し，常長いものを表す位置 lrs S (Tk ) を覚えておき，そこから順に文に Tk [i..|Tk |] を参照することで，タイプ 1 の接尾辞の明示的な

字 a を挿入していく．しかしながら，完全オンラインの状況下

挿入を省略することができる．Ukkonen のアルゴリズムでは，では，lrs S (Tk ) の位置は，k 番目の文字列以外の入力で逐次変上記の性質を利用して，タイプ 1 では処理を省略し，タイプ 2更される．図 ??に活性点が引き戻される例を示す．そのため，の接尾辞から挿入していく．タイプ 2 の接尾辞で最長のもの

入力のたびにすべての活性点を正しい位置に管理した場合，nは，位置 lrs S (Tk ) で表現されている．そのため，活性点は位個の入力に対して，一般化接尾辞木の構築に O(Kn log σ) 時間

置 lrs s (Tk ) を保存しておき，そこからタイプ２の接尾辞を長を要する．

さの降順に挿入していく．STree(S ′ ) 上の活性点の位置 v から問題２ また，仮にすべての活性点を正しい位置に管理できた

文字 a で遷移できないときは，新たな葉ノード w を作成し，vとしても，活性点の位置が引き戻されることによる影響がある．

と w を文字 a から始まるラベルで接続する．その後，活性点

いま j 番目の活性点の位置が参照 (vj , cj , ℓj ) で表現されていたを v の接尾辞リンク先に変更し，同様の処理を行う．この時，とする．その時，入力 (k, a) により，j 番目の活性点の位置が最初に位置 v から文字 a で遷移可能であるとき，パスラベル

参照 (vj′ , c′j , ℓj′ ) に変更された時，ℓ′j >= ℓj という不等式が成り

va = lrs s (Tk ) は最長のタイプ 3 接尾辞である．そのため，活立つ．Ukkonen の準オンライン構築アルゴリズムでは，ℓ′j をタ

性点を位置 va に変更し，文字 a の挿入を終了する．この活性

イプ２の接尾辞の挿入回数で抑えることで，時間計算量をなら点の更新はフェーズ n = |S| が進むたびに，拡張される接尾辞

し線形時間にしていたが，活性点が引き戻される場合 ℓ′j をならの開始位置 j の深さが単調に増加することを意味する．そのたすことはできない．このように，完全オンラインの状況下では，

め，後戻りを行わずオンライン線形時間構築が可能となる．

準オンラインにおける計算量をならすテクニックが使えない．

4. 2 left-to-right 完全オンライン接尾辞木構築の問題点

問題３ 別の問題として，葉ラベルの管理があげられる．各文

部分語グラフと違い，接尾辞木の場合，準オンラインと同様

字列の末尾にユニークな区切り文字を挿入する準オンラインとの時間計算量で完全オンラインへの拡張することは容易ではな

違い，完全オンラインの設定では，j 番目の文字列の部分文字

い．以下に，その理由を 3 つあげる．

列を参照する三つ組 (j, i, ∞) で表現された葉ラベルを，別の文

問題１ 入力として文書番号と入力文字の組 (k, a) を受け取り，

字列 Tk が追い越す状況が発生する．このとき，j 番目の文字

k 番目の文字列 Tk が Tk a に更新される場合を想定する．部分列が管理する葉ラベルで変更が必要なものをすべて，k 番目の語グラフの完全オンライン構築と同様に，文字列の本数だけ活文字列が管理する葉ラベルに変更しなければならない．このた

DAWG
a

b

a

a

b

c

a

a

b

b

b
cc

b
c

c

c

LPT
b

a
a
a

a

b

b

a
c

b

b

c

c

Suffix Tree
a

c
b

b

c

a
a
図

5 長 さ n=10 の 完 全 オ ン ラ イ ン 入 力 S

=

b a

b

b

c

a

b
c

(1, a), (1, b), (2, b), (1, a), (2, a), (1, b), (1, c), (2, b), (2, c), (2, d)cが与えられた時の接尾辞木の構築．時刻 t = 8 時の S 8 = {T1 =ababc, T2 = bab} における接尾時木と，時刻 t = 10 時のS 10 = {T1 = ababc, T2 = babcd} における接尾時木を示す．
lrs S (Ti ) は文字列集合 S 上で 2 回以上出現している文字列 Tiの最長の接尾辞を表す．S 8 と S 10 において，lrs

S (T1 ) の位置が引き戻されることを示している．

図6

S ′ = {T1 = aaab, T2 = ababc, T3 = ab} と S = {T1 c, T2 , T3 }に 対 す る ，部 分 語 グ ラ フ DAWG(S) と そ の LPT (S) とSTree(S ′ ) の対応．DAWG における太矢印は primary な枝を表す．破線矢印は LPT (S) と STree(S ′ ) で対応するノード間を表す．

め，準オンラインでは可能だった，３つ組によるタイプ１接尾辞の更新省略テクニックを用いることができない．
以下の節でこれらの問題を，部分語グラフを用いて解決する方法を示す．

4. 3 left-to-right 完全オンライン一般化接尾辞木構築アルゴリズム

辞リンクを探す問題は suﬃx tree oracle と呼ばれる．我々は，Fischer と Gawrychowski ら [8] による suﬃx tree oracle のな
らし計算量版を導入する．これらにより，問題１，２を解決する．問題３のためには，葉ラベルの新たな表現方法を導入する．
補題 3. 文字列集合 S ′ に入力 (k, a) を追加し，文字列集合 S

本小節では，部分語グラフを用いて，上記の問題点を解決し，に更新する場合を考える．ある文字列 Tk a の最長タイプ３接尾一般化接尾辞木の完全オンライン構築アルゴリズムを提案する．

辞 lrs S (Tk a) の STree(S ′ ) 上の位置を，S の総文字列長に線形

図 7 に完全オンライン状況下における接尾辞木の更新例を示め

な領域の補助データ構造を用いることで O(log σ) 時間で計算

す．アルゴリズムの概要を以下に示す．Tk a の接尾辞の挿入を，可能である．

Ukkonen のアルゴリズムとは逆に，タイプ２の最も短いもの
から順に昇順で挿入していく．そのために，最も長いタイプ３
接尾辞の位置 v からアルゴリズムを始める．このアイデアは，接尾辞木の実時間構築 (real time construction) でも用いられている [7]．挿入開始地点を見つけるために，まず部分語グラ
フ上で挿入開始地点を見つけ，それに対応する接尾辞木上の位置を計算する．また，１つ長い接尾辞へ移動するためには，接尾辞リンクの逆リンクを導入する必要がある．対応する逆接尾（証明）

S ′ の longest path tree, LPT LPT (S ′ ) を導入する．

LPT (S ′ ) は，DAWG(S ′ ) の primary 枝のみからなる木構造である．LPT の各ノードは，対応する部分語グラフのノードが分岐している時，マークをつけられる．また，マークされたノードと，同じ部分文字列を表現する STree(S ′ ) 上の実ノードを互
いにリンクする．また，LPT (S ′ ) は nearest marked ancestor(NMA) と呼ばれるデータ構造 [9] により，(1) 任意のノードから，最も近いマークされた祖先のノードを返す．(2) マークさ

図 7

完全オンライン一般化接尾辞木問題における更新．S ′ = {T1 = abab, T2 = aaab} から

S = {T1 b, T2 } へ更新する．まず，タイプ 1 の接尾辞 ababb, babb は対応する部分語グラフ DAWG(S) の更新で自動的に行われる．その後，タイプ 1 の接尾辞を，逆接尾辞リンクを用いて短いものから順に挿入していく．

れていないノードを挿入する．(3) ノードをマークする．操作の総文字列長に線形な領域の補助データ構造を用いることでをならし O(1) 時間で行える．

O(log σ) 時間で計算可能である．
′

入力 (k, a) に対して，DAWG(S ) を DAWG(S) に更新した
時，DAWG(S ′ ) 上で最後に挿入した接尾辞は，ある文字列 Tk aの最長タイプ 3 接尾辞 lrs S (Tk a) の DAWG(S) 上の位置を表している．そこで，DAWG(S ′ ) を更新後，DAWG(S) の lrs S (Tk a)に対応する LPT (S) のノード v から対応する STree(S ′ ) 上のノード v ′ へ移動を行えばよい．この時，ノード v がマークされているならば，リンクを辿った先が STree(S ′ ) 上の lrs S (Tk a)に対応するノード v ′ である．ノード v がマークされていない
場合，NMA クエリをかけることで，最も近いマークされた祖先のノード u を見つけ，そこから u に対応する接尾辞木上のノード u′ に移動する．u′ から v ′ への移動は，u と v の文字深さの差をオフセットとして u′ から移動すれば良い．この時，枝の選択に O(log σ) 時間がかかる．また，u′ から v ′ のパス上には，LPT のマークされたノードの定義より実ノードは存在しない．STree(S ′ ) 上の v ′ で新たな実ノードが作成された場合，′

上記補題により，最長のタイプ３接尾辞の位置を計算できる．そこから，接尾辞を昇順に挿入していくには，接尾辞木
上の逆接尾辞リンクをたどって，１文字長い接尾辞を表現す
る位置に移動する必要がある．逆接尾辞リンクとは，ノード vと文字 b に対して，slink (vb) = v の時，rslink b (v) = vb と定義されるリンクである．ここで，suﬃx tree oracle とは，ノード v と文字 b の組 (v, b) が与えらえれた時，rslink b (u) が定義されている v の最近祖先 u を返すデータ構造である．Fischerと Gawrychowski [8] による suﬃx tree oracle では，最悪計算
量 O(log log n + (log log σ)2 / log log log σ) 時間と O(n) 語領域
でこれを達成する．ここに，n は接尾辞木の葉ノードの個数である．以下の補題で，より単純なならし計算量の suﬃx tree

oracle を導入する．
補題 4. n 個の葉を持つ接尾辞木に対して，領域 O(n) 語で，LPT (S) の v をマークし，v とリンクすれば良い．DAWG(S)suﬃx tree oracle クエリをならし O(log σ) 時間で答え，ならしの領域計算量は STree(S) と同じく O(n) 語であり，NMA デー

O(log σ) 時間で新たな接尾辞を挿入可能である，ここに σ はアタ構造 [9] はノード数に線形な領域で格納できるため，明らか

ルファベットサイズである．

にこの補助データ構造は S の総文字列長に線形な領域計算量（証明）を持つ．時間計算量は，DAWG(S) の lrs S (Tk a) の位置を見

oracle では，最悪計算量を達成するために，NMA クエリを最つけるために，DAWG(S ′ ) から DAWG(S) に更新するならし(Sketch) Fischer と Gawrychowski [8] の suﬃx tree

悪 O(log log n) 時間で解くデータ構造を採用している [7]．こO(log σ) 時間かかる．lrs S (Tk a) から NMA クエリを引く時間のデータ構造を Westbrook [9] による NMA 構造に置き換えはならし O(1) 時間である．接尾辞木上の lrs S (Tk a) の位置をることにより，ならし O(1) 時間で解くことができる．また，計算するために，枝の選択が１回必要なので，O(log σ) 時間(log log σ)2 / log log log σ の項は整数アルファベットを仮定し′かかる．以上により，lrs S (Tk a) の STree(S ) 上の位置を，Sたときに predecessor クエリをとくための時間である．我々は，

二分木用いることで，より一般的なアルファベットに対してpredecesor クエリを O(log σ) 時間でとく．以上により，計算量はならし O(log σ) 時間となる．

[5]

最後に，問題３を解決するため，葉へ向かう辺のラベルの新
たな参照表現であるラベルの遅延表現を導入する．基本的なア[6]

イデアは，葉へ向かう最初の一文字のみ管理し，具体的なラベル文字は，対応する部分語グラフ上で読み取る方法である．こ[7]

れにより，以下の補題を与える．
補題 5. 入力 (k, a) が与えられたとき，葉へ向かうラベルの遅[8]延表現により，ならし O(log σ) 時間で，必要なすべての葉ラベ
ルの更新が可能である．
（証明）(Sketch). STreeS の内部ノード w から，新たな葉ノード e を挿入した時，w に対応する部分語グラフのノード w′

[9]
[10]

は，sink ノードまでのパスで，w から e までのラベルを表現している．葉へ向かうラベルは，部分語グラフによる新たな sink
ノードの作成で自動的に更新される．問題となるのは，先頭文字しか記憶していない w から e への辺上で，新たな内部ノード[11]

u を作成した時である．この時，w から u へのラベル l は先頭一文字を除いて不明だが，新たな入力が到着するたび，部分語グラフの対応するノードからラベル文字を読み取り，l を遅延評価で確定させることができる．
以上の補題により，以下の定理を得る．
定理 6. K 本の文字列の集合 S に対して n 個の完全オンライ
ン入力が与えられたとき，O(n log σ) 時間かつ O(n) 語領域でSTree(S) を更新可能である．

5. ま と め
本稿では非同期に文字が入力される複数ストリームに対する索引構築を考察した．その結果，まず完全オンライン構築の設定を導入した．次に，部分語グラフのならし O(n log σ) 時間とO(n) 語領域で完全オンライン構築するアルゴリズムを与えた．
ここで n は総文字列長，σ はアルファベットサイズである．最後に，一般化接尾辞木について，部分語グラフと並列に構築することでならし O(n log σ) 時間と O(n) 語領域で完全オンライン構築するアルゴリズムを与えた．今後の課題として，実際のストリームデータでは，スライディングウィンドウ [10] や頻出
語の適応的収集 [11, 12] などのより高度な機能をもつ文字列索引も必要である．
文

献[1] E. Ukkonen. On-line construction of suﬃx trees. Algorithmica, Vol. 14, No. 3, pp. 249–260, 1995.
[2] A. Blumer, J. Blumer, D. Haussler, R. Mcconnell, andA. Ehrenfeucht. Complete inverted files for eﬃcient text
retrieval and analysis. J. ACM, Vol. 34, No. 3, pp. 578–595,
1987.
[3] Dan Gusfield and Jens Stoye. Linear time algorithms forfinding and representing all the tandem repeats in a string.
J. Comput. Syst. Sci., Vol. 69, No. 4, pp. 525–546, 2004.
[4] P. Weiner. Linear pattern-matching algorithms. In Proc. of[12]

14th IEEE Ann. Symp. on Switching and Automata Theory, pp. 1–11, 1973.
Anselm Blumer, Janet Blumer, David Haussler, Andrzej
Ehrenfeucht, M. T. Chen, and Joel Seiferas. The smallest automaton recognizing the subwords of a text. TCS,
Vol. 40, pp. 31–55, 1985.
Dan Gusfield. Algorithms on Strings, Trees, and Sequences:
Computer Science and Computational Biology. Cambridge
University Press, 1997.
Dany Breslauer and Giuseppe F. Italiano. Near real-time
suﬃx tree construction via the fringe marked ancestor problem. J. Discrete Algorithms, Vol. 18, pp. 32–48, 2013.
Johannes Fischer and Pawel Gawrychowski. Alphabetdependent string searching with wexponential search trees.
In CPM 2015, pp. 160–171, 2015. Full version is available
at http://arxiv.org/abs/1302.3347.
Jeﬀery Westbrook. Fast incremental planarity testing. In
ICALP 1992, pp. 342–353, 1992.
Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda,
and Setsuo Arikawa. Compact directed acyclic word graphs
for a sliding window. In Proceedings of 9th International
Symposium on String Processing and Information Retrieval(SPIRE 2002), pp. 310–324, 2002.
高木拓也, 有村博紀. マルチヘッド接尾辞トライを用いた低メモ
リ型マルチストリーム索引の構築. 第 7 回データ工学と情報マ
ネージメントに関するフォーラム (DEIM’15), No. P2. 電子情報通信学会, 2008 年 3 月.
上村卓史, 金田悠作, 喜田拓也, 有村博紀. 大規模なテキストに対する部分文字列出現頻度の推定. 第 19 回データ工学ワークショップ (DEWS ’08), No. E7-1. 電子情報通信学会, 2008.