Download Implementation of DCA Compression Method

6
CHAPTER 2. PRELIMINARIES
Definition 2.19 (Suffix trie depth)
Suffix trie depth k is the maximum height allowed for the trie. We will denote it as
maxdepth k.
Note 2.4 (Suffix trie depth limit)
Due to the suffix trie depth limit k, suffix trie represents only suffixes S ⊂ σ(T ), ∀x ∈ S :
|x| ≤ k.
Theorem 2.1 (Suffix trie [18])
Suffix trie ST rie(T ) can be constructed in time proportional to the size of ST rie(T )
which, in the worst case, is O(|T |2 ).
Definition 2.20 (Suffix tree [18])
Suffix tree STree(T ) of T is a data structure that represents STrie(T ) in space linear
in the length |T | of T . This is achieved by representing only a subset Q0 ∪ {⊥} of the
states of STrie(T ). We call the states in Q0 ∪ {⊥} the explicit states. Set Q0 consists of
all branching states (states from which there are at least two transitions) and all leaves
(states from which there are no transitions) of STrie(T ). By definition, root is included
into the branching states. The other states of STrie(T ) (the states other than root and ⊥
from which there is exactly one transition) are called implicit states as states of STree(T );
they are not explicitly present in STree(T ).
Note 2.5 (Suffix link)
Suffix link is a key feature for linear-time construction of the suffix tree. In a complete
suffix tree, all internal non-root nodes have a suffix link to another internal node. Suffix
link corresponds to function f (r) of state r. If the path from the root to a node spells
the string bv, where b ∈ Σ is a symbol and v is a string (possibly empty), it has a suffix
link to the internal node representing v.
Note 2.6 (Suffix tree)
Suffix tree represents all suffixes of a given string. It is designed for fast substring searching, each node represents a substring, which is determined by the path to the node. The
difference between suffix tree and suffix trie could be more obvious from Figure 2.1.
The large amount of information in each edge and node makes the suffix tree very expensive, consuming about ten to twenty times [11] the memory size of the source text in
good implementations. The suffix array reduces this requirement to a factor of four, and
researchers have continued to find smaller indexing structures.
Definition 2.21 (Antifactor [3])
Antifactor (or Forbidden Word ) is a word that never appears in a given text.
Let Σ be a finite alphabet and Σ∗ the set of finite words of symbols from Σ, the empty
word ε included.
Let L ⊂ Σ∗ be a factorial language, i.e. ∀u, v ∈ Σ∗ , uv ∈ L ⇒ u, v ∈ L. The complement
Σ∗ \ L of L is a (two sided) ideal of Σ∗ . Denote by MF(L) its base: Σ∗ \ L = Σ∗ MF(L)Σ∗ .