Algoritmus vyhledávání řetězců Boyer – Moore - Boyer–Moore string-search algorithm
Třída | Hledání řetězců |
---|---|
Datová struktura | Tětiva |
Nejhorší případ výkon | Θ (m) předzpracování + O (mn) shoda[poznámka 1] |
Nejlepší případ výkon | Θ (m) předzpracování + Ω (n / m) shoda |
Nejhorší případ složitost prostoru | Θ (k)[poznámka 2] |
v počítačová věda, Algoritmus vyhledávání řetězců Boyer – Moore je efektivní algoritmus prohledávání řetězců to je standardní měřítko pro praktickou literaturu pro vyhledávání řetězců.[1] Byl vyvinut společností Robert S. Boyer a J Strother Moore v roce 1977.[2] Původní práce obsahovala statické tabulky pro výpočet posunů vzoru bez vysvětlení, jak je vyrobit. Algoritmus pro výrobu tabulek byl publikován v návazné práci; tento dokument obsahoval chyby, které byly později opraveny Wojciech Rytter v roce 1980.[3][4] The algoritmus preprocesy the tětiva hledán (vzor), ale ne hledaný řetězec (text). Je tedy vhodný pro aplikace, ve kterých je vzor mnohem kratší než text nebo kde přetrvává při více vyhledáváních. Algoritmus Boyer – Moore využívá informace shromážděné během kroku předzpracování k přeskočení částí textu, což má za následek nižší konstantní faktor než mnoho jiných algoritmů pro vyhledávání řetězců. Obecně platí, že algoritmus běží rychleji, jak se zvyšuje délka vzoru. Klíčovými vlastnostmi algoritmu je shoda na konci vzoru, nikoli na hlavě, a přeskakování po textu ve skokech více znaků, než aby se prohledával každý jednotlivý znak v textu.
Definice
A | N | P | A | N | M | A | N | - |
P | A | N | - | - | - | - | - | - |
- | P | A | N | - | - | - | - | - |
- | - | P | A | N | - | - | - | - |
- | - | - | P | A | N | - | - | - |
- | - | - | - | P | A | N | - | - |
- | - | - | - | - | P | A | N | - |
- S[i] označuje znak v indexu i řetězce S, počítáno od 1.
- S[i..j] označuje podřetězec řetězce S počínaje indexem i a končí v j, včetně.
- A předpona z S je podřetězec S[1..i] pro některé i v rozsahu [1, n], kde n je délka S.
- A přípona z S je podřetězec S[i..n] pro některé i v rozsahu [1, n], kde n je délka S.
- Řetězec, který se má hledat, se nazývá vzor a je označen P. Jeho délka je n.
- Hledaný řetězec se nazývá text a je označen T. Jeho délka je m.
- An zarovnání z P na T je index k v T tak, že poslední znak P je zarovnán s indexem k z T.
- A zápas nebo výskyt z P nastane při vyrovnání, pokud P je ekvivalentní k T[(k-n+1)..k].
Popis
Algoritmus Boyer – Moore hledá výskyt P v T provedením explicitního srovnání znaků v různých zarovnáních. Místo a vyhledávání hrubou silou všech zarovnání (kterých je ), Boyer – Moore využívá informace získané předzpracováním P přeskočit co nejvíce zarovnání.
Před zavedením tohoto algoritmu bylo obvyklým způsobem hledání v textu zkoumání každého znaku textu, zda neobsahuje první znak vzoru. Jakmile to bylo nalezeno, následné znaky textu by byly porovnány se znaky vzoru. Pokud nedojde k žádné shodě, bude text znovu zkontrolován znak po znaku ve snaze najít shodu. Je tedy třeba prozkoumat téměř každý znak v textu.
Klíčovým poznatkem v tomto algoritmu je, že pokud je konec vzoru srovnáván s textem, je možné provést skoky podél textu, spíše než kontrolovat každý znak textu. Důvod, proč to funguje, je ten, že při seřazení vzoru proti textu je poslední znak vzoru porovnán se znakem v textu. Pokud se znaky neshodují, není třeba pokračovat v prohledávání textu. Pokud znak v textu neodpovídá žádnému ze znaků ve vzoru, je umístěn další znak v textu ke kontrole n znaky dále podél textu, kde n je délka vzoru. Pokud je to znak v textu je ve vzoru se provede částečné posunutí vzoru podél textu, aby se seřadilo podél shodného znaku, a postup se opakuje. Přeskakování textu, aby bylo možné provádět srovnání, spíše než kontrola každého znaku v textu, snižuje počet srovnání, která je třeba provést, což je klíčem k účinnosti algoritmu.
Formálněji začíná algoritmus zarovnáním , takže začátek P je zarovnán se začátkem T. Znaky v P a T jsou poté porovnány počínaje indexem n v P a k v T, pohybující se dozadu. Řetězce se shodují od konce roku P na začátek P. Porovnání pokračují až do začátku roku 2006 P je dosaženo (což znamená, že existuje shoda) nebo dojde k neshodě, při které je zarovnání posunuto dopředu (doprava) podle maximální hodnoty povolené řadou pravidel. Porovnání se provádí znovu při novém zarovnání a proces se opakuje, dokud se zarovnání neposune za konec T, což znamená, že již nebudou nalezeny žádné další shody.
Pravidla posunu jsou implementována jako vyhledávání tabulek v konstantním čase pomocí tabulek generovaných během předzpracování P.
Pravidla směny
Posun se vypočítá použitím dvou pravidel: pravidla špatného znaku a pravidla dobré přípony. Skutečné posunutí posunu je maximum posunů vypočítaných těmito pravidly.
Pravidlo špatného charakteru
Popis
- | - | - | - | X | - | - | K. | - | - | - |
A | N | P | A | N | M | A | N | A | M | - |
- | N | N | A | A | M | A | N | - | - | - |
- | - | - | N | N | A | A | M | A | N | - |
Pravidlo špatného znaku považuje postavu za T kdy selhal srovnávací proces (za předpokladu, že k takovému selhání došlo). Další výskyt tohoto znaku vlevo v P je nalezen a posun, který uvádí tento výskyt do souladu s neshodným výskytem v T je navrženo. Pokud se znak neodpovídá nalevo v P, je navržen posun, který pohybuje celou P za bodem nesouladu.
Předběžné zpracování
Metody se liší podle přesného tvaru, který by měla mít tabulka pro pravidlo špatného znaku, ale jednoduché řešení pro vyhledávání v konstantním čase je následující: vytvořte 2D tabulku, která je indexována nejprve indexem znaku C v abecedě a za sekundu indexem i ve vzoru. Toto vyhledávání vrátí výskyt C v P s dalším nejvyšším indexem nebo -1, pokud takový výskyt neexistuje. Navrhovaný posun poté bude , s čas vyhledávání a prostor, za předpokladu konečné abecedy délky k.
Níže uvedené implementace C a Java mají a složitost prostoru (make_delta1, makeCharTable). To je stejné jako původní delta1 a Tabulka špatných znaků BMH. Tato tabulka mapuje postavu na pozici posunout o , přičemž poslední instance - nejmenší částka posunu - má přednost. Všechny nepoužívané znaky jsou nastaveny jako jako ověřovací hodnota.
Pravidlo dobré přípony
Popis
- | - | - | - | X | - | - | K. | - | - | - | - | - |
M | A | N | P | A | N | A | M | A | N | A | P | - |
A | N | A | M | P | N | A | M | - | - | - | - | - |
- | - | - | - | A | N | A | M | P | N | A | M | - |
Pravidlo dobré přípony je v koncepci i implementaci výrazně složitější než pravidlo špatného charakteru. Stejně jako pravidlo špatného znaku také využívá algoritmickou vlastnost srovnání začínajícího na konci vzoru a pokračujícího na začátek vzoru. Lze to popsat takto:[5]
Předpokládejme pro dané zarovnání P a T, podřetězec t z T odpovídá příponě P, ale při příštím srovnání vlevo dojde k nesouladu. Pak najděte kopii zcela vpravo, pokud existuje t ' z t v P takhle t ' není přípona P a znak nalevo od t ' v P se liší od znaku nalevo od t v P. Posun P doprava, takže podřetězec t ' v P zarovná s podřetězcem t v T. Li t ' neexistuje, pak posuňte levý konec P za levým koncem t v T o nejmenší částku tak, aby předpona posunutého vzoru odpovídala příponě t v T. Pokud takové řazení není možné, pak řazení P podle n místa vpravo. Pokud je výskyt P je nalezen, pak posuňte P o nejmenší částku, aby a správně předpona posunuté P odpovídá příponě výskytu P v T. Pokud takové řazení není možné, pak řazení P podle n místa, to znamená směna P minulost t.
Předběžné zpracování
Pravidlo dobré přípony vyžaduje dvě tabulky: jednu pro použití v obecném případě a druhou pro použití, když buď obecný případ nevrátí žádný smysluplný výsledek, nebo dojde ke shodě. Tyto tabulky budou označeny L a H resp. Jejich definice jsou následující:[5]
Pro každého i, je největší pozice menší než n takový ten řetězec odpovídá příponě a takový, že znak před touto příponou se nerovná . je definována jako nula, pokud neexistuje žádná poloha splňující podmínku.
Nechat označuje délku největší přípony to je také předpona P, pokud existuje. Pokud žádný neexistuje, nechte být nula.
Obě tyto tabulky jsou konstruovatelné v čas a použití prostor. Posun zarovnání pro index i v P darováno nebo . H by měl být použit pouze v případě, že je nula nebo byla nalezena shoda.
Galilovo pravidlo
Byla navržena jednoduchá, ale důležitá optimalizace Boyer – Moore Galil v roce 1979.[6]Na rozdíl od řazení se Galilovo pravidlo zabývá urychlením skutečných srovnání provedených při každém zarovnání přeskočením částí, o nichž je známo, že se shodují. Předpokládejme, že při zarovnání k1, P je ve srovnání s T až k charakteru C z T. Pak pokud P je přesunuta do k2 tak, aby jeho levý konec byl mezi C a k1, v další srovnávací fázi předpona P musí odpovídat podřetězci T[(k2 - n)..k1]. Pokud se tedy srovnání dostanou do polohy k1 z T, výskyt P lze zaznamenat bez výslovného porovnání minulosti k1. Kromě zvýšení efektivity Boyer-Moore je v nejhorším případě vyžadováno Galilovo pravidlo pro prokázání provedení lineárního času.
Galilovo pravidlo v původní verzi je účinné pouze pro verze, které produkují více shod. Aktualizuje rozsah podřetězců pouze na C = 0, tj. celý zápas. Zobecněná verze pro řešení dílčích dávek byla v roce 1985 uvedena jako Algoritmus Apostolico – Giancarlo.[7]
Výkon
Algoritmus Boyer – Moore uvedený v původním článku má nejhorší dobu běhu pouze pokud vzor funguje ne se objeví v textu. To bylo poprvé prokázáno Knuth, Morris, a Pratt v roce 1977,[8]následován Guibas a Odlyzko v roce 1980[9] s horní mezí 5n v nejhorším případě srovnání. Richard Cole poskytl důkaz s horní mezí 3n srovnání v nejhorším případě v roce 1991.[10]
Když vzor dělá vyskytují se v textu, doba běhu původního algoritmu je v nejhorším případě. Je to snadno vidět, když se vzor i text skládají pouze ze stejného opakovaného znaku. Zahrnutí však Galilovo pravidlo má za následek lineární běh ve všech případech.[6][10]
Implementace
Různé implementace existují v různých programovacích jazycích. v C ++ je také součástí standardní knihovny od C ++ 17 Zvýšit poskytuje obecné vyhledávání Boyer – Moore provádění v rámci Algoritmus knihovna. v Go (programovací jazyk) existuje implementace v hledat. jít. D (programovací jazyk) používá a BoyerMooreFinder pro shodu na základě predikátů v rámci rozsahů jako součást běhové knihovny Phobos.
Algoritmus Boyer – Moore se také používá v GNU je grep.[11]
Níže uvádíme několik jednoduchých implementací.
z psaní na stroji import *# Tato verze je citlivá na anglickou abecedu v ASCII pro porovnávání malých a velkých písmen.# Chcete-li tuto funkci odebrat, definujte alphabet_index jako ord (c) a nahraďte instance „26“# s „256“ nebo libovolným maximálním požadovaným bodem kódu. U Unicode se možná budete chtít shodovat v UTF-8# bajtů místo vytváření tabulky velikosti 0x10FFFF.ALPHABET_SIZE = 26def alphabet_index(C: str) -> int: "" "Vrátit index daného znaku v anglické abecedě, počítaný od 0." "" val = ord(C.dolní()) - ord("A") tvrdit val >= 0 a val < ALPHABET_SIZE vrátit se valdef match_length(S: str, idx1: int, idx2: int) -> int: "" "Vrátí délku shody podřetězců S začínajících na idx1 a idx2." "" -li idx1 == idx2: vrátit se len(S) - idx1 match_count = 0 zatímco idx1 < len(S) a idx2 < len(S) a S[idx1] == S[idx2]: match_count += 1 idx1 += 1 idx2 += 1 vrátit se match_countdef základní_preproces(S: str) -> Seznam[int]: "" "Return Z, základní předběžné zpracování S. Z [i] je délka podřetězce začínající na i, která je také předponou S. Toto předběžné zpracování se provádí v čase O (n), kde n je délka S. """ -li len(S) == 0: # Zpracovává případ prázdného řetězce vrátit se [] -li len(S) == 1: # Zpracovává případ jednoznakového řetězce vrátit se [1] z = [0 pro X v S] z[0] = len(S) z[1] = match_length(S, 0, 1) pro i v rozsah(2, 1 + z[1]): # Optimalizace z cvičení 1-5 z[i] = z[1] - i + 1 # Definuje dolní a horní mez z-boxu l = 0 r = 0 pro i v rozsah(2 + z[1], len(S)): -li i <= r: # i spadá do existujícího z-boxu k = i - l b = z[k] A = r - i + 1 -li b < A: # b končí v existujícím z-boxu z[i] = b jiný: # b končí na nebo po konci z-boxu, musíme udělat explicitní shodu napravo od z-boxu z[i] = A + match_length(S, A, r + 1) l = i r = i + z[i] - 1 jiný: # i se nenachází v existujícím z-boxu z[i] = match_length(S, 0, i) -li z[i] > 0: l = i r = i + z[i] - 1 vrátit se zdef bad_character_table(S: str) -> Seznam[Seznam[int]]: """ Generuje R pro S, což je pole indexované polohou nějakého znaku c v Anglická abeceda. Na tomto indexu v R je pole délky | S | +1, které pro každou specifikuje index i v S (plus index za S) další umístění znaku c, na které se setkal, když procházející S zprava doleva počínaje i. Používá se pro vyhledávání v konstantním čase pro pravidlo špatného znaku v algoritmu vyhledávání řetězců Boyer-Moore, i když má mnohem větší velikost než řešení s nekonstantním časem. """ -li len(S) == 0: vrátit se [[] pro A v rozsah(ALPHABET_SIZE)] R = [[-1] pro A v rozsah(ALPHABET_SIZE)] alfa = [-1 pro A v rozsah(ALPHABET_SIZE)] pro i, C v vyjmenovat(S): alfa[alphabet_index(C)] = i pro j, A v vyjmenovat(alfa): R[j].připojit(A) vrátit se Rdef good_suffix_table(S: str) -> Seznam[int]: """ Generuje L pro S, pole používané při implementaci pravidla silné dobré přípony. L [i] = k, největší pozice v S taková, že S [i:] (přípona S začínající na i) odpovídá přípona S [: k] (podřetězec v S končící na k). Při použití v Boyer-Moore dává L částku posunout P relativně k T tak, aby nebyly přeskočeny žádné instance P v T a přípona P [: L [i]] odpovídá podřetězci T odpovídajícímu příponou P v předchozím pokusu o shodu. Konkrétně, pokud k neshodě došlo v poloze i-1 v P, je dána velikost posunu rovnicí len (P) - L [i]. V případě, že L [i] = -1, použije se tabulka s úplným posunem. Protože záleží pouze na správných příponách, L [0] = -1. """ L = [-1 pro C v S] N = základní_preproces(S[::-1]) # S [:: - 1] obrátí S N.zvrátit() pro j v rozsah(0, len(S) - 1): i = len(S) - N[j] -li i != len(S): L[i] = j vrátit se Ldef full_shift_table(S: str) -> Seznam[int]: """ Generuje F pro S, pole použité ve zvláštním případě pravidla dobré přípony v Boyer-Moore algoritmus vyhledávání řetězců. F [i] je délka nejdelší přípony S [i:], která je také a předpona S. V případech, kdy se používá, velikost posunu vzoru P vzhledem k text T je len (P) - F [i] pro nesoulad vyskytující se na i-1. """ F = [0 pro C v S] Z = základní_preproces(S) nejdelší = 0 pro i, zv v vyjmenovat(obráceně(Z)): nejdelší = max(zv, nejdelší) -li zv == i + 1 jiný nejdelší F[-i - 1] = nejdelší vrátit se Fdef string_search(P, T) -> Seznam[int]: """ Implementace algoritmu vyhledávání řetězců Boyer-Moore. Toto najde všechny výskyty P v T a zahrnuje mnoho způsobů předzpracování vzoru k určení optima částka posune řetězec a přeskočí srovnání. V praxi běží v O (m) (a dokonce sublinear) čas, kde m je délka T. Tato implementace provádí malá a velká písmena vyhledávání podle abecedních znaků ASCII, mezery nejsou zahrnuty. """ -li len(P) == 0 nebo len(T) == 0 nebo len(T) < len(P): vrátit se [] zápasy = [] # Předzpracování R = bad_character_table(P) L = good_suffix_table(P) F = full_shift_table(P) k = len(P) - 1 # Představuje zarovnání konce P vzhledem k T předchozí_k = -1 # Představuje zarovnání v předchozí fázi (Galilovo pravidlo) zatímco k < len(T): i = len(P) - 1 # Znak k porovnání v P h = k # Znak k porovnání v T zatímco i >= 0 a h > předchozí_k a P[i] == T[h]: # Zápasy začínající od konce P i -= 1 h -= 1 -li i == -1 nebo h == předchozí_k: # Byla nalezena shoda (Galilovo pravidlo) zápasy.připojit(k - len(P) + 1) k += len(P) - F[1] -li len(P) > 1 jiný 1 jiný: # Žádná shoda, posun o max. Špatný charakter a pravidla dobrých přípon char_shift = i - R[alphabet_index(T[h])][i] -li i + 1 == len(P): # Neshoda se stala na první pokus suffix_shift = 1 elif L[i + 1] == -1: # Odpovídající přípona se nikde v P neobjeví suffix_shift = len(P) - F[i + 1] jiný: # Odpovídající přípona se objeví v P suffix_shift = len(P) - 1 - L[i + 1] posun = max(char_shift, suffix_shift) předchozí_k = k -li posun >= i + 1 jiný předchozí_k # Galilovo pravidlo k += posun vrátit se zápasy
#zahrnout <stdint.h>#zahrnout <stddef.h>#zahrnout <stdbool.h>#zahrnout <stdlib.h>#define ALPHABET_LEN 256#define max (a, b) ((a // PRAVIDLO ŠPATNÉHO CHARAKTERU.// tabulka delta1: delta1 [c] obsahuje vzdálenost mezi poslední// znak patu a nejpravější výskyt c v pat.//// Pokud se c v patu nevyskytuje, pak delta1 [c] = patlen.// Pokud je c na řetězci [i] a c! = Pat [patlen-1], můžeme bezpečně posunout i// over by delta1 [c], což je minimální vzdálenost potřebná k posunu// pat dopředu, aby se řetězec [i] seřadil s nějakým znakem v pat.// c == pat [patlen-1] vrácení nuly je pouze problém BMH, který// nemá delta2. BMH v takovém případě činí hodnotu patlenem.// Sledujeme tuto volbu namísto původní 0, protože přeskakuje// více. (správnost?)//// Tento algoritmus běží v alphabet_len + patlen time.prázdnota make_delta1(ptrdiff_t *delta1, uint8_t *pat, size_t patlen) { pro (int i=0; i < ALPHABET_LEN; i++) { delta1[i] = patlen; } pro (int i=0; i < patlen-2; i++) { delta1[pat[i]] = patlen-1 - i; }}// true, pokud je přípona slova začínajícího slovem [pos] předponou// slovabool is_prefix(uint8_t *slovo, size_t Wordlen, ptrdiff_t poz) { int sufixlen = Wordlen - poz; // zde také můžete použít funkci knihovny strncmp () // vrátit se ! strncmp (slovo, & slovo [pos], přípona); pro (int i = 0; i < sufixlen; i++) { -li (slovo[i] != slovo[poz+i]) { vrátit se Nepravdivé; } } vrátit se skutečný;}// délka nejdelší přípony slova končící na slovo [pos].// přípona_délka ("dddbcabc", 8, 4) = 2size_t přípona_délka(uint8_t *slovo, size_t Wordlen, ptrdiff_t poz) { size_t i; // zvýší délku přípony i na první neshodu nebo začátek // slova pro (i = 0; (slovo[poz-i] == slovo[Wordlen-1-i]) && (i < poz); i++); vrátit se i;}// PRAVIDLO DOBRÉ DOPLŇKY.// tabulka delta2: vzhledem k nesouladu v pat [pos] chceme zarovnat// s další možnou úplnou shodou by mohlo být založeno na tom, co my// vědět o pat [pos + 1] to pat [patlen-1].//// V případě 1:// pat [pos + 1] to pat [patlen-1] se jinde v pat nevyskytuje,// další věrohodná shoda začíná v neshodě nebo po ní.// Pokud v podřetězci pat [pos + 1 .. patlen-1] leží předpona// pat, je zde další věrohodná shoda (pokud jich je více// předpony v podřetězci, vyberte nejdelší). Jinak by// další věrohodná shoda začíná za znakem zarovnaným s// pat [patlen-1].//// V případě 2:// pat [pos + 1] to pat [patlen-1] se vyskytuje jinde v pat. The// neshoda nám říká, že se nedíváme na konec zápasu.// Můžeme se však dívat do středu zápasu.//// První smyčka, která se stará o případ 1, je obdobou// tabulka KMP, upravená pro „zpětné“ pořadí skenování s// další omezení, které podřetězce považuje za// potenciální předpony jsou všechny přípony. V nejhorším případě// pat se skládá ze stejného písmene opakovaného, takže každá přípona je// předpona. Tato smyčka sama o sobě nestačí, nicméně:// Předpokládejme, že pat je „ABYXCDBYX“ a text je „..... ABYXCDEYX“.// Porovnáme X, Y a najdeme B! = E. Neexistuje žádná předpona pat// v příponě „YX“, takže první smyčka nám říká, abychom přeskočili vpřed// o 9 znaků.// Ačkoli je povrchně podobný tabulce KMP, tabulce KMP// spoléhá na informace o začátku částečné shody// že algoritmus BM nemá.//// Druhá smyčka řeší případ 2. Protože přípona_délka nemusí být// jedinečný, chceme vzít minimální hodnotu, která nám to řekne// jak daleko je nejbližší potenciální shoda.prázdnota make_delta2(ptrdiff_t *delta2, uint8_t *pat, size_t patlen) { ssize_t p; size_t last_prefix_index = patlen-1; // první smyčka pro (p=patlen-1; p>=0; p--) { -li (is_prefix(pat, patlen, p+1)) { last_prefix_index = p+1; } delta2[p] = last_prefix_index + (patlen-1 - p); } // druhá smyčka pro (p=0; p < patlen-1; p++) { size_t jen = přípona_délka(pat, patlen, p); -li (pat[p - jen] != pat[patlen-1 - jen]) { delta2[patlen-1 - jen] = patlen-1 - p + jen; } }}// Vrací ukazatel na první shodu.// Viz také glibc memmem () (non-BM) a std :: boyer_moore_searcher (první shoda).uint8_t* boyer_moore (uint8_t *tětiva, size_t stringlen, uint8_t *pat, size_t patlen) { ptrdiff_t delta1[ALPHABET_LEN]; ptrdiff_t delta2[patlen]; // C99 VLA make_delta1(delta1, pat, patlen); make_delta2(delta2, pat, patlen); // Prázdný vzor musí být považován za speciálně -li (patlen == 0) { volný, uvolnit(delta2); vrátit se tětiva; } size_t i = patlen - 1; // str-idx zatímco (i < stringlen) { ptrdiff_t j = patlen - 1; // pat-idx zatímco (j >= 0 && (tětiva[i] == pat[j])) { --i; --j; } -li (j < 0) { volný, uvolnit(delta2); vrátit se &tětiva[i+1]; } ptrdiff_t posun = max(delta1[tětiva[i]], delta2[j]); i += posun; } volný, uvolnit(delta2); vrátit se NULA;}
/** * Vrátí index v tomto řetězci prvního výskytu * zadaný podřetězec. Pokud se nejedná o podřetězec, vraťte -1. * * Neexistuje žádný Galil, protože generuje pouze jednu shodu. * * @param haystack Řetězec, který má být skenován * @param needle Cílový řetězec k vyhledávání * @return Počáteční index dílčího řetězce */ veřejnost statický int indexOf(char[] kupka sena, char[] jehla) { -li (jehla.délka == 0) { vrátit se 0; } int charTable[] = makeCharTable(jehla); int offsetTable[] = makeOffsetTable(jehla); pro (int i = jehla.délka - 1, j; i < kupka sena.délka;) { pro (j = jehla.délka - 1; jehla[j] == kupka sena[i]; --i, --j) { -li (j == 0) { vrátit se i; } } // i + = jehla.délka - j; // Pro naivní metodu i += Matematika.max(offsetTable[jehla.délka - 1 - j], charTable[kupka sena[i]]); } vrátit se -1; } /** * Vytvoří tabulku skoků na základě neodpovídajících informací o postavách. */ soukromé statický int[] makeCharTable(char[] jehla) { finále int ALPHABET_SIZE = Charakter.MAX_VALUE + 1; // 65536 int[] stůl = Nový int[ALPHABET_SIZE]; pro (int i = 0; i < stůl.délka; ++i) { stůl[i] = jehla.délka; } pro (int i = 0; i < jehla.délka - 2; ++i) { stůl[jehla[i]] = jehla.délka - 1 - i; } vrátit se stůl; } /** * Vytvoří tabulku skoků na základě posunu skenování, ke kterému dochází k neshodě. * (pravidlo špatného charakteru). */ soukromé statický int[] makeOffsetTable(char[] jehla) { int[] stůl = Nový int[jehla.délka]; int lastPrefixPosition = jehla.délka; pro (int i = jehla.délka; i > 0; --i) { -li (isPrefix(jehla, i)) { lastPrefixPosition = i; } stůl[jehla.délka - i] = lastPrefixPosition - i + jehla.délka; } pro (int i = 0; i < jehla.délka - 1; ++i) { int jen = přípona Délka(jehla, i); stůl[jen] = jehla.délka - 1 - i + jen; } vrátit se stůl; } /** * Je jehla [p: konec] předponou jehly? */ soukromé statický booleovský isPrefix(char[] jehla, int p) { pro (int i = p, j = 0; i < jehla.délka; ++i, ++j) { -li (jehla[i] != jehla[j]) { vrátit se Nepravdivé; } } vrátit se skutečný; } /** * Vrátí maximální délku podřetězce končícího na p a je příponou. * (dobré pravidlo přípony) */ soukromé statický int přípona Délka(char[] jehla, int p) { int len = 0; pro (int i = p, j = jehla.délka - 1; i >= 0 && jehla[i] == jehla[j]; --i, --j) { len += 1; } vrátit se len; }
Varianty
The Algoritmus Boyer – Moore – Horspool je zjednodušení algoritmu Boyer – Moore využívající pouze pravidlo špatného znaku.
The Algoritmus Apostolico – Giancarlo zrychluje proces kontroly, zda v daném zarovnání došlo ke shodě přeskočením explicitních srovnání znaků. Toto používá informace shromážděné během předběžného zpracování vzoru ve spojení s délkou shody přípon zaznamenanou při každém pokusu o shodu. Ukládání délek shod přípon vyžaduje další tabulku o stejné velikosti jako hledaný text.
The Raita algoritmus zlepšuje výkonnost algoritmu Boyer-Moore-Horspool. Vyhledávací vzor konkrétního podřetězce v daném řetězci se liší od algoritmu Boyer-Moore-Horspool.
Poznámky
Reference
- ^ Hume; Neděle (listopad 1991). Msgstr "Rychlé vyhledávání řetězců". Software - praxe a zkušenosti. 21 (11): 1221–1248. doi:10.1002 / spe. 4380211105. S2CID 5902579.
- ^ Boyer, Robert S.; Moore, J Strother (Říjen 1977). Msgstr "Algoritmus rychlého vyhledávání řetězců". Comm. ACM. New York: Sdružení pro výpočetní techniku. 20 (10): 762–772. doi:10.1145/359842.359859. ISSN 0001-0782. S2CID 15892987.
- ^ Knuth, Donald E .; Morris, Jr., James H .; Pratt, Vaughan R. (1977). "Rychlé porovnávání vzorů v řetězcích". SIAM Journal on Computing. 6 (2): 323–350. doi:10.1137/0206024. ISSN 0097-5397.
- ^ Rytter, Wojciech (1980). "Správný algoritmus předběžného zpracování pro vyhledávání řetězců Boyer – Moore". SIAM Journal on Computing. 9 (3): 509–512. doi:10.1137/0209037. ISSN 0097-5397.
- ^ A b Gusfield, Dan (1999) [1997], „Kapitola 2 - Přesná shoda: Klasické srovnávací metody“, Algoritmy pro řetězce, stromy a sekvence (1. vyd.), Cambridge University Press, s. 19–21, ISBN 0521585198
- ^ A b Galil, Z. (Září 1979). "Na zlepšení nejhorší doby běhu algoritmu shody řetězců Boyer-Moore". Comm. ACM. New York: Sdružení pro výpočetní techniku. 22 (9): 505–508. doi:10.1145/359146.359148. ISSN 0001-0782. S2CID 1333465.
- ^ Apostolico, Alberto; Giancarlo, Raffaele (únor 1986). „Strategie vyhledávání řetězců Boyer – Moore – Galil Revisited“. SIAM Journal on Computing. 15: 98–105. doi:10.1137/0215007.
- ^ Knuth, Donald; Morris, James H.; Pratt, Vaughan (1977). "Rychlé porovnávání vzorů v řetězcích". SIAM Journal on Computing. 6 (2): 323–350. CiteSeerX 10.1.1.93.8147. doi:10.1137/0206024.
- ^ Guibas, Leonidas; Odlyzko, Andrew (1977). „Nový důkaz linearity algoritmu vyhledávání řetězců Boyer – Moore“. Sborník z 18. výročního symposia o základech informatiky. Washington, District of Columbia: IEEE Computer Society: 189–195. doi:10.1109 / SFCS.1977.3. S2CID 6470193.
- ^ A b Cole, Richard (září 1991). „Těsné hranice složitosti algoritmu porovnávání řetězců Boyer – Moore“. Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, Pensylvánie: Společnost pro průmyslovou a aplikovanou matematiku: 224–233. ISBN 0-89791-376-0.
- ^ https://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html
externí odkazy
- Původní práce o algoritmu Boyer-Moore
- Příklad algoritmu Boyer-Moore z domovské stránky J Strother Moore spoluautorem algoritmu
- Papír Richarda Colea z roku 1991, který dokazuje runtime linearitu