algorithms

Advanced Applications Su ffix Links from Lowest Common Ancestors Suppose we are given a suffix tree and it is required to establish suffix links for each internal node. This may become necessary if the suffix tree creation algorithm does not construct suffix links but they are needed for an application of interest. For example, the suffix tree may be constructed via suffix arrays, completely avoiding the construction and use of suffix links for building the tree. The links can be easily established if the tree is preprocessed for l ca queries. Mark each internal node v of the suffix tree with a pair of leaves ( i, j ) such that leaves labeled i and j are in the subtrees of different children of v . The marking can be done in linear time by a bottom-up traversal of the tree. To find the suffix link from an internal node v (other than the root) marked with ( i, j ), note that v = l ca ( i, j ) and l cp ( suf f i , suf f j ) = path - l abel ( v ). Let path - l abel ( v ) = cα , where c is the first charac...

Lowest Common Ancestors Consider a string s and two of its suffixes suf f i and suf f j . The longest common prefix of the two suffixes is given by the path label of their lowest common ancestor. If the string-depth of each node is recorded in it, the length of the longest common prefix can be retrieved from the lowest common ancestor. Thus, an algorithm to find the lowest common ancestors quickly can be used to determine longest common prefixes without a single character comparison. In this section, we describe how to preprocess the suffix tree in linear time and be able to answer lowest common ancestor queries in constant time [3]. Bender and Farach’s l c a algorithm Let T be a tree of n nodes. Without loss of generality, assume the nodes are numbered 1 .. . n . Let l ca ( i, j ) denote the lowest common ancestor of nodes i and j . Bender and Farach’s algorithm performs a linear time preprocessing of the tree and can answer l ca queries in constant time. Let E be an Euler tour of the t...

Applications In this section, we present algorithms for several string problems using suffix trees and suffix arrays. While the same run-time bounds can be achieved for many interesting applications with either a suffix tree or a suffix array, there are others which involve a space vs. time trade off. Even in cases where the same run-time bound can be achieved, it is often easier to design the algorithm first for a suffix tree, and then think if the implementation can be done using a suffix array. For this reason, we largely concentrate on suffix trees. The reader interested in reading more on applications of suffix arrays is referred to [1, 2]. Pattern Matching Given a pattern P and a text T , the pattern matching problem is to find all occurrences of P in T . Let | P | = m and | T | = n . Typically, n >> m . Moreover, T remains fixed in many applications and the query is repeated for many different patterns. For example, T could be a text document and P could represent a word search. Or, T co...

Patricia The data structure Patricia ( P ractical A lgorithm T o R etrieve I nformation C oded I n A lphanumeric) is a compressed binary trie in which the branch and element nodes have been melded into a single node type. Consider the compressed binary trie of Figure 28.18 . Circular nodes are branch nodes and rectangular nodes are element nodes. The number inside a branch node is its bit number field; the left child of a branch node corresponds to the case when the appropriate key bit is 0 and the right child to the case when this bit is 1. The melding of branch and element nodes is done by moving each element from its element node to an ancestor branch node. Since the number of branch nodes is one less than the number of element nodes, we introduce a header node and make the compressed binary trie the left subtree of the header. Pointers that originally went from a branch node to an element node now go from that branch node to the branch node into which the correspond- ing element h...

Linear Time Construction Algorithms In this section, we explore linear time construction algorithms for suffix trees and suffix arrays. We also show how suffix trees and suffix arrays can be derived from each other in linear time. In suffix tree and suffix array construction algorithms, three different types of alphabets are considered: a constant or fixed size alphabet ( | Σ | = O (1)), integer alphabet (Σ = { 1 , 2 ,.. . , n } ), and arbitrary alphabet. Suffix trees and suffix arrays can be constructed in linear time for both constant size and integer alphabets. The constant alphabet size case covers many interesting application areas, such as English text, or DNA or protein sequences in molecular biology. The integer alphabet case is interesting because a string of length n can have at most n distinct characters. Furthermore, some algorithms use a recursive technique that would generate and require operating on strings over integer alphabet, even when applied to strings over a fixed alphabet. Su ...