Muutke küpsiste eelistusi

125 Problems in Text Algorithms: with Solutions [Pehme köide]

4.50/5 (4 hinnangut Goodreads-ist)
, ,
  • Formaat: Paperback / softback, 344 pages, kõrgus x laius x paksus: 227x150x19 mm, kaal: 500 g, Worked examples or Exercises
  • Ilmumisaeg: 01-Jul-2021
  • Kirjastus: Cambridge University Press
  • ISBN-10: 1108798853
  • ISBN-13: 9781108798853
Teised raamatud teemal:
125 Problems in Text Algorithms: with SolutionsSuurem pilt
  • Formaat: Paperback / softback, 344 pages, kõrgus x laius x paksus: 227x150x19 mm, kaal: 500 g, Worked examples or Exercises
  • Ilmumisaeg: 01-Jul-2021
  • Kirjastus: Cambridge University Press
  • ISBN-10: 1108798853
  • ISBN-13: 9781108798853
Teised raamatud teemal:
Püsilink: https://www.kriso.ee/db/9781108798853.html
Märksõnad:
"String matching is one of the oldest algorithmic techniques, yet still one of the most pervasive in computer science. The past 20 years have seen technological leaps in applications as diverse as information retrieval and compression. This copiously illustrated collection of puzzles and exercises in key areas of text algorithms and combinatorics on words offers graduate students and researchers a pleasant and direct way to learn and practice with advanced concepts. The problems are drawn from a large range of scientific publications, both classic and new. Building up from the basics, the book goes on to showcase problems in combinatorics on words (including Fibonacci or Thue-Morse words), pattern matching (including Knuth-Morris-Pratt and Boyer-Moore-like algorithms), efficient text data structures (including suffix trees and suffix arrays), regularities in words (including periods and runs) and text compression (including Huffman, Lempel-Ziv and Burrows-Wheeler-based methods)"--

Muu info

Worked problems offer an interesting way to learn and practice with key concepts of string algorithms and combinatorics on words.
Preface ix
1 The Very Basics of Stringology
1(16)
2 Combinatorial Puzzles
17(36)
1 Stringologic Proof of Fermat's Little Theorem
18(1)
2 Simple Case of Codicity Testing
19(1)
3 Magic Squares and the Thue-Morse Word
20(2)
4 Oldenburger-Kolakoski Sequence
22(2)
5 Square-Free Game
24(2)
6 Fibonacci Words and Fibonacci Numeration System
26(2)
7 Wythoff's Game and Fibonacci Word
28(2)
8 Distinct Periodic Words
30(3)
9 A Relative of the Thue-Morse Word
33(1)
10 Thue-Morse Words and Sums of Powers
34(1)
11 Conjugates and Rotations of Words
35(2)
12 Conjugate Palindromes
37(2)
13 Many Words with Many Palindromes
39(2)
14 Short Superword of Permutations
41(2)
15 Short Supersequence of Permutations
43(2)
16 Skolem Words
45(3)
17 Langford Words
48(2)
18 From Lyndon Words to de Bruijn Words
50(3)
3 Pattern Matching
53(58)
19 Border Table
54(2)
20 Shortest Covers
56(2)
21 Short Borders
58(2)
22 Prefix Table
60(2)
23 Border Table to the Maximal Suffix
62(3)
24 Periodicity Test
65(2)
25 Strict Borders
67(3)
26 Delay of Sequential String Matching
70(2)
27 Sparse Matching Automaton
72(2)
28 Comparison-Effective String Matching
74(2)
29 Strict Border Table of the Fibonacci Word
76(2)
30 Words with Singleton Variables
78(3)
31 Order-Preserving Patterns
81(2)
32 Parameterised Matching
83(2)
33 Good-Suffix Table
85(3)
34 Worst Case of the Boyer-Moore Algorithm
88(2)
35 Turbo-BM Algorithm
90(2)
36 Siring Matching with Don't Cares
92(1)
37 Cyclic Equivalence
93(3)
38 Simple Maximal Suffix Computation
96(2)
39 Self-Maximal Words
98(2)
40 Maximal Suffix and Its Period
100(3)
41 Critical Position of a Word
103(2)
42 Periods of Lyndon Word Prefixes
105(2)
43 Searching Zimin Words
107(3)
44 Searching Irregular 2D Patterns
110(1)
4 Efficient Data Structures
111(69)
45 List Algorithm for Shortest Cover
112(1)
46 Computing Longest Common Prefixes
113(2)
47 Suffix Array to Suffix Tree
115(4)
48 Linear Suffix Trie
119(3)
49 Ternary Search Trie
122(2)
50 Longest Common Factor of Two Words
124(2)
51 Subsequence Automaton
126(2)
52 Codicity Test
128(2)
53 LPF Table
130(4)
54 Sorting Suffixes of Thue-Morse Words
134(3)
55 Bare Suffix Tree
137(2)
56 Comparing Suffixes of a Fibonacci Word
139(2)
57 Avoidability of Binary Words
141(3)
58 Avoiding a Set of Words
144(2)
59 Minimal Unique Factors
146(2)
60 Minimal Absent Words
148(4)
61 Greedy Superstring
152(3)
62 Shortest Common Superstring of Short Words
155(2)
63 Counting Factors by Length
157(3)
64 Counting Factors Covering a Position
160(1)
65 Longest Common-Parity Factors
161(1)
66 Word Square-Freeness with DBF
162(2)
67 Generic Words of Factor Equations
164(2)
68 Searching an Infinite Word
166(3)
69 Perfect Words
169(4)
70 Dense Binary Words
173(2)
71 Factor Oracle
175(5)
5 Regularities in Words
180(50)
72 Three Square Prefixes
181(2)
73 Tight Bounds on Occurrences of Powers
183(2)
74 Computing Runs on General Alphabets
185(3)
75 Testing Overlaps in a Binary Word
188(2)
76 Overlap-Free Game
190(2)
77 Anchored Squares
192(3)
78 Almost Square-Free Words
195(2)
79 Binary Words with Few Squares
197(2)
80 Building Long Square-Free Words
199(2)
81 Testing Morphism Square-Freeness
201(2)
82 Number of Square Factors in Labelled Trees
203(3)
83 Counting Squares in Combs in Linear Time
206(2)
84 Cubic Runs
208(2)
85 Short Square and Local Period
210(2)
86 The Number of Runs
212(2)
87 Computing Runs on Sorted Alphabet
214(5)
88 Periodicity and Factor Complexity
219(1)
89 Periodicity of Morphic Words
220(2)
90 Simple Anti-powers
222(2)
91 Palindromic Concatenation of Palindromes
224(1)
92 Palindrome Trees
225(2)
93 Unavoidable Patterns
227(3)
6 Text Compression
230(45)
94 BW Transform of Thue-Morse Words
231(2)
95 BW Transform of Balanced Words
233(4)
96 In-place BW Transform
237(2)
97 Lempel-Ziv Factorisation
239(3)
98 Lempel-Ziv-Welch Decoding
242(2)
99 Cost of a Huffman Code
244(4)
100 Length-Limited Huffman Coding
248(5)
101 Online Huffman Coding
253(3)
102 Run-Length Encoding
256(5)
103 A Compact Factor Automaton
261(3)
104 Compressed Matching in a Fibonacci Word
264(2)
105 Prediction by Partial Matching
266(3)
106 Compressing Suffix Arrays
269(2)
107 Compression Ratio of Greedy Superstrings
271(4)
7 Miscellaneous
275(43)
108 Binary Pascal Words
276(2)
109 Self-Reproducing Words
278(2)
110 Weights of Factors
280(2)
111 Letter-Occurrence Differences
282(1)
112 Factoring with Border-Free Prefixes
283(3)
113 Primitivity Test for Unary Extensions
286(2)
114 Partially Commutative Alphabets
288(2)
115 Greatest Fixed-Density Necklace
290(2)
116 Period-Equivalent Binary Words
292(3)
117 Online Generation of de Bruijn Words
295(3)
118 Recursive Generation of de Bruijn Words
298(2)
119 Word Equations with Given Lengths of Variables
300(2)
120 Diverse Factors over a Three-Letter Alphabet
302(2)
121 Longest Increasing Subsequence
304(2)
122 Unavoidable Sets via Lyndon Words
306(3)
123 Synchronising Words
309(2)
124 Safe-Opening Words
311(3)
125 Superwords of Shortened Permutations
314(4)
Bibliography 318(14)
Index 332
Maxime Crochemore is Emeritus Professor of Université Gustave-Eiffel and of King's College London. He holds an Honorary Doctorate from the University of Helsinki. He is the author of more than 200 articles on algorithms on strings and their applications, and co-author of several books on the subject. Thierry Lecroq is Professor in the Department of Computer Science at the University of Rouen Normandy (France). He is currently head of the research team 'Information Processing in Biology and Health' of the 'Laboratory of Computer Science, Information Processing and System'. He has been one of the coordinator of the working group in Stringology of the French CNRS for more than 10 years. Wojciech Rytter is Professor of University of Warsaw. He is the author of a large number of publications on automata, formal languages, parallel algorithms and algorithms on texts. He is a co-author of several books on these subjects, including 'Efficient Parallel Algorithms', 'Text Algorithms' and 'Analysis of algorithms and data structures'. He is a member of Academia Europaea.