IWOCA 2024

Computing Minimal Absent Words
and Extended Bispecial Factors
with CDAWG Space
Shunsuke Inenaga1, Takuya Mieno2, Hiroki Arimura3,Mitsuru Funakoshi1, Yuta Fujishige4
1 Kyushu University

2 University of Electro-Communications
3 Hokkaido University
4 Fujitsu

Minimal Absent Words (MAWs) [1/2]A string w over an alphabet S is calleda Minimal Absent Word (MAW) for a string S, if:
1. w is a character from S not occurring in S, or
2. w = aub (a, b S, u S*) does not occur in S,
but both au and ub occur in S.

Examplew= b a b
S= a b a a b

Minimal Absent Words (MAWs) [1/2]A string w over an alphabet S is calleda Minimal Absent Word (MAW) for a string S, if:
1. w is a character from S not occurring in S, or
2. w = aub (a, b S, u S*) does not occur in S,but both au and ub occur in S.

Examplew= b a b
S= a b a a bbab is a MAW for abaab

Minimal Absent Words (MAWs) [2/2]MAW(S) denotes the set of MAWs for a string S.

ExampleS = abaabS = {a, b, c}

MAW(S) = {aaa, a a b a , bab, bb, c}

The number |MAW(S)| of MAWs for a string S of lengthn over an alphabet of size s is O(sn), and there is amatching lower bound [Crochemore et al. 1998].

Motivations for Computing MAWs


Computing (minimal) absent words for a given stringhas various applications including:Data compression (anti-dictionary)[Crochemore et al. 2000] [Crochemore & Navarro 2002][Ayad et al. 2021]

Sequence comparison[Chairungsee & Crochemore 2012][Charalampopoulos et al. 2018]

Bioinformatics[Almirantis et al. 2017] [Koulouras & Frith 2019][Pratas & Silva 2020]

Computing MAWs with DAWG [1/3]Previous algorithms [Crochemore et al. 1998, Fujishige etal. 2023] for computing MAWs for a string S of length nuse DAWG (Directed Acyclic Word Graph) for S, which isan O(n)-size automaton representing all substrings of S.
[Blumer et al. 1985]

E.g. S = a b a b c bcabcbaacbcb

Substrings of S are representedby the same node of DAWG(S)iff they have the same ending
position(s) in S.

suffix link

Computing MAWs with DAWG [1/3]Previous algorithms [Crochemore et al. 1998, Fujishige etal. 2023] for computing MAWs for a string S of length nuse DAWG (Directed Acyclic Word Graph) for S, which isan O(n)-size automaton representing all substrings of S.
[Blumer et al. 1985]

E.g. S = a b a b c be cabb

abab
bababcbaacbcb

Substrings of S are representedby the same node of DAWG(S)iff they have the same ending
position(s) in S.

suffix link

Computing MAWs with DAWG [2/3]If the edges of DAWG are sorted, then one can compute
MAW(S) in O(n + |MAW(S)|) time [Fujishige et al. 2023].

DAWG for string S

aucub cConsider each pair of nodes au and u which
are connected by a suffix link, where a is acharacter and u is a string.

Compare the labels of the out-edges ofnodes au and u in sorted order.
 For b: au has no out-edge with b,
but u has an out-edge with b.
 aub is a MAW for the input string S.
 For c: both au and u have out-edges with c auc is not a MAW for the input string S,
but this cost of character comparisons canbe charged to this out-edge of au labeled c.

Computing MAWs with DAWG [3/3]
E.g. S = a b a b c b

DAWG for string Saucb aub c

 aub is a MAW

suffix linkaccbabcb

Longest string inthis node is abc
Shortest string inthis node is bab

 baba is a MAW

Redundancy in MAW computation with DAWG
E.g. S = a b a b c bDAWG for string S

aucb aub c

 aub is a MAW

suffix linkaccbabc

Both these nodes
have only one childcb

 No MAWs to output

Redundancy in MAW computation with DAWG
E.g. S = a b a b c b

DAWG for string S

aucb aub c

 aub is a MAW

suffix linkaccbabc

Both these nodes
have only one childcb

 No MAWs to output

From DAWG to CDAWG (Compact DAWG)
E.g. S = a b a b c b
DAWG [Blumer et al. 1985]

b aac

CDAWG [Blumer et al. 1987]

cb abbabcbc(1) Keep only
branching nodes +source & sink
(2) Path contraction

acbb ccbacbbcbb

Encoding CDAWG in O(e) space [1/2]123456

CDAWG for S = a b a b c bb abacbb cc(2,2)(1,2) (5,6)

b(5,6)

acbbcbb(3,6)

(3,6)

(5,6)

Each string edge label
xcan beencoded by a pair(i, j) of positions suchthat x = S[i..j].
 CDAWG withe edges can be
stored in O(e) space,plus the input stringof length n.

Encoding CDAWG in O(e) space [2/2]S = ababcbb abacbb cbacbbcbbTheorem 1c[Belazzougui & Cunial 2015, Inenaga 2024]

It is possible to store the edge labels ofthe CDAWG in O(e) total space, so thateach edge string label x can be retrieved inO(|x|) time, where e is the number of edges
in the CDAWG.
Note: e can be as small as O(log n) forsome highly repetitive strings.

Computing MAWs with CDAWG [1/3]
E.g. S = a b a b c b
DAWG

CDAWGb aacc

Longest string inthis node is abb abbabcbcc
Shortest string inthis node is babb baba is a MAW
Node for bab
is missing in the CDAWG

abcbcbacbbcb

Computing MAWs with CDAWG [2/3]
Theorem 2 [Belazzougui & Cunial 2015]

The number of “missing” nodes in the CDAWG of string S
for computing MAW(S) is at most the number of edgesof the CDAWG for the reversed string .
Theorem 3 [Belazzougui & Cunial 2015]

There exists a data structure of O() spacethat can output a representation of MAW(S) for
the input string S in O(|MAW(S)|) time.

How much is the gap between and?

Computing MAWs with CDAWG [3/3]
How much is the gap between and?

Theorem 4 [Karkkainen 2017, Inenaga 2024]

There exists a family of strings of length n such that=W.
Theorem 5 [Inenaga, Kosolobov, Zuba 2024 (unpublished)]

For any string of length n,=O.

Our Contribution
Theorem 6

There exists a data structure of O( min) space thatcan output a representation of MAW(S) for string S
in O(|MAW(S)|) time, where min.
algorithmtimespace

Crochemore et al. 1998

O(sn)

O(n)

Fujishige et al. 2023

O(n + |MAW(S)|)O(n)

Belazzougui & Cunial 2015
Ours

O(|MAW(S)|)
O(|MAW(S)|)O()

O( min)Note: and are at most 2n-1, and can be as small as O(log n)
for some highly repetitive strings (e.g. Fibonacci strings).

Computing MAWs in O( min) space [1/4]Case 1aOur CDAWG-based algorithm is edge-based,
while the previous DAWG-based algorithm is node-based.

u0

au0
u1cu2

au3dfeu3b dfsuffix links

Computing MAWs in O( min) space [1/4]Case 1a

Our CDAWG-based algorithm is edge-based,
while the previous DAWG-based algorithm is node-based.

u0

au0
au1
au2
au3df

u1

For a given edge of CDAWG,
we compute MAWs
au1c, au2e, au3b in a batch.

cu2eu3b df

suffix links
missing nodesComputing MAWs in O( min) space [2/4]Case 2

Our CDAWG-based algorithm is edge-based,
while the previous DAWG-based algorithm is node-based.

au0

au0
u1

au1cu2

au2

For a given edge of CDAWG,
we compute MAWs
au1c and au2e in a batch.

esuffix links

au3u3

missing nodesComputing MAWs in O( min) space [3/4]
The primary edges are those that are in thelongest paths from the source to the nodes.

S = ababcbb abacbb ccbb abacabbcbbcbb
CDAWG

LPT(longest path tree)

Computing MAWs in O( min) space [3/4]
The primary edges are those that are in thelongest paths from the source to the nodes.

S = ababcbb abacbb ccbequivalentabbccbcbabcbb abcacbcbb
CDAWG

LPT+(longest path tree plus)bbComputing MAWs in O( min) space [4/4]S = ababcb
LPT+cbabcb

primary edgesb abcacbcb

suffix linksbb

missing nodes

 baba is a MAW

Computing MAWs in O( min) space [4/4]S = ababcb
LPT+cbb

primary edges

Sacbbabacbbcb

suffix links
missing nodescb

 aa and ac are MAWs

LPT+LPT+

Suffix Treebb cab ccbbababcbc$abcc$

Suffix Tree$a

S = ababcbababcbc$

bcbb$abcbc$

LPT+ is of size Q(e) while
Suffix Tree is of size Q(n).

cbbbacb$aabccb$ca $c aabcbcbba$ac$abbbba c caccbbb$$bacccbb$$ccb$c$b$ca $babcbc$

ConclusionsWe have shown a CDAWG-based data structureof O(e) space that can report all MAWs in optimal time.

Our data structure can be extended to reportminimal rare words (MRW) in optimal time:
A string aub is a k-MRW of a string S if aub occurs ktimes in S, while au and ub occur more than k times in S.

 0-MRWs are MAWs.
 1-MRWs are MUSs (minimal unique substrings)[Ilie & Smyth 2011]

Future Work

Is there a data structure of O(r) space that reports
all MAWs/MRWs in optimal time, where r is the numberof equal-letter runs in the BWT (Burrows-Wheelertransform)?
It is know that r e [Belazzougui & Cunial 2017].

There is a data structure of O(r polylog(n)) spacethat can do this in O(()polylog(n) + output) timewith O(s log n) working space (under review).

We want to do this in optimal O(output) time withO() space.