Exact String Matching Algorithms
| 2002
|
|---|
| Algorithms | Total
| 1997
| 1998
| 1999
| 2000
| 2001
| Jan
| Feb
| Mar
| Apr
| May
| Jun
| Jul
| Aug
|
|---|
| Boyer & Moore | 26933 | 461 | 1801 | 2980 | 2284 | 9796 | 1092 | 971 | 1648 | 1328 | 1457 | 1277 | 1083 | 755
|
|---|
| Brute Force | 20648 | 321 | 1142 | 3072 | 1653 | 6435 | 801 | 704 | 1150 | 1122 | 1080 | 1120 | 1110 | 938
|
|---|
| Knuth, Morris & Pratt | 19465 | 330 | 1564 | 2925 | 2007 | 6754 | 645 | 537 | 1024 | 919 | 947 | 736 | 608 | 469
|
|---|
| Karp & Rabin | 12247 | 207 | 659 | 1669 | 1407 | 4245 | 457 | 473 | 726 | 623 | 545 | 472 | 422 | 342
|
|---|
| Automaton | 9533 | 180 | 527 | 1247 | 1027 | 3430 | 371 | 351 | 453 | 456 | 411 | 405 | 327 | 348
|
|---|
| Quick Search | 9375 | 183 | 542 | 1267 | 842 | 3322 | 352 | 381 | 455 | 433 | 415 | 388 | 415 | 380
|
|---|
| Morris & Pratt | 8179 | 140 | 571 | 1123 | 881 | 2901 | 316 | 274 | 446 | 364 | 335 | 286 | 290 | 252
|
|---|
| Shift Or | 7462 | 148 | 428 | 989 | 812 | 2654 | 306 | 297 | 373 | 349 | 299 | 296 | 254 | 257
|
|---|
| Turbo Boyer Moore | 6979 | 156 | 585 | 1029 | 682 | 2436 | 259 | 229 | 319 | 269 | 284 | 279 | 250 | 202
|
|---|
| Horspool | 6145 | 79 | 384 | 794 | 618 | 2131 | 291 | 241 | 301 | 335 | 260 | 276 | 235 | 200
|
|---|
| Tuned Boyer Moore | 5731 | | | 334 | 638 | 2549 | 263 | 243 | 366 | 293 | 295 | 296 | 240 | 214
|
|---|
| Not So Naive | 5190 | 98 | 325 | 723 | 568 | 1845 | 219 | 171 | 248 | 246 | 232 | 195 | 164 | 156
|
|---|
| Simon | 5194 | 89 | 328 | 736 | 562 | 1844 | 217 | 189 | 235 | 234 | 219 | 203 | 166 | 162
|
|---|
| KmpSkip | 4970 | 0 | 140 | 551 | 555 | 2068 | 238 | 189 | 253 | 259 | 212 | 175 | 181 | 149
|
|---|
| AlphaSkip | 4504 | 0 | 177 | 653 | 512 | 1622 | 202 | 208 | 263 | 234 | 194 | 159 | 147 | 133
|
|---|
| Skip | 4204 | 0 | 169 | 649 | 398 | 1474 | 233 | 189 | 212 | 194 | 179 | 164 | 175 | 168
|
|---|
| SMOA | 4131 | 85 | 335 | 609 | 442 | 1408 | 150 | 159 | 211 | 170 | 157 | 149 | 128 | 128
|
|---|
| Smith | 3747 | 56 | 235 | 479 | 375 | 1375 | 165 | 162 | 189 | 174 | 162 | 134 | 131 | 110
|
|---|
| Optimal Mismatch | 3651 | 80 | 261 | 603 | 437 | 1241 | 125 | 122 | 178 | 151 | 121 | 118 | 113 | 101
|
|---|
| Colussi | 3636 | 79 | 234 | 519 | 412 | 1264 | 146 | 128 | 158 | 161 | 154 | 135 | 120 | 126
|
|---|
| Two Way | 3613 | 67 | 211 | 502 | 387 | 1316 | 154 | 138 | 169 | 159 | 138 | 145 | 124 | 103
|
|---|
| Zhu & Takaoka | 3603 | 54 | 229 | 469 | 370 | 1327 | 163 | 141 | 160 | 155 | 146 | 159 | 117 | 113
|
|---|
| Apostolico & Giancarlo | 3530 | 73 | 239 | 461 | 421 | 1229 | 129 | 96 | 154 | 155 | 160 | 154 | 155 | 104
|
|---|
| Reverse Factor | 3515 | 70 | 228 | 452 | 345 | 1208 | 158 | 133 | 178 | 164 | 165 | 141 | 138 | 135
|
|---|
| Maximal Shift | 3448 | 89 | 275 | 448 | 384 | 1177 | 156 | 129 | 164 | 147 | 149 | 116 | 115 | 99
|
|---|
| Apostolico & Crochemore | 3400 | 61 | 197 | 481 | 401 | 1178 | 132 | 102 | 205 | 150 | 139 | 132 | 118 | 104
|
|---|
| Turbo Reverse Factor | 3203 | 54 | 210 | 454 | 384 | 1117 | 135 | 109 | 159 | 128 | 121 | 120 | 98 | 114
|
|---|
| Galil & Giancarlo | 3108 | 69 | 217 | 448 | 381 | 1070 | 129 | 102 | 142 | 130 | 115 | 116 | 93 | 96
|
|---|
| Raita | 3067 | 60 | 193 | 452 | 337 | 1080 | 121 | 101 | 143 | 151 | 117 | 128 | 82 | 102
|
|---|
| Reverse Colussi | 2968 | 58 | 201 | 404 | 329 | 1065 | 109 | 88 | 132 | 121 | 133 | 123 | 108 | 97
|
|---|
| Backward Oracle Matching | 2742 | | | | 411 | 1230 | 134 | 135 | 151 | 172 | 153 | 134 | 115 | 107
|
|---|
| Galil & Seiferas | 2667 | 41 | 170 | 379 | 319 | 906 | 102 | 100 | 134 | 117 | 101 | 112 | 102 | 84
|
|---|
| Berry & Ravindran | 2190 | | | | 306 | 974 | 121 | 107 | 134 | 137 | 108 | 123 | 87 | 93
|
|---|
| Forward Dawg Matching | 1558 | | | | | 575 | 138 | 97 | 135 | 135 | 136 | 122 | 114 | 106
|
|---|
| Backward Nondeterministic Dawg Matching | 1327 | | | | | 484 | 118 | 96 | 120 | 112 | 105 | 110 | 94 | 88
|
|---|
| Total | 215853 | 3388 | 12777 | 27891 | 21887 | 76730 | 8847 | 7892 | 11488 | 10447 | 9944 | 9198 | 8219 | 7135
|
|---|
page d'accueil
home page
Thierry Lecroq