Ãëàâíàÿ    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
Ïðåäìåòíûé óêàçàòåëü
Leech, John      74
Lefebvre, Arnaud      24 102 105
Left-extendible      see "LE"
Leftmost position (in string)      4—5 7
Lempel, Abraham      40 157 175—178 350
Length (of string)      7—8
Lentin, Andre      20 329 339
letter      6
Levenshtein, V.I.      44
Lewis, Harry R.      295
Lexicographic order      8 12 100 128—129 133 135 170—172
Li, Yin      xii 57 89 360—370
Local optimality (of approximate squares)      381 385 388—390 395
Longest common factor      see "LCF"
Longest common prefix      see "LCP" "lcp"
Longest common subsequence      see "LCS" "lcs"
Longest common suffix      342 344 353
Loop, invariant      23 158 162—163 202 270 356
Loop, variant      23
Lorentz, Richard J.      51 329—331 340—350 393—395
Lothaire, M.      x 85
Lowest common ancestor      see "LCA"
Lowrance, Roy      243
Lu, Weilin      24 85 102 105
Lyndon, decomposition      28—33 40 157—167 173—174
Lyndon, Roger C.      29 158
Lyndon, word      28—31 33 157—170 173
Lyngso, Rune B.      357 375
Main, Michael G.      40 51 56 329—331 340—349 350—356 381 393—395
Manber, Udi      149—156 205 279 286—292 305—308 315—316 375
Margaritis, Konstantinos G.      231
Masek, William J.      264 274
Match, approximate      237—293 380—396
Match, exact      181—235
Match, false      199 201
Mauri, G.      149
Maximal periodicity      see "Run"
Maximal repetition      see "Run"
McCreight, Edward M.      113 116—121 138 154
McFaddin, Scott      391
McNaughton, Robert F.      304
McNulty, George F.      74
Meidanis, Joao      ix
Meltzer, A.      213
Metacharacter      46—48 237 289—290 298—299 308
Metric      45 238 241 259 266 398 402
Michailidis, Panagiotis D.      231
Mignosi, Filippo      22 85
Miller, Dianne      95 100
Minimum starting point      1
Moore, Dennis      xii 84 95 100 334 365
Moore, J. Strother      23 42 127 187—198 206—225 231—235 273 297 309 313—314 325
Morphism      61—65 71—77 80 85—86
Morphism, block of      72—75
Morphism, identity      63
Morphism, initiator of      72—73
Morphism, inverse      63—64
Morphism, iteration of      62—64
Morphism, terminator of      72—73
Morris, James H.      42 181—187 194 235
Morrison, Donald R.      37
Muth, Robert      316
Muthukrishnan, S.      127
Myers, Gene W.      149—156 256—264 276 279—286 302 375 395 401
Nagy, Benedek      202
Navarro, Gonzalo      ix 266 285 292—293 297 309 317—326
NDFA      297—308 310
NE, array      see "Array"
NE, repeat      see "Repeat"
NE, tree      see "Tree"
Necklace      4 25—33 59 62 90 157 174
Necklace, infinite      4
Needleman, Saul B.      241
NLE, array      see "Array"
NLE, repeat      see "Repeat"
NLE, tree      see "Tree"
Non-left-extendible      see "NLE"
Non-right-extendible      see "NRE"
Nondeterministic finite automaton      see "NDFA"
Nonextendible      see "NE"
Normal form      10—11 13—14 23 35—36 52—53 93 111 158 161—162 195—196 221 331 338 347 365
Normal form, right      14 196 221
NRE, array      see "Array"
NRE, repeat      see "Repeat"
NRE, tree      see "Tree"
Occurs      8 267
Odlyzko, Andrew M.      14 194
On (an alphabet)      6
On-line      19 39 90—91 93 99 104—105 121 125 126 139 166 174 177 234 241 369—370
Optimal alignment (of strings)      238
Overlap (of substrings)      9 54 66—67 328 339 357 362 381 390 395
p-canonical      95—101 103 107 166
P-equivalence      94—95 100—101
Palindrome      13 71
Papadimitriou, Christos H.      295
Parikh, Rohit J.      348
Park, James      391
Park, Kunsoo      263—264 279 396—402
Paterson, Michael S.      164 234 264 274
Path score (in grid graph)      386—388
Pattern      42
Pattern, approximate      43—51 57—58 180 237—293 315—326 380—402
Pattern, generic      xi 51—59 327—402
Pattern, intrinsic      xi 35—41 109—178
Pattern, multiple      46—49 295—326
Pattern, specific      x 41—51 179—326
Pattern-equivalence      see "p-equivalence"
Pattern-free      26 32—33 51 61—62 64 72—75 86 330 350
pattern-matching      see "Pattern"
Pavesi, G.      149
Pederson, Christian N.S.      56 357 375 379
Period      10—11 13—24 26—27 52 55 58—59 162 194—196 219—221 224 227 335 339 347 351 353—355 358 362—363 365—366 370
Period, "the"      10
Period, approximate      51 58 328 396—402
Period, array      370
Period, minimum      10
Period, tree      370
Period, trivial      10
Periodic      11
Periodic, 3-periodic      195—197 210 221
Periodic, strongly      11 13 67
Periodic, weakly      11 13
periodicity      14—24 26 51 111 161 195 197 219 328 350 359—402
Periodicity Lemma      20—22 24 32 111 358 363
Periodicity, maximal      see "Run"
Perleberg, Chris H.      273
Perrin, Dominique      234
Petho, Attila      xii
Pinzon, Yoan J.      264
Plandowski, Wojciech      223 225 313
Pleasants, Peter A.B.      62
Plouffe, Simon      95
Position in a string      7—8
Position, nodes (in suffix tree)      372—374 377—378
Position, tree      140 175
Pratt, Vaughan R.      42 181—187 194 235
Predecessor (in a string)      4—5 7—8
Prefix      9
Prefix, node (in suffix tree)      116—117 119 124—126
Prefix, proper      8—9
Prefix-preserving      66 68 77 79
Preparata, Franco P.      38 329 391
primitive      11 13 22 26 28 32—33 158—160 162 170—171 355
Processing time      see "Execution time"
Quasiperiod(ic)      57 328 359
Rabin, Michael O.      199—202
Raman, Rajeev      53
Randall, Jim      75
Rauzy, Gerard      85
Re      55—56 59 370
Reachable (in an FA)      301 303 307
Refinement (in Crochemore's algorithm)      332—340 348
Regnier, Mireille      194 211
Regular, expression      46—49 180 237 286 291 295 297—309
Regular, set      48
Reichert, Thomas A.      241
Reid, James F.      264
REPEAT      53—57
Repeat, approximate      57—58 348 360 380—396
Repeat, complete      53—54 370—375
Repeat, mixed      54
Repeat, NE      55 57 357 360 370—375 379—380
Repeat, NLE      371—372 374
Repeat, NRE      371—372
Repeat, split      54 56 357
Repeat, tandem      54—55 59 329 379—380
Repeating substring      53
Repeating substring, maximal NE      373
Repetition      11 51—52 329—358
Repetition weak      59 62
Repetition, approximate      58 238 381—382
Repetition-free      26 32—33 51 86
Repetitive      11
Restivo, Antonio      22
Right extension      39 364—366 369
Right-extendible      see "RE"
Rightmost position (in string)      4—5 7
Rivest, Ronald L.      233
Rotation (of string)      25—28 31—33 50 55 59 75 79—82 84 111 158 160 197 222 347 362—363
Rote, Guenter      85
Run      56 78 82—86 328—329 331 347 349—358 360 382
Run, leftmax      353 358
Run, leftmost      349—356
Run, rightmax      353 355
Ryan, Patrick J.      xii 17 24 102 105
Rytter, Wojciech      ix 193 223 225 313
s-factorization      40 157 175—178 349—352 355—358
Sadakane, Kunihiko      150 154
Sakoe, Hiroaki      241
Sankoff, David      241
Schensted, Craige      264
Schmidt, Jeanette P.      263—264 380—396 401
Schuetzenberger, Marcel P.      20 329 339
Score (of approximate match)      381 384—388 390—394
Scoring matrix      44 241 243—244 381 384 397 401
Sedgewick, Robert      150 154
Seebold, Patrice      85
Seiferas, Joel      113 141 234
Sellers, Peter H.      381 388
Sentinel ($)      36 115 121 140 149 174 186 189 198
Sequence of iterates      62—64
Sequence, big (in Crochemore refinement)      334—335 337
Sequence, small (in Crochemore refinement)      334—338
Sethi, Ravi      305
Setubal, Joao      ix
Shallit, Jeffrey      75
Shift, cyclic      see "Rotation"
Shift, long (in Boyer — Moore)      195—196 221
Shift, safe      191
Shift, short (in Boyer — Moore)      195—196 221
Shift, Type I (in Boyer — Moore)      190—191 196—197 222—223
Shift, Type II (in Boyer — Moore)      191 195—196 220
Shiloach, Yossi      174
Shinohara, A.      149
Shrdlu, Etaoin      218
Signature (in Karp — Rabin)      199—200
Sim, Jeong Seop      396—402
Simpson, R. Jamie      xii 13 32 70—71 84 349—350 357 363
Sink (in DAWG)      142 144
Sink (in FA)      see "State accepting"
Skip loop      208—209 213 215 217—219 232
Sloane, N.J.A.      95
Slowscan      117 119—121 137 139
Smartscan      124—126
Smit, G. de V.      185 194
Smith, Temple F.      384
Smyth, Jocelyn      xii
Source in FA      see "State start"
Source in grid graph      386—389
Source in suffix tree      138 147—148
Space complexity      90—91 204 233—235 241 246 292 391
Square      11
Square, abelian      62
Square, approximate      381 383 390—391 393 395
Square, NE      67 69 71
Square, new (in Algorithm ML)      341 344
Square, newleft (in Algorithm ML)      342 344 349 353
Square, newright (in Algorithm ML)      342—343 348—349 353
Square, overlapping      381 390 395
Square, regular (in Thue strings)      70
Square, split      381 390—391
Square, tandem      381 390—391 393—396
Square-free      61—62 72—75
Stable sort      128
Staircase (of covers)      364 366—369
State (of a computation)      202—204 295—320
State (of a computation), accepting      298—301 303 308 310—311 314
State (of a computation), active      317—320
State (of a computation), start      297—299 301—302 308
State (of a computation), vector      265 269 271
Stephen, Graham A.      ix
Stolarsky, Kenneth B.      85
Stoye, Jens      38 357 375
String      4—14
String, b-canonical      100—108
String, circular      see "Necklace"
String, coverable      54 56 59 360 379—380
String, empty      5—8
String, Fibonacci      see "Fibostring"
String, finite      7
String, infinite      4—6 9 61—87
String, initial      62 64 71 86—87
String, linear      4—14
String, p-canonical      94—100
String, Sturmian      85
String, text      42 47 49 187 193 195 199 205 209 212 233 265—267 269 279 284—285 297 300 302 304—305 307—309 312—313 315—318 323—324
String, Thue      51 62—75 77 93—94
Subsequence      45
Subsequence, longest common      see "LCS"
Substitution      43—45 50 240 242—244 269 274 287 289 291 317—318 320
Substitution, rule      see "Morphism"
Substring      8
Substring, coverable      54 56 360 379
Substring, dead (in cover algorithm)      364—369
Substring, live (in cover algorithm)      364—369
Substring, proper      8
Substring, repeating      see "Repeating substring"
Subword tree      see "Suffix tree"
Successor (in a string)      4—5 7—8
Suffix      9
Suffix tree      36—39 90 111 113—150 155—157 176—177 264 273 279 296 298 304 310 330—331 339—340 356—357 360 370—380
Suffix tree, linked      5
Suffix tree, traversal of      see "Fastscan" "Slowscan" "Smartscan"
Suffix, array      40 111 149—156 370—372 375—380
Suffix, function      116 126 138 141 143 145
Suffix, proper      9
Suffix, tree      see "Suffix tree"
Sun, Yu      24 102 105
Sunday, Daniel M.      209 212—219 231—232
Superstring      8
Superstring, proper      8
Swanson, Kurt      113
Syntax tree      see "Tree"
Szymanski, Thomas G.      250—256 264
Tail (of run)      56 82
Tail (of suffix)      115 118—119 138
Takeda, Masayuki      149
Tang, Yudong      370—380
Tarhio, Jorma      273
Tarjan, Robert Endre      135
1 2 3
blank
Ðåêëàìà
blank
blank
HR
@Mail.ru
       © Ýëåêòðîííàÿ áèáëèîòåêà ïîïå÷èòåëüñêîãî ñîâåòà ìåõìàòà ÌÃÓ, 2004-2024
Ýëåêòðîííàÿ áèáëèîòåêà ìåõìàòà ÌÃÓ | Valid HTML 4.01! | Valid CSS! Î ïðîåêòå