58093 String Processing Algorithms

Lectures, Autumn 2016, period II

Juha Kärkkäinen
Contents

0. Introduction

1. Sets of strings
• Search trees, string sorting, binary search

2. Exact string matching

• Finding a pattern (string) in a text (string)

3. Approximate string matching

• Finding in the text something that is similar to the pattern

4. Text Indexes
• Suffix tree and suffix array
• Preprocess a long text for fast string matching and
all kinds of other tasks
2
 0. Introduction
Strings and sequences are one of the simplest, most natural and most used
forms of storing information.

• natural language, biosequences, programming source code, XML,

music, any data stored in a file

• Many algorithmic techniques are first developed for strings and later
generalized for more complex types of data such as graphs.

The area of algorithm research focusing on strings is sometimes known as

stringology. Characteristic features include

• Huge data sets (document databases, biosequence databases, web

crawls, etc.) require efficiency. Linear time and space complexity is the
norm.

• Strings come with no explicit structure, but many algorithms discover

implicit structures that they can utilize.

3
About this course

On this course we will cover a few cornerstone problems in stringology. We

will describe several algorithms for the same problems:

• the best algorithms in theory and/or in practice

• algorithms using a variety of different techniques

The goal is to learn a toolbox of basic algorithms and techniques.

On the lectures, we will focus on the clean, basic problem. Exercises may
include some variations and extensions. We will mostly ignore any
application specific issues.

4
Strings

An alphabet is the set of symbols or characters that may occur in a string.

We will usually denote an alphabet with the symbol Σ and its size with σ.

Examples of alphabets:

• Σ = {a, b, . . . , z}

• Integer alphabet: Σ = {0, 1, 2, . . . , σ − 1}

• Byte alphabet: Σ = {0, 1, 2, . . . , 255}

• ASCII alphabet: all printable ASCII symbols

• Unicode alphabet

• ...

5
Alphabet or not:

• UTF-8
– Encoding of Unicode symbols using 1–4 bytes
– Not an alphabet, Unicode is the underlying alphabet
– Alternatively, we can treat a UTF-8 encoded string as
a sequence of bytes.

• Words in a natural language text

– Unbounded alphabet: no fixed upper bound on size
– Encoding a word as sequence of symbols is inefficient,
better to encode using integers when efficiency matters.

6
A string is a sequence of symbols. The set of all strings over an alphabet Σ
is
∞
[
∗
Σ = Σk = Σ0 ∪ Σ1 ∪ Σ2 ∪ . . .
k=0
where
k
z }| {
k
Σ = Σ × Σ × ··· × Σ
= {a1 a2 . . . ak | ai ∈ Σ for 1 ≤ i ≤ k}
= {(a1 , a2 , . . . , ak ) | ai ∈ Σ for 1 ≤ i ≤ k}
is the set of strings of length k. In particular, Σ0 = {ε}, where ε is the
empty string.

We will usually write a string using the notation a1 a2 . . . ak , but sometimes

using a1 · a2 · · · · · ak or (a1 , a2 , . . . , ak ) may avoid confusion.

7
There are many notations for strings.

When describing algorithms, we will typically use the array notation to

emphasize that the string is stored in an array:
S = S[1..n] = S[1]S[2] . . . S[n]
T = T [0..n) = T [0]T [1] . . . T [n − 1]
Note the half-open range notation [0..n) which is often convenient.

In an abstract context, we often use other notations, for example:

• α, β ∈ Σ∗
• x = a1a2 . . . ak where ai ∈ Σ for all i
• w = u · v = uv, u, v ∈ Σ∗ (w is the concatenation of u and v)

We will use |w| to denote the length of a string w.

8
Individual characters or their positions usually do not matter. The
significant entities are the substrings or factors.

Definition 0.1: Let w = xyz for any x, y, z ∈ Σ∗ . Then x is a prefix,

y is a factor (substring), and z is a suffix of w.
If x is both a prefix and a suffix of w, then x is a border of w.

Example 0.2: Let w = bonobo. Then

• ε, b, bo, bon, bono, bonob, bonobo are the prefixes of w

• ε, o, bo, obo, nobo, onobo, bonobo are the suffixes of w
• ε, bo, bonobo are the borders of w
• ε, b, o, n, bo, on, no, ob, bon, ono, nob, obo, bono, onob, nobo, bonob, onobo, bonobo
are the (distinct) factors of w.

Note that ε and w are always suffixes, prefixes, and borders of w.

A suffix/prefix/border of w is proper if it is not w, and nontrivial if it is not ε
or w.

9
Models of Computation
The usual model for analyzing algorithms is RAM (Random Access
Machine), where all basic operations such as memory accesses, comparisons
and arithmetic operations take constant time.
However, RAM can be unrealistically powerful:

• A string a1a2 . . . an ∈ Σn for an integer alphabet Σ = [0..σ) can be

encoded as a single integer by considering the characters as digits:
X
x= ai σ n−i
i∈[1..n]

• Then many operations on strings can be executed in constant time

independent of the string length.

A more realistic model is word RAM, that allows only w-bit integers, where
w is the machine word size.

• Common assumption: w = Ω(log n), where n is total size of the memory

used, because we need at least log n bits to represent addresses.
• In real machines, typically w = 64.

10
The word RAM model still allows packing about w/ log σ characters into a
single machine word. We call this the packed string model.

• This technique is somewhat realistic and can speed up real

implementations.

• It requires some assumptions about how the string is encoded and

complicates analysis.

In this course we usually assume a simple string model, where characters

can be accessed only individually.

11
We consider three alphabet models.

General alphabet: An arbitrary set Σ = {c1 , c2 , . . . , cσ }.

• We usually assume that the alphabet is ordered: c1 < c2 < · · · < cσ .

• Algorithms can only use character comparisons.

Integer alphabet: Σ = {0, 1, 2, . . . , σ − 1}.

• Algorithms can use more powerful operations such as using a symbol as

an address to a table or arithmetic operations to compute a hash
function.
• Packed string model requires integer alphabet.

Constant alphabet: A general alphabet for a (small) constant σ.

• Almost any operation on characters and even sets of characters can be

performed in constant time.

12
The alphabet models are really used for classifying and analysing algorithms
rather than alphabets:

• Algorithms for the general alphabet model that use only comparisons
are highly general and can be used in almost any situation.
• Using the more powerful operations of the integer alphabet model can
make algorithms faster. However, it makes the algorithms less general,
and can complicate the analysis.
• The constant alphabet model often indicates one of two things:
– The effect of the alphabet on the complexity is complicated and the
constant alphabet model is used to simplify the analysis.
– The time or space complexity of the algorithm is heavily (e.g.,
linearly) dependent on the alphabet size and the algorithm is
effectively unusable for large alphabets.

An algorithm is called alphabet-independent if its complexity has no

dependence on the alphabet size.

13
Example 0.3: Suppose we want to count how many distinct characters
occur in a given string. We can do this by maintaining a set of distinct
characters. Each character of the string is added to the set if not already
there. The alphabet model determines the choice of the set data structure:

• With general alphabet model, we can use a balanced binary search tree.

• With integer alphabet model, we can use an array of size σ, which is

much faster.

• If σ is large, an array of size σ might be too big. We could use a hash

table instead.

• With constant alphabet model, we could even use an unordered list

without affecting the time complexity.

An alternative solution is to sort the characters, which groups identical

characters together. The choice of the sorting algorithm then depends on
the alphabet model.

14
 1. Sets of Strings
Basic operations on a set of objects include:

Insert: Add an object to the set

Delete: Remove an object from the set.
Lookup: Find if a given object is in the set, and if it is, possibly
return some data associated with the object.

There can also be more complex queries:

Range query: Find all objects in a given range of values.

There are many other operations too but we will concentrate on these here.

15
An efficient execution of the operations requires that the set is stored as a
suitable data structure.

• A (balanced) binary search tree supports the basic operations in

O(log n) time and range searching in O(log n + r) time, where n is the
size of the set and r is the size of the result.

• An ordered array supports lookup and range searching in the same time
as binary search trees using binary searching. It is simpler, faster and
more space efficient in practice, but does not support insertions and
deletions.

• A hash table supports the basic operations in constant time (usually

randomized) but does not support range queries.

A data structure is called dynamic if it supports insertions and deletions

(tree, hash table) and static if not (array). Static data structures are
constructed once for the whole set of objects. In the case of an ordered
array, this involves another important operation, sorting. Sorting can be
done in O(n log n) time using comparisons and even faster for integers.

16
The above time complexities assume that basic operations on the objects
including comparisons can be performed in constant time. When the objects
are strings, this is no more true:

• The worst case time for a string comparison is the length of the shorter
string. Even the average case time for a random set of n strings is
O(logσ n) in many cases, including for basic operations in a balanced
binary search tree. We will later show an even stronger result for
sorting later. And sets of strings are rarely fully random.
• Computing a hash function is slower too. A good hash function
depends on all characters and cannot be computed faster than the
length of the string.

For a string set R, there are also new types of queries:

Prefix query: Find all strings in R that have the query string S as a
prefix. This is a special type of range query.
Lcp (longest common prefix) query: What is the length of the
longest prefix of the query string S that is also a prefix of some
string in R.

Thus we need special set data structures and algorithms for strings.
17
Trie
A simple but powerful data structure for a set of strings is the trie. It is a
rooted tree with the following properties:

• Edges are labelled with symbols from an alphabet Σ.

• For every node v, the edges from v to its children have different labels.

Each node represents the string obtained by concatenating the symbols on

the path from the root to that node.
The trie for a string set R, denoted by trie(R), a e
is the smallest trie that has nodes representing
all the strings in R. The nodes representing l n l
strings in R may be marked.
i n i
Example 1.1: trie(R) for
R = {ali, alice, anna, elias, eliza}. c a a z

e s a

18
The trie is conceptually simple but it is not simple to implement efficiently.
The time and space complexity of a trie depends on the implementation of
the child function:

For a node v and a symbol c ∈ Σ, child(v, c) is u if u is a child of v

and the edge (v, u) is labelled with c, and child(v, c) = ⊥ (null) if v
has no such child.

As an example, here is the insertion algorithm:

Algorithm 1.2: Insertion into trie
Input: trie(R) and a string S[0..m) 6∈ R
Output: trie(R ∪ {S})
(1) v ← root; j ← 0
(2) while child(v, S[j]) 6= ⊥ do
(3) v ← child(v, S[j]); j ← j + 1
(4) while j < m do
(5) Create new node u (initializes child(u, c) to ⊥ for all c ∈ Σ)
(6) child(v, S[j]) ← u
(7) v ← u; j ← j + 1
(8) Mark v as representative of S

19
There are many implementation options for the child function including:

Array: Each node stores an array of size σ. The space complexity is O(σN ),
where N is the number of nodes in trie(R). The time complexity of the
child operation is O(1). Requires an integer alphabet.

Binary tree: Replace the array with a binary tree. The space complexity is
O(N ) and the time complexity O(log σ). Works for a general alphabet.

Hash table: One hash table for the whole trie, storing the values
child(v, c) 6= ⊥. Space complexity O(N ), time complexity O(1).
Requires an integer alphabet.

A common simplification in the analysis of tries is to use a constant

alphabet model. Then the implementation does not matter: Insertion,
deletion, lookup and lcp query for a string S take O(|S|) time.

Note that a trie is a complete representation of the strings. There is no

need to store the strings separately.

20
Prefix free string sets

Many data structures and algorithms for a string set R become simpler if R
is prefix free.

Definition 1.3: A string set R is prefix free if no string in R is a prefix of

another string in R.

There is a simple way to make any string set prefix free:

• Let $ 6∈ Σ be an extra symbol satisfying $ < c for all c ∈ Σ.

• Append $ to the end of every string in R.

This has little or no effect on most operations on the set. The length of
each string increases by one only, and the additional symbol could be there
only virtually.

Example 1.4: The set {ali, alice, anna, elias, eliza} is not prefix free
because ali is a prefix of alice, but {ali$, alice$, anna$, elias$, eliza$} is
prefix free.

21
If R is prefix free, the leaves of trie(R) represent exactly R. This simplifies
the implementation of the trie.

Example 1.5: The trie for {ali$, alice$, anna$, elias$, eliza$}.

a e
l n l
i n i
$ a a z
c
$ s a
e
$ $
$

22
Compact Trie
Tries suffer from a large number of nodes, close to ||R|| in the worst case.

• For a string set R, we use |R| to denote the number of strings in R and
||R|| to denote the total length of the strings in R.

The space requirement can be problematic, since typically each node needs
much more space than a single symbol.

Compact tries reduce the number Example 1.6: Compact trie for
of nodes by replacing branchless {ali$, alice$, anna$, elias$, eliza$}.
path segments with a single edge. a
• The label of a new edge is the eli
concatenation of the labels of li
the edges it replaced.
nna$
$
as$ za$
ce$

23
The space complexity of a compact trie is O(|R|) (in addition to the
strings):

• In a compact trie, every internal node (except possibly the root) has at
least two children. In such a tree, there is always at least as many
leaves as internal nodes. Thus the number of nodes is at most 2|R|.
• The egde labels are factors of the input strings. If the input strings are
stored separately, the edge labels can be represented in constant space
using pointers to the strings.

The time complexities are the same or better than for tries:

• An insertion adds and a deletion removes at most two nodes.

• Lookups may execute fewer calls to the child operation, though the
worst case complexity is the same.
• Prefix and range queries are faster even on a constant alphabet.

24
Ternary Trie

Tries can be implemented in the general alphabet model but a bit

awkwardly using a comparison-based child function. Ternary trie is a simpler
data structure based on symbol comparisons.

Ternary trie is like a binary search tree except:

• Each internal node has three children: smaller, equal and larger.
• The branching is based on a single symbol at a given position as in a
trie. The position is zero (first symbol) at the root and increases along
the middle branches but not along side branches.

There are also compact ternary tries based on compacting branchless path
segments.

25
Example 1.7: Ternary tries for {ali$, alice$, anna$, elias$, eliza$}.

a
e a
l
n l l
i i eli
n i c
c
$ a a $ e$ nna$ a
e
z
$ s s$
$ a za$
$
$

Ternary tries have the same asymptotic size as the corresponding (σ-ary)
tries.

26
A ternary trie is balanced if each left and right subtree contains at most half
of the strings in its parent tree.

• The balance can be maintained by rotations similarly to binary search

trees.
b rotation d

d b
A B D E

C D E A B C

• We can also get reasonably close to a balance by inserting the strings in

the tree in a random order.

Note that there is no restriction on the size of the middle subtree.

27
In a balanced ternary trie each step down either

• moves the position forward (middle branch), or

• halves the number of strings remaining in the subtree (side branch).

Thus, in a balanced ternary trie storing n strings, any downward traversal

following a string S passes at most |S| middle edges and at most log n side
edges.

Thus the time complexity of insertion, deletion, lookup and lcp query is
O(|S| + log n).

In comparison based tries, where the child function is implemented using

binary search trees, the time complexities could be O(|S| log σ), a
multiplicative factor O(log σ) instead of an additive factor O(log n).

Prefix and range queries behave similarly (exercise).

28