Academic
Publications
Fast String Searching

Fast String Searching,10.1002/spe.4380211105,Software - Practice and Experience,Andrew Hume,Daniel Sunday

Fast String Searching   (Citations: 74)
BibTex | RIS | RefWorks Download
SUMMARY Since the Boyer-Moore algorithm was described in 1977, it has been the standard benchmark for the practical string search literature. Yet this yardstick compares badly with current practice. We describe two algorithms that perform 47% fewer comparisons and are about 4.5 times faster across a wide range of architectures and compilers. These new variants are members of a family of algorithms based on the skip loop structure of the pre- ferred, but often neglected, fast form of Boyer-Moore. We present a taxonomy for this family, and de- scribe a toolkit of components that can be used to design an algorithm most appropriate for a given set of requirements.
Journal: Software - Practice and Experience - SPE , vol. 21, no. 11, pp. 221-234, 1991
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...All the algorithms were tested in the testing framework of Hume and Sunday [7]...

    Branislav Durianet al. Bit-Parallel Search Algorithms for Long Patterns

    • ...String matching algorithms can be divided into three categories: the prefix based matching(KMP [1] ,shift-and/or etc), the suffix based matching(BM [2] ,Sunday [3] etc), and the factor matching(BNDM [4] ,BOM [4] etc) (n is the length of the...
    • ...Scanning suffix of the pattern, it has the best of the best time complexity of the algorithms [3] ...

    Jun-bo Wanget al. A Fast Single Pattern Matching Algorithm Based on the Bit-Parallel

    • ...At the implementation level, the test starting the outer while loop can be removed by placing a copy of the pattern as a stopper in the end of the text [11]...
    • ...All the algorithms were tested in a testing framework of Hume and Sunday [11]...
    • ...The English text is the beginning of the KJV bible. The DNA text is from Hume and Sunday [11]...
    • ...BM is the implementation fast.rev.d12 of Boyer–Moore algorithm by Hume and Sunday [11] which follows original suggestions of Boyer and Moore [2] about maximal efficiency...

    Branislav Durianet al. Tuning BNDM with q-Grams

    • ...More effective implementations of the Fast-Search and Forward-Fast-Search algorithm are obtained along the same lines of the Tuned-Boyer-Moore algorithm [HS91] by making use of a fast-loop, using a technique described in Section 4.1 and shown in Figure 3(A)...
    • ...The first idea consists in extending the BOM algorithm with a fast-loop over oracle transitions, along the same lines of the Tuned-Boyer-Moore algorithm [HS91]...
    • ...The fast-loop we are using here has first introduced in the Tuned-Boyer-Moore algorithm [HS91] and later largely used in almost all variations of the Boyer-Moore algorithm...

    Simone Faroet al. Efficient Variants of the Backward-Oracle-Matching Algorithm

    • ...The reference algorithms are Tuned BM (3 unrolled shifts [10]), SBNDM2 [11], NEW [12] for 3 characters qgrams and hash (NEW3), BOM, EBOM, FBOM, the algorithm with EBOM only removing the unnecessary branches (REBOM) and the algorithm with FBOM only removing the unnecessary branches (RFBOM)...

    Fan Hongboet al. Fast Variants of the Backward-Oracle-Marching Algorithm

Sort by: