Главная    Ex Libris    Книги    Журналы    Статьи    Серии    Каталог    Wanted    Загрузка    ХудЛит    Справка    Поиск по индексам    Поиск    Форум   
blank
Авторизация

       
blank
Поиск по указателям

blank
blank
blank
Красота
blank
Crochemore M., Rytter W. — Jewels of stringology
Crochemore M., Rytter W. — Jewels of stringology



Обсудите книгу на научном форуме



Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter


Название: Jewels of stringology

Авторы: Crochemore M., Rytter W.

Аннотация:

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 algorithmic problems the 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.


Язык: en

Рубрика: Computer science/Алгоритмы/

Статус предметного указателя: Готов указатель с номерами страниц

ed2k: ed2k stats

Год издания: 2002

Количество страниц: 310

Добавлена в каталог: 15.11.2005

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID
blank
Предметный указатель
2D-pattern matching by hashing algorithm      273
AC function      172
Adaptive-Huffman-coding algorithm      152
Agrep      197
Aho      3 164 172 181 211 214 216
Aho — Corasick automaton      164 172 214 216
Alignment      7 8 183
Alignment graph      185
Alphabet      10
Alphabetical ordering      86 93 98 101 133 134
Alternative-Compute-PREF procedure      39
Amir      222 225 247 284
Apostolico      32 68 196
Approximate algorithm      274
Approximate matching      4 8 183 192 193 196 209 212 214 215
Approximate string-matching with at most k errors algorithm      193
Baeza — Yates      109 196
Baker      222 284
Bell      161
Benson      225 247
Bentley      161
Bird      222
Blumer      84
BM algorithm      28
BMG algorithm      30
Border      11 12 17 21—23 33—36 38 40 127 130 199 216 217 234 276 279
Boyer      19 26 29 32 33 39 41 43 221 273
Breslauer      256
Browne      196
Brute-force algorithm      112
Brute-force1 algorithm      20
Brute-force2 algorithm      27
BuildSMA function      166 169
Bulletin board      258
Burrows      161
CHARACTER      10
Chen      68
Cleary      162
Code      4 142 145—147 150 156 158 271 276 277 284
Codeword      143 145 147 149—152 154 158 276—278
Coding function      276
Cole      44
Commentz — Walter      181
Comp function      180
Comp1 function      180
Computation-of-ModifiedFailureTable algorithm      281
Compute-BM-Shifts procedure      40
Compute-Bord procedure      171
Compute-Borders1 procedure      34
Compute-Borders2 procedure      34
Compute-Borders3 procedure      38
Compute-by-Splitting procedure      257
Compute-Prefixes procedure      38
Compute-strong-borders procedure      35
Compute-table-of-suffixes procedure      40
Construct-Oracle algorithm      106
Corasick      164 172 181 211 214 216
Cormack      161
CRCW PRAM      250 252 255—257
CREW PRAM      250 252—257 259 268 269
Critical factorization      136 140
Critical position      42 43
Crochemore      32 84 123 140 161 162 181
Cyclic equivalence      139 140
Cyclic shifts      16 17
Cyclic-Equivalence algorithm      140
Desert area      204 205 219
Deterministic sample      218—220 223 254 255 258
Deterministic sampling      254 270
Dictionary of basic factors      6 85 86 88 90 92 95 101 104 109 259
Dictionary of coding      142 143 154 156 158 159
Directed acyclic word graph (DAWG)      5 45 46 69 122 160
Doubling technique      258
du      196
Duel      199—203 207 209 252 253 269
Duval      140
Dynamic programming      8 183 184 186 190 191
Edit distance      4 7 183—186 188 191 196 249 250 268—270
Edit function      185
Efficiency of algorithms      8 209
entropy      149 150 160 161
EREW PRAM      62
Even      161
Expensive duel      202 203 207
Expensive-duel function      202
f-factorization      122 123 160
Factor      10
Factor automaton      5 69 175
Factorization      6 121 122 156 158 159 277
Failure function      21 111 119 167 170 175 181 281 284
Failure link      166
Failure table      34 119 120 166 167 170—172 217 283
Faller      161
Fano      161
Farach      96 104 109 222 225 247 284
Fast-on-average algorithm      31
Feng      284
Fibonacci word      13 14 46 47 121 128
Field of fire      219 220 254
Find-good-sample algorithm      207
Fischer      196
Galil      31 32 123 136 138—140 207 223 235 244—248 256 269 270
Gallager      161
Giancarlo      32 223
Gonnet      109 196
GP algorithm      247
Greedy      115 156 157
Greedy algorithm      239
Greedy-SCS function      274
Grid graph      268
GS algorithm      139
Guerra      196
Gusfield      123
Harrison      284
Hartman      161
Hashing      271—273 284
Hirschberg      196 284
HL algorithm      283
Hopcroft      107 181
Horspool      161
Hsu      196
Huffman      147—155 160 161
Huffman algorithm      148
Huffman code      145 146 149 150 263
Huffman coding      6 141 143 145 146 151 152 161 250 263 268
Huffman tree      147—149 151—154 249 263—267
Hunt      196
Identifier      59
INDEX      5 59
Informal-MaxSuffix-Matching algorithm      128
Kambayashi      196
Karp      85 89 107 215 258 271—273 284
Karp — Rabin algorithm      272
Kasai      109
Kernighan      3
KMP algorithm      24
KMR algorithm      89
Knuth      19 20 23 24 31 33 44 68 161
Kraft's inequality      146
Kruskal      196
Landau      196
Larmore      284
Lattice-Periodic-Extend procedure      246
LCA dictionary      101 106 107
Lecroq      32
Legal interval      282
Lempel      123 142 143 158 160 161
Les function      190
letter      10
Lexicographic ordering      86 93 98 101 133 134
Line-Periodic-Extend procedure      247
Linear-SQUARE function      122
Local period      136
Longest common factor      60—62 68 84
Longest common subsequence      4 8 183 186—191 196
Longest increasing subsequence      190 196
Longest repeated factor      62 89 90
Longest-Self-Maximal-Prefix function      129
Lorentz      123
Lowest common ancestor      62
Main      123
Manacher      123
Manacher algorithm      114
Manber      109 196
Masek      196
Match      10
MATCH-EXTENDS function      280
Matching with don't cares      183 193—196 212 213
Matching with errors      191—193 196
Maximal suffix      125 128—134 136 139 140
Maxsuf-and-Period function      131
MaxSuf-and-PeriodO function      130
MaxSuffix-Matching algorithm      129
McCreight      59 63—68 104
McCreight algorithm      67
McMillan's inequality      146
Mignosi      162
Miller      85 89 107 215 258
Minimization      69
Mismatch      23 214
Model of machine      9 26 163 176 249 278
Modified-KMP algorithm      280
Moffat      161
Monge property      266
Moore      19 26 29 32 33 39 41 43 221 273
Morris      19—24 31 33 44 127 248
Morse      150
MP algorithm      23
Multi-pattern matching      3 172 209 211 214—216 218
Muthukrishnan      284
Myers      109 196
Naive-Period function      126
Naive-Scan function      37
Nakatsu      196
naming      85 87 90
Naming function      278 279
Naming table      85 87
Neal      162
Needleman      196
Nelson      161
Nonperiodic-Extend procedure      246
Numbering      85
Occur      10
Occurrence shift      29
On-line-DAWG algorithm      74
On-line-KMP algorithm      25
On-line-trie algorithm      51
Optimal algorithm      8 10 85 121 191 202
Optimal factorization      156 157
Optimal parallel algorithm      2 9 199 202 249 250 254—257 268—270 273
Overlap-free      14
Palindrome      8 13 111—115 117—119 123
Palstar      111 112 115—119 181
PALSTAR function      118
Paragraph      281
Parallel random access machine (PRAM)      249 250
Park      235 244—248
Paterson      196 284
Pattern      1
Pattern matching      1
Pattern-matching automaton      4 71 164 175 181 259
Pattern-matching machine      175 181
Period      11 225
Periodic      11 136
periodicity      11
Perrin      140 181
Plandowski      284
POSITION      10
Pratt      19—24 31 33 44 127 161 248
Prefix code      145—149 151
Prefix computation      251—254 273
Prefix memorization      30
Prefprod function      251
primitive      16 138
Pseudoperiod      249 255
PSTAR function      115
Quadrangle inequality      266
Rabin      271—273 284
Random access machine (RAM)      26 179 249 251 278
REFINE procedure      260
Regular pair      92
Repeating prefix      138
Restivo      162
Rodeh      161
Rosenberg      85 89 107 215 258
Rotation      139
Rytter      140 270
Safe shift      21 27
Salemi      162
Sampling      136 137 199 204 209 218 219 223 252 254
Sankoff      196
Sardinas      284
Scheme of McCreight algorithm algorithm      64
Schieber      196
Search algorithm      96
Seiferas      68 123 136 138—140
Self-maximal      125
Semi-greedy factorization      157 159 161
Sequential-Sampling algorithm      137
Shannon      161
Shortest common superstring      7 271 274 276
Simulatel algorithm      180
Sink      73
Sleator      161
Slow duel      269
SMA algorithm      165
Source      142
SpecialCase-MP algorithm      127
Splitting      73 75 98 99 249 255 256
Square function      121
Square-free      14
Storer      161
Stoye      123
String-searching-by-duels function      203
String-searching-by-expensive-duels algorithm      203
Strong border      24 33 35
Subsequence      10
Substitution      276
Subword      10
Subword trie      46
Suffix array      5 91 92 109
Suffix link      49 70 72
Suffix tree      5 46—48
Suffix-Merge-Sort algorithm      104
Suffix-Testing algorithm      241
Suffix-testing problem      241
Suffvx-Tree-by-Refining algorithm      260
Symbol      10
Szymanski      196
Table of borders      21
Takaoka      284
Tarhio      284
Tarjan      161
text      1
Time-space optimal algorithm      2 8 127 140
Turbo-BM      32
Two-way automaton      176
Two-way Pattern-Matching algorithm      133
Ukkonen      49 51—53 55 56 79 84 104 196 284
Ukkonen algorithm      53
1 2
blank
Реклама
blank
blank
HR
@Mail.ru
       © Электронная библиотека попечительского совета мехмата МГУ, 2004-2020
Электронная библиотека мехмата МГУ | Valid HTML 4.01! | Valid CSS! О проекте