Raita algoritmus - Raita algorithm - Wikipedia

Tento článek má několik problémů. Prosím pomozte vylepši to nebo diskutovat o těchto otázkách na internetu diskusní stránka. (Zjistěte, jak a kdy tyto zprávy ze šablony odebrat) Téma tohoto článku nemusí splňovat požadavky Wikipedie obecný pokyn k notabilitě. Pomozte prosím určit notabilitu citováním spolehlivé sekundární zdroje to jsou nezávislý tématu a poskytnout jeho významné pokrytí nad rámec pouhé triviální zmínky. Pokud nelze určit významnost, je pravděpodobné, že článek bude sloučeny, přesměrovánnebo smazáno. Najít zdroje: "Raita algoritmus"  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Březen 2015) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

V počítačové vědě je Raita algoritmus je algoritmus prohledávání řetězců což zlepšuje výkon Algoritmus Boyer – Moore – Horspool. Tento algoritmus předzpracovává hledaný řetězec pro vzor, ​​který je podobný Algoritmus vyhledávání řetězců Boyer – Moore. Vyhledávací vzor konkrétního podřetězce v daném řetězci se liší od algoritmu Boyer – Moore – Horspool. Tento algoritmus publikoval Timo Raita v roce 1991.^[1]

Popis

Algoritmus Raita hledá vzor „P“ v daném textu „T“ porovnáním každého znaku vzoru v daném textu. Hledání proběhne následovně. Okno pro text „T“ je definováno jako délka „P“.

1. Nejprve se porovná poslední znak vzoru se znakem okna zcela vpravo.
2. Pokud existuje shoda, první znak vzoru se porovná se znakem nalevo od okna.
3. Pokud se znovu shodují, porovná se prostřední znak vzoru se středním znakem okna.

Pokud je vše v předběžné kontrole úspěšné, pak původní srovnání začíná od druhého znaku po předposlední. Pokud v libovolné fázi algoritmu existuje nesoulad, provede funkci posunutí špatného znaku, která byla vypočítána ve fázi předběžného zpracování. Funkce posunu chybných znaků je identická s funkcí navrženou v algoritmu Boyer – Moore – Horspool.^[1]

Moderní formulace podobné předběžné kontroly se nachází v std :: string :: find, lineární / kvadratický porovnávač řetězců, v libc ++ a libstdc ++. Za předpokladu dobře optimalizované verze memcmp„Nepřeskočení znaků v„ původním srovnání “má tendenci být efektivnější, protože je pravděpodobné, že vzor bude zarovnán.^[2]

C kód pro Raita algoritmus

#zahrnout <limits.h>#zahrnout <stddef.h>#define ALPHABET_SIZE (1 << CHAR_BITS) / * obvykle 256 * // * Předběžné zpracování: špatně shodná tabulka BMH. * /statický v souladu prázdnota preBmBc(char *pat, size_t lpat, ptrdiff_t bmBc[]) {  size_t i;  pro (i = 0; i < ALPHABET_SIZE; ++i)    bmBc[i] = lpat;  pro (i = 0; i < lpat - 1; ++i)    bmBc[pat[i]] = lpat - i - 1;}prázdnota RAITA(char *pat, size_t lpat, char *s, size_t n) {  ptrdiff_t bmBc[ALPHABET_SIZE];  / * Pouzdra pro rychlé hrany. * /  -li (lpat == 0 || lpat > n)    vrátit se;  -li (lpat == 1) {    char *match_ptr = s;    zatímco (match_ptr < s + n) {      match_ptr = memchr(match_ptr, pat[0], n - (match_ptr - s));      -li (match_ptr != NULA) {        VÝSTUP(match_ptr - s);        match_ptr++;      } jiný        vrátit se;    }  }  preBmBc(pat, lpat, bmBc);  / * Předběžné okno. * /  char prvníCh = pat[0];  char středníCh = pat[lpat / 2];  char lastCh = pat[lpat - 1];  / * Hledání * /  ptrdiff_t j = 0;  zatímco (j <= n - m) {    char C = s[j + lpat - 1];    / * To by mohlo poškodit lokalitu dat na dlouhých vzorcích. U těchto zvážit snížení     * počet předběžných testů nebo použití více seskupených indexů. * /    -li (lastCh == C && středníCh == s[j + lpat / 2] && prvníCh == s[j] &&        memcmp(&pat[1], &s[j+1], lpat - 2) == 0)      VÝSTUP(j);    j += bmBc[C];  }}

Příklad

Vzor: abddb

Text: abbaabaabddbabadbb

Fáze před zpracováním:

  a b d 4 3 1

 Pokus 1: abbaabaabddbabadbb .... b Posun o 4 (bmBc [a])

Porovnání posledního znaku vzoru s pravým znakem v okně. Je to nesoulad a posunutý o 4 podle hodnoty ve fázi předběžného zpracování.

 Pokus 2: abbaabaabddbabadbb A.d.B Posun o 3 (bmBc [b])

Zde se shodují poslední a první znak vzoru, ale prostřední znak je neshoda. Takže vzor se posune podle fáze předzpracování.

 Pokus 3: Abbaabaabddbabadbb ABDDB Posun o 3 (bmBc [b])

Našli jsme zde přesnou shodu, ale algoritmus pokračuje, dokud se nemůže posunout dále.

 Pokus 4: abbaabaABDDBabadbb .... b Posun o 4 (bmBc [a])

V této fázi se musíme posunout o 4 a nemůžeme posunout vzorec o 4. Takže algoritmus končí. Velká písmena jsou přesnou shodou vzoru v textu.

Složitost

1. Fáze předběžného zpracování trvá O (m), kde „m“ je délka vzoru „P“.
2. Fáze hledání vyžaduje časovou složitost O (mn), kde „n“ je délka textu „T“.

Viz také

• Algoritmus vyhledávání řetězců Boyer – Moore
• Algoritmus Boyer – Moore – Horspool

Reference

externí odkazy

• Animace a popis appletu pro Raita Algorithm