冬のLAシンポジウム 2019 [26]

複数テキスト索引構造のオンライン構築
高木 拓也 （富士通研究所）〇 稲永 俊介 （九州大学）
有村 博紀 （北海道大学）
Dany Breslauer （無所属）
Diptarama Hendrian （東北大学）

オンライン複数文字列の索引


問題: 末尾に文字の追加を許す複数の文字列に対する索引を高速に構築せよ.



動機: マルチストリームデータ処理
 各種センサ，トラジェクトリ，Twitter，などなど

索引
センサ群
s1

ユーザ
T1 abcaab

s2

T2 cc

s3

T3 bcdax

オンライン複数文字列の索引


問題: 末尾に文字の追加を許す複数の文字列に対する索引を高速に構築せよ.

動機: マルチストリームデータ処理
 各種センサ，トラジェクトリ，Twitter，などなど

索引
センサ群
s1
s2
s3

ユーザ
a

T1 abcaab
T2 ccaT3 bcdax

オンライン複数文字列の索引


問題: 末尾に文字の追加を許す複数の文字列に対する索引を高速に構築せよ.

動機: マルチストリームデータ処理
 各種センサ，トラジェクトリ，Twitter，などなど

索引
センサ群
cs1

ユーザ
T1 abcaabc

s2

T2 ccas3

T3 bcdax

オンライン複数文字列の索引


問題: 末尾に文字の追加を許す複数の文字列に対する索引を高速に構築せよ.



動機: マルチストリームデータ処理
 各種センサ，トラジェクトリ，Twitter，などなど

索引
センサ群
s1

T1 abcaabc

s2

T2 ccas3

T3 bcdax

bc? ユーザ

接尾辞木 (Suffix Tree)

入力文字列 T のすべての接尾辞を表現する
根つき木 (オートマトンの亜種)

T = ababcの接尾辞

Tababcbabc
abc
bccab bcab cccabcbab?

接尾辞木 (Suffix Tree)

入力文字列 T のすべての接尾辞を表現する
根つき木 (オートマトンの亜種)

T = ababcの接尾辞Tababc
babc
abcbccab bcab cccabcbab?

複数文字列に対する接尾辞木

複数の入力文字列 T1, …, TK のすべての接尾辞を表現する根つき木

T1 = a b a b c
T2 = b a a a b
K = 2 の場合

cab cbaaab bbacca ba cb

複数文字列に対する接尾辞木

複数の入力文字列 T1, …, TK のすべての接尾辞を表現する根つき木
複数文字列の共通パターン発見

T1 = a b a b c
T2 = b a a a b
K = 2 の場合

cab cbaaab b

各文字列 Ti の末尾/先頭に新たな文字が追加される毎に，接尾辞木を高速に更新したい

bacca ba cbba?

【本研究の出発点】
単一文字列の場合の構築時間

複数文字列の場合は？

右左オンライン構築 [Weiner 1973]
文字を先頭に追加していく単一文字列の接尾辞木をO(n log σ)時間・O(n) 領域で構築できる．

左右オンライン構築 [Ukkonen 1995]
文字を末尾に追加していく単一文字列の接尾辞木をO(n log σ)時間・O(n) 領域で構築できる．
n：文字列の長さ，σ：文字種類数※ 比較モデルでは O(n log σ) 時間が最適 ソートの下界 Ω(n log σ) が適用される研究の初期段階

2015年5月～

右左オンライン（先頭に文字追加）については，Weiner のアルゴリズムをそのまま複数文字列に拡張できそうですね

高木君

有村先生

稲永

研究の初期段階
イケそうですね高木君

イケてますね有村先生

稲永

研究の初期段階
左右オンライン（末尾に文字追加）については，
Ukkonen のアルゴリズムをそのまま複数文字列に拡張するのは難しそうですね？

高木君

有村先生

稲永

研究の初期段階
そこをなんとか

高木君

有村先生

稲永

研究の初期段階
右左オンラインの接尾辞木を並行して構築することで，左右オンラインの接尾辞木を構築できそうです

高木君

有村先生

稲永

研究の初期段階
イケそうですね高木君

イケてますね

有村先生

稲永

本研究にまつわるヒストリー
2015/5
2016/7

研究開始（高木，稲永，有村）
文字列処理に関する国際会議 CPM で発表

CPM 2016 の論文の主張
主張１ （右左オンライン構築）
Weiner のアルゴリズムをそのまま適用することで，先頭に文字が追加されていく複数文字列の接尾辞木を O(N log σ)時間・O(N) 領域で構築できる．

主張２ （左右オンライン構築）
主張１の結果と，Ukkonen のアルゴリズムを用いて，末尾に文字が追加されていく複数文字列の接尾辞木を O(N log σ)時間・O(N) 領域で構築できる．
N：複数文字列の長さの総和，σ：文字種類数

Dany からメールが届く

2017年1月

あなた方の CPM の論文を読みました．
残念ながら間違ってると思います．
Dany Breslauer

Mjsk!?
高木君

有村先生

稲永

Dany からメールが届く

2017年1月

マジです．
複数文字列のオンライン処理特有の問題を見逃していると思います．
Dany Breslauer

やってもた…

高木君

有村先生

稲永

我々の CPM 2016 論文は主張１ （右左オンライン構築）
Weiner のアルゴリズムをそのまま適用することで，先頭に文字が追加されていく複数文字列の接尾辞木をO(N log σ)時間 O(N) 領域で構築できる．

主張２ （左右オンライン構築）
主張１の結果と，Ukkonen のアルゴリズムを用いて，末尾に文字が追加されていく複数文字列の接尾辞木をO(n log σ)時間 O(n) 領域で構築できる．
N：複数文字列の長さの総和，σ：文字種類数

本研究にまつわるヒストリー
2015/5
2016/72017/1

研究開始（高木，稲永，有村）
文字列処理に関する国際会議 CPM で発表
Dany から３人にメールが届き，CPM の論文に致命的なエラーが見つかる

全然イケてない…

チーム結成!!

2017年2～3月

高木君

有村先生

稲永一緒に問題を解決しましょう！
DanyDiptarama君

Weiner アルゴリズムの下界定理１
Weiner のアルゴリズムをそのまま複数文字列に適用すると Ω(N1.5) 時間かかる．

ウソの主張１(再掲)
Weiner のアルゴリズムをそのまま適用することで，先頭に文字が追加されていく複数文字列の接尾辞木をO(N log σ)時間 O(N)領域で構築できる．
N：複数文字列の長さの総和，σ：文字種類数
 σ ≤ N が常に成り立つΩ(N1.5) 時間の証明
aaaaa$
aaaa$
aaa$
aa$
a$

T1
T2
T3
T4
T5

Ω(N1.5) 時間の証明
a$a$
a$

$a$
a$

aaaaa$
aaaa$
aaa$
aa$a$

T1
T2
T3
T4T5

Ω(N1.5) 時間の証明
axbx
bx は文字列，b は文字とする．
x と bx を表す頂点があるとき，b でラベル付けされたリンクをx から bx に向かって張る．

a$$a$aa$aaa$
aa$aaa$ aaaaaa$
aaaa$
aaa$
aa$a$

文字列を左に伸ばすときに便利

T1
T2
T3
T4
T5

Ω(N1.5) 時間の証明
aa$

$a$

acaaaaa$aaaa$aaa$
aa$
a$a$
aaa$
aa$aaa$ a

文字追加前の T1 を表す葉からスタート

T1
T2
T3
T4
T5

Ω(N1.5) 時間の証明
aa$$

a$acaaaaa$
aaaa$aaa$aa$a$a$
aaa$aa$aaa$ a

追加文字 c のリンクを持つ最も深い頂点を探す

T1
T2
T3
T4T5

Ω(N1.5) 時間の証明
aa$$a$

acaaaaa$aaaa$aaa$aa$a$a$
aaa$aa$aaa$ a

追加文字 c のリンクを持つ最も深い頂点を探す

T1
T2
T3
T4
T5

Ω(N1.5) 時間の証明
aa$

$a$

acaaaaa$aaaa$aaa$aa$a$a$aaa$
aa$aaa$ a

追加文字 c のリンクを持つ最も深い頂点を探す

T1
T2
T3
T4
T5

Ω(N1.5) 時間の証明
aa$$a$

acaaaaa$aaaa$aaa$aa$
a$a$aaa$aa$aaa$ a

追加文字 c のリンクを持つ最も深い頂点を探す

T1
T2
T3
T4T5

Ω(N1.5) 時間の証明
aa$

$a$

acaaaaa$aaaa$aaa$
aa$
a$a$
aaa$
aa$aaa$ a

追加文字 c のリンクを持つ最も深い頂点を探す

T1
T2
T3
T4T5

Ω(N1.5) 時間の証明a$$acaaaaa$aaaa$aaa$aa$a$$c aaa a$aaaa$aaa$aaaa$ aac
根まで行っても c のリンク$がなかったので，文字追加後の T1 を表す
新たな葉を根から挿入

T1
T2
T3
T4T5

Ω(N1.5) 時間の証明
a$$acaaaaa$
caaaa$aaa$aa$a$$c aaa a$aaaa$aaa$aaaa$ aac$

追加文字 c のリンクを持つ最も深い頂点を探す

T1
T2
T3
T4
T5

Ω(N1.5) 時間の証明a$$acaaaaa$caaaa$aaa$aa$a$$c aaa a$aaaa$aaa$aaaa$ aac$

追加文字 c のリンクを持つ最も深い頂点を探す

T1
T2
T3
T4
T5

Ω(N1.5) 時間の証明
a$$acaaaaa$
caaaa$
aaa$aa$a$$c aaa a$aaaa$aaa$aaaa$ aac$

追加文字 c のリンクを持つ最も深い頂点を探す

T1
T2
T3
T4
T5

Ω(N1.5) 時間の証明a$$acaaaaa$
caaaa$
aaa$
aa$
a$

$
c aaa a$aaaa$aaa$aaaa$ aac$

追加文字 c のリンクを持つ最も深い頂点を探す

T1
T2
T3
T4
T5

Ω(N1.5) 時間の証明a$$acaaaaa$caaaa$
aaa$
aa$
a$

$
c aaa a$aaaa$aaa$aaaa$ aac$

追加文字 c のリンクを持つ最も深い頂点を探す

T1
T2
T3
T4T5

Ω(N1.5) 時間の証明a$$acaaaaa$caaaa$aaa$aa$a$$c aaa a$aaaa$aaa$aaaa$ aac$

追加文字 c のリンクを持つ最も深い頂点を探す

T1
T2
T3
T4
T5

Ω(N1.5) 時間の証明a$$acaaaaa$caaaa$aaa$aa$a$$c aaa a$aaaa$aaa$aaaca$ a$ca$※ このステップに関係ないリンクは一部省略

T1
T2
T3
T4
T5

Ω(N1.5) 時間の証明
a$$acaaaaa$
caaaa$
caaa$
aa$a$$c aaa a$aaaa$aaa$aaaca$ a$ca$※ このステップに関係ないリンクは一部省略

T1
T2
T3
T4T5

Ω(N1.5) 時間の証明a$$acaaaaa$
caaaa$
caaa$
aa$a$$c aaa a$aaaa$aaa$aaaca$ a$ca$※ このステップに関係ないリンクは一部省略

T1
T2
T3
T4
T5

Ω(N1.5) 時間の証明a$$acaaaaa$
caaaa$
caaa$
aa$a$$c aaa a$aaaa$aaa$aaaca$ a$ca$※ このステップに関係ないリンクは一部省略

T1T2
T3T4T5

Ω(N1.5) 時間の証明
a$$acaaaaa$caaaa$caaa$aa$a$$c aaa a$aaaa$aaa$aaaca$ a$ca$※ このステップに関係ないリンクは一部省略

T1T2
T3
T4T5

Ω(N1.5) 時間の証明
a$$acaaaaa$
caaaa$
caaa$
aa$a$$c aaa a$aaaa$aaa$aaaca$ a$ca$※ このステップに関係ないリンクは一部省略

T1T2
T3
T4T5

Ω(N1.5) 時間の証明
a$$acaaaaa$
caaaa$
caaa$aa$a$$c aa a a $aaa a $aac a a $a$ caa$ a$ca$※ このステップに関係ないリンクは一部省略

T1
T2
T3
T4T5

Ω(N1.5) 時間の証明
a$$acaaaaa$
caaaa$
caaa$aa$a$$c aa a a $aaa a $aac a a $a$ caa$ a$ca$※ このステップに関係ないリンクは一部省略

T1
T2
T3
T4T5

Ω(N1.5) 時間の証明
a$$acaaaaa$
caaaa$
caaa$aa$a$$c aa a a $aaa a $aac a a $a$ caa$ a$ca$※ このステップに関係ないリンクは一部省略

T1T2
T3
T4T5

Ω(N1.5) 時間の証明
a$$acaaaaa$caaaa$caaa$aa$a$$c aa a a $aaa a $aac a a $a$ caa$ a$ca$※ このステップに関係ないリンクは一部省略

T1
T2
T3
T4
T5

Ω(N1.5) 時間の証明a$$acaaaaa$
caaaa$
caaa$
aa$a$$c aa a a $aaa a $aac a a $a$ caa$ a$ca$※ このステップに関係ないリンクは一部省略

T1T2
T3
T4T5Ω(N1.5) 時間の証明
a$$caaaaa$caaaa$
caaa$
caa$a$ac$aaa$aa ac a a$a$c a aaa$
$ caa$ a$ca$※ このステップに関係ないリンクは一部省略

T1
T2
T3
T4T5

Ω(N1.5) 時間の証明
a$$caaaaa$caaaa$
caaa$
caa$
ca$

ac$aaa$aa ac a a$a$c a aaa$
$ caa$ a$ca$※ このステップに関係ないリンクは一部省略

T1
T2
T3
T4T5

Ω(N1.5) 時間の証明
a$$caaaaa$caaaa$
caaa$
caa$ca$ac$aaa$aa ac a a$a$c a aaa$$ caa$ a$ca$※ このステップに関係ないリンクは一部省略

T1
T2
T3
T4T5

Ω(N1.5) 時間の証明
a$$caaaaa$caaaa$
caaa$
caa$
ca$

ac$aaa$aa ac a a$a$c a aaa$
$ caa$ a$ca$※ このステップに関係ないリンクは一部省略

T1
T2
T3
T4T5

Ω(N1.5) 時間の証明$$

caaaaa$caaaa$
caaa$
caa$
ca$

c aaaa c$aa$$aaca a$a$c a aaa$
$ caa$ a$ca$※ このステップに関係ないリンクは一部省略

T1T2
T3T4T5

Ω(N1.5) 時間の証明$$

Kcaaaaa$caaaa$
caaa$ Kcaa$
ca$c aaaa c$aa$$aaca a$a$c a aaa$
$ caa$ a$ca$※ このステップに関係ないリンクは一部省略

K 個の c の追加に対して訪れた頂点数は Ω(K2)Ω(N1.5) 時間の証明
cc$

先頭への c の追加を
K ステップ繰り返す

KK

cccccaaaaa$
acc
cccccaaaa$$ccaacccccccaaa$
Ka$$ca$ acccccaa$acc acca$$$
ccccca$a $a cacaa c$c$
aa$$ccaaaa a $c$$ca$$caaca$ca$aa$$ca$$ a $ $c
訪れた頂点の総数 = Ω(K3)c$
文字列長の総和 N = Θ(K2)cc 時間計算量 = Ω(N1.5)

右左オンライン構築～完全版
定理 ２
先頭に文字を追加していく複数文字列の接尾辞木をO(N log σ)時間 O(N)領域で構築するアルゴリズムが存在する．
【テクニックの概要】


１文字追加につき Ω(K) 個訪れていた頂点をO(1) 時間でジャンプできればよい．



このジャンプを木の最近マーク祖先 (NMA) 問題に帰着．

NMA のデータ構造を愚直に用いると O(σN) 領域必要だが，注意深く選んだ頂点集合にのみ用いると O(N) 領域に収まる．

NMA による高速化
ccc$

頂点 v がマーク頂点 ●⇔ v は c のリンクを持つac$
caa cc ac$$$ ac caca a$$ccc aa a $ ca$$c caaac$ca $c$
aa c c$aa$c$$c

cccaaaaa$
cccaaaa$
ccaaa$
ccaa$
cca$

T1
T2
T3
T4
T5

NMA による高速化$

頂点 v がマーク頂点 ●⇔ v は a のリンクを持つ

cccaaaaa$ T1
aac
ccaaaa$ T2$aaaa
ccaaa$
T3aac$$$ accaa$ T4aaa a$$ acca$ T5aaa a $ a$a$aaa$ aa $$aa$aa$$$
このようなデータ構造をc文字ごとに構築する左右オンライン構築
定理 ４
Ukkonen のアルゴリズムをそのまま複数文字列に適用すると Ω(N2) 時間かかる．

定理 ５
末尾に文字を追加していく複数文字列の接尾辞木をO(N log σ)時間 O(N)領域で構築するアルゴリズムが存在する．
※ ただし，定理５の接尾辞木では葉のラベルを陽に管理しない．
(葉に達する場合のパターン照合は別の方法で行う)

本研究にまつわるヒストリー
2015/5
2016/72017/1

研究開始（高木，稲永，有村）
文字列処理に関する国際会議 CPM で発表
Dany から３人にメールが届き，CPM の論文に致命的なエラーが見つかる
2017/2～3 Dany と Diptarama が研究に参加
2017/7
すべての問題を解決!
2017/12/20 第１版の執筆が完了し，共著者にメール
2017/12/21 Dany が急逝
2018/3
Algorithmica に投稿
2019/10
Algorithmica に採択/掲載

Meeting with Dany @北海道大学 (2017/6）【Dany Breslauer 氏の功績に敬意を表します】