From Algorithms on Strings
Overview
In this chapter, we present data structures for storing the suffixes of a text. These structures are conceived for providing a direct and fast access to the factors of the text. They allow to work on the factors of the string in almost the same way as the suffix array of Chapter 4 does, but the more important part of the technique is put on the structuring of data rather than on algorithms to search the text.
The main application of these techniques is to provide the basis of an index implementation as described in Chapter 6. The direct access to the factors of a string allows a large number of other applications. In particular, the structures can be used for matching patterns by considering them as search machines (see Chapter 6).
Two types of objects are considered in this chapter, trees and automata, together with their compact versions. Trees have for effect to factorize the prefixes of the strings in the set. Automata additionally factorize their common suffixes. The structures are presented in decreasing order of size.
The representation of the suffixes of a string by a trie (Section 5.1) has the advantage to be simple but can lead to a quadratic memory space according to the length of the considered string. The (compact) suffix tree (Section 5.2) avoids this drawback and admits a linear memory space implementation.
The minimization (in the sense of automata) of the suffix trie gives the minimal suffix automaton described in Section 5.4.
Products & Services
Roller chain sprockets engage chain drives in power transmission and conveyor systems, though sprockets can engage any perforated material. Chain drives can produce a mechanical advantage as speed reducers/increasers. ISO sprockets are designed to engage British Standard Chain and conform to ISO standard R606. These sprockets are not interchangable with ANSI defined sprockets.
Topics of Interest
The techniques introduced in the two previous chapters find immediate applications for the realization of the index of a text. The utility of considering the suffixes of a text for this kind of...
Overview This chapter is devoted to the detection of local periodicities that can occur inside a string. The method for detecting these periodicities is based on a partitioning of the suffixes...
Overview This chapter presents the algorithmic and combinatorial framework in which are developed the following chapters. It first specifies the concepts and notation used to work on strings,...
In this chapter, we address the problem of searching for a pattern in a text when the pattern represents a finite set of strings. We present solutions based on the utilization of automata. Note first...
In this chapter, we consider the problem of searching for all the occurrences of a fixed string in a text. The methods described here are based on combinatorial properties. They apply when the string...
