Nigel Horspool
Nigel Horspool

Tento algoritmus pro vyhledávání řetězců představil v roce 1980 Nigel Horspool (Kanada) a vznikl zjednodušením algoritmu Boyer-Moore (autor jej také původně pojmenoval SBM - Simplified Boyer-Moore). Za toto zjednodušení platí využitím většího množství paměti a v některých situacích i horším výkonem. V praktických aplikacích se vlastnosti obou algoritmů podobají.

Algoritmus je vhodné použít v situacích, kdy je abeceda v porovnání s typickou délkou vyhledávaného řetězce velká. To může být případ textových editorů, ve kterých se běžně pracuje s mezinárodními znakovými sadami a vyhledávají se jen krátká slova či jejich spojení.

Kroky algoritmu

Posunovací tabulka

Prvním krokem je vytvoření pomocné "posunovací" tabulky. Tabulka obsahuje záznam pro každý znak abecedy (např. 256 záznamů pro ASCII, 65536 záznamů pro šestnáctibitový Unicode) a její hodnota udává, o kolik znaků se může pozice v prohledávaném řetězci bezpečně posunout, nedojde-li ke shodě s vyhledávaným řetězcem. Indexem do tabulky je poslední znak vyhodnocované části prohledávaného řetězce.

Tabulka se vyplní podle následujících pravidel:

  • Pro znaky, které ve vyhledávaném řetězci nejsou, je možný posun o celou délku vyhledávaného řetězce (proto bude většina řádků obsahovat právě tuto hodnotu).
  • Pro znaky, které ve vyhledávaném řetězci jsou, se zjistí vzdálenost jejich posledního výskytu ve vyhledávaném řetězci od konce.

Pokud například vyhledáváme v dekadickém čísle posloupnost 01214, bude posunovací tabulka vypadat následovně:

Index znakuPosunVysvětlení
04číslo "0" je čtvrtý znak po posledním znaku řetězce, čteme-li jej zprava (4-1210)
11číslo "1" je první znak po posledním znaku řetězce, čteme-li jej zprava (4-1)
22číslo "2" je druhý znak po posledním znaku řetězce, čteme-li jej zprava (4-12)
35číslo "3" se ve vyhledávaném řetězci nevyskytuje
40číslo "4" je poslední znak řetězce
55číslo "5" se ve vyhledávaném řetězci nevyskytuje
65číslo "6" se ve vyhledávaném řetězci nevyskytuje
75číslo "7" se ve vyhledávaném řetězci nevyskytuje
85číslo "8" se ve vyhledávaném řetězci nevyskytuje
95číslo "9" se ve vyhledávaném řetězci nevyskytuje

Vyhledávání s tabulkou

Sestavená tabulka se potom využije pro posun pozice v hlavním cyklu algoritmu:

package search;

public class BoyerMooreHorspool {
    public static int find(final char[] haystack, final char[] needle) {
        final int[] jumpTable = createJumpTable(needle);
        int iHaystack = 0;
        while (haystack.length - iHaystack >= needle.length) {
            // start comparing haystack piece with the needle right-to-left
            int iNeedle = needle.length - 1;
            while (haystack[iHaystack + iNeedle] == needle[iNeedle]) {
                if (iNeedle == 0) {
                    // FOUND
                    return iHaystack;
                }
                iNeedle--;
            }
            // move position in haystack
            final int iHaystackForNeedleEnd = iHaystack + needle.length - 1;
            iHaystack += jumpTable[haystack[iHaystackForNeedleEnd]];
        }
        // NOT FOUND
        return -1;
    }

    /**
     * Creates jump table.
     * @param needle string to search for
     * @return array of jumps for each character of the needle
     */
    private static int[] createJumpTable(final char[] needle) {
        final int alphabetSize = Character.MAX_VALUE - Character.MIN_VALUE + 1;
        final int[] jumpTable = new int[alphabetSize];

        for (int iJumpTable = 0; iJumpTable < jumpTable.length; iJumpTable++) {
            // for characters not in needle
            jumpTable[iJumpTable] = needle.length;
        }

        for (int iNeedle = 0; iNeedle < needle.length; iNeedle++) {
            // for characters in needle
            final int iTableForNeedleCharacter = (int) needle[iNeedle];
            jumpTable[iTableForNeedleCharacter] = needle.length - 1 - iNeedle;
        }

        return jumpTable;
    }
}

Zdrojový kód Pokrytí testy

Složitost

Teoretická asymptotická složitost algoritmu je stejná jako u naivního algoritmu, a sice € O(m \cdot n) €, kde €m€ je délka vyhledávaného řetězce a €n€ délka řetězce, ve kterém vyhledávání probíhá. V běžných případech však složitost klesá až k lineární € O(n) €.

Reference