CHAPTER 1. INTRODUCTION 2
hashing to allow efficient access to a particular list. Subsequent searching for a
word can be done efficiently by locating the corresponding list and enumerating
all the positions of occurrence. For signature files, it is built by first partitioning
the text into pages; then, each word is hashed into a fixed length s-bit value, and
a page is represented by a signature that forms by ‘OR’ing all the hash values of
the words appearing in that page. Subsequent searching for a word can often be
confined to a small number of pages whose signature ‘agrees’ with the hash value
of the word. In general, word-based indexes are able to support fast word queries;
in addition, they are small in size, occupying about 20-30% of the original text
size [82].
Unfortunately, word-based indexes are not suitable to handle texts without
clear-cut word boundaries like DNA sequences, Chinese texts and Japanese texts.
In these circumstances, full-text indexes, which are indexes that make no assump-
tion on the word boundary, are relied upon, at the cost of increasing the space
occupancy. Basically, these indexes are constructed by storing information on
all the substrings occurring in the texts. Suffix trees [57, 79] and suffix arrays
[56] are two fundamental full-text indexes in the literature, which find numerous
applications in areas including biological research (e.g., gene hunting, promoter
consensus identification, and motif finding) [38], data mining [41] and text com-
pression [28]. Suffix tree is a compact version of the trie that stores all suffixes
of the given text. Each suffix is represented by a unique leaf storing its start-
ing position. Based on the suffix tree, any substring of the text can be found
by following some path descending from the root. The importance of the suffix
tree is underlined by the fact that it has been rediscovered many times in the
scientific literature, disguised under different names [34]. Some examples include
the compact bi-tree [79], the prefix tree [15], the PAT tree [30], the position tree
[3, 47, 53], the repetition finder [67], and the subword tree [8, 15]. On the other
hand, suffix array is a reduced form of a suffix tree, which is obtained by visiting
the leaves of the corresponding suffix tree from left to right. More precisely, it
is an array of positions, sorted in the lexicographic order of the corresponding
suffixes.
Both suffix tree and suffix array exhibit superb searching performance. Given
the suffix tree of a text T whose characters are from an alphabet Σ, we can search
for a pattern P within T using O(p log |Σ| + occ) time,
∗
where occ denotes the
∗
We use the notation log
c
b
n to denote (log n/ log b)
c
, which is the c-th power of the base-b
logarithm of n. Unless specified, we use b = 2.
