Boyer-Moore algoritmus

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2018. július 30-án felülvizsgált verziótól ; az ellenőrzések 28 szerkesztést igényelnek .

Boyer-Moore algoritmus
Valaki után elnevezve	Robert S. Boyer [d] és J Strother Moore [d]
Szerző	Robert S. Boyer [d] és J Strother Moore [d]
célja	Alkarakterlánc hatékony keresése egy karakterláncban
Adatstruktúra	Húrok
legrosszabb idő	$\Theta (n+m)$
A memória költsége	$\Theta (m+\|\Sigma \|)$ vagy $\Theta (m)$
Médiafájlok a Wikimedia Commons oldalon

A Boyer-Moore karakterlánc-kereső algoritmus egy általános célú algoritmus, amelyet arra terveztek, hogy egy karakterláncban lévő részkarakterláncot keressen . Tervezte : Robert Boyerés Jay Moore1977 - ben [1] . Ennek az algoritmusnak az az előnye, hogy bizonyos mennyiségű előzetes számítás árán a sablonon (de nem azon a karakterláncon, amelyben a keresés történik) a sablont nem hasonlítják össze a forrásszöveggel minden pozícióban - bizonyos esetekben az ellenőrzések közül kimarad, mivel nyilvánvalóan nem ad eredményt.

A Boyer-Moore algoritmus modern változatának számítási összetettségének általános becslése , ha nem használjuk a stop karaktertáblát (lásd lent), és ha a stop karaktertáblát használjuk, hol a keresett karakterlánc hossza. , a keresési minta hossza, az ábécé , amelyen az összehasonlítás történik [2] . $O(n+m)$ $O(n+m+|\Sigma |)$ $n$ $m$ $\Sigma$

Az algoritmus leírása

Az algoritmus három ötleten alapul.

1. Lapolvasás balról jobbra, összehasonlítás jobbról balra. A szöveg (sor) eleje és a minta egyesül, az ellenőrzés a minta utolsó karakterétől indul. Ha a karakterek egyeznek, a minta utolsó előtti karakterét hasonlítja össze, stb. Ha a mintában szereplő összes karakter megegyezik a karakterlánc átfedő karaktereivel, akkor az alsztringet megtalálta, és a következő előfordulását keresi.

Ha a minta valamely karaktere nem egyezik a karakterlánc megfelelő karakterével, a minta néhány karakterrel jobbra tolódik, és a teszt az utolsó karaktertől kezdődik.

Az előző bekezdésben említett „keveseket” két heurisztikával számítjuk ki.

2. Állítsa le a szimbólum-heurisztikát. ( Megjegyzés: a stop szimbólum heurisztika a Boyer-Moore algoritmus legtöbb leírásában megtalálható, beleértve Boyer és Moore eredeti cikkét is [1] , de nem szükséges a futási idő becsléséhez [2] ; ráadásul ez a heurisztika további memóriát igényel munkára és többletidőre a sablon elkészítése során.) $O(n+m)$ $O(|\Sigma |)$ $O(|\Sigma |)$

Tegyük fel, hogy a "bell" szót keressük. Az első betű nem egyezik - "k" (nevezzük ezt a betűt stop szimbólumnak ). Ezután áthelyezheti a sablont jobbra az utolsó „k” betűig.

Karakterlánc: * * * * * * - * * * * * * Sablon: k o l o k o l Következő lépés: k o l o k o l

Ha nincs stop karakter a mintában, a minta eltolódik a stop karakter mögött.

Karakterlánc: * * * * * a l * * * * * * * * Sablon: k o l o k o l Következő lépés: k o l o k o l

Ebben az esetben a stop karakter "a", és a minta eltolódik úgy, hogy közvetlenül a betű mögé kerüljön. A Boyer-Moore algoritmusban a stop-karakter heurisztika egyáltalán nem veszi figyelembe az illesztett utótagot (lásd lent), így a minta első betűje ("k") az "l" alatt lesz, és egy ismert dummy ellenőrzésre kerül sor.

Ha a „k” stopszimbólum egy másik „k” betű mögött van, a stopszimbólum-heurisztika nem működik.

Karakterlánc: * * * * - c o l * * * * * Sablon: k o l o k o l Következő lépés: k o l o k o l

Ilyen helyzetekben a Boyer-Moore algoritmus harmadik ötlete segít - a megfelelő utótag-heurisztika.

3. Az illesztett utótag heurisztikája. Informálisan, ha az S utótag illeszkedik a minta jobbról balra olvasása közben, de a mintában az S előtti b karakter (vagyis a minta PbS) nem egyezik, akkor az illesztett utótag heurisztika a mintát a legkevesebb számmal tolja el. helyen jobbra úgy, hogy az S karakterlánc illeszkedjen a mintához, és a mintában az adott S egyezést megelőző karakter különbözik b-től (ha van ilyen karakter egyáltalán). Formálisan ennél a sablonnál egy egész tömb suffshift[0..m] számít, amelyben a suffshift[i] egyenlő azzal a minimális számmal , hogy (ha és ), és bármelyikre , amelyre és érvényes (magyarázatként lásd az alábbi példákat). ). Ekkor, ha a minta jobbról balra történő olvasása közben a karakterek megegyeztek , de a karakter nem, akkor a minta suffshift[mk] karakterekkel jobbra tolódik. Például: $s[0..m{-}1]$ $j>0$ $s[i{-}j]\neq s[i{-}1]$ $i>0$ $ij\geq 0$ $s[i{-}j{+}k]=s[i{-}1{+}k]$ $k>0$ $0\leq i-j+k<m$ $0\leq i-1+k<m$ $s$ $k{-}1$ $s[m{-}1],s[m{-}2],\ldots ,s[m{-}k{+}1]$ $s[m{-}k]$

Sor: * * * * * * * p a * * * * * Sablon: s ka l k a l k a Következő lépés: c a l c a l c a

Ebben az esetben a „ka” utótag illeszkedett, és a minta jobbra tolódik a legközelebbi „ka”-hoz, amely előtt nincs „l”.

Karakterlánc: * * t o c o l * * * * * Sablon: k o l o k o l Következő lépés: k o l o k o l

Ebben az esetben a „közel” utótag illeszkedett, és a sablon jobbra tolódik a legközelebbi „közel”-hez, amely előtt nincs „l”. Ha az "about" részkarakterlánc már nincs a mintában, de "count"-val kezdődik, átvált "count"-ra stb.

Figyelmeztetés : A megfelelő utótag legközelebbi előfordulása előtt a betűk hibája előfeltétel. Ha az egyező utótag legközelebbi előfordulására szorítkozunk, akkor az algoritmus elfogadhatatlanul lassan működhet. Például, amikor egy hosszúsági mintát keres egy karakterláncban , amely az "a" karaktereket és egy hosszúságú karakterláncot tartalmazza , egy algoritmus, amely a karaktereltérések figyelembevétele nélkül használja az eltolásokat, akkor is végrehajt műveleteket, ha stop karakterheurisztikust használ. Másrészt bebizonyosodott [2] , hogy a BM algoritmus futási ideje, figyelembe véve a karakterek eltérését (vagyis a fent definiált suffshift tömb használatával), a stop karakter heurisztika használata nélkül is egyenlő ( M. Kroshmore és W. Ritter [2] könyvében ezt a tényt bizonyítja Cole 1994-es bizonyításának [3] módosítása , amely csak a nem periodikus minták esetét vette figyelembe). $cabababa\ldots ba$ $2n$ $aaa\ldots aababab\ldots ba$ $2n$ $baba\ldotsba$ $2n$ $O(n^{2})$ $O(n+m)$

Mindkét heurisztika előzetes számításokat igényel - a keresési mintától függően két táblázat töltődik ki. A stop szimbólumok táblázata méretében megfelel az ábécének - (például ha az ábécé 256 karakterből áll, akkor a hossza 256); utótag táblázat - a kívánt mintára, azaz . $O(|\Sigma |)$ $O(m)$

Ismertesse meg mindkét táblázatot részletesebben.

Stop szimbólum táblázat

A stop karaktertáblázat felsorolja az ábécé minden karakterének utolsó pozícióját a mintában ( az utolsó betű kivételével ). Minden olyan karakterre, amelyet nem tartalmaz , 0-t írunk, ha a karakterek számozása 1-től kezdődik (vagy −1-et, ha a számozás 0-tól kezdődik). Például, ha , a StopTable stop karakterek táblázata így fog kinézni (a táblázat nullától számozott karakterlánc esetén van megadva; karakterek számozásakor egytől minden számhoz hozzá kell adni egyet): $s$ $s$ $s=abcdadcd$

abcd szimbólum [az összes többi] Utolsó pozíció 4 1 6 5 -1

Vegye figyelembe, hogy a "d" stop karakter esetében az utolsó pozíció 5 lesz, nem 7 - az utolsó betűt nem veszi figyelembe. Ez egy ismert hiba, ami szuboptimálishoz vezet. A BM algoritmus esetében ez nem végzetes (az utótag-heurisztika megmenti a helyzetet), de végzetes a BM algoritmus egy egyszerűsített változatánál - a Horspool algoritmusnál .

Ha a minta és a jobbról balra mutató karakterlánc összehasonlításakor az eltérés a pozícióban történt , és a stop karakter a , akkor a mintát karakterenként kell eltolni . $s[0..m{-}1]$ $text[i..i{+}m{-}1]$ $j$ $c=text[j]$ $i'=j-StopTable[c]$

Utótag táblázat

Az adott minta minden lehetséges utótagjához megadjuk azt a legkisebb mértéket , amennyivel a mintát jobbra kell tolni , hogy újra egyezzen a karakterrel , és ugyanakkor az ezt megelőző karakter ne egyezzen meg az utótagot megelőző karakterrel . Ha ilyen eltolás nem lehetséges, tegye (mindkét számozási rendszerben). Például a következő lesz: $t$ $s$ $t$ $t$ $t$ $|s|=m$ $s=aaccbccbcc$

Utótag [üres] c cc bcc ... aaccbccbcc Eltolás 2 1 6 10 ... 10 Ábra Ez volt ? ?c ?cc ?bcc ... aaccbccbcc lett aaccbccbcc aaccbccbcc aaccbccbcc aaccbccbcc ... aaccbccbcc

A "harang" esetében: $s=$

Utótag [üres] l ol kol ... okol harang Váltás 1 7 7 4 ... 4 4 Ábra Ez volt ? ?l ?ol ?kol ... ?csengő bell bell bell bell bell ... harang harang lett

Létezik egy algoritmus a suffshift[0..m] utótag táblázat kiszámítására futási idővel . [2] Ez az algoritmus ugyanazon az elgondoláson alapul, mint az előtagfüggvény és a karakterlánc Z függvény számítására szolgáló algoritmusok [4] [5] . Ennek az algoritmusnak a megvalósítása C++ nyelven a következő: $O(m)$

std :: vektor < int > suffshift ( m + 1 , m ); std :: vektor < int > z ( m , 0 ); for ( int j = 1 , maxZidx = 0 , maxZ = 0 ; j < m ; ++ j ) { if ( j <= maxZ ) z [ j ] = std :: min ( maxZ - j + 1 , z [ j - maxZidx ]); míg ( j + z [ j ] < m && s [ m - 1 - z [ j ]] == s [ m - 1 - ( j + z [ j ])]) z [ j ] ++ ; if ( j + z [ j ] - 1 > maxZ ) { maxZidx = j ; maxZ = j + z [ j ] -1 ; _ } } for ( int j = m - 1 ; j > 0 ; j -- ) suffshift [ m - z [ j ] ] = j ; //1. hurok for ( int j = 1 , r = 0 ; j <= m - 1 ; j ++ ) //#2 hurok if ( j + z [ j ] == m ) for (; r <= j ; r ++ ) if ( suffshift [ r ] == m ) suffshift [ r ] = j ;

A kód első ciklusában az úgynevezett Z-függvény kiszámításához használt kód reprodukálódik , de az invertált karakterláncé . [5] Mégpedig minden olyan esetében, amelynél az elem tartalmazza a karakterlánc leghosszabb utótagjának hosszát , amely egyben a teljes karakterlánc utótagja is . A tömb segítségével kiszámítja a kívánt tömb suffshift[0..m] értékét (lásd lentebb). Az utolsó ciklus minden iterációjánál 1-gyel, a benne beágyazott ciklus minden iterációjánál pedig 1-gyel csökken. Ezért, mivel , , és a Z-függvény kiszámításának algoritmusa működik (lásd pl. , a megfelelő cikk , valamint cikk [5] ) , ennek az algoritmusnak a teljes futási ideje . $z[1..m{-}1]$ $s[0..m-1]$ $j$ $0\leq j<m-1$ $z[m-1-j]$ $s[0..j]$ $s$ $z$ $j$ $k$ $j\geq 0$ $k\geq 0$ $O(m)$ $O(m)$

A bemutatott kód helyességének bizonyítására célszerű elképzelni, hogy a karakterláncot elemzik , ami megegyezik a fordított karakterlánccal . A suffshift definíciója szerint van suffshift[ ] , ahol a legkisebb pozitív szám, amelyben vagy 1) a karakterlánc a karakterlánc előtagja , vagy 2) a karakterlánc egyenlő a és a karakterek és különbözőek. A 2) esetben definíció szerint szükségszerűen teljesül . Így az 1-es hurok től 1-ig futva megtalálja a 2. szabály által kapott összes utóeltolás értéket. Az 1) szabály által kapott suffshift értékek kiszámításához először is, ha egy előtag , akkor szükségszerűen teljesül , másodszor pedig, ha suffshift[ ] = egyeseknél , akkor szükségszerűen . E két megfigyelés alapján a 2. hurok kiszámítja a fennmaradó inicializálatlan suffshift értékeket (azaz úgy, hogy suffshift[k] = m). $s'[0..m{-}1]$ $s$ $mk$ ${\displaystyle=j}$ $j$ $s'[j..m{-}1]$ $s'[0..k{-}1]$ $s'[j..j{+}k{-}1]$ $s'[0..k{-}1]$ $s'[j{+}k]$ $s'[k]$ $z$ $z[j]=k$ $j$ $m-1$ $s'[j..m{-}1]$ $s'[0..k{-}1]$ $j+z[j]=m$ $r$ $j$ $r$ $r\leq j$

Az algoritmus megvalósítása

Számoljuk meg az adott sablonhoz tartozó suffshift[0..m] eltolások tömbjét . Ekkor a Boyer-Moore algoritmus C++ implementációja a szöveg első előfordulásának időbeni megtalálására stop karakter heurisztikák használata nélkül a következő [2] : $s[0..m{-}1]$ $s$ $text[0..n{-}1]$ $O(n+m)$

for ( int i = 0 , j = 0 ; i <= n - m && j >= 0 ; i += suffshift [ j + 1 ] ) { for ( j = m - 1 ; j > = 0 && s [ j ] == szöveg [ i + j ]; j -- ); if ( j < 0 ) jelentés_előfordulás ( i ); }

Egy ilyen algoritmus nem alkalmas arra, hogy egy szövegben egy minta minden előfordulását időben megtalálja. Ha eltávolítjuk a "j >= 0" feltételt a külső ciklusból, akkor az algoritmus minden előfordulást megkeres, de legrosszabb esetben olyan műveleteket hajthat végre, amelyek jól láthatóak egy csak a " betűkből álló" karakterlánc figyelembevételével. a". Az összes előfordulás kereséséhez a következő módosítást használjuk, amely az úgynevezett Galil-szabály [6] miatt idővel működik : $O(m+n)$ $O(mn)$ $O(n+m)$

int j , kötött = 0 ; //mindig vagy kötött = 0 vagy kötött = m - suffshift[0] for ( int i = 0 ; i <= n - m ; i += suffshift [ j + 1 ]) { for ( j = m - 1 ; j >= kötött && s [ j ] == szöveg [ i + j ]; j -- ); if ( j < kötött ) { jelentés_előfordulás ( i ); kötött = m - utóeltolódás [ 0 ]; j = -1_ _ //Állítsa be a j-t úgy, mintha a teljes mintát olvasnánk, nem csak a korlátig } else { kötött = 0 ; } }

Galil szabálya a következő egyszerű megfigyelésen alapul. Ha egy előfordulást találunk a pozícióban , akkor a következő keresés megpróbálja megtalálni a minta előfordulását a suffshift[0] pozícióban, és a suffshift definíciója szerint a karakterek már ismertek a suffshift[0] karaktereivel . Tehát, amikor jobbról balra keresést végez annak meghatározására, hogy előfordul-e minta a pozícióban , nincs értelme a suffshift[0] karakterek ellenőrzésének . Erre való a "kötött" változó. Bebizonyosodott, hogy egy ilyen heurisztika segít időt kapni a minta minden előfordulásának megkeresésére a karakterláncban [6] . $s$ $én$ $i'=i+$ $s[i'],s[i'{+}1],\ldots ,s[i{+}m{-}1]$ ${\displaystyle s[0],s[1],\ldots ,s[m{-))$ ${-}1]$ $én'$ ${\displaystyle s[0],s[1],\ldots ,s[m{-))$ ${-}1]$ $O(n+m)$

A stop szimbólum heurisztika engedélyezéséhez elegendő i += suffshift[j+1]a " " sort a következő kifejezésre cserélni a fő ciklus végén:

if ( j < kötött ) i += suffshift [ j + 1 ]; else i += max ( suffshift [ j + 1 ], j - StopTable [ szöveg [ i + j ]]);

Példa az algoritmus működésére

A kívánt minta: " abbad". A stop szimbólum táblázat így fog kinézni (ebben a példában kényelmesebb lesz a számozást egyből használni)

Szimbólum abd [egyéb] 4 3 5 0 pozíció

Az összes lehetséges utótag táblázata (kivéve az üres) maximum 5-ös eltolódást ad.

abeccaabadbabbad abbad

Egy mintát helyezünk a vonalra. Nincs utótagegyezés - az utótag táblázat egy pozícióval való eltolódást ad. A " " forráskarakterlánc (5. pozíció) nem egyező karakteréhez сa stop karaktertáblázatba 0 kerül beírásra. A mintát 5-0=5pozíciókkal jobbra tolja.

abeccaabadbabbad abbad

A 3-5. szimbólum megegyezett, de a második nem. A " а" heurisztika nem működik ( 2-4=-2). De mivel a karakterek egy része megegyezett, az illesztett utótag heurisztikája lép életbe, egyszerre öt pozícióval eltolva a mintát!

abeccaabadbabbad abbad

Ismét nincs egyező utótag. A stop karakterek táblázatának megfelelően eltoljuk a mintát egy pozícióval, és megkapjuk a minta kívánt előfordulását:

abeccaabadbabbad abbad

A helyesség igazolása

Az algoritmus helyességének bizonyításához elegendő bemutatni, hogy ha egyik vagy másik heurisztika egynél több pozícióval jobbra tolódást javasol, akkor a hiányzó pozíciókban nem található meg a minta.

Tehát az S utótag egyezzék meg , a sablon karakterlánc egyenlő a PbS -vel , a stop karakter a (a továbbiakban a kis betűk szimbólumok, a nagy betűk karakterláncok).

Karakterlánc: * * * * * * * * a [-- S --] * * * * Minta: [--- P ---] b [-- S --]

Stop szimbólum heurisztika. Akkor működik, ha nincs karakter a V karakterláncban. Ha P=WaV és nincs karakter a V karakterláncban , akkor a stop karakter heurisztika | V |+1 pozíció.

Karakterlánc: * * * * * * * * * * * * a [-- S --] * * * * * * * * Minta: [- W -] a [--- V ---] b [-- S --] Kihagyás: [- W -] a [--- V ---] b [-- S --] Új lépés: [- W -] a [--- V ---] b [-- S --]

Valójában, ha a V karakterlánc nem tartalmazza az a betűt , akkor nincs mit próbálni a hiányzó | v | pozíciókat.

Ha nincs karakter a mintában , akkor a stop karakter heurisztika |-vel való eltolást javasol P |+1 pozíció - és szintén nincs értelme a hiányzó | P |.

Karakterlánc: * * * * * * * * * a [-- S --] * * * * * * * * Minta: [--- P ---] b [-- S --] Kihagyás: [--- P ---] b [-- S --] Új lépés: [--- P ---] b [-- S --]

Illesztett utótag-heurisztika. Maga az informális kifejezés - "a legkisebb mennyiség, amennyit a mintát jobbra kell tolni, hogy S ismét megfeleljen, de az adott S-vel való egyezés előtti karakter (ha van ilyen) más lenne, mint a b" - mondja, hogy kisebb a műszakok haszontalanok.

Opciók

Boyer-Moore-Horspool algoritmus

A Boyer-Moore-Horspool (ABMH) algoritmus jobban működik, mint a Boyer-Moore algoritmus (ABM) véletlenszerű szövegeken – az átlagos becslés jobb rá.

Az ABMX csak a stopszimbólum heurisztikát használja; a stop karakter a minta utolsó karakterével megegyező bemeneti karakterlánc karaktere, függetlenül attól, hogy hol történt az eltérés .

Mivel a valódi keresési minták ritkán rendelkeznek egyenletes eloszlással , az ABMS nyereséget és veszteséget is adhat az ABM-hez képest.

A Zhu-Takaoka algoritmus

Rövid ábécéken (például DNS -szakaszok összehasonlításakor az ábécé csak négy karakterből áll: A , T , G , C ) a stop-karakter-heurisztika már a rövid utótagokon is meghiúsul. Az ABM teljesítményének ilyen körülmények között történő javításának legegyszerűbb módja, ha egy karakterpárhoz készítünk egy táblázatot egy stop karakter helyett: a nem egyezőnek és az előtte lévőnek [7] . Egy ilyen algoritmust Zhu-Takaoka algoritmusnak neveztek.

Az előfeldolgozás időt vesz igénybe. $O(m+|\Sigma |^{2})$

Turbo-Boyer-Moore algoritmus

A turbó-Boyer-Moore algoritmust M. Kroshmore vezette tudóscsoport fejlesztette ki , más megközelítést kínál a rövid ábécékhez, és egyúttal megoldja a második problémát - a legrosszabb esetben a kvadratikus összetettséget.

A stop karakter-heurisztika és az illesztett utótag-heurisztika mellett egy harmadik heurisztikát alkalmazunk, a turboshift-heurisztikát [8] .

Hagyja, hogy az UV utótag először illeszkedjen (és az utótag heurisztika működött, teljes átfedést biztosítva ennek az utótagnak), a második alkalommal - egy rövidebb V (esetleg V = ∅).

! ! bemeneti karakterlánc: * * * * * * * * * * # [-U-] [V] * * * * * * * * # [V] * * * * * * 1. Illesztett UV: * [-U-] [V] * * * * [-U-] [V] 2. Ekkor V egyezett: * [-U-] [V] * * * * * * [-U-] [V] Utótag heurisztikus eltolása: * [-U-] [V] * * * * * * * [-U-] [V] Turbóváltó: * [-U-] [V] * * * * * * [-U-] [V]

Az ábrán látható, hogy a minimális lehetséges eltolódás | U |. Ellenkező esetben a felkiáltójelekkel jelölt két karakter a beviteli karakterláncban különbözik, de a mintában ugyanaz. Ez a turboshift heurisztika.

Az algoritmus a legrosszabb esetben elvégzi az első egyezéshez való összehasonlítást. $2n$

Összehasonlítás más algoritmusokkal

Előnyök

A Boyer-Moore algoritmus nagyon gyors "jó" adatokon.[ pontosítás ] , és a "rossz" adatok megjelenésének valószínűsége rendkívül kicsi. Ezért a legtöbb esetben az optimális, ha nem lehetséges a keresést végző szöveg előfeldolgozása [9] . Hacsak nem rövid szövegeken, az erősítés nem indokolja az előzetes számításokat.

Hátrányok

A Boyer-Moore család algoritmusai nem terjednek ki hozzávetőleges keresésre, bármely karakterlánc keresésére több közül.

Az összehasonlítás nem " fekete doboz " (csak ha a stop-karakter heurisztikát használjuk), így a leggyorsabb keresés végrehajtásakor vagy az optimalizálóra kell hagyatkozni a sikeres működéshez , vagy manuálisan optimalizálni kell a keresést assembly nyelven.

Ha a szöveg ritkán változik, és a keresés gyakran történik (például egy keresőmotor ), akkor indexelheti a szöveget. Az indexkereső algoritmus gyorsabb[ pontosítás ] a Boyer-Moore algoritmus.

Nagy ábécéken (például Unicode ) a stop karaktertábla sok memóriát foglalhat el. Ilyen esetekben vagy elhagyják a hash táblákat , vagy felosztják az ábécét, például egy 4 bájtos karaktert kétbájtos karakterpárnak tekintve, vagy (ami a legegyszerűbb) a Boyer egy változatát használják. -Moore-algoritmus a stop karakterek heurisztikája nélkül.

A Boyer-Moore algoritmusnak számos olyan módosítása létezik, amelyek még nagyobb gyorsítást céloznak – ilyen például a turbó algoritmus, az inverz Colussi algoritmus [10] és mások.

Lásd még

Jegyzetek

↑ 12 Boyer , Moore, 1977 .
↑ 1 2 3 4 5 6 Crochemore, Rytter, 2002 .
↑ Cole, 1994 .
↑ Gasfield, 2003 .
↑ 1 2 3 MAXimális :: algo :: String Z-függvény és számítása . Letöltve: 2017. március 14. Az eredetiből archiválva : 2017. április 26.. (határozatlan)
↑ 12 Galil , 1979 .
↑ Zhu-Takaoka algoritmus archiválva : 2008. december 16. a Wayback Machine -nél
↑ Turbo-BM algoritmus archiválva : 2008. december 16. a Wayback Machine -nél
↑ Pontos karakterláncillesztő algoritmusok – Bevezetés Archiválva : 2008. december 16. a Wayback Machine -nél
↑ Reverse Colussi algoritmus archiválva : 2016. március 9. a Wayback Machine -nél

Irodalom

Kormen T. H. , Leyzerson C. E. , Rivest R. L. , Stein K. Algorithms: construction and analysis = Introduction to Algorithms / szerk. S. N. Triguba ; per. angolról. I. V. Krasikov , N. A. Orekhov ,N. Romanov - 2. kiadás - M. : Williams, 2005. - 801 p. — ISBN 5-8459-0857-4 .
Crochemore M. , Rytter W. Jewels of Stringology. Szingapúr: World Publishing Scientific Co. Pte. Kft., 2002. - 310 p. — ISBN 981-02-4782-6 .
Boyer RS , Moore JS Gyors karakterlánc-kereső algoritmus // Az ACM kommunikációja . - 1977. - T. 20 , 10. sz . - S. 762-772 . doi :/ 359842.359859 .
Cole R. A Boyer-Moore karakterlánc-illesztési algoritmus bonyolultságának szigorú határai // SIAM Journal on Computing . - 1994. - T. 23 , 5. sz . - S. 1075-1091 . - doi : 10.1137/S0097539791195543 .
Galil Z. A Boyer-Moore string matching algoritmus legrosszabb eset futási idejének javításáról // Communications of the ACM . - 1979. - T. 22 , 9. sz . - S. 505-508 . - doi : 10.1145/359146.359148 .
Gasfield D. Karakterláncok, fák és szekvenciák az algoritmusokban: számítástechnika és számítási biológia = Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology / ford. angolról. I. V. Romanovszkij . - Szentpétervár. : Nyevszkij-dialektus, 2003. - 654 p. — ISBN 5-7940-0103-8 .

Húrok
Karakterlánc hasonlósági mértékek	Távolság Damerau és Loewenstein között Levenshtein távolság Hamming távolság Jaro-Winkler hasonlóságok
Substring keresés	Boyer-Moore algoritmus Boyer-Moore-Horspool algoritmus Knuth-Morris-Pratt algoritmus Rabin-Karp algoritmus előtag funkció Z-függvény Algoritmus Aho - Korasik
palindromák	palindromfa Menedzser algoritmusa
Sorozat-igazítás	Needleman-Wunsha algoritmus Smith-Waterman algoritmus
Utótag szerkezetek	Utótag tömb Utótag automata utótag fa előtag fa
Egyéb	elemzése Mintaillesztés A legnagyobb közös sorozat Legnagyobb közös részkarakterlánc