Finding Characteristic Substrings
from Compressed Texts
Shunsuke Inenaga
Kyushu University, Japan
Hideo Bannai
Kyushu University, JapanText Mining and Text Compression
Text mining is a task of finding some rule and/or
knowledge from given textual data.
Text compression is to reduce a space to store
given textual data by removing redundancy.
compressdecompressOur Contribution
We present efficient algorithms to findcharacteristic substrings (patterns) from given
compressed strings directly (i.e., without
decompression).
Longest repeating substring (LRS)Longest non‐overlapping repeating substring (LNRS)
Most frequent substring (MFS)
Most frequent non‐overlapping substring (MFNS)
Left and right contexts of given pattern

Text Compression by Straight Line Program
SLP T
X1 = aX2 = b
X3 = X1X2
X4 = X3X1
X5 = X3X4
X6 = X5X5
X7 = X4X6
X8 = X7X5T=

SLP T is a CFG in the Chomsky normal form
which generates language {T}.

Text Compression by Straight Line Program
SLP T
X1 = aX2 = b
X3 = X1X2
X4 = X3X1
X5 = X3X4
X6 = X5X5
X7 = X4X6
X8 = X7X5T=Encodings of the LZ‐family, run‐length,Sequitur, etc. can quickly be transformed into SLP.

Exponential Compression by SLP
Highly repetitive texts can be exponentially large
w.r.t. the corresponding SLP‐compressed texts.
Text T = ababab…ab(T is an N repetition of ab)

SLP T : X1 = a, X2 = b, X3 = X1X2, X4 = X3X3,X5 = X4X4, ... , Xn = Xn-1Xn-1
N = O(2n)Any algorithms that decompress given SLP‐compressed texts can take exponential time!
We present efficient (i.e., polynomial‐time)algorithms without decompression.

Finding Longest Repeating Substring
Input: SLP T which generates text T
Output: A longest repeating substring (LRS) of T≠
T≠
ExampleT = aabaabcabaabb

Key Observation – 6 Cases of Occurrences of LRS
Xi
Xl

Xi
Xr

Case 1

Xl

Case 4

Xr

Case 2

Xi
Xl

Xi
Xl

Case 3Xi
Xr

Xl

Case 5

Xr

Xi
Xr

Xl

Case 6Xr

Algorithm to Compute LRSInput: SLP T
Output: LRS of text T
foreach variable Xi of SLP T do
compute LRS of Case 1;
compute LRS of Case 2;
compute LRS of Case 3;
compute LRS of Case 4;
compute LRS of Case 5;
compute LRS of Case 6;
return two positions and the length of
the “longest” LRS above;

Algorithm to Compute LRSInput: SLP T
Output: LRS of text T
foreach variable Xi of SLP T do
Xlcompute LRS of Case 1;
compute LRS of Case 2;
compute LRS of Case 3;
compute LRS of Case 4;
Case 1compute LRS of Case 5;
compute LRS of Case 6;
return two positions and the length of
the “longest” LRS above;

XiXr

Algorithm to Compute LRSInput: SLP T
Output: LRS of text T
foreach variable Xi of SLP T doXlcompute LRS of Case 1;
compute LRS of Case 2;
compute LRS of Case 3;
compute LRS of Case 4;
Case 1compute LRS of Case 5;
compute LRS of Case 6;
return two positions and the length of
the “longest” LRS above;

XiXr

Algorithm to Compute LRSInput: SLP T
Output: LRS of text T
foreach variable Xi of SLP T do
compute LRS of Case 1;
compute LRS of Case 2;
compute LRS of Case 3;
compute LRS of Case 4;
compute LRS of Case 5;
compute LRS of Case 6;
return two positions and the length of
the “longest” LRS above;

Algorithm to Compute LRSInput: SLP T
Output: LRS of text T
foreach variable Xi of SLP T do
Xlcompute LRS of Case 1;
compute LRS of Case 2;
compute LRS of Case 3;
compute LRS of Case 4;
Case 2compute LRS of Case 5;
compute LRS of Case 6;
return two positions and the length of
the “longest” LRS above;

XiXr

Algorithm to Compute LRSInput: SLP T
Output: LRS of text T
foreach variable Xi of SLP T do
Xlcompute LRS of Case 1;
compute LRS of Case 2;
compute LRS of Case 3;
compute LRS of Case 4;
Case 2compute LRS of Case 5;
compute LRS of Case 6;
return two positions and the length of
the “longest” LRS above;

Xi
Xr

Algorithm to Compute LRSInput: SLP T
Output: LRS of text T
foreach variable Xi of SLP T do
compute LRS of Case 1;
compute LRS of Case 2;
compute LRS of Case 3;
compute LRS of Case 4;
compute LRS of Case 5;
compute LRS of Case 6;
return two positions and the length of
the “longest” LRS above;

Algorithm to Compute LRSInput: SLP T
Output: LRS of text TXiXlXr

foreach variable Xi of SLP T do
compute LRS of Case 1;
compute LRS of Case 2;
Case 3compute LRS of Case 3;
compute LRS of Case 4;
compute LRS of Case 5;
compute LRS of Case 6;
return two positions and the length ofLRS of Xi of Case 3 isthe longest common
the “longest” LRS above;

substring of Xl and Xr.

Longest Common Substring of Two SLPs

Theorem 1 [Matsubara et al. 2009]

For every pair of variables Xl and Xr, we cancompute a longest common substring of Xland Xr in total of O(n4logn) time.
n is num. of variables in SLP TAlgorithm to Compute LRSInput: SLP T
Output: LRS of text TXi
Xlforeach variable Xi of SLP T do
compute LRS of Case 1;
compute LRS of Case 2;
Case 4compute LRS of Case 3;
compute LRS of Case 4;
compute LRS of Case 5;
compute LRS of Case 6;
return two positions and the length ofthe “longest” LRS above;Xr

Case 4
Xi
Xl
Xj

Xr

Case 4‐1
Xi
Xl
Xj

Xr

Xs

Xt
Xj

Case 4‐1

Xl

Xt

Overlap ofXl and Xt

Case 4‐1
Xi
Xl
Xj

Expandoverlap

Xr

Xs

Xt
XjOverlap ofXl and Xt

Case 4‐2XiXlXrXj

ExpandoverlapXsXjXt

Overlap ofXr and Xs

Set of Overlaps

X

Set of length of overlapsof X and YY

Set of Overlaps
OL(aabaaba, abaababb) = {1, 3, 6}
X

aabaabaabaababb
Yabaababb
Yabaababb
YSet of Overlaps
Lemma 1 [Kaprinski et al. 1997]
For every pair of variables Xi and Yj,
OL(Xi, Yj) forms O(n) arithmetic progressions.

Lemma 2 [Kaprinski et al. 1997]
For every pair of variables Xi and Yj,OL(Xi, Yj) can be computed in total of O(n4logn) time.

n is num. of variables in SLP T

Case 4Lemma 3
For every variable Xi, a longest repeating substringin Case 4 can be computed in O(n3logn) time.
[Sketch of proof]• We can expand all elements of each arithmetic
progression of OL(Xi, Xj) in O(nlogn) time.
• The size of OL(Xi, Xj) is O(n) by Lemma 1.
• There are at most n-1 descendants Xj of Xi.

Algorithm to Compute LRSInput: SLP T
Output: LRS of text TXiXlXr

foreach variable Xi of SLP T do
compute LRS of Case 1;
compute LRS of Case 2;
Case 5compute LRS of Case 3;
compute LRS of Case 4;
Symmetric to Case 4
compute LRS of Case 5;
compute LRS of Case 6;
return two positions and the length of
the “longest” LRS above;

Algorithm to Compute LRSInput: SLP T
Output: LRS of text TXi
Xl

Xr

foreach variable Xi of SLP T do
compute LRS of Case 1;
compute LRS of Case 2;
Case 6compute LRS of Case 3;
compute LRS of Case 4;
Similarly to Case 4
compute LRS of Case 5;
compute LRS of Case 6;
return two positions and the length of
the “longest” LRS above;

Finding Longest Repeating Substring

Theorem 2

For any SLP T which generates text T, wecan compute an LRS of T in O(n4logn) time.

n is num. of variables in SLP T

Finding Longest Non‐Overlapping Repeating Substring

Input: SLP T which generates text TOutput: A longest non‐overlapping repeating
substring (LNRS) of T

ExampleT = ababababab

LRS of T is abababab
LRNS of T is abab

Finding Longest Non‐Overlapping Repeating Substring

Theorem 3

For any SLP T which generates text T, we
can compute an LNRS of T in O(n6logn) time.

n is num. of variables in SLP T

Finding Most Frequent Substring

Input: SLP T which generates text T
Output: A most frequent substring (MFS) of T

The solution is always
the empty string .

Finding Most Frequent Substring

Input: SLP T which generates text T
Output: A most frequent substring (MFS) of Tof length 2T

Algorithm to Compute MFS||2 substringsof length 2

Y1
Input: SLP T
Output: MFS of text Taforeach substring P of T of length 2 doconstruct an SLP P which generates substring P;
compute num. of occurrences of P in T;
return substring of maximum num. of occurrences;

Y3Y2bLemma 4
For every pair of variables Xi and Yj, the number ofoccurrences of Yj in Xi can be computed in total of O(n2) time.

Finding Most Frequent Substring

Theorem 4

For any SLP T which generates text T, we cancompute an MFS of T of length 2 in O(||2n2)
time.

n is num. of variables in SLP T

Finding Most Frequent Non‐Overlapping Substring

Input: SLP T which generates text T
Output: A most frequent non‐overlapping substring(MFNS) of T of length 2Example

T = aaaaababab

MFS of T of length 2 is aa
MFNS of T of length 2 is abFinding Most Frequent Non‐Overlapping Substring

Theorem 5

For any SLP T which generates text T, we cancompute an MFNS of T of length 2 inO(n4logn) time.

n is num. of variables in SLP T

Computing Left and Right Contexts of Given Pattern
Input: Two SLPs T and P which generate
text T and pattern P, respectively
Output: Substring P of T such that
 (resp. ) always precedes (resp. follows) P in T
 and  are as long as possible

ExampleT = bbaabaabbaabb

P = ab
 = ba=Computing Left and Right Contexts of Given Pattern

Examples of applications of computing left andright contexts of patterns are:
Blog spam detection [Narisawa et al. 2007]
Compute maximal extension of most frequent
substrings (MFS)TBoundary Lemma [1/2]
XXlXrYYY

Lemma 5 [Miyazaki et al. 1997]
For any SLP variables X = XlXr and Y, the occurrencesof Y that touch or cover the boundary of X form asingle arithmetic progression.

Boundary Lemma [2/2]
XXlXruuv Yuuv Yuuv

YLemma 5 [Miyazaki et al. 1997](Cont.) If the number of elements in the progression ismore than 2, then the step of the progression is thesmallest period of Y.

Left and Right ContextsXXl

Xruuv uuv uuv YThe left context  ofY in X is a suffix of u.

The right context of Y in X is a prefixof uv[|v|: |uv|].

Computing Left and Right Contexts of Given Pattern

Theorem 6

For any SLPs T and P which generate text T
and pattern P, respectively, we can computethe left and right contexts of P in T inO(n4logn) time.

n is num. of variables in SLP T

Conclusions and Future Work
We presented polynomial time algorithms to findcharacteristic substrings of given SLP‐compressedtexts.
Our algorithms are more efficient than any algorithms
that work on uncompressed strings.

Would it be possible to efficiently find other types ofsubstrings from SLP‐compressed texts?
Squares (substrings of form xx)
Cubes (substrings of form xxx)
Runs (maximal substrings of form xk with k ≥ 2)
Gapped palindromes (substrings of form xyxR with |y| ≥ 1)