Jewels of Stringology : Text Algorithms.
Title:
Jewels of Stringology : Text Algorithms.
Author:
Crochemore, Maxime.
ISBN:
9789812778222
Personal Author:
Physical Description:
1 online resource (322 pages)
Contents:
Contents -- Preface -- 1 Stringology -- 1.1 Text file facilities -- 1.2 Dictionaries -- 1.3 Data compression -- 1.4 Applications of text algorithms in genetics -- 1.5 Efficiency of algorithms -- 1.6 Some notation and formal definitions -- 1.7 Some simple combinatorics of strings -- 1.8 Some other interesting strings -- 1.9 Cyclic shifts and primitive words -- Bibliographic notes -- 2 Basic string searching algorithms -- 2.1 Knuth-Morris-Pratt algorithm -- 2.2 Boyer-Moore algorithm and its variations -- Bibliographic notes -- 3 Preprocessing for basic searchings -- 3.1 Preprocessing patterns for MP and KMP algorithms -- 3.2 Table of prefixes -- 3.3 Preprocessing for Boyer-Moore algorithm -- 3.4 * Analysis of Boyer-Moore algorithm -- Bibliographic notes -- 4 On-line construction of suffix trees -- 4.1 Tries and their compact versions -- 4.2 Prelude to Ukkonen algorithm -- 4.3 Ukkonen algorithm -- Bibliographic notes -- 5 More on suffix trees -- 5.1 Several applications of suffix trees -- 5.2 McCreight algorithm -- Bibliographic notes -- 6 Subword graphs -- 6.1 Directed acyclic graph -- 6.2 On-line construction of subword graphs -- 6.3 The reverse perspective -- 6.4 Compact subword graphs -- Bibliographic notes -- 7 Text algorithms related to sorting -- 7.1 The naming technique: KMR algorithm -- 7.2 Two-dimensional KMR algorithm -- 7.3 Suffix arrays -- 7.4 Constructing suffix trees by sorting -- 7.5 The Lowest-Common-Ancestor dictionary -- 7.6 Suffix-Merge-Sort -- Bibliographic notes -- 8 Symmetries and repetitions in texts -- 8.1 Searching for symmetric words -- 8.2 Compositions of symmetric words -- 8.3 Searching for square factors -- Bibliographic notes -- 9 Constant-space searchings -- 9.1 Constant-space matching for easy patterns -- 9.2 MaxSuffix-Matching -- 9.3 Computation of maximal suffixes.
9.4 Matching patterns with short maximal suffixes -- 9.5 Two-way matching and magic decomposition -- 9.6 Sequential sampling for unordered alphabets -- 9.7 Galil-Seiferas algorithm -- 9.8 Cyclic equality of words -- Bibliographic notes -- 10 Text compression techniques -- 10.1 Substitutions -- 10.2 Static Huffman coding -- 10.3 Dynamic Huffman coding -- 10.4 Factor encoding -- Bibliographic notes -- 11 Automata-theoretic approach -- 11.1 Aho-Corasick automaton -- 11.2 Determinizing automata -- 11.3 Two-way pushdown automata -- Bibliographic notes -- 12 Approximate pattern matching -- 12.1 Edit distance -- 12.2 Longest common subsequence problem -- 12.3 String matching with errors -- 12.4 String matching with don't care symbols -- Bibliographic notes -- 13 Matching by dueling and sampling -- 13.1 String matching by duels -- 13.2 String matching by sampling -- Bibliographic notes -- 14 Two-dimensional pattern matching -- 14.1 Multi-pattern approach -- 14.2 Don't cares and non-rectangular patterns -- 14.3 2D-Pattern matching with mismatches -- 14.4 Multi-pattern matching -- 14.5 Matching by sampling -- 14.6 An algorithm fast on the average -- Bibliographic notes -- 15 Two-dimensional periodicities -- 15.1 Amir-Benson-Farach algorithm -- 15.2 Geometry of two-dimensional periodicities -- 15.3 * Patterns with large monochromatic centers -- 15.4 * A version of the Galil-Park algorithm -- Bibliographic notes -- 16 Parallel text algorithms -- 16.1 The abstract model of parallel computing -- 16.2 Parallel string-matching algorithms -- 16.3 * Splitting technique -- 16.4 Parallel KMR algorithm and application -- 16.5 Parallel Huffman coding -- 16.6 Edit distance - efficient parallel computation -- Bibliographic notes -- 17 Miscellaneous -- 17.1 Karp-Rabin string matching by hashing -- 17.2 Shortest common superstrings.
17.3 Unique-decipherability problem -- 17.4 Parameterized pattern matching -- 17.5 Breaking paragraphs into lines -- Bibliographic notes -- Bibliography -- Index.
Abstract:
The term "stringology" is a popular nickname for text algorithms, or algorithms on strings. This book deals with the most basic algorithms in the area. Most of them can be viewed as "algorithmic jewels" and deserve reader-friendly presentation. One of the main aims of the book is to present several of the most celebrated algorithms in a simple way by omitting obscuring details and separating algorithmic structure from combinatorial theoretical background. The book reflects the relationships between applications of text-algorithmic techniques and the classification of algorithms according to the measures of complexity considered. The text can be viewed as a parade of algorithms in which the main purpose is to discuss the foundations of the algorithms and their interconnections. One can partition the algorithmic problems discussed into practical and theoretical problems. Certainly, string matching and data compression are in the former class, while most problems related to symmetries and repetitions in texts are in the latter. However, all the problems are interesting from an algorithmic point of view and enable the reader to appreciate the importance of combinatorics on words as a tool in the design of efficient text algorithms. In most textbooks on algorithms and data structures, the presentation of efficient algorithms on words is quite short as compared to issues in graph theory, sorting, searching, and some other areas. At the same time, there are many presentations of interesting algorithms on words accessible only in journals and in a form directed mainly at specialists. This book fills the gap in the book literature on algorithms on words, and brings together the many results presently dispersed in the masses of journal articles. The presentation is reader-friendly; many examples and about two hundred figures illustrate nicely the behaviour
of otherwise very complex algorithms. Contents: Stringology; Basic String Searching Algorithms; Preprocessing for Basic Seachings; On-Line Construction of Suffix Trees; More on Suffix Trees; Subword Graphs; Text Algorithms Related to Sorting; Symmetries and Repetitions in Texts; Constant-Space Searchings; Text Compression Techniques; Automata-Theoretic Approach; Approximate Pattern Matching; Matching by Dueling and Sampling; Two-Dimensional Pattern Matching; Two-Dimensional Periodicities; Parallel Text Algorithms; Miscellaneous. Readership: Undergraduates, graduate students and researchers in algorithmics.
Local Note:
Electronic reproduction. Ann Arbor, Michigan : ProQuest Ebook Central, 2017. Available via World Wide Web. Access may be limited to ProQuest Ebook Central affiliated libraries.
Genre:
Added Author:
Electronic Access:
Click to View