CIAC 2015

An opportunistic text indexing structure
based on run length encoding
Yuya Tamakoshi, Keisuke Goto, Shunsuke Inenaga,
Hideo Bannai, Masayuki Takeda
Kyushu University, Japan

Kyushu University, Japan

Kyushu University, Japan

Kyushu U.

Kyushu U.

Kyushu University, Japan
Itoshima Peninsula

Kyushu U.

糸島
String Island

String matching
Input: text string T and pattern string P
Output: all occurrences of P in T

String matching
Input: text string T and pattern string P
Output: all occurrences of P in T
text T

We introduce a general framework which is suitable tocapture an essence of compressed pattern matchingaccording to various dictionary based compressions. The
goal is to find all occurrences of a pattern in a text
without decompression, which is one of the most active
topics in string matching. Our framework includes suchcompression methods as Lempel-Ziv family, (LZ77, LZSS,
LZ78, LZW), byte-pair encoding, and the static dictionary
based method.

pattern P compress

String matching
Input: text string T and pattern string P
Output: all occurrences of P in T
 String matching is fundamental to areas such as Information Retrieval
 Bioinformatics, etc.

Indexed string matching
Preprocess: build index on fixed text T
Query: pattern string P
Answer: all occurrences of P in T
 Goal is to construct a space-efficient index on T
which quickly answers to string matching query.
 Text T can be very long (e.g., DNA sequences).
 We may receive many different query patterns.

Classical text index: Suffix Array
The suffix array SA of text T is an array which
stores the beginning positions of the suffixes of
T in lexicographic order [Manber & Myers, 1991].

T = cococacao$$ is an end-marker
which appears only atthe end of any string.

Classical text index: Suffix Array
The suffix array SA of text T is an array which
stores the beginning positions of the suffixes of
T in lexicographic order [Manber & Myers, 1991].
1 cococacao$
2 ococacao$
3
cocacao$4
ocacao$5cacao$
6
acao$
7
cao$
8
ao$
9
o$
10
$

Classical text index: Suffix Array
The suffix array SA of text T is an array which
stores the beginning positions of the suffixes of
T in lexicographic order [Manber & Myers, 1991].
1 cococacao$
2 ococacao$
3
cocacao$4
ocacao$5cacao$
6
acao$
7
cao$
8
ao$
9
o$
10
$

SA 10 $
6 acao$
8 ao$
5 cacao$
Sort
7 cao$
3 cocacao$
1 cococacao$
9 o$
4 ocacao$
2 ococacao$

String matching with suffix array
Binary search a given pattern P on SASA
P = coc

10
6
8
5
7
3
1
9
4
2

$
acao$
ao$
cacao$
cao$
cocacao$cococacao$o$ocacao$ococacao$String matching with suffix array
Binary search a given pattern P on SASA
P = coc

>

cao$

10
6
8
5
7
3
1
9
4
2

$
acao$
ao$
cacao$
cao$
cocacao$cococacao$o$ocacao$ococacao$String matching with suffix array
Binary search a given pattern P on SASA
P = coc

<

o$

10
6
8
5
7
3
1
9
4
2

$
acao$
ao$
cacao$
cao$
cocacao$cococacao$o$ocacao$ococacao$String matching with suffix array
Binary search a given pattern P on SASA
P = coc=

cocacao$

10
6
8
5
7
✔3
1
9
4
2

$
acao$
ao$
cacao$
cao$
cocacao$cococacao$o$ocacao$ococacao$String matching with suffix array
Binary search a given pattern P on SASA
P = coc=

cococacao$

10
6
8
5
7
✔3
✔1
9
4
2

$
acao$
ao$
cacao$
cao$
cocacao$cococacao$o$ocacao$ococacao$String matching with suffix array
Binary search a given pattern P on SASA✔

✔

1 2 3 4 5 6 7 8 9 10

T = cococacao$
P = coc

10
6
8
5
7
✔3
✔1
9
4
2

$
acao$
ao$
cacao$
cao$
cocacao$cococacao$o$ocacao$ococacao$String matching with suffix arraySA
All occurrences of P in T canbe found in O(m log u+occ)
time using SA.
u
The search time can be
improved to O(m+log u+occ)
using the LCP array.

10
6
8
5
7
3
1
9
4
2

$
acao$
ao$
cacao$
cao$
cocacao$cococacao$o$ocacao$ococacao$u = |T|m = |P|
occ = # occ. of P in T

SA+LCP
Theorem [Manber & Myers, 1991]

There is an index (SA+LCP) which
reports all occ occurrences of P in T
in O(m+logu+occ) time, and requires
2ulogu + ulogσ + O(u) bits of space.
SA & LCP

Text T

Auxiliary data
structure This can take too much spacefor large text T (i.e., for large u).

u = |T|m = |P|
σ = |S|Compressed index
 There are a number of compressed indexes
which occupy only compressed size of text.
 FM-index [Ferragina & Mancini, 2000],
Compressed Suffix Array [Grossi & Vitter, 2000],
Lempel-Ziv index [Gagie et al., 2014], etc.

 Most of them are slower than SA+LCP.

Our proposal
New compressed index based on
run length encoding (RLE) of text whichis smaller & faster than SA+LCP.

Run Length Encoding (RLE)
The run length encoding of text T, denoted RLE(T),is a compressed representation of T in which eachmaximal run a…a of characters is encoded by a p,
where p denotes the length of the maximal run.

T = aaaabbbaacccccccbbbbbaaaaa$
RLE(T) = a4b3a2c7b5a5$
 Applications to RLE include: black-white fax messages
 image format (PackBits, TIFF)
 music format (MIDI)

RLE suffixes
Let n = |RLE(T)|. For any 1 ≤ i ≤ n, RLEsuf(i) is
the suffix of RLE(T) starting with the i-th run.
RLE(T): a4b3a2c7b5a5$

n=7

RLEsuf(1): a4b3a2c7b5a5$
RLEsuf(2): b3a2c7b5a5$
RLEsuf(3):a 2 c7 b5 a5 $RLEsuf(4):c7 b 5 a5 $RLEsuf(5):b 5 a5 $RLEsuf(6):a5 $RLEsuf(7):$Difficulty in indexing RLE suffixes
 We want to index only RLE suffixes of the text,
but simply sorted RLE suffixes don’t work!
sorted RLE suffixes of text

a5b...
a5b...
a5c...
a4b...
a4c...
a4c...
a4c...
a3b...
a3b...

Difficulty in indexing RLE suffixes
 We want to index only RLE suffixes of the text,
but simply sorted RLE suffixes don’t work!
sorted RLE suffixes of text

aaaaab...
aaaaab...
aaaaac...
aaaab...
aaaac...
aaaac...
aaaac...
aaab...
aaab...

Difficulty in indexing RLE suffixes
 We want to index only RLE suffixes of the text,
but simply sorted RLE suffixes don’t work!
sorted RLE suffixes of text

RLE(P): a2b1

Pattern occurrences are
spread out, so wecannot binary search!!

aaaaab...
✔ aaaaab...
aaaaac...
✔ aaaab...
aaaac...
aaaac...
aaaac...
...
✔ aaab...
✔ aaab✔

Our ideas to index RLE suffixes When sorting RLE suffixes, we “ignore”
the exponents of the first runs of RLE
suffixes of text T.

 To find occurrences of pattern P, we first“ignore” the exponent of the first run of
RLE(P), and find its corresponding range.
 We then pick up only the occurrences ofRLE(P) from this range.

Truncated RLE suffixes
tRLEsuf(i) is the suffix of RLEsuf(i) where
the first exponent pi is truncated to 1.
RLEsuf(1): a4b3a2c7b5a5$
RLEsuf(2): b3a2c7b5a5$
RLEsuf(3):a2 c 7 b5 a 5 $RLEsuf(4):c7 b5 a 5 $RLEsuf(5):b5 a 5 $RLEsuf(6):a5 $RLEsuf(7):$tRLEsuf(1): a1b3a2c7b5a5$
tRLEsuf(2): b1a2c7b5a5$
tRLEsuf(3):a1 c7 b 5 a5 $tRLEsuf(4):c1 b5 a5 $tRLEsuf(5):b1 a5 $tRLEsuf(6):a1 $tRLEsuf(7):$Our index: Truncated RLE Suffix Array
The tRLE suffix array tRLESA of text T is an array
which stores the beginning positions of thetRLE suffixes in lexicographical order.
1
2
3
4
5
6
7

a1 b 3 a2 c7 b 5 a5 $b 1 a2 c7 b 5 a5 $a1 c7 b 5 a5 $c1 b 5 a5 $b 1 a5 $a1 $$tRLESA

7
6

Sort

1
3
5
2
4

$
a1 $
a 1 b3 a2 c7 b5 a 5 $a 1 c7 b5 a5 $b 1 a5 $b 1 a2 c7 b5 a5 $c 1 b5 a5 $

Monotonicity on Truncated RLE Suffix ArraytRLESA

99

11
40
55

72
19
26

4

...

...

47

tRLE suffixes

b(2)c5a2 b2a6...
b(9)c5a2 b3a1...
b(1)c5a2 b5a4...
b(2)c5a2 b7a3...
b(3)c5a2 b8c2...
b(9)c5a2 b6c3...
b(1)c5a2 b6c3...
b(5)c5a2 b4c7...
b(1)c5a2 b1c8...
...

...

Ignored exponents in parentheses

Monotonicity on Truncated RLE Suffix Array

47
99

11

The range
bc5a2 matches

40
55

72
19
26

4

b(2)c5a2 b2a6...
b(9)c5a2 b3a1...
b(1)c5a2 b5a4...
b(2)c5a2 b7a3...
b(3)c5a2 b8c2...
b(9)c5a2 b6c3...
b(1)c5a2 b6c3...
b(5)c5a2 b4c7...
b(1)c5a2 b1c8...
...

...

This range canbe found by
a binary search.

tRLE suffixes...

RLE(P): b3c5a2b4

tRLESA
...

We first lookfor bc5a2

Monotonicity on Truncated RLE Suffix Array

47
99

11

The range
bc5a2 matches

40
55

72
19
26

4

tRLE suffixes...

RLE(P): b3c5a2b4

tRLESA...

We next lookfor bc5a2b4

b(2)c5a2 b2a6...
b(9)c5a2 b3a1...
b(1)c5a2 b5a4...
b(2)c5a2 b7a3...
b(3)c5a2 b8c2...
b(9)c5a2 b6c3...
b(1)c5a2 b6c3...
b(5)c5a2 b4c7...
b(1)c5a2 b1c8...
...

...

Monotonicity on Truncated RLE Suffix Array

47
99

11

The range
bc5a2 matches

40
55

72
19
26

4

tRLE suffixes...

RLE(P): b3c5a2b4

tRLESA...

We next lookfor bc5a2b4

b(2)c5a2 b2a6...
b(9)c5a2 b3a1... monotonicallynon-decreasing
(1)
5
2
5
4...
b ca bab(2)c5a2 b7a3...
b(3)c5a2 b8c2...
b(9)c5a2 b6c3... monotonicallyb(1)c5a2 b6c3... non-increasingb(5)c5a2 b4c7...
b(1)c5a2 b1c8...
...

...

Matching with Truncated RLE Suffix Array

47
99

11
40

the range
bc5a2b4 matches

72
19
26

4

b(2)c5a2 b2a6...
b(9)c5a2 b3a1...
b(1)c5a2 b5a4...
b(2)c5a2 b7a3...
b(3)c5a2 b8c2...
b(9)c5a2 b6c3...
b(1)c5a2 b6c3...
b(5)c5a2 b4c7...
b(1)c5a2 b1c8...
...

...

Based on themonotonicity,
this range canbe found by
a binary search.

55

tRLE suffixes...

RLE(P): b3c5a2b4

tRLESA...

We next lookfor bc5a2b4

Matching with Truncated RLE Suffix Array

47
99

11
40

the range
bc5a2b4 matches

55

72
19
26

4

tRLE suffixes...

RLE(P): b3c5a2b4

tRLESA
...

We finally lookfor b3c5a2b4

b(2)c5a2 b2a6...
b(9)c5a2 b3a1...
b(1)c5a2 b5a4...
b(2)c5a2 b7a3...
b(3)c5a2 b8c2...
b(9)c5a2 b6c3...
b(1)c5a2 b6c3...
b(5)c5a2 b4c7...
b(1)c5a2 b1c8...
...

...

Matching with Truncated RLE Suffix Array

47
99

11
40

the range
bc5a2b4 matches

55

72
19
26

4

tRLE suffixes...

RLE(P): b3c5a2b4

tRLESA
...

We finally lookfor b3c5a2b4

...

...

b(2)c5a2 b2a6...
b(9)c5a2 b3a1...
b(1)c5a2 b5a4...
b(2)c5a2 b7a3...
b(3)c5a2 b8c2...
b(9)c5a2 b6c3...
b(1)c5a2 b6c3...
We want only thoseb(5)c5a2 b4c7...
whose1st exponents
(1)
5
2
1
8...
b c a b c are at least 3

Matching with Truncated RLE Suffix Array
exponents tRLESA

9

99

1

11

2

40

3

55

9

72

1

19

5

26

1

4
...

b(2)c5a2 b2a6...
b(9)c5a2 b3a1...
b(1)c5a2 b5a4...
b(2)c5a2 b7a3...
b(3)c5a2 b8c2...
b(9)c5a2 b6c3...
b(1)c5a2 b6c3...
b(5)c5a2 b4c7...
b(1)c5a2 b1c8...
...

47

...

...

2

...

We use an array ofignored exponentsof the first runs.

...

RLE(P): b3c5a2b4

tRLE suffixes

Matching with Truncated RLE Suffix Array
exponents tRLESA

9

99

1

11

2

40

3

55

9

72

1

19

5

26

1

4
...

b(2)c5a2 b2a6...
b(9)c5a2 b3a1...
b(1)c5a2 b5a4...
b(2)c5a2 b7a3...
b(3)c5a2 b8c2...
b(9)c5a2 b6c3...
b(1)c5a2 b6c3...
b(5)c5a2 b4c7...
b(1)c5a2 b1c8...
...

47tRLE suffixes
...

...

the range
bc5a2b4 matches

2...

RLE(P): b3c5a2b4...

We finally lookfor b3c5a2b4

Matching with Truncated RLE Suffix Array
exponents tRLESA
2

47

9

99

1

11

2

40

3

55

9

✔

72
19

5

26

1

4

...

...

b(2)c5a2 b2a6...
b(9)c5a2 b3a1...
b(1)c5a2 b5a4...
b(2)c5a2 b7a3...
b(3)c5a2 b8c2...
b(9)c5a2 b6c3...
b(1)c5a2 b6c3...
b(5)c5a2 b4c7...
b(1)c5a2 b1c8...
...

1tRLE suffixes...

Range Maximum
Query (RMQ)...

RLE(P): b3c5a2b4...

We finally lookfor b3c5a2b4

Matching with Truncated RLE Suffix Array
exponents
tRLESAtRLE
suffixes
We perform
RMQ’srecursively,

RMQ

9

99

1

11

2

40

3

✔

55

9

✔

72

1
5

19
✔

26

4

...

...

b(9)c5a2 b3a1...
b(1)c5a2 b5a4...
b(2)c5a2 b7a3...
b(3)c5a2 b8c2...
b(9)c5a2 b6c3...
b(1)c5a2 b6c3...
b(5)c5a2 b4c7...
b(1)c5a2 b1c8...
...

1

...

RMQ

...

RLE(P): b3c5a2b4

in the 1st & 2nd halves of the range.
247b(2)c5a2 b2a6...
...

We finally lookfor b3c5a2b4

Matching with Truncated RLE Suffix Array
exponents tRLESA

RMQ

9

99

1

11

2

40

3

✔

55

9

✔

72

1
5

19
✔

26

4

...

...

b(9)c5a2 b3a1...
b(1)c5a2 b5a4...
b(2)c5a2 b7a3...
b(3)c5a2 b8c2...
b(9)c5a2 b6c3...
b(1)c5a2 b6c3...
b(5)c5a2 b4c7...
b(1)c5a2 b1c8...
...

1

...

RMQ

...

RLE(P): b3c5a2b4

tRLE suffixes

Recursion ends when the range
maxima is less than 3.
247b(2)c5a2 b2a6...
...

We finally lookfor b3c5a2b4

Matching with Truncated RLE Suffix Array
exponents tRLESA
47

9

99

1

11

2

40

3

✔

55

9

✔

72

1
5

19
✔

26

4
...

b(2)c5a2 b2a6...
b(9)c5a2 b3a1...
b(1)c5a2 b5a4...
b(2)c5a2 b7a3...
b(3)c5a2 b8c2...
b(9)c5a2 b6c3...
b(1)c5a2 b6c3...
b(5)c5a2 b4c7...
b(1)c5a2 b1c8...
...

1
...

[Fischer & Heum, 2011].

2...

Each RMQ takes
O(1) time...

# of RMQ’s we
perform is O(occ).

...

RLE(P): b3c5a2b4

tRLE suffixes

Our results
Theorem 1 (RLE-index)

There is an index which, given RLE(P),reports all occ occurrences of P in T
in O(q+log n+occ) time, and requires
2nlogu + nlogσ + nlogn + O(n) bits of space.
u = |T|n = |RLE(T)|(n ≤ u)q = |RLE(P)|σ = |S|Our results
Theorem 1 (RLE-index)

There is an index which, given RLE(P),reports all occ occurrences of P in T
in O(q+log n+occ) time, and requires
2nlogu + nlogσ + nlogn + O(n) bits of space.
 SA+LCP takes O(m+log u+occ) time
for pattern matching ( m = |P| ).
 Since q ≤ m and n ≤ u always hold,our index is faster than SA+LCP.

u = |T|n = |RLE(T)|(n ≤ u)q = |RLE(P)|σ = |S|Our results
Theorem 1 (RLE-index)

There is an index which, given RLE(P),reports all occ occurrences of P in T
in O(q+log n+occ) time, and requires
2nlogu + nlogσ + nlogn + O(n) bits of space.
 SA+LCP requires
2ulogu + ulogσ + O(u) bits of space.
 Our RLE-index is smaller whentext T is compressible with RLE.

u = |T|n = |RLE(T)|(n ≤ u)q = |RLE(P)|σ = |S|Our results
Theorem 2 (Construction time & space)

Given RLE(T) of size n, the RLE-index of T
can be constructed in O(n log n) time withO(n log u) bits of working space.
 We introduced new combinatorialproperties of RLE suffixes.

u = |T|n = |RLE(T)| We also use the idea of induced-sorting[Nong et al., 2011] which was originallydesigned for fast suffix array construction.

Conclusions & Future work
 Our RLE-index is always faster than SA+LCP.
 Our RLE-index is smaller than SA+LCP
when the text is compressible by RLE(i.e. when the n log n term is negligible).
 Comparisons to other compressed index(e.g., FM-index, compressed SA, LZ-index).

FAQ

LCP array and Range Minima
The LCP array of T stores the length of the longest
common prefix of neighboring suffixes in SA of T.
SA LCP- $10
6
0 acao$81 ao$
50 cacao$
7
2 cao$
3
1 cocacao$
1
3 cococacao$
90 o$
4
1 ocacao$
22 ococacao$

LCP array and Range Minima
The LCP array of T stores the length of the longest
common prefix of neighboring suffixes in SA of T.
SA LCP- $10
6
0 acao$81 ao$
50 cacao$
7
2 cao$
3
1 cocacao$
1
3 cococacao$
90 o$
4
1 ocacao$
22 ococacao$

LCP array and Range Minima
The LCP array of T stores the length of the longest
common prefix of neighboring suffixes in SA of T.
SA LCP- $10
6
0 acao$81 ao$
50 cacao$
7
2 cao$
3
1 cocacao$
1
3 cococacao$
90 o$
4
1 ocacao$
22 ococacao$

LCP array and Range Minima
The length of the LCP of any suffixes can also becomputed by a range minimum query.
LCP- $0 acao$1 ao$
0 ✔ cacao$
2 cao$
1 cocacao$
3 ✔ cococacao$
0 o$
1 ocacao$
2 ococacao$

LCP array and Range Minima
The length of the LCP of any suffixes can also becomputed by a range minimum query.
LCP- $0 acao$1 ao$
0 ✔ cacao$
2 cao$
Range minimum query 1 cocacao$
3 ✔ cococacao$
0 o$
1 ocacao$
2 ococacao$

LCP array and Range Minima
For any integer array of length k,there is a data structure which
supports range minimum query inO(1) time, and requires 2k + o(k) bitsof extra space [Fischer & Heum, 2011].

S-type and L-type RLE suffixes
RLEsuf(i) is S-type if RLEsuf(i) < RLEsuf(i+1).
RLEsuf(i) is L-type if RLEsuf(i) > RLEsuf(i+1).
 a4b3a2c7b5a5$ is S-type, because
a4b3a2c7b5a5$ < b3a2c7b5a5$.
 b3a2c7b5a5$ is L-type, because
b3a2c7b5a5$ < a2c7b5a5$.
※ Lex. order < on RLE strings is the same as
the lex. order < on decompressed strings.

Properties of lex. order of RLE suffixes
For any 1 ≤ i ≤ n, let ai, pi be the ith characterand exponent of RLE(T), respectively.

Lemma
For any RLEsuf(i) and RLEsuf(j) with ai = aj ,1. if RLEsuf(i) is L-type and RLEsuf(j) is S-type,then RLEsuf(i) < RLEsuf(j).

2. if RLEsuf(i) and RLEsuf(j) are L-type and pi < pi ,then RLEsuf(i) < RLEsuf(j).
3. if RLEsuf(i) and RLEsuf(j) are S-type and pi > pi ,then RLEsuf(i) < RLEsuf(j).

Properties of lex. order of RLE suffixes
Lemma (Case 1)

For any RLEsuf(i) and RLEsuf(j) with ai = aj ,1. if RLEsuf(i) is L-type and RLEsuf(j) is S-type,then RLEsuf(i) < RLEsuf(j).
S-type (a < b)

L-type (a > $)a 5 $ < a4 b3 a 2 c7 b5 a5 $

aaaaa$<
aaaabbbaacccccccbbbbbaaaaa$

Properties of lex. order of RLE suffixes
Lemma (Case 2)

For any RLEsuf(i) and RLEsuf(j) with ai = aj ,2. if RLEsuf(i) and RLEsuf(j) are L-type and pi < pi ,then RLEsuf(i) < RLEsuf(j).
L-type (b > a)L-type (b > a)b3 a 2 c7 b5 a 5 $ < b5 a5 $bbbaacccccccbbbbbaaaaa$<

bbbbbaaaaa$

Properties of lex. order of RLE suffixes
Lemma (Case 3)

For any RLEsuf(i) and RLEsuf(j) with ai = aj ,3. if RLEsuf(i) and RLEsuf(j) are S-type and pi > pi ,then RLEsuf(i) < RLEsuf(j).
S-type (a < b)S-type (a < c)a4 b 3 a2 c7 b 5 a5 $ < a2 c7 b5 a 5 $aaaabbbaacccccccbbbbbaaaaa$<

aacccccccbbbbbaaaaa$

Our results
Theorem 3 (accessing SA)
There is an index which, given an integer 1 ≤ j ≤ u,answers SA[j] in O(log2 n) time, and requires𝑢n(3logu + logn + logσ) + 2σlog + O(n loglogn)
σbits of space.
 Use a wavelet tree [Grossi et al., 2003]
in place of RMQ data structure.

 Then, we can access arbitrary positionof SA, using our RLE-index.

u = |T|n = |RLE(T)|σ = |S|