北大有村研セミナー 2023.08.21-23

Symmetric CDAWG
稲永 俊介

2

基礎的なテキスト索引
Text: cocoaoaoccca oao

パス縮約(コンパクト化)

Suffix Tree

Suffix Trieccoaoca oaa

Directed Acyclic
Word Graph (DAWG)

aco

同型マージ
(最小化)

aaco

同型マージ
(最小化)

coaoaoaaoc

パス縮約(コンパクト化)
Compact Directed Acyclic
Word Graph (CDAWG)

oaa3

基礎的なテキスト索引
Text: cocoaoaoccca oao

パス縮約(コンパクト化)

Suffix Tree

Suffix Trieccoaoca oaa

Directed Acyclic
Word Graph (DAWG)

aco

同型マージ
(最小化)

aaco

同型マージ
(最小化)

coaoaoaaoc

パス縮約(コンパクト化)
Compact Directed Acyclic
Word Graph (CDAWG)

oaa

From Suffix Trie to DAWG (最小化)babccabbacbbc

ababcbbcb

同型な木（グラフ）をボトムアップにマージしていくb
接尾辞を受理するノード

4

From Suffix Trie to DAWG (最小化)babccabbacbbc

ababcbbcb

同型な木（グラフ）をボトムアップにマージしていくb
接尾辞を受理するノード

5

From Suffix Trie to DAWG (最小化)babccabbacbbcababcbbcbb
接尾辞を受理するノード

6

From Suffix Trie to DAWG (最小化)babccabbacbbcababcbbcb

同型な木（グラフ）をボトムアップにマージしていくb
接尾辞を受理するノード

7

From Suffix Trie to DAWG (最小化)baccaababcb

bbacbccb
接尾辞を受理するノード

8

From Suffix Trie to DAWG (最小化)baccaababcbbbacbcbc

同型な木（グラフ）をボトムアップにマージしていく接尾辞を受理するノード

9

From Suffix Trie to DAWG (最小化)babccaababcbbacbcb
接尾辞を受理するノード

10

From Suffix Trie to DAWG (最小化)babccaababcb

babcc

同型な木（グラフ）をボトムアップにマージしていくb
接尾辞を受理するノード

11

From Suffix Trie to DAWG (最小化)baccaababcb

bacbcb接尾辞を受理するノード

12

From Suffix Trie to DAWG (最小化)
b?

acac?

ababcbbabcc

同型に見えるが，一方は受理ノードで他方は受理ノードではないので，マージしないb
接尾辞を受理するノード

13

From Suffix Trie to DAWG (最小化)baccaababcb

babc

DAWG of stringababcbcb
接尾辞を受理するノード

14

DAWG の最小性定理 [Blumer et al. 1985]
文字列 w の DAWG は w の接尾辞を受理する最小のオートマトンである．

明らかに suffix trie は w の接尾辞を受理する．
よって DAWG も接尾辞を受理する．



マージできるところはすべてマージしたので，DAWG が w の接尾辞を受理する最小のオートマトンである．

15

16Suffix Links of Suffix Triebabccabbacbbcabbcb

ノード ax の suffix link の文字ラベルは a で，その行き先は x である．

aS, x

S*

17

Suffix Links of Suffix Triebabccabbacbbbacbbcb

ノード ax の suffix link の文字ラベルは a で，その行き先は x である．

aS, xS*

18

Suffix Links of Suffix Triebbabccacbbaca bbbacbcbbb

ノード ax の suffix link の文字ラベルは a で，その行き先は x である．

aS, xS*Suffix Links of Suffix Triecbabbacbbca abacbbbcbcb

各 suffix link パスは必ず根に到達する．

19

Suffix Link Tree of Suffix Triebbcacca aa bbbb baacacbba bbbaaacbc bb

よって suffix link は(辺が逆向きの)木を成す(suffix link tree).

20

21

Suffix Link Tree of Suffix Triebabcabbabcbcbcabbaacbbcbba

Suffix Trie of ababcb

acbbaabaSuffix Link Tree of ababcb

22

Suffix Link Tree = 反転文字列の Suffix Triebabcabbabcbcbcabbaacbbcbba

Suffix Trie of ababcb

acbbaabaSuffix Trie of bcbaba

23

Suffix Link Tree = 反転文字列の Suffix Trie事実文字列 w の suffix trie の suffix link tree は反転文字列 wR の suffix trie に等しい．

文字列 x を表す頂点の suffix link パス はx の文字を逆順に読みながら根に到達するから．

24

ノードのマージと Suffix Link の関係
bbcabbcbabacac bbbbcbca b

マージされるノードはsuffix link パスで繋がっている25

ノードのマージと Suffix Link の関係
bbabcbcac bbbacbbcbca bab

ノードをマージするとき，suffix link を同時にパス縮約する

26

ノードのマージと Suffix Link の関係
bbaccac bbbbbacabbbacbcb

ノードをマージするとき，
suffix link を同時にパス縮約する

27

ノードのマージと Suffix Link の関係bbabcbcac bbacbbcbcbbaba

ノードをマージするとき，
suffix link を同時にパス縮約する

28

ノードのマージと Suffix Link の関係
bbcbaabcbcababcbabcbbcb

ノードをマージするとき，
suffix link を同時にパス縮約する

29

ノードのマージと Suffix Link の関係
bbcbaabcbcababcbabcbbcb

縮約した suffix link パスが
DAWG のこの頂点のsuffix link である．

30

Suffix Links of DAWGbbaacbacbaa acbbacb aabcbcbaba

DAWG の suffix link もまた木をなす31

Suffix Links of DAWGbbaacbacbaba acbbacb aabccbabaaacbabababacbabab

DAWG of ababcb

Contracted SLT of ababcb

32

SLT of DAWG = 反転文字列の Suffix Treebbaacbacbaba acbbacb aabccbabaaacbabababacbabb

DAWG of ababcb

Suffix Tree of bcbabaa33

SLT of DAWG = 反転文字列の Weiner Treeb

このような suffix tree をWeiner Tree という

baacbacbaa acbbacb aabcb

DAWG of ababcbcbababaacbabababacbaba

反転文字列の接尾辞を受理するノード

Suffix Tree of bcbaba

34

SLT of DAWG = 反転文字列の Suffix Tree定理 [Blumer et al. 1985]
文字列 w の DAWG の suffix link は反転文字列 wR の Suffix Tree に等しい．
(1) w の suffix trie のノードをマージしてオートマトンを最小化しながら，同時に suffix link をパス縮約(2) wR の suffix trie の辺をパス縮約(1) は表の世界（順向き文字列 w）を主体にした操作．
(2) は裏の世界（逆向き文字列 wR）を主体にした操作．
これらの操作は表裏一体の「同じ作業」である．

35

基礎的なテキスト索引
Text: cocoaoaoccca oao

パス縮約(コンパクト化)

Suffix Tree

Suffix Trieccoaoca oaa

Directed Acyclic
Word Graph (DAWG)

aco

同型マージ
(最小化)

aaco

同型マージ
(最小化)

coaoaoaaoc

パス縮約(コンパクト化)Compact Directed Acyclic
Word Graph (CDAWG)

oaa36

From DAWG to CDAWG わかりやすさのために表と裏の世界の対応する頂点を同じ色で塗っている
bbaacbacbaba acbbacb aabccbabaaacbabababacbabb

DAWG of ababcb

Suffix Tree of bcbaba

a37

From DAWG to CDAWG (パス縮約)
bbaacbacbaba acbbacb aabcbabacbaacbabababacbab

分岐していない頂点とその子をマージする

DAWG of ababcb

Suffix Tree of bcbaba

a38

From DAWG to CDAWG (パス縮約)
bbaacbacbbaa abb aabbcbbacbcb

DAWG of ababcb

cbabaaacbabababaSuffix Tree of bcbaba

cbaba

39

From DAWG to CDAWG (パス縮約)
bbaacbacbbaa abb aabcbbcbbacbcbabaaacbababab
分岐していない頂点とその子をマージする

DAWG of ababcbaSuffix Tree of bcbaba

cbaba

40

From DAWG to CDAWG (パス縮約)
bbaacbacbbaa abb aabcbbacbbcb

DAWG of ababcbcbabaaacbabababaSuffix Tree of bcbaba

cbaba41

From DAWG to CDAWG (パス縮約)
bbaacbacbbaa abb aabcbbcbbacbcbaba

分岐していない頂点とその子をマージする

DAWG of ababcb

aacbabababaSuffix Tree of bcbaba

cbaba

42

From DAWG to CDAWG (パス縮約)
bbaa ababcc c bbb b a aabbcabbcbabcb

DAWG of ababcbcbabaaacbabababaSuffix Tree of bcbaba

cbaba

43

From DAWG to CDAWG (パス縮約)
bbaa ababcc c bbb b a aabbcab

分岐していない頂点とその子をマージする

cbabcbDAWG of ababcb

cbababaacbabababaSuffix Tree of bcbaba

cbaba

44

From DAWG to CDAWG (パス縮約)
bbbaa a cbbabcc c bbb b a aabbcabccb

CDAWG of ababcbbabaacbaababa

CDAWG of bcbabacbaba45

From DAWG to (S)CDAWG
定理 [Blumer et al. 1987]

DAWG から CDAWG を O(n) 時間で得られる．

定理 [Blumer et al. 1987]

Suffix link 付き DAWG から Symmetric CDAWG をO(n) 時間で得られる．
n は入力文字列長46

基礎的なテキスト索引
Text: cocoaoaoccca oao

パス縮約(コンパクト化)

Suffix Tree

Suffix Trieccoaoca oaa

Directed Acyclic
Word Graph (DAWG)

aco

同型マージ
(最小化)

aaco同型マージ(最小化)

coaoaoaaoc

パス縮約(コンパクト化)
Compact Directed Acyclic
Word Graph (CDAWG)

oaa47

From Suffix Tree to CDAWG (最小化)bbaacbacbaba acbbacb aabcbabacbaacbabababacbab

Suffix link で繋がった同型な頂点をマージ

DAWG of ababcb

Suffix Tree of bcbabaa48

From Suffix Tree to CDAWG (最小化)bbaacbacbbaa abb aabbcbbacbcb

DAWG of ababcbcbabaaacbabababaSuffix Tree of bcbaba

cbaba

49

From Suffix Tree to CDAWG (最小化)bbaacbacbbaa abb aabbcbbacbcb

DAWG of ababcb

cbabaaacbabababaSuffix link で繋がった同型な頂点をマージ

Suffix Tree of bcbaba

cbaba

50

From Suffix Tree to CDAWG (最小化)bbaacbacbbaa abb aabcbbacbbcb

DAWG of ababcb

cbabaaacbabababaSuffix Tree of bcbaba

cbaba

51

From Suffix Tree to CDAWG (最小化)bbaacbacbbaa abb aabcbbacbbcb

DAWG of ababcbcbabaaacbabababaSuffix link で繋がった同型な頂点をマージ

Suffix Tree of bcbaba

cbaba

52

From Suffix Tree to CDAWG (最小化)bbaa ababcc c bbb b a aabbcabbcbabcb

DAWG of ababcb

cbabaaacbabababaSuffix Tree of bcbaba

cbaba53

From Suffix Tree to CDAWG (最小化)bbaa ababcc c bbb b a aabbcab

Suffix link で繋がった同型な頂点をマージ

cbabcbDAWG of ababcb

cbababaacbabababaSuffix Tree of bcbaba

cbaba

54

From Suffix Tree to CDAWG (最小化)bbbaa a cbbabcc c bbb b a aabbcabccb

CDAWG of ababcbbabaacbaababa

CDAWG of bcbaba

cbabaFrom Suffix Tree to CDAWGb

黒: primary edge
青: secondary edgebaa a cbbabcc c bbb b a aabbcabccb

CDAWG of ababcbbaba55

suffix link
= hard Weiner link
= primary edge

bbacbaababaababcb

CDAWG of bcbabacbaba56

From Suffix Tree to (S)CDAWG
定理 [Blumer et al. 1987]

Suffix Tree から CDAWG を O(n) 時間で得られる．
定理 [Blumer et al. 1987]

Soft Weiner link 付き Suffix Tree からSymmetric CDAWG を O(n) 時間で得られる．
Soft Weiner link = DAWG の secondary edge なので，結局 DAWG  CDAWG の変換とまったく同じ
n は入力文字列長SCDAWG の出力線形領域構築

57

定理 [Inenaga 2023?]
長さ n の入力文字列 w の SCDAWG をO(n log s) 時間，O(el + er) 領域で構築できる．
er と el はそれぞれ w と wR の CDAWG の辺数．


CDAWG(w$) と CDAWG(wR$) をそれぞれ O(n log s) 時間,O(er) 領域 ・ O(el) 領域で構築 [Inenaga et al. 2005] し，$辺を削除．

CDAWG(w) と CDAWG(wR) の頂点の対応を求めたい．

順向き文字列 w 側の代表元を lex order でソートする．
 （すでにソートされている） primary edge を巡回すればよい．



逆向き文字列 wR 側の代表元を co-lex order でソートする．
 CDAWG(wR) の suffix link を辞書式順序でソートする．
O(min(er , el ) log s) 時間，O(min(er , el )) 領域
 CDAWG(wR) の suffix link = CDAWG(w) の primary edge
なので，ソートされた suffix link を巡回すればよい．

Symmetric CDAWG
CDAWG of ababcb

黒: primary edge
青: secondary edgebba abbc cb b58ababcbcbcbababcb
代表元の lex order のソート順:
ab, ababcb, b

CDAWG of bcbababbbacbababaabaababccbababbcbaba
代表元の co-lex order のソート順ba, bcbaba, bSuffix Trie と SCDAWG の関係

Suffix Trie of ababcb
Suffix Trie of bcbaba
bbcaca aa bbbb baacacbba bbbaaaccc bbb59

CDAWG of ababcb
CDAWG of bcbaba
baa a cbbabcc c bbb b a aabbcabb

Symmetric Suffix Trie の頂点のうち，順向き文字列 w と逆向き文字列 wR の両方で
枝別れ or suffix に対応している頂点だけを残したのが SCDAWGcbcbaba