Boyer-Moore-Horspool algoritmus
A Boyer-Moore-Horspool algoritmus egy olyan algoritmus , amely egy karakterláncban lévő részkarakterláncot keres , a Boyer-Moore algoritmus egyszerűsített változata . Az ABMX jobban működik, mint a Boyer-Moore algoritmus véletlenszerű szövegeken, az átlagos pontszám től - től egy karakterig terjed a szövegben [1] . Ezenkívül a számításigényes illesztési utótag heurisztika kimarad.
Az ABMX becslése azonban ( a legrosszabb esetben a nem időszakos sablonokon) | tű |·| szénakazal | (3 | szénakazal helyett | Boyer-Moore-nak).
Az algoritmus leírása
Az algoritmus a Boyer-Moore algoritmus egy módosítása . Az algoritmus ötlete a következő.
1. Szkennelés balról jobbra, összehasonlítás "fekete doboz" módban. A primitív algoritmushoz hasonlóan a szöveg eleje és a sablon kombinálva van, az összehasonlítás a szokásos „ memóriaszakaszok összehasonlítása ” eljárással történik . Ha a minta összes karaktere megegyezett a karakterlánc egymásra helyezett karaktereivel, akkor az alkarakterlánc megtalálható, és a keresés véget ért.
Ha a minta bármely karaktere nem egyezik a karakterlánc megfelelő karakterével, a minta néhány karakterrel jobbra tolódik. Ezt a "keveset" egy ilyen heurisztika szerint választják ki.
2. Megváltozott a stop szimbólum heurisztika. A minta utolsó karaktere fölött megjelenő szöveg karakterét vesszük (függetlenül attól, hogy hol történt az eltérés!). A képen "b" van.
↓ stop karakter Szöveg abadb * * * * abbad minta Következő abbad ellenőrzésA sablont úgy toljuk el, hogy a sablon „b” betűje a stop szimbólum alatt legyen. Ezt egy eltolási táblázat segítségével valósítjuk meg: az ábécé minden karakteréhez a lehető legnagyobb eltolást tároljuk, amely nem hagy ki egy stop karaktert. Vagyis (a sorok számozása 1-gyel): shift ( c ) = | tű |−lastpos( c , tű [1..| tű |−1]) , ahol a lastpos egy karakter utolsó előfordulása a karakterláncban, a tű [ a .. b ] a részkarakterlánc művelet.
Az "abbad" mintánál a táblázat így néz ki.
| Szimbólum | a | b | (Egyéb) |
|---|---|---|---|
| Elfogultság | egy | 2 | 5 |
A sablonban nem szereplő szimbólumok esetén az eltolás értéke megegyezik a sablon hosszával - 5. A sablon utolsó szimbólumát nem veszik figyelembe az eltolási táblázat kiszámításakor (tele van hurkolással ).
Kényelmesebb a táblázat kiszámítása, ha végignézi a sablon összes szimbólumát:
c=MIN_CHAR..MAX_CHAR esetén műszak[c] = |tű| mert i=1..|tű|-1 műszak[tű[i]] = |tű|-iPélda az algoritmus működésére
A kívánt minta az "abbad" (az ehhez a mintához tartozó táblázat fent található).
abeccacbadbabbad abbadEgy mintát helyezünk a vonalra. A "c" forráskarakterlánc utolsó karaktere nem szerepel a mintában. Tolja el a mintát 5 pozícióval jobbra a "c" eltolási értékének megfelelően:
abeccacbadbabbad abbadA minta három karaktere megegyezett, de a negyedik nem. Tolja el a mintát 5 pozícióval jobbra a "d" eltolási értékének megfelelően:
abeccacbadbabbad abbadAz "a" karakterlánc utolsó karaktere nem egyezik a minta karakterével. Tolja el a mintát jobbra 1-gyel az "a" eltolási értékének megfelelően, és kapja meg a minta kívánt előfordulását:
abeccacbadbabbad abbadOpciók
Szandi algoritmusa
A stop karakterhez a tűt követő karaktert vesszük .
Wright-algoritmus
Angol szövegekre optimalizált empirikus algoritmus . Összehasonlítja az utolsó karaktert, majd az elsőt, majd a középsőt, majd az összes többit; eltérés esetén Horspool műszak.
Előnyök
Átlagosan nagyon gyors[ adja meg ] . Könnyen megvalósítható. A szabványos függvényt használja a memóriaterületek összehasonlítására, általában összeszerelő szinten optimalizálva egy adott processzorhoz.
Hátrányok
A Boyer-Moore család többi algoritmusához hasonlóan nincs módosítva közelítő keresésre, több karakterlánc egyidejű keresésére.
A "rossz" adatok regressziója valamivel gyakrabban történik, mint a Boyer-Moore algoritmusban. Minél változatosabbak a karakterek a forrásszövegben, annál jobban viselkedik az ABMX.
Irodalom
- Niklaus Wirth Algoritmusok és adatstruktúrák. — M.: Nyevszkij-dialektus, 2006. S. 352. ISBN 5-7940-0065-1
Jegyzetek
- ↑ Horspool algoritmus . Letöltve: 2012. augusztus 12. Az eredetiből archiválva : 2012. augusztus 29..
Linkek
| Húrok | |
|---|---|
| Karakterlánc hasonlósági mértékek | |
| Substring keresés | |
| palindromák | |
| Sorozat-igazítás | |
| Utótag szerkezetek | |
| Egyéb | |