Jewels of Stringology: Text AlgorithmsWorld Scientific, 2002 - 310 Seiten 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. |
Inhalt
Preface | 1 |
Twodimensional periodicities | 15 |
Basic string searching algorithms | 19 |
Preprocessing for basic searchings | 33 |
Online construction of suffix trees | 45 |
More on suffix trees | 59 |
Subword graphs | 73 |
Text algorithms related to sorting | 85 |
Text compression techniques | 141 |
Automatatheoretic approach | 163 |
Approximate pattern matching | 183 |
Matching by dueling and sampling | 199 |
Twodimensional pattern matching | 209 |
Bibliographic notes | 247 |
Miscellaneous | 271 |
Bibliography | 281 |
Andere Ausgaben - Alle anzeigen
Jewels Of Stringology: Text Algorithms Maxime Crochemore,Wojciech Rytter Eingeschränkte Leseprobe - 2002 |
Häufige Begriffe und Wortgruppen
2dpda alphabet Assume automata automaton basic begin end binary BM algorithm BM_Shift Bord[j Boyer-Moore algorithm Chapter codewords columns complexity computed consecutive consider constant construction corresponding Crochemore current match data compression DAWG DAWG's DAWG(text defined denote deterministic dictionary duels edges edit distance efficient encoding essential nodes example Fibonacci words Figure function Galil given graph grid graph Hence Huffman coding Huffman tree i-th input integer iteration labeled LCPref leaf Lemma length letter linear linear-time linear-time algorithm lowest common ancestor maximal suffix MaxSuf mismatch Morris-Pratt non-empty non-periodic O(n log occurrences on-line optimal palindromes palstar parallel pat[j path pattern matching period position powerset construction prefix code preprocessing processors quad-I Rad[i sample scanned shift SMA(II sorted sequence stack string matching sub-array subtrees subword suffix arrays suffix links suffix tree table Bord text array text[i Theorem Tree(II Trie two-dimensional vectors word