Pattern Matching on
Compressed Texts II
Shunsuke Inenaga
Kyushu University, Japan

Agenda Fully Compressed Pattern Matching Straight Line Program Compressed String Comparison
 Period of Compressed String
 Pattern Discovery from Compressed

String (Palindrome and Square) FCPM for 2D SLP
 Open Problems

Fully Compressed Pattern Matching [1/3]
compressed pattern:&(aG
Dagstuhl

compressed text:
geoiy083qa0gj(#*gpfomo)#(JGWRE$(U)%ARY)(JPED(A%RJG)ER%U)JGODAAQWT$JGWRE)$R
J)REWJFDOPIJKSeoiy083qa0gj(#*gpfomo)#(JG
WRE$(U)%ARY)(JPED(A%RJG)ER%U)JGODAAQWT$JGWRE)$geoiy083qa0gj(#*gpfomo)#(JG
WRE$(U)%ARY)(JPED(A%RJG)ER%U)JGODAAQWT$JGWRE)$geoiy083qa0gj(#*gpfomo)#(JG
WRE$(U)%ARY)(Fully Compressed Pattern Matching [2/3]classical patternmatching algorithm

uncompressed
text
uncompressed
patterncompressed
text
uncompressed
patterncompressed
textcompressedpatternpcompressed patternmatching algorithm

fully compressed patternmatching algorithmPossible Application of FCPM
compressed text

I’m here.

where.jpg

compressedpatternwally.jpg

Fully Compressed Pattern Matching [3/3]
FCPM Problem
Input : T = compress(T) and P = compress(P).
Output : Set Occ(T, P) of substring occurrencesof pattern P in text T.

 Occ(T , P ) 

| u |  1: T  uPw, u, w   Straight Line Program [1/2]
SLP T : sequence of assignments
X1 = expr1 ; X2 = expr2; … ; Xn = exprn;
Xk : variable,aexprk :Xi Xj( a ( i, j < k ).

SLP T for string T is a CFG in Chomsky
normal form s.t. L(T) = {T}.

Straight Line Program [2/2]
SLP Tn

X1 = aX2 = b
X3 = X1X2
X4 = X3X1
X5 = X3X4
X6 = X5X5
X7 = X4X6
X8 = X7X5T=
N

N = O(2n)Straight Line Program [2/2]
SLP Tn

X1 = aX2 = b
X3 = X1X2
X4 = X3X1
X5 = X3X4
X6 = X5X5
X7 = X4X6
X8 = X7X5X8X7

X5T=N

N = O(2n)From LZ77 to SLP

For any string T given in LZ77-compressed
form of size k, an SLP generating T of sizeO(k2) can be constructed in O(k2) time.
[Rytter ’00, ’03, ’04]

FCPM for SLP
FCPM Problem for SLP
Input : SLP T for text T and SLP P for pattern P.
Output : Compact representation of set Occ(T, P)
of substring occurrences of P in T.
 We want to solve the problem efficiently(i.e., polynomial time & space in n and m).
◦ n = the size of SLP T, m = the size of SLP P

 T (also P) cannot be decompressed |Occ(T,P)| = O(2n)  compact representation
 |T| = O(2n)Key DefinitionOcc (X, Y) = { iOcc(X, Y) | |Xl| - |Y|

i|Xl|}X
XlXr

Y

set of occurrences of Y
that cover or touch theboundary of Xl and Xr.

X: variable of T
Y: variable of P

Key Lemma[Miyazaki et al. ’97]

X
XlXr

Occ (X, Y) forms a single
arithmetic progression.

O(1) spaceY

Key Observation
Occ( X , Y ) Occ( X l , Y )  Occ  ( X , Y )  Occ( X r , Y ) | X l |[Miyazaki et al. ’97]

X
XlXr
Computing Occ(X, Y) is
reduced to computing
Occ (X, Y).

YYYDP for Occ (Xi, Yj)

Occ (T, P)

Xn

Occ (Xn,Yj)

Occ (Xn,Ym)

Occ (Xn,Y1)

O(1) spaceXi

Occ (Xi,Y1)

Occ (Xi,Yj)

Occ (Xi,Ym)

X1

Occ (X1,Y1)

Occ (X1,Yj)

Occ (X1,Ym)

Y1

YjYm

Compact representation of Occ(T, P)
which answers a membership query to
Occ(T, P) in O(n) time.

Known Results
TimeSpaceCompression

Miyazaki et al. ’97

O(m2n2)

O(mn)

SLP

Lifshits ’07

O(mn2)O(mn)

SLP

Hirao et al. ’00

O(mn)

O(mn)

Balanced SLP

Balanced SLP

Fully Compressed Subsequence
Pattern Matching [1/2]
FC Subsequence PM Problem
Input : SLP T for text T and SLP P for pattern P.
Output : Find whether P is a subsequence of T.
 P is said to be a subsequence of T, if P can beobtained by removing zero or more charactersfrom T.

Fully Compressed Subsequence
Pattern Matching [2/2]

The Fully Compressed Subsequence
Pattern Matching Problem on SLP
compressed strings is NP-hard.
[Lifshits & Lohrey ’06]

Compressed String Comparison [1/2]
CSC Problem
Input : SLPs T and S for strings T and S, resp.
Output : Dis(similarity) of T and S.

Compressed String Comparison [2/2]
MeasureEquality
Hamming
Distance

TimeSpaceO(mn2)O(mn)

Reference
Lifshits ’07#P-complete

PSPACE

Lifshits ’07

Longest Common
SubstringO((m+n)4log(m+n))O((m+n)3)

Matsubara etal. ’08

Longest Common
Subsequence

NP-hardPSPACE

Lifshits &Lohrey ’06

Property of common substrings [1/3] For each common substring Z of string S and T,

there always exists a variable Xi = XlXr and Yj = YLYR
such that:◦ Z is a common substring of Xi and Yj◦ Z contains an overlap between Xl and YR

XiXlOverlap

XrZcommonsubstringw
YLZ

Yj

YR

Property of common substrings [2/3]• For each common substring Z of string S and T,
there always exists a string w such that:– w is a substring of Z
– w is an overlap of variables of S and TXi

XlOverlap

Xrw

YL

Yj

YR

Property of common substrings [1/3] For each common substring Z of string S and T,

there always exists a string w such that:◦ Z can be calculated by expanding wXiXlOverlap

XrZ

commonsubstringw
YLZ

Yj

YR

ExpandProcess

Computing Overlaps
Lemma [Karpinski et al. ’97]
For any variables Xi and Xj of SLP T, OL(Xi, Xj) canbe represented by O(n) arithmetic progressions.
Xi

Yj

Theorem [Karpinski et ai. ’97]

For any SLP T, OL(Xi, Xj) can be computed in total ofO(n4logn) time and O(n3) space for each i, j.

Periods of Compressed String [1/2]Compressed Period Problem
Input : SLP T for string T.
Output : Compact representation of set Period(T)of periods of T.

 Period (T )  | T |  | u | : T  uv  wu, v , w  Periods of Compressed String [2/2]

An O(n)-size representation ofPeriod(T) can be computed in O(n4)time with O(n3) space.
[Lifshits ’06, ’07]

Compressed Palindrome Discovery [1/2]Compressed Palindrome Discovery Problem
Input : SLP T for string T.
Output : Compact representation of set Pal(T)of maximal palindromes of T.
 Pal(T) ={(p,q) : T[p:q] is the maximal palindrome
centered at ( p  q ) / 2  .

 ex. T = baabbaa}

Compressed Palindrome Discovery [2/2]

An O(n2)-size representation ofPal(T) can be computed in O(n4)time with O(n2) space.
[Matsubara et al. ’08]

Composition System
CS T : sequence of assignments
X1 = expr1 ; X2 = expr2; … ; Xn = exprn;
Xk : variable,a( a   exprk :( i, j < k ),
Xi Xj
[p]
XiXj[q] ( i, j < k ).
[p]

X = X[1:p][q] X = X[|X|-q+1:|X|]From LZ77 to CS
For any string T given in LZ77-compressed
form of size k, a CS generating T of sizeO(klogk) can be constructed in polynomialtime.
[Gasieniec et al. ’96]

Compressed Square Discovery [1/2]Compressed Square Problem
Input : CS T for string T.
Output : Check the square freeness of T
(whether T contains a square or not).
 A square is any non-empty string of theform xx.

Compressed Square Discovery [2/2]

We can test square freeness of T inpolynomial time in the size of given
composition system T.
[Gasieniec et al. ’96, Rytter’00]

2D SLP
2D SLP T : sequence of assignments
X1 = expr1 ; X2 = expr2; … ; Xn = exprn;
Xk : variable,aexprk :Xi  Xj
Xi Xj

Xk( a   ( i, j < k, height(Xi) = height(Xj) ),( i, j < k, width(Xi) = width(Xj) ),= Xi Xjhorizontal concatenation 

Xk =XiXj

vertical concatenation

FCPM for 2D SLP

The Fully Compressed Pattern
Matching Problem for 2D SLP isP 2 -complete.
[Berman et al. ’97, Rytter’00]

Open Problems [1/2] Edit distance of two SLP-compressedstrings.

 Compact representation of all maximal

runs of an SLP-compressed string.

◦ A run is any string x whose minimal period psatisfies p  |x|/2.
83◦ ex. (aab )  aabaabaa

c

5N

Max Number of Runs
in a StringcN[Kolpakov & Kucherov ’99]

c
5N
[Rytter ’06]
1.05N

4N

3N

2N

N

0

3.48N
[Puglisi et al. ’08]
3.44N
[Rytter ’07]

1.6N
[Crochemore & Ilie ’08]

1.048N[Crochemore et al. ’08]

1.00N
0.95N

0.944565N[Kusano et al. ’08]

0.90N

0.927N[Franek et al. ’03]

N: (uncompressed) text length

Open Problems [2/2] Fully Compressed Tree Pattern Matching forgrammar based XML compression.
◦ TGCA (Tree Grammar Compression Algorithm)[Onuma et al. ’06]

References [1/5][Matsubara et al. ’08] W. Matsubara, S. Inenaga, A. Ishino, A. Shinohara, T.
Nakamura, and K. Hashimoto, Computing longest common
substring and all palindromes from compressed strings, Proc.
SOFSEM'08, LNCS4910, pp. 364-375, 2008

[Lifshits ’07] Y. Lifshits, Processing compressed texts: A tractability
border , Proc. CPM'07, LNCS 4580, pp 228-240, 2007

[Lifshits ’06] Y. Lifshits, Solving Classical String Problems an
Compressed Texts, Dagstuhl Seminar Proceedings 06201, Schloss
Dagstuhl, 2006

[Hirao et ail. ’00] M. Hirao, A. Shinohara, M. Takeda, and S. Arikawa, Faster
fully compressed pattern matching algorithm for balanced
straight-line programs, Proc. of SPIRE2000, pp. 132-138, IEEE Computer
Society, 2000

References [2/5][Miyazaki et al. ’97] M. Miyazaki, A. Shinohara, and M. Takeda, An
improved pattern matching algorithm for strings in terms ofstraight-line programs, Proc. CPM'97, LNCS1264, pp.1-11, 1997

[Gasieniec ’96] L. Gasieniec, M. Karpinski, W. Plandowski, W. Rytter,Efficient Algorithms for Lempel-Zip Encoding (ExtendedAbstract), Proc. SWAT’96, LNCS1097, pp. 392-403, 1996

[Lifsthis & Lohrey ’06] Y. Lifshits and M. Lohrey, Querying andEmbedding Compressed Texts, Proc. MFCS’06, LNCS4162, pp. 681-692,
2006



[Rytter ’04] W. Rytter, Grammar Compression, LZ-Encodings, andString Algorithms with Implicit Input, Proc. ICALP 2004, LNCS 3142,
pp. 15-27, 2004

References [3/5][Rytter ’03] W. Rytter, Application of Lempel-Ziv factorization tothe approximation of grammar-based compression, TCS, Volume302, Number 1-3, pp. 211-222, 2003



[Rytter ’00] W. Rytter, Compressed and fully compressed patternmatching in One and Two Dimensions, Proceedings of IEEE, Volume
88, Number 11, pp. 1769-1778, 2000

[Berman et al. ’97] P. Berman, M. Karpinski, L. L. Larmore, W. Plandowski, W.
Rytter, On the Complexity of Pattern Matching for Highly
Compressed Two-Dimensional Texts, Proc. CPM’97, LNCS1264, pp.
40-51 1997[Onuma et al. ’06] J. Onuma, K. Doi, and A. Yamamoto, Data compression
and anti-unification for semi-structured documents with treegrammars (in Japanese), IEICE Technical Report AI2006-9, pages 45–50,2006.

References [4/5][Kusano et al. ’08] K. Kusano, W. Matsubara, A. Ishino, H. Bannai, A.
Shinohara, New Lower Bounds for the Maximum Number of Runs
in a String, http://arxiv.org/abs/0804.1214

[Franek et al. ’03] F. Franek, R. Simpson, W. Smyth, The maximum
number of runs in a string, Proc. AWOCA’03, pp. 26–35, 2003.

[Kolpakov & Kucherov ’99] R. Kolpakov and G. Kucherov, Finding
maximal repetitions in a word in linear time, Proc. FOCS’99, pp.
596–604, 1999.

[Rytter ’06] W. Rytter, The number of runs in a string: Improved
analysis of the linear upper bound, Proc. STACS’06, LNCS3884, pp.
184–195, 2006.

References [5/5][Rytter ’07] W. Rytter, The number of runs in a string, Inf. Comput.,
Volume 205, Number 9, pp. 1459–1469, 2007.



[Crochemore & Ilie ’08] M. Crochemore and L. Ilie, Maximal repetitions
in strings, J. Comput. Syst. Sci., Volume 74, Number 5, pp. 796-807, 2008.



[Crochremore et al. ’08] M. Crochemore, L. Ilie, and L. Tinta, Towards a
Solution to the "Runs" Conjecture, Proc. CPM’08, LNCS5029, pp. 290302, 2008.



[Puglisi et al. ’08] S. Puglisi, J. Simpson, W. F. Smyth, How many runs can astring contain?, TCS, Volume 401, Issues 1-3, pp.165-171, 2008.

[Kaprinski et al. ’97] M. Karpinski, W. Rytter, A. Shinohara, An efficientpattern-matching algorithm for strings with short descriptions,
Nordic Journal of Computing, Number 4, pp.172–186, 1997.