TUNING THE BOYER-MOORE-HORSPOOL STRING SEARCHING ALGORITHM

被引：47

作者：

RAITA, T

机构：

[1] Department of Computer Science, University of Turku, Turku, SF-20520

来源：

SOFTWARE-PRACTICE & EXPERIENCE | 1992年 / 22卷 / 10期

关键词：

DESIGN OF ALGORITHMS; STRING SEARCHING; PATTERN MATCHING;

D O I：

10.1002/spe.4380221006

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

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

页数：6

相关论文

共 10 条

[1] THE BOYER-MOORE-GALIL STRING SEARCHING STRATEGIES REVISITED [J].

APOSTOLICO, A ;

GIANCARLO, R .

SIAM JOURNAL ON COMPUTING, 1986, 15 (01) :98-105

[2]

Baeza-Yates R. A., 1989, SIGIR Forum, V23, P34, DOI 10.1145/74697.74700

[3] IMPROVED STRING SEARCHING [J].

BAEZAYATES, RA .

SOFTWARE-PRACTICE & EXPERIENCE, 1989, 19 (03) :257-271

[4] FAST STRING SEARCHING ALGORITHM [J].

BOYER, RS ;

MOORE, JS .

COMMUNICATIONS OF THE ACM, 1977, 20 (10) :762-772

[5] IMPROVING THE WORST CASE RUNNING TIME OF THE BOYER-MOORE STRING MATCHING ALGORITHM [J].

GALIL, Z .

COMMUNICATIONS OF THE ACM, 1979, 22 (09) :505-508

[6]

GUIASU S, 1977, INFORMATION THEORY A

[7] A NEW PROOF OF THE LINEARITY OF THE BOYER-MOORE STRING SEARCHING ALGORITHM [J].

GUIBAS, LJ ;

ODLYZKO, AM .

SIAM JOURNAL ON COMPUTING, 1980, 9 (04) :672-682

[8] PRACTICAL FAST SEARCHING IN STRINGS [J].

HORSPOOL, RN .

SOFTWARE-PRACTICE & EXPERIENCE, 1980, 10 (06) :501-506

[9] A CORRECT PREPROCESSING ALGORITHM FOR BOYER-MOORE STRING-SEARCHING [J].

RYTTER, W .

SIAM JOURNAL ON COMPUTING, 1980, 9 (03) :509-512

[10] ON THE EXPECTED SUBLINEARITY OF THE BOYER-MOORE ALGORITHM [J].

SCHABACK, R .

SIAM JOURNAL ON COMPUTING, 1988, 17 (04) :648-658