Tuning the Boyer-Moore-Horspool string searching algorithm

被引：0

作者：

Raita, Timo ^{[1
]}

机构：

[1] Univ of Turku, Turku, Finland

来源：

Software - Practice and Experience | 1992年 / 22卷 / 10期

关键词：

Codes (symbols) - Computer programming - Data processing - Data structures - Heuristic methods - Pattern recognition - Performance - Subroutines;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

Substring search is a common activity in computing. The fastest known search method is that of Boyer and Moore with the improvements introduced by Horspool. This paper presents a new implementation which takes advantage of the dependencies between the characters. The resulting code runs 25 per cent faster than the best currently-known routine.

引用

页码：879 / 884

共 50 条

[21] On obtaining the Boyer-Moore string-matching algorithm by partial evaluation
Danvy, Olivier
Rohde, Henning Korsholm
INFORMATION PROCESSING LETTERS, 2006, 99 (04) : 158 - 162
[22] TIGHT BOUNDS ON THE COMPLEXITY OF THE BOYER-MOORE STRING-MATCHING ALGORITHM
COLE, R
SIAM JOURNAL ON COMPUTING, 1994, 23 (05) : 1075 - 1091
[23] Searching BWT compressed text with the Boyer-Moore algorithm and binary search
Bell, T
Powell, M
Mukherjee, A
Adjeroh, D
DCC 2002: DATA COMPRESSION CONFERENCE, PROCEEDINGS, 2002, : 112 - 121
[24] FASTER STRING SEARCHES - BOYER-MOORE MAY BE THE ALGORITHM YOU NEED
MENICO, C
DR DOBBS JOURNAL, 1989, 14 (07): : 74 - 75
[25] APPROXIMATE BOYER-MOORE STRING MATCHING
TARHIO, J
UKKONEN, E
SIAM JOURNAL ON COMPUTING, 1993, 22 (02) : 243 - 260
[26] Left-to-right preprocessing computation for the Boyer-Moore string matching algorithm
Ibaraki Univ, Ibaraki, Japan
Comput J, 5 (413-416):
[27] IMPROVING THE WORST CASE RUNNING TIME OF THE BOYER-MOORE STRING MATCHING ALGORITHM
GALIL, Z
COMMUNICATIONS OF THE ACM, 1979, 22 (09) : 505 - 508
[28] A left-to-right preprocessing computation for the Boyer-Moore string matching algorithm
Takaoka, T
COMPUTER JOURNAL, 1996, 39 (05): : 413 - 416
[29] BOYER-MOORE APPROACH TO APPROXIMATE STRING MATCHING
TARHIO, J
UKKONEN, E
LECTURE NOTES IN COMPUTER SCIENCE, 1990, 447 : 348 - 359
[30] A VARIATION ON THE BOYER-MOORE ALGORITHM
LECROQ, T
THEORETICAL COMPUTER SCIENCE, 1992, 92 (01) : 119 - 144

← 1 2 3 4 5 →