Dagstuhl Seminar 13232

Algorithms on
grammar compressed strings
Shunsuke Inenaga
Kyushu University, Japan

What we did after Dagstuhl Seminar08261
 In Dagstuhl Seminar 08261 (in 2008),
I gave a survey talk about algorithmic results on
grammar-based compressed strings, which wereachieved before 2008.
 Today, I will talk about our new(er) results
we achieved after 2008.

Collaborations
 Japanese:
Hideo Bannai, Tomohiro I, Masayuki Takeda,Keisuke Goto, Yuto Nakashima, Kouji Shimohira,Takanori Yamamoto (Kyushu U.),
Ayumi Shinohara, Kazuyuki Narisawa,Wataru Matsubara (Tohoku U.)
 International:
Paweł Gawrychowski (Max Planck),
Travis Gagie (U. Helsinki), Gad M. Landau (U. Haifa),
Moshe Lewenstein (Bar Ilan U.)

Compressed String Processing (CSP)
non-CSP
decompress
compresseddata........
...........
...........
...........
...........
...........
...........
...........
...........
...........

uncompressed
data

CSP

outputIn CSP we do notdecompress
the whole dataprocess
compresseddata

process

outputCompressed String Processing [Cont.]
 Suppose that huge string data is stored in acompressed form.
 Given a compressed string, our goal is to perform
various kinds of processing on the compressedstring, without decompressing the whole string.
 Our input is a straight-line program (SLP).

Straight Line Program (SLP)An SLP is a sequence of productions
X1 = expr1, X2 = expr2 , ···, Xn = exprn• expri = a(a)• expri = Xl Xr ( l, r < i ) The size of the SLP is the number n of productions.
 An SLP is essentially a CFG deriving a single string.
 SLPs model outputs of grammar-based compression
algorithms (e.g., Re-pair, Sequitur, LZ78, etc).

Example of SLPSLP S
X1 = aX2 = bX3 = X1 X1X4 = X1 X2X5 = X3 X4X6 = X5 X4X7 = X5 X6Derivation tree T of SLP S
765

5

3443

4

1

1

12

1

1

12

12aaabaaabab

string represented by SLP SDAG view of SLPDAG for SLP S

Derivation tree T of SLP S
77665553

4

121

112

1

1

12

12abaaabaaabab34434

 DAG is compressed representation of derivation tree.
 SLP is compressed representation of string.

Important Remark
X66X55443111212aaababX4

 Derivation trees are used only for explanations,and are never constructed in our algorithms.
 CSP on SLPs can be seen as algorithmic techniqueto perform various kinds of operations
on the DAG for SLP, not on the derivation tree.

Notations
n : the size of a given SLP S
h : the height of the derivation tree T of S
N : the length of the decompressed string w
that is represented by SLP S
 log2 N

hn always holds.

 In theory, N = O(2n).
 Solutions polynomial in n are beneficial.

Pattern Mining
problemtimespace (words)

q-gramfrequencies

O(qn)

O(qn)

q-gramfrequenciesO(N-)

O(N-)

q-gramnon-overlapping
frequencies

O(q2n)

O(qn)longest repeating
substringO(n4 log n)

O(n3)

N-

min(qn, N) always holds

SLP Text v.s Uncompressed Patternproblemtimespace (words)(window)
subsequence
matching

O(nM)

O(nM)

(window)
VLDC patternmatching

O(nM)

O(nM)

convolution

O((N-) log M)

O((N-) log M)

 M is the length of uncompressed pattern N- min(nM, N) always holds

String Regularities
problemtime
O(n3h log N)

space (words)
O(n2)repetitions(runs & squares)

O(n3h)O(n2)palindromesO(nh (n + h log N))O(n2)gappedpalindromesO(nh (n2+ g log N))

O(n (n + g))

O(n2h)
O(nh (n  log2 N))

O(n2)
O(n2)

square freenessperiods
coversg is the fixed gap length

Factorization
problemtimespace (words)

LZ78 factorization

O(n+ s log N)
O(n + s log s)O(zn2h log N)

O(n+ s)O(n + s log s)O(n2 + z)

LyndonfactorizationO(n4 + mn3h)O(n2)LyndonfactorizationO(nh (n + log2 N))O(n2)LZ78 factorization
LZ77 factorization

 s is the number of LZ78 factors
 z is the number of LZ77 factors
 m is the number of Lyndon factors

And Some Others
problemtimespace (words)

longest common
substringO(n4 log n)O(n2 log N)

longest common
extensionO(n3h) preprocessO(h log N) queryO(n2)Aho-CorasickautomatonO(n4 log n)O(n2 log N)

Our SLP-based Aho-Corasick automaton runsin O(|u| (k + h + log||)) time on uncompressed text u,
where k is the number of patterns.

q-gram Frequency on SLP
Problem 1 (q-gram frequencies on SLP)

Given an SLP S representing string w
and a positive integer q, compute Occ(w, p)
for all substrings p of w of length q.

Occ(w, p) : the number of occurrences of p in w

Solution for Uncompressed String
 Given the uncompressed string w, we can solve

the q-gram frequencies problem in O(N) time,using the suffix array and LCP array of w.
SA LCP

q=3875
3
16420
1
350
24$
a$
aba$
ababa$
abababa$ba$baba$
bababa$Solution for Uncompressed String
 Given the uncompressed string w, we can solve

the q-gram frequencies problem in O(N) time,using the suffix array and LCP array of w.
SA LCP

q=3875316420
135024$a$aba$
ababa$
abababa$ba$baba$
bababa$Solution for Uncompressed String
 Given the uncompressed string w, we can solve

the q-gram frequencies problem in O(N) time,using the suffix array and LCP array of w.
SA LCP

q=387531642$
0a$
1 <3 aba$
3
3 ababa$5abababa$
0ba$
2baba$
4bababa$Solution for Uncompressed String
 Given the uncompressed string w, we can solve

the q-gram frequencies problem in O(N) time,using the suffix array and LCP array of w.
SA LCP

q=387531642$0a$
1 <3 aba$
33 ababa$
3 abababa$
50ba$
2baba$
4bababa$Solution for Uncompressed String
 Given the uncompressed string w, we can solve

the q-gram frequencies problem in O(N) time,using the suffix array and LCP array of w.
SA LCP

q=3

8
7
5
3
1
6
4
2$
0a$
1 <3 aba$
3
3 ababa$
3 abababa$
50 <3 ba$2baba$
4bababa$

Output (pos, q, #occ)(5, 3, 3)

Solution for Uncompressed String
 Given the uncompressed string w, we can solve

the q-gram frequencies problem in O(N) time,using the suffix array and LCP array of w.
SA LCP

q=387531642$
0a$
1aba$
3ababa$5abababa$0ba$
2 <3 baba$
4
3 bababa$

Output (pos, q, #occ)(5, 3, 3)(4, 3, 2)

Solution for Uncompressed String
In the sequel, I will show how to simulate
this O(N)-time algorithm in O(qn) time.
SA LCP

q=387
5
3
1
642$
0a$
1aba$
3ababa$5abababa$0ba$
2 <3 baba$
4
3 bababa$

Output (pos, q, #occ)(5, 3, 3)(4, 3, 2)

StabAn integer interval [b, e] (1 b e N) is said to bestabbed by a variable Xi, if the LCA of the bth andeth leaves of the derivation tree T is labeled by Xi.
7
65

5

3

4

4

4

3

1

1

1

2

1

1

1

2

1

2

aaabaaabab

1

2

3

4

5

6

7

8

910

Observation
 Assume that the occurrence of a q-gram p

starting at position j is stabbed by variable Xi.
 Then, in any other occurrence of Xi in T,

there is another stabbed occurrence of p.
TXipp

w
j

Xi

j+q -1Xip

Sub-problems
 Hence, the q-gram frequencies problem on

SLP reduces to the following sub-problems:Problem 2

For each variable Xi, count the number ofoccurrences of Xi in the derivation tree T.
Problem 3

For each variable Xi, count the number ofoccurrences of each q-gram stabbed by Xi.

Solving Problem 2
Lemma 1

Problem 2 can be solved in O(n) time.

7653412ab

Solving Problem 2Lemma 1

Problem 2 can be solved in O(n) time.
1

 The root occurs exactly once.

7653412ab

Solving Problem 2
Lemma 1

Problem 2 can be solved in O(n) time.
17615341

2ab1

 For each node in a topologicalorder, propagate its number ofoccurrences to its children.

Solving Problem 2
Lemma 1

Problem 2 can be solved in O(n) time.
1
762 534 1

12ab1

 For each node in a topologicalorder, propagate its number ofoccurrences to its children.

Solving Problem 2
Lemma 1

Problem 2 can be solved in O(n) time.
1762 52 34 312ab1

 For each node in a topologicalorder, propagate its number ofoccurrences to its children.

Solving Problem 2
Lemma 1

Problem 2 can be solved in O(n) time.
1
762 52 34 34 1

2ab1

 For each node in a topologicalorder, propagate its number ofoccurrences to its children.

Solving Problem 2
Lemma 1

Problem 2 can be solved in O(n) time.
1762 52 34 37 12 3ab1

 For each node in a topologicalorder, propagate its number ofoccurrences to its children.

Solving Problem 2Lemma 1

Problem 2 can be solved in O(n) time.
1767162 5552 34 3

7 12 3

11121

1121

2baaabaaababa

3

4434

Solving Problem 3
 Each variable Xi can stab at most q-1 occurrencesof q-grams.

Xi
Xl

Xr

q-1

Solving Problem 3
 We decompress substringti = Xl[|Xl|-q+2..|Xl|] Xr[1..q-1] of length 2q-2.
Xi
Xl

Xr
tiq-1

q-1

Solving Problem 3 Clearly, all q-grams stabbed by Xi occur inside ti.

XiXlXrti

q-1

q-1

Solving Problem 3Lemma 2Problem 3 can be solved in O(qn) time.
 For all variables Xi, substring ti can becomputed in a total of O(qn) time, by asimple DP.

 We construct the suffix array and LCP arrayfor string z = t1t2 … tn, in O(|z|) = O(qn) time.

q-gram Frequency on SLP
Theorem 1 [JDA 2013]

Problem 1 (q-gram frequencies on SLP) canbe solved in O(qn) time.

 Easily follows from Lemma 1 and Lemma 2.

Experimental Result
English text (200MB) from Pizza & Chili corpus
120SLPTime (sec)

100
8060

uncompressed string40
20023456q

78910

Improved Algorithm for Larger q
 For smaller values of q,our O(qn) solution overcomes the O(N) solution
both in theory and in practice.
 Is it possible to improve our solution so that

it works efficiently for larger values of q?
 At least in theory, the answer is yes!

Improved Algorithm for Larger qLemma 3

We can construct, in linear time, an edgelabeled tree of size O(N-) representing all
q-grams which occur in w.

min(qn, N) denotes the total lengthof the edge labels of the tree.

 N-

Example of Edge-Labeled Tree
derivation tree T
76554434333

3

1

12

12

1

12

12

1

12aabab aabab aabedge-labeled tree (q = 3)

aabaaba654ab 7

Example of Edge-Labeled Tree
derivation tree T
765544343

333

1

1212

112

12112aabab aabab aabedge-labeled tree (q = 3)

aabaaba654

ab 7

Example of Edge-Labeled Tree
derivation tree T
7655443433311212112aabab aab

This tree contains all the1information
2 1 needed
1 2 tocompute q-grams stabbed
aby eachb variable.
a a bedge-labeled tree (q = 3)

aabaaba654

ab 73

Improved Algorithm for larger qTheorem 1 [CPM 2012]

Problem 1 (q-gram frequencies on SLP) canbe solved in O(N-) = O(min(qn, N)) time.
 We use a linear-time algorithm to construct

the suffix tree of a tree (cf. Shibuya 2003).
 Our improved solution is at least as

efficient as the O(N)-time solution, and canbe much faster when q and n are small.

Finding Repetitions on SLP
Problem 4 (finding repetitions on SLP)

Given an SLP S representing string w,
compute squares and runs that occur in w.

squares(of form xx)

abbabbabbbabbbabbbaruns(maximal repetition xk x’)Stabbed Runs
 For each run in the string w, there is a uniquevariable Xi that stabs the run.
TXiw

Stabbed Runs [Cont.] In other occurrences of Xi in the derivation

tree, the same run is stabbed by Xi.
TXi

w

Xi

Stabbed Runs [Cont.]
 Computing runs in string w reduces tocomputing stabbed runs for each variable Xi.
TXiw

Xi

Stabbed Runs [Cont.]
 For each variable Xi, firstly we compute(the beginning and ending positions of)stabbed squares.
XiStabbed Runs [Cont.]
 We then determine how long the periodicity

continues to the right and to the left.
 We can efficiently do this without decompressing Xi.

Xi

Stabbed Runs [Cont.]
 We then determine how long the periodicity

continues to the right and to the left.
 We can efficiently do this without decompressing Xi.

Xi

Finding Repetitions on SLP
Theorem 2 [MFCS 2013]

O(n log N)-size representation of all runs
and squares can be computed in O(n3h)time using O(n2) space.
 There are  (N) runs in a string of length N.
 Naïve representation of runs requires

O(2n) space in the worst case.
 Hence we need a compact representation of output.

Compact Representation of Runs
Lemma 4

Our O(n log N)-size representation of runs
supports the following query in O(h log N) time:
Given an interval [b, e] with 1,
count the number of runs and squares that
occur in the substring w[b..e].

Finding Palindromes on SLP
Problem 5 (finding palindromes on SLP)

Given an SLP S representing string w,
compute maximal palindromes of w.

maximalpalindromes

abbbaabbbbabbbaab

Finding Palindromes on SLP
Problem 5 (finding palindromes on SLP)

Given an SLP S representing string w,
compute maximal palindromes of w.

maximalpalindromes

abbbaabbbbabbbaab

Finding Palindromes on SLP
Problem 5 (finding palindromes on SLP)

Given an SLP S representing string w,
compute maximal palindromes of w.

maximalpalindromes

abbbaabbbbabbbaab

Stabbed Palindromes
 For each variable Xi, there can be 3 different

types of stabbed maximal palindromes.

Xi

Xi

Xi

Type 1

Type 2Type 3

Computing Type 1 Palindromes
 Type 1 maximal palindromes of Xi can becomputed by extending the arms of thesuffix palindromes of Xl.
XiXrXlabSuffix Palindromes
Lemma 5 [Apostolico et al., 1995]

For any string of length N, the lengths of its
suffix palindromes can be represented byO(log N) arithmetic progressions.

 We can extend the suffix palindromesbelonging to the same arithmetic progression
in a batch, efficiently, using the periodicity.

Finding Palindromes on SLP
Theorem 3 [TCS 2009]

O(n log N)-size representation of all maximal
palindromes can be computedin O(nh (n + h log N)) time using O(n2) space.

 The above time complexity is improved toO(nh (n + log2 N)) by using our recent LCE
algorithm on SLP.

Finding Gapped Palindromes on SLP
Problem 6 (finding gapped palindromes on SLP)

Given an SLP S representing string w andGia positive integer g, computeg-gappedpalindromes that occur in w.

3-gappedpalindromes

abababcbabaabbabca

Stabbed g-gapped Palindromes There are 3 types of g-gapped palindromes

stabbed by variable Xi.

XiXi

Xi

Type 1

Type 2Type 3

Finding Gapped Palindromes on SLP
Theorem 4 [MFCS 2013]O(n (log N + g))-size representation of all
g-gapped palindromes can be computedin O(nh (n2 + g log N)) time using O(n2) space.

 Because of the gap between arms, we cannot

use Lemma 5 (ar. pr. suffix palindromes).
 Instead, we used a similar technique to oursolution for computing stabbed squares.

Concluding Remarks
 A number of string problems can be efficientlysolved on SLP-compressed strings.
 The common key concept is stabbing, which wecall “串 (kushi)”, a Japanese meaning a skewer.

Oden(traditional
Japanese food)