√лавна€    Ex Libris     ниги    ∆урналы    —татьи    —ерии     аталог    Wanted    «агрузка    ’удЋит    —правка    ѕоиск по индексам    ѕоиск    ‘орум   
blank
јвторизаци€

       
blank
ѕоиск по указател€м

blank
blank
blank
 расота
blank
Smyth B. Ч Computing patterns in strings
Smyth B. Ч Computing patterns in strings

„итать книгу
бесплатно

—качать книгу с нашего сайта нельз€

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



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


Ќазвание: Computing patterns in strings

јвтор: Smyth B.

јннотаци€:

The computation of patterns in strings is a fundamental requirement in many areas of science and information processing. The operation of a text editor, the lexical analysis of a computer program, the functioning of a finite automaton, the retrieval of information from a database - these are all activities which may require that patterns be located and computed.
In other areas of science, the algorithms that compute patterns have applications in such diverse fields as data compression, cryptography, speech recognition, computer vision, computational geometry and molecular biology.


язык: en

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

—татус предметного указател€: √отов указатель с номерами страниц

ed2k: ed2k stats

√од издани€: 2003

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

ƒобавлена в каталог: 23.11.2005

ќперации: ѕоложить на полку | —копировать ссылку дл€ форума | —копировать ID
blank
ѕредметный указатель
$\Pi$-equivalence (in DAWGs)      141 143Ч145 155
Aggarwal, Alok      391
Agrep      289
Aho, Alfred V.      16 46 176 199 305 309Ч313 341
Algorithms, ACFA      309Ч313
Algorithms, ADBG      269Ч274
Algorithms, BM      187Ч198
Algorithms, BMFAST      208Ч209
Algorithms, BMG      219Ч223
Algorithms, BMGS      220Ч223
Algorithms, BMH      210Ч212
Algorithms, BMS1      213Ч215
Algorithms, BMS2      215Ч218
Algorithms, BMS2*      217Ч218
Algorithms, Border      14Ч20
Algorithms, BYN      317Ч326
Algorithms, C      331Ч340
Algorithms, calcLP      344Ч347
Algorithms, calcLP'      344Ч347
Algorithms, calcR      353Ч355
Algorithms, CWFA      313Ч314
Algorithms, DBG      202Ч205
Algorithms, DFA      302Ч305
Algorithms, Dvl      158Ч167
Algorithms, Dvl*      162Ч167
Algorithms, Easy      42
Algorithms, F      126Ч136
Algorithms, FST      370Ч380
Algorithms, H1      245
Algorithms, H2      246Ч248
Algorithms, H3      248Ч249
Algorithms, HS      250Ч256
Algorithms, KK      356Ч258
Algorithms, KMP      181Ч187
Algorithms, KMP*      184Ч185
Algorithms, KMPH      226Ч231
Algorithms, KR      198Ч201
Algorithms, LS      360Ч370
Algorithms, LZ      175Ч178
Algorithms, M      279Ч286
Algorithms, M*      285
Algorithms, MaxSuff      170Ч174
Algorithms, McC      117Ч121
Algorithms, MinSuff      167Ч170
Algorithms, ML      340Ч349
Algorithms, Mn      350Ч356
Algorithms, NDFA      297Ч302
Algorithms, S      380Ч396
Algorithms, SAComplex      149Ч156
Algorithms, SANaive      149Ч156
Algorithms, SASimple      149Ч156
Algorithms, SIPS1      399Ч401
Algorithms, SIPS2      401
Algorithms, TD      140Ч149
Algorithms, Turbo-BM      223Ч225
Algorithms, U      276Ч279
Algorithms, Ukn      121Ч126
Algorithms, UM      256Ч263
Algorithms, WF      241Ч244 266Ч269
Algorithms, WM      286Ч292 315Ч316
Algorithms, WM*      305Ч308
Allison, Lloyd      202 264
Allouche, Jean-Paul      75 85
Alphabet      6Ч7 61Ч62 91Ч92
Alphabet, binary      6 26 39 62 194
Alphabet, general      see "Unordered"
Alphabet, indexed      39 92 94 113 126 136 188 190 198 302 304Ч305 308 312 314 316Ч317 325 331Ч332 348 380 384
Alphabet, ordered      6 8 27Ч33 39 41 46 92 113 120Ч121 126 157 170 187 198 250 253 256 330Ч332 339 349
Alphabet, quaternary      6
Alphabet, standard      95
Alphabet, ternary      6 62
Alphabet, unordered      6 92 94 139 175 329 332 341
Amoux, Pierre      85
Andersson, Ame      113
Antecedent      63Ч64
Apostolico, Alberto      37Ч38 56 113 174 222 256 329 361 379 391
Arikawa, S.      149
Arlazarov, V.L.      264 302
Array, benefit      381 383Ч386 388Ч391 395
Array, border      15Ч20 23Ч24 36 52Ч53 57 91Ч93 100Ч108 111Ч112 182 191Ч192 309Ч312 342 359Ч360 362 364 366Ч367
Array, cost      239Ч245 256 263 265Ч268 274Ч276 285 381Ч383 400Ч401
Array, cover      36 57 91 359Ч370
Array, Monge      391Ч393
Array, NE      375Ч380
Array, NRE      378Ч380
Array, right border      23 192
Array, suffix      see "Suffix"
Astoorian, Dan      75
Asymptotic complexity      8 12 14 22 32 211 256 285 290Ч291 325
Asymptotically optimal      19 24 91 136 381
Atallah, Mikhail J.      391
Avoidance problem      61Ч62 67 69 74Ч75 78 85
Avoidance problem, weak      62
b-canonical      100Ч108
B-equivalence      100Ч108
Backtracking      19 90Ч91 158 161Ч162 222 227 234 384
Baeza-Yates, Ricardo      ix 42 185 194 202Ч205 211 264 271 273 285 292 297 309 317Ч326
Baghdadi, Leila      xii
Base-pairs      42
Bean, Dwight R.      74
Benefit array      see "Array"
Benson, Gary      395
Bentley, Jon L.      150 154
Berstel, Jean      85 363
Binary letter comparison      164
Block (of a morphism)      see "Morphism"
Blumer, Anselm      141
Blumer, Janet      141
Boasson, Luc      363
Booth, Kellogg S.      174
Border      9Ч24 36 66Ч67 79 100Ч108
Border, array      see "Array"
Border, longest      9 13Ч16 19 22Ч23 36 66 75 93 103 106 111 162 182 184 190 192 217 220Ч221
Border, tree      see "Tree"
Border-equivalence      see "b-equivalence"
Boshernitzan, M.      85
Bowsher, S.      185
Boyer, Robert S.      23 42 127 187Ч198 206Ч225 231Ч235 273 297 309 313Ч314 325
Branch nodes      38 121 125 376Ч378
Braunholtz, C.H.      69 71 74
Breslauer, Dany      361
Brodal, Gerth S.      56 357 375 379
Caelli, Terry      xii
Canonical form (of necklace)      27Ч28 31 33 40 90 158 174Ч175
Castelli, M. Gabriella      22
Chang, William I.      277Ч279 285 293
Chappie, Jerry      xii
Charras, Christian      181 231
Chen, K.T.      29 158
Chen, M.T.      113 141
Chiba, Seibi      241
Cluster property      151 153 156
Code      63Ч64 71 75 80
Cohen, Donald N.      241
Cole, Richard      91 164 194Ч195 234 293
Collision      200
Colussi, Livio      234
Commentz-Walter, Beate      313Ч314
complexity      see "Asymptotic complexity"
Concatenation      4Ч7 73 126 158
conjugate      65Ч68 71 173
Corasick, Margaret      309Ч313
Cost (of edit operation)      239Ч245 256Ч259 381Ч385
Cost, array      see "Array"
Cover      54 56Ч57 59 359Ч370
Cover of a necklace      59
Cover, array      see "Array"
Cover, tree      see "Tree"
Coverable      see "String"
Crawford, Tim      53
Crochemore, Maxime      ix 40 51 55 138 141 149 174 193 223 225 233Ч234 264 273 313 329Ч340 350 360 379 382
cube      11 62 67 69 78Ч79 81Ч84
Currie, James D.      32 74
Cyclic shift      see "Rotation"
Czumaj, Artur      223 225 313
D-run      376Ч377 380
Dag      145Ч148
Davies, G.      185
DAWG      40 111 140Ч150 155 225
de Luca, Aldo      85
Decomposition      9 40 157 397
Decomposition, Lyndon      see "Lyndon"
DELETE      see "Deletion"
Deletion      43Ч45 50 239Ч241 258Ч259 289 291 317 384
Dependency graph      257Ч259 263 381 386
Deterministic finite automaton      see "DFA"
DFA      302Ч305
Difference matrix      279Ч281
Differences (in Myers' algorithm), horizontal      279 281 283
Differences (in Myers' algorithm), vertical      279 281
Dinic, E.A.      264 302
Directed acyclic graph      see "DAG"
Directed acyclic word graph      see "DAWG"
Distance (between strings)      43Ч46 57Ч58 238 259 266
Distance (between strings), absolute      397
Distance (between strings), asymmetric edit      50
Distance (between strings), deletion      50
Distance (between strings), edit      44 50 237Ч238 244 264 269 274Ч277 279Ч280 284Ч286 288 292 309 316Ч317 323Ч324 383 395Ч397 401Ч402
Distance (between strings), Hamming      43 58 237Ч238 241 269 271 273 292 309 317 362 402
Distance (between strings), Levenshtein      43Ч45 50 58 237Ч239 244Ч245 250 257 263 264 266Ч268 279Ч280 286 288Ч289 309 317
Distance (between strings), relative      397Ч400
Distance (between strings), weighted      44 50 237Ч238 266 397Ч398
Dix, Trevor I.      202 264
Doemoelki, Balint      42 202Ч205 264
Duval, Jean-Pierre      24 28 102 105 157Ч175
Dynamic-programming      238Ч239 381Ч385 401
Edit operations      43Ч44 50 238 242Ч244 268 384 386 395 see "Indel" "Insertion" "Substitution"
Ehrenfeucht, Andrzej      56 74 141 285 379
El-Mabrouk, Nadia      273
Element      3Ч5
Encoding      13 52Ч53 55 77Ч78 82Ч84 90 93 166 329 347 382
Equal (of strings)      8 12
Erdos, Pal      62
Erickson, Brian W.      381 388
execution time      7 18 90Ч91 165Ч166 207
Execution time, amortized      93 105 112
Execution time, average-case      152 165 174 194 201 206 211 225 232Ч235 276Ч277 279 285 292Ч293 323
Execution time, worst-case      22 24 39 42 62 77 90 150 152 162 164Ч166 174 185 187 194Ч195 201 206Ч207 209 211 218Ч220 225Ч226 232Ч235 250 253 264 273 276Ч277 279 285Ч286 293 303 305 307 313Ч314 323 329 332 358 382
EXPONENT      10Ч11 13 20 36 52Ч54 61Ч62 347 350 381
Exponent, "the"      10
Exponent, maximum      10
Exponent, trivial      10
FA      38 296Ч314 317Ч326
Factor      9 31 158 351Ч352 355Ч356 358 398 400Ч401
Factorization      see "Decomposition"
Failure function algorithm      16 310
Farach, Martin      113Ч114 126Ч136 361
Faradzev, I.A.      264 302
Fastscan      117 119Ч120 124Ч125 137 139
Fibonacci string      see "Fibostring"
Fibostring      52Ч53 56 58Ч59 62Ч64 66 71 76Ч87 93Ч94 108 112Ч114 175Ч177 185
Fibostring, generalized      78
Fibostring, infinite      77 79
Fibostring, infinite generalized      79
Fibostring, reverse      86
Fine, N.J.      20
Finite automaton      see "FA"
Fischer, Michael J.      241Ч244
Flipflop variable      246
Four Russians technique      264 302
Fox, R.H.      29 158
Fraenkel, Aviezri S.      85 349Ч350 357
Frangk, Frantisek      xii 24 85 102 105 340 347 370Ч380
Galil, Zvi      91 164 219Ч220 234 273 279
Gao, Shudi      24 102 105 108
Gap (between repeats)      54 56 338Ч339 360Ч361
Gasieniec, Leszek      223 225 313
Generator      10Ч11 13 52Ч55 57 158Ч163 328Ч329 339 353 355 357 372
Generator, "the"      10
Generator, approximate      360 381Ч382 396Ч402
Generator, trivial      10
Giancarlo, Raffaele      91 164 222 234 273
Giegerich, Robert      126
Golden mean      77 108
Gonnet, Gaston H.      42 194 202Ч205 211 264 271 273 285
grep      46
Grid graph      381 386Ч395
guard      212Ч213 218Ч219 232
Guerra, C.      256
Guibas, Leo J.      14 194
Gusfield, Dan      ix 38 177 331 357 375
Hamming, Richard      43
Hancart, Christophe      ix 193 223 226Ч231
Hannan, Sampath K.      395
Harel, Dov      135
Hariharan, Ramesh      91 164 234 293
Hash function      199Ч200
Haton, Jean-Paul      241
Haussler, David      141 285
Head (of suffix)      115Ч116 118Ч121 138
Herendi, Tamas      75
Hirschberg, Dan S.      46 244Ч250 264
Holub, Jan      149
Hopcroft, John E.      16 46 176 199 299 341
Horspool, R. Nigel      210Ч212 232
Hoshino, H.      149
Huang, Xiaoqiu      238 382
Hume, Andrew      209 213 217Ч218 231Ч232
Hunt, James W.      250Ч256 264
I-run      376Ч377
ID-run      see "I-run" "D-run"
Iliopoulos, Costas S.      xii 53 84 174 264 331 361 396Ч402
Indel      258Ч259 267 269 274
Inenaga, S.      149
Initiator (of morphism)      see "Morphism"
Insert      see "Insertion"
insertion      43Ч45 50 239Ч240 258Ч259 289 291 317 320 384
Iteration (of morphism)      see "Morphism"
Jacobson, Guy      264
Jarominek, Stefan      223 225
Jennings, Christopher G.      212
Jiang, Jiandong      22 85
K-approximate match      see "Match"
k-differences problem      274Ч286 289 292
k-mismatches problem      269Ч274 285Ч286 289
Karaman, Ayse      85
Karp, Richard M.      46 198Ч201
Keraenen, Veikko      62
Kim, Sung-Ryul      263Ч264
Knuth, Donald E.      18 20 36 42 77 97 98 108 176 181Ч187 194 235 330
Kolpakov, Roman      56 84 331 349Ч350 356Ч358
Kosaraju, S. Rao      357
Kowalski, G.      213
Kronrod, M.A.      264 302
Kruskal, Joseph B.      241
Kucherov, Gregory      56 84 331 349Ч350 356Ч358
Kurtz, Stefan      126 138 149
Lampe, Jordan      277Ч279 285
Landau, Gad M.      263Ч264 273 279 285 395 401
Larmore, Lawrence      391
Larsson, N. Jesper      113 150 154
Lawler, Eugene L.      285 293
LCA      114 130Ч131 135Ч136 139
LCF      51 137 140
LCP      129 131 135 151Ч155 342 344 371Ч380
LCP, LCP tree      see "Tree"
lcp, nodes (in suffix tree)      372Ч374 378Ч380
LCS      249Ч250
LE      55Ч56 58Ч59 71 370 389
Lecroq, Thierry      ix xii 24 102 105 181 193 223 225 231 233 235 313
1 2 3
blank
–еклама
blank
blank
HR
@Mail.ru
       © Ёлектронна€ библиотека попечительского совета мехмата ћ√”, 2004-2017
Ёлектронна€ библиотека мехмата ћ√” | Valid HTML 4.01! | Valid CSS! ќ проекте