Simple Linear-Time Off-Line
Text Compression byLongest-First Substitution
Ryosuke Nakamura, Hideo Bannai,
Shunsuke Inenaga, Masayuki Takeda
Kyushu University, Japan

Lossless Compression
UncompressedCompressedLossless Data Compression• Dictionary-based Compression– LZ77 [Ziv and Lemple, ‘77]

• BW Transform-based Compression[Burrows and Wheeler, ‘94]
– Bzip• Grammar-based Compression– SEQUITUR [Nevill-Manning and Witten ‘97]
– RE-PAIR [Larrson and Moffat ‘00]
Fast compressed pattern matching [Kida et al. ‘03]

Grammar-based Compression
Stringtransformababaabaaba

deriveContext FreeGrammar
S→aBAABA→baa
B→ba

Our Target

encodeBit String

decode000101000010

Grammar-based Compression• There exist more than one grammar
generating the same string.
• Input string : aaaaaaaabaaaaaaaa
S → aaaaaaaabaaaaaaaa
S → AbA, A → BB, B → aaaa
S → AAbAA, A → aaaa
S → AAAAbAAAA, A → aa
• We want a small grammar.

Grammar-based Compression• There exist more than one grammar
generating the same string.
• Input string : aaaaaaaabaaaaaaaa
S → aaaaaaaabaaaaaaaa
Finding the smallest grammar
is NP-hard [Storer ’77]

S → AbA, A → BB, B → aaaa
S → AAbAA, A → aaaa
S → AAAAbAAAA, A → aa
• We want a small grammar.

Greedy Method• Recursively replaces frequent and/or long
factors by non-terminal symbols.
aaaaaa aaaaaaaa
Input string: aaaaaaaaaabaaaaaaaa
S → XXXXbXXXX
X → aaXXXX XXXX
Replaced string : XXXXbXXXX
S → YbY
X → aaY → XXXX

Greedy Method• Most Frequent First Substitution (MFFS)
recursively replaces the most frequent factors
by non-terminal symbols• Longest First Substitution (LFS)
recursively replaces the longest repeating
factors by non-terminal symbols

Greedy Method• Most Frequent First Substitution (MFFS)
recursively replaces the most frequent factors
RE-PAIR : linear time algorithm for MFFS
by non-terminal symbols[Larsson and Moffat ‘00]
• Longest First Substitution (LFS)
recursively replaces the longest repeating
factors by non-terminal symbols

Text Compression
by Longest First Substitution[Bentley and McIlroy ‘99]
• Recursively replaces
Longest Repeating Factors (LRFs)
by non-terminal symbols
ac aab acabdcaa
aababdcaa
S → acdaabcacabdcaababdcaad
aab ac abdcaa longest repeating factoracac
S → acdaabcacXbXd,
X→abdcaa
S → YdaabcYXbXd, X→abdcaa, Y→ac

Time Complexities ofLongest First Substitution Approach• n : length of input string– naive algorithm : O(n4) time
– algorithm using minimal augmented suffix
trees [Brodal et al. ’02] : O(n2log n) : time
– our algorithm : O(n) time ☺

Our algorithm• Uses a new data structure
sparse lazy suffix trees（SLSTrees）
based on suffix trees [Weiner ’73];• Runs in linear time and space.

Algorithm Flow Chart
input string
construct SLSTreeO(n)look forlongest repeating factor

O(n)updateSLSTreereplaced stringO(1)(amortized)
Is there any longest repeating factor?

yesreplace longest repeating factor
by non-terminal symbol，andmake new production ruleO(1)(amortized)
nooutput grammar

O(n) + O(n) = O(n) time

How to find Longest Repeating Factor012345678910
abbabbabab$
ab ab abab2(0,8)

ababb$

1(1,9)

baa104b$ b(1,4)
a a $ 35bb(0,3)
(2,7)
b9ba$
8$
aab abb6bbab7a$
0 1 2 3 4b 5 6$ 7 8 9 10ab$
4baaabbab53$bba b$ b a b a b 1$
02

length offactor
beginning positions(min,max)
5 : abbab
4 : bbab3 : bab2 : ab

If we use suffix tree…
abbabbabab$

abXXab$

YXXY$

O(n)

O(n)

O(n)bbba ab b$b a 6abb$
3ab$0a$10 a b a$ b $ b9 ab8ba$ ab
7 a b $bab 5$ 4ba$
b1$2ab b$
X

6X
a$X bXX
b$a4X
a$b5ba$ 3$
b20$
1

O(n2)

B X $4YY
Y $ X $3 X
Y2Y$$
0
1…

Using sparse lazy suffix tree
abbabbabab$bba ab b$b a 6abb$3abb0

abXXab$YXXY$aalazya$bb
10 a
10updatea$$$ b $ b9 a
98 Xb8・$ a b a・
7 b$bbabaab 5$ 4babba
1b$20$O(n)lazy
updateX・・babab$1$
lazy
10 update…

What is laziness?
012345678910
abX・・X・・ab $length of next longest repeating factor ≦length of current longest repeating factor

length oflongest
repeatingfactor

a$8a$b

1X・・babab$
0$
9updated(candidates for next LRF)
X・・babab$1not updated

not replaced

What is laziness?
012345678910
abX・・X・・ab $length of next longest repeating factor ≦length of current longest repeating factor

length oflongest
repeatingfactor

aa$b

1$

$

updated(candidates for next LRF)

XX・
98Our algorithm
・ linear timetakes・b・ab
not updated
ababba$b
not replaced$10Smaller grammar withLongest First Substitution (LFS2)• Consider the right side of production rules
constructed by the LFS method.
abbabbbabbbbababbab$
S → XYbYX$
S → XbbabbbbabX$bbab
X → abbab
X → abbab
Y → bbab
XbbabbbbabX$1bbab$2
want to replace with Y

S → XYbYX$X → aY
Y → bbabSmaller grammar withLongest First Substitution (LFS2)• Consider the right side of production rules
constructed by the LFS method.
abbabbbabbbbababbab$LFS
LFS2
S → XYbYX$
S → XYbYX$
X → abbab
X → aYY → bbabY → bbab
15
12grammar size
grammar size : total length of the right side of production rules.

Smaller grammar withLongest First Substitution (LFS2)• Consider the right side of production rules
constructed by the LFS method.
abbabbbabbbbababbab$LFSLFS2
We developed a linear
S → algorithm
XYbYX$ for LFS2.
S → XYbYX$time
X → abbab
X → aYY → bbabY → bbab
15
12grammar size
grammar size : total length of the right side of production rules.

Comparison of grammar sizes• Input texts : Canterbury Corpus

Conclusions• We developed– a linear time algorithm for longest firstsubstitution (LFS);– a linear time algorithm for LFS2.

• LFS2 generates smaller grammars than
MFFS for small files.

Future Work• Efficient encoding of LFS grammars to bitstrings.
• Compressed pattern matching specialized
for LFS compressed texts.
– The right side of most production rules
consists only of terminal symbols (not LFS2).
e.g., S → YdaabcYXbXd, X→abdcaa, Y→ac
There should be efficient pattern matchingalgorithms for this.