Bojer-Mur-Horspolov algoritam

U Informatici, Boyer–Moore–Horspool algoritam or Horspool's algorithm je jedan algoritam za nalaženje podstringova u strings. It was published by Nigel Horspool in 1980.

To je pojednostavljena verzija Bojer–Murovog string search algoritma koji je povezan sa Knuth–Morris–Pratt algoritmom. Algortiam menja prostor ta vreme u cilju dobijanja složenost prosečnog slučaja of O(N) na slučajnom tekstu , iako on ima O(MN) unajgorem slučaju, gde je dužina paterna M , a dužina stringa koji se pretražuje N.

Primer primene

Evo jednog primera implementacije Bojer-Mur-HorspoLovog algoritma, napisan u C.

#include <string.h>
#include <limits.h>

/* Returns a pointer to the first occurrence of "needle"
 * within "haystack", or NULL if not found. Works like
 * memmem().
 */

/* Note: In this example needle is a C string. The ending
 * 0x00 will be cut off, so you could call this example with
 * boyermoore_horspool_memmem(haystack, hlen, "abc", sizeof("abc"))
 */
const unsigned char *
boyermoore_horspool_memmem(const unsigned char* haystack, size_t hlen,
                           const unsigned char* needle,   size_t nlen)
{
    size_t scan = 0;
    size_t bad_char_skip[UCHAR_MAX + 1]; /* Officially called:
                                          * bad character shift */

    /* Sanity checks on the parameters */
    if (nlen <= 0 || !haystack || !needle)
        return NULL;

    /* ---- Preprocess ---- */
    /* Initialize the table to default value */
    /* When a character is encountered that does not occur
     * in the needle, we can safely skip ahead for the whole
     * length of the needle.
     */
    for (scan = 0; scan <= UCHAR_MAX; scan = scan + 1)
        bad_char_skip[scan] = nlen;

    /* C arrays have the first byte at [0], therefore:
     * [nlen - 1] is the last byte of the array. */
    size_t last = nlen - 1;

    /* Then populate it with the analysis of the needle */
    for (scan = 0; scan < last; scan = scan + 1)
        bad_char_skip[needle[scan]] = last - scan;

    /* ---- Do the matching ---- */

    /* Search the haystack, while the needle can still be within it. */
    while (hlen >= nlen)
    {
        /* scan from the end of the needle */
        for (scan = last; haystack[scan] == needle[scan]; scan = scan - 1)
            if (scan == 0) /* If the first byte matches, we've found it. */
                return haystack;

        /* otherwise, we need to skip some bytes and start again.
           Note that here we are getting the skip value based on the last byte
           of needle, no matter where we didn't match. So if needle is: "abcd"
           then we are skipping based on 'd' and that value will be 4, and
           for "abcdd" we again skip on 'd' but the value will be only 1.
           The alternative of pretending that the mismatched character was
           the last character is slower in the normal case (E.g. finding
           "abcd" in "...azcd..." gives 4 by using 'd' but only
           4-2==2 using 'z'. */
        hlen     -= bad_char_skip[haystack[last]];
        haystack += bad_char_skip[haystack[last]];
    }

    return NULL;
}

Karakteristike

Algoritam se najbolje pokazuje sa dugačkim stringovima, kada dosledno pogađa karakter koji se ne podudara na ili blizu kraja psolednjeg bajta trenutne poyicije u plastu sena i psolednjeg bajta igle koji se više ne ponavljaju u celoj igli. Na primer 32 bajta needle se zavrsava sa "z" pretražuje kroz 255 bajtova sena slame koji nema 'z' bajt , za to će biti potrebno 224 ponavljanja.

Najbolji slučaj je isti kao za Boyer–Moore string search algoritam iuveliko O notaciji, iako konstantno iznad inicijalizacije i za svaku petlju je manje.

Ponašanje u najgorem slucaju se dešava kada je loš karakter koji prskačete konstantno nizak (sa donje granice od 1 bajta kretanja) i kada veliki deo igel odgovara plastu sena. Loš karakter preskačete samona parcijalnom pokdudaranju, kada se konačni karakter igle pojavljuje i u ostalim delovima igle, sa jednim bajtom kretanja dešava se kada je isti bajtu obe poslednje dve pozicije.

kanonski degenerisan slučaj sličan gornjem najboljem slučaju je igla za 'a' bajt praćena sa 31 'z' bajtova u plastu sena koji se sastoji od 255 'z' bajtova. Ovo ce uraditi 31 uspešno bajt poređenje, 1 bajt poređenje koje ne uspe, a zatim krenuti napred 1 bajt. Ovaj proces će se ponoviti223 puta (255 - 32), svodeći totalno poredjenje bajtova na 7,168 (32 * 224).

Najgori slučaj je znatno veći nego za Boyer–Moore string search algoritam, iako je jasno da je teško postići unormalnim slučajevima korišćenja. takođe je vredno napomenuti da je ovaj najgori slučaj, najgori slučaj i za naivne (but usual) memmem() algoritme, iako implementacija ima tendenciju da bude ynatno optimizovanan (i više je keš prijateljski).

Vidi još

• Boyer–Moore string search algorithm

Spoljašnje veze

• Description of the algorithm
• StringSearch – high-performance pattern matching algorithms in Java – Implementations of many String-Matching-Algorithms in Java (BNDM, Boyer-Moore-Horspool, Boyer-Moore-Horspool-Raita, Shift-Or)
• Boyer-Moore-Horspool implementation for Delphi - Non-visual components (TSearch and TFileSearch) which enable very fast data searches using the Boyer-Moore-Horspool search algorithm.
• C++ implementation