Boyer-Mooren algoritmi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 30. heinäkuuta 2018 tarkistetusta versiosta . tarkastukset vaativat 28 muokkausta .

Boyer-Mooren algoritmi
Nimetty	Robert S. Boyer [d] ja J Strother Moore [d]
Tekijä	Robert S. Boyer [d] ja J Strother Moore [d]
tarkoitus	Tehokas alimerkkijonon haku merkkijonosta
Tietorakenne	jouset
pahin aika	${\näyttötyyli \Theta (n+m)}$
Muistin hinta	$\Theta (m+\|\Sigma \|)$ tai ${\näyttötyyli \Theta (m)}$
Mediatiedostot Wikimedia Commonsissa

Boyer-Mooren merkkijonohakualgoritmi on yleiskäyttöinen algoritmi, joka on suunniteltu etsimään alimerkkijonoa merkkijonosta . Suunnittelija Robert Boyerja Jay Moorevuonna 1977 [1] . Tämän algoritmin etuna on, että mallia ei verrata lähdetekstiin kaikissa paikoissa tietyn määrän alustavia laskutoimituksia mallissa (mutta ei merkkijonossa, jossa haku tehdään). tarkistuksista jätetään väliin, koska ne eivät selvästikään anna tulosta.

Yleinen arvio Boyer-Moore-algoritmin modernin version laskennallisesta monimutkaisuudesta on , jos lopetusmerkkitaulukkoa ei käytetä (katso alla) ja jos käytetään lopetusmerkkitaulukkoa, missä on etsittävän merkkijonon pituus , on hakukuvion pituus, on aakkoset , jolla vertailu tehdään [2] . $O(n+m)$ $O(n+m+|\Sigma |)$ $n$ $m$ $\Sigma$

Algoritmin kuvaus

Algoritmi perustuu kolmeen ideaan.

1. Skannaa vasemmalta oikealle, vertaa oikealta vasemmalle. Tekstin (rivin) alku ja kuvio yhdistetään, tarkistus alkaa kuvion viimeisestä merkistä. Jos merkit täsmäävät, verrataan kuvion toiseksi viimeistä merkkiä jne. Jos kaikki kuvion merkit vastaavat merkkijonon päällekkäisiä merkkejä, osamerkkijono on löydetty ja alimerkkijonon seuraava esiintymä etsitään.

Jos jokin kuvion merkki ei vastaa merkkijonon vastaavaa merkkiä, kuviota siirretään muutaman merkin verran oikealle ja testi alkaa uudelleen viimeisestä merkistä.

Nämä edellisessä kappaleessa mainitut "harvat" lasketaan kahdella heuristiikalla.

2. Lopeta symboliheuristiikka. ( Huomautus: stop- symboliheuristiikka esiintyy useimmissa Boyer-Mooren algoritmin kuvauksissa, mukaan lukien Boyerin ja Mooren alkuperäinen artikkeli [1] , mutta se ei ole välttämätön ajoaikaestimaatin [2] saavuttamiseksi ; lisäksi tämä heuristiikka vaatii lisämuistia työhön ja lisäaikaa mallin valmistelun aikana.) $O(n+m)$ $O(|\Sigma |)$ $O(|\Sigma |)$

Oletetaan, että etsimme sanaa "bell". Ensimmäinen kirjain ei täsmää - "k" (kutsutaan tätä kirjainta stop-symboliksi ). Sitten voit siirtää mallin oikealle sen viimeiseen kirjaimeen "k".

Merkkijono: * * * * * * * * * * * * * Malli: k o l o k o l Seuraava vaihe: k o l o k o l

Jos kuviossa ei ole lopetusmerkkiä, kuvio siirtyy lopetusmerkin ohi.

Merkkijono: * * * * * a l * * * * * * * * Malli: k o l o k o l Seuraava vaihe: k o l o k o l

Tässä tapauksessa stop-merkki on "a", ja kuviota siirretään niin, että se on aivan kyseisen kirjaimen takana. Boyer-Moore-algoritmissa stop-merkkiheuristiikka ei katso sovitettua päätettä ollenkaan (katso alla), joten kuvion ensimmäinen kirjain ("k") on "l":n alla ja yksi tunnettu nukke. tarkastus tehdään.

Jos pysäytyssymboli "k" on toisen kirjaimen "k" takana, pysäytyssymboliheuristiikka ei toimi.

Merkkijono: * * * * - c o l * * * * * Malli: k o l o k o l Seuraava vaihe: k o l o k o l

Tällaisissa tilanteissa Boyer-Moore-algoritmin kolmas idea tulee apuun - täsmäytysliitteen heuristiikka.

3. Sovitun jälkiliitteen heuristinen. Epävirallisesti, jos pääte S sovitetaan, kun kuviota luetaan oikealta vasemmalle, mutta kuviossa S:tä edeltävä merkki b (eli kuvio on PbS) ei täsmää, sovitettu suffiksiheuristiikka siirtää kuviota vähiten paikoista oikealle niin, että merkkijono S vastaa kuviota ja kuviossa annettua osumaa S edeltävä merkki olisi eri kuin b (jos sellaista on ollenkaan). Muodollisesti tälle mallille otetaan huomioon kokonaislukutaulukko suffshift[0..m], jossa suffshift[i] on yhtä suuri kuin vähimmäisluku siten, että (jos ja ) ja mille tahansa jolle ja pitää (katso alla olevat esimerkit selitykseksi ). Sitten, jos merkit vastaavat kuviota oikealta vasemmalle luettaessa , mutta merkki ei täsmää, kuvio siirtyy suffshift[mk]-merkit oikealle. Esimerkiksi: $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]$

Rivi: * * * * * * * p kohtaan a * * * * * Malli: s ka l k a l k a Seuraava vaihe: c a l c a l c a

Tässä tapauksessa "ka"-liite täsmäsi, ja kuvio siirtyy oikealle lähimpään "ka":een, jonka edessä ei ole "l"-kirjainta.

Merkkijono: * * t o c o l * * * * * Malli: k o l o k o l Seuraava vaihe: k o l o k o l

Tässä tapauksessa "lähellä"-liite täsmäsi, ja malli siirretään oikealle lähimpään "lähelle", jonka edessä ei ole "l". Jos alimerkkijono "about" ei ole enää kuviossa, mutta se alkaa sanalla "count", siirtyy "count"-muotoon jne.

Varoitus : Kirjainten yhteensopimattomuus ennen lähintä vastaavan päätteen esiintymistä on edellytys. Jos rajoitamme siirtymään lähimpään täsmätyn päätteen esiintymään, algoritmi voi toimia liian hitaasti. Esimerkiksi kun etsitään pituuskuviota merkkijonosta, joka sisältää merkkejä "a" ja sen jälkeen merkkijonon pituus , algoritmi, joka käyttää siirtoja ottamatta huomioon merkkien yhteensopimattomuutta, suorittaa toimintoja jopa käytettäessä stop-merkkiheuristia. Toisaalta on todistettu [2] , että BM-algoritmin ajoaika, kun otetaan huomioon merkkien yhteensopimattomuus (eli käyttämällä yllä määriteltyä suffshift-taulukkoa), on yhtä suuri myös ilman stop-merkkiheuristiikkaa ( M. Kroshmoren ja W. Ritterin kirjassa [2] annettu todiste tästä tosiasiasta on muunnelma Colen vuoden 1994 todistuksesta [3] , jossa käsiteltiin vain ei-jaksollisia kuvioita). $cabababa\ldots ba$ $2n$ $aaa\ldots aababab\ldots ba$ $2n$ $baba\ldotsba$ $2n$ $O(n^{2})$ $O(n+m)$

Molemmat heuristiikka vaativat esilaskelmia - hakumallista riippuen täytetään kaksi taulukkoa. Pysäytyssymbolien taulukko vastaa kooltaan aakkosia - (esimerkiksi jos aakkosto koostuu 256 merkistä, sen pituus on 256); suffiksitaulukko - haluttuun kuvioon, eli . $O(|\Sigma |)$ $O(m)$

Kuvataan molempia taulukoita yksityiskohtaisemmin.

Pysäytysmerkkitaulukko

Pysäytysmerkkitaulukossa luetellaan aakkosten jokaisen merkin viimeinen sijainti kuviossa ( lukuun ottamatta viimeistä kirjainta ). Kaikille merkeille, joita ei ole mukana , kirjoitetaan 0, jos merkkien numerointi alkaa 1:stä (tai −1, jos numerointi alkaa 0:sta). Esimerkiksi jos , stop-merkkien taulukko StopTable näyttää tältä (taulukko on annettu nollasta numeroitulle merkkijonolle; kun numeroitat merkkejä yhdestä, sinun on lisättävä kaikkiin numeroihin yksi): $s$ $s$ $s=abcdadcd$

Symboli abcd [kaikki muut] Viimeinen sijoitus 4 1 6 5 -1

Huomaa, että d-pysäytysmerkin viimeinen paikka on 5, ei 7 - viimeistä kirjainta ei oteta huomioon. Tämä on tunnettu virhe, joka johtaa alioptimaalisuuteen. BM-algoritmille se ei ole kohtalokas (liiteheuristiikka pelastaa tilanteen), mutta se on kohtalokas BM -algoritmin yksinkertaistetulle versiolle - Horspool-algoritmille .

Jos kuviota verrattaessa merkkijonoon oikealta vasemmalle epäsuhta esiintyi kohdassa , ja stop-merkki on , kuviota on siirrettävä merkeillä. $s[0..m{-}1]$ $text[i..i{+}m{-}1]$ $j$ $c=text[j]$ $i'=j-StopTable[c]$

Suffiksitaulukko

Jokaiselle mahdolliselle tietyn kuvion päätteelle määritetään pienin määrä, jolla kuviota on siirrettävä oikealle, jotta se täsmää uudelleen ja samaan aikaan tätä esiintymää edeltävä merkki ei vastaisi jälkiliitettä edeltävää merkkiä . Jos tällainen siirto ei ole mahdollista, laita (molemmissa numerointijärjestelmissä). Esimerkiksi tulee olemaan: $t$ $s$ $t$ $t$ $t$ $|s|=m$ $s=aaccbccbcc$

Suffiksi [tyhjä] c cc bcc ... aaccbccbcc Poikkeama 2 1 6 10 ... 10 Kuva Se oli ? ?c ?cc ?bcc ... aaccbccbcc tuli aaccbccbcc aaccbccbcc aaccbccbcc aaccbccbcc ... aaccbccbcc

" Kellolle ": $s=$

Suffiksi [tyhjä] l ol kol ... okol bell Vuoro 1 7 7 4 ... 4 4 Kuva Se oli ? ?l ?ol ?kol ... ?soittaa kelloa tuli bell bell bell bell ... bell bell

Suffiksitaulukon suffshift[0..m] laskemiseksi käyntiajalla on algoritmi . [2] Tämä algoritmi perustuu samoihin ideoihin kuin etuliitefunktion ja merkkijono Z-funktion laskenta-algoritmit [4] [5] . Tämän algoritmin toteutus C++:ssa on seuraava: $O(m)$

std :: vektori < int > suffshift ( m + 1 , m ); std :: vektori < int > z ( m , 0 ); for ( int j = 1 , maxZidx = 0 , maxZ = 0 ; j < m ; ++ j ) { jos ( j <= maxZ ) z [ j ] = std :: min ( maxZ - j + 1 , z [ j - maxZidx ]); while ( 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 -- ) jälkisiirto [ m - z [ j ] ] = j ; //silmukka #1 for ( int j = 1 , r = 0 ; j <= m - 1 ; j ++ ) //silmukka #2 if ( j + z [ j ] == m ) for (; r <= j ; r ++ ) if ( suffshift [ r ] == m ) suffshift [ r ] = j ;

Koodin ensimmäisessä silmukassa toistetaan koodi niin sanotun Z-funktion laskemiseksi , mutta käänteisen merkkijonon osalta . [5] Nimittäin kaikille sellaisille, että , elementti sisältää merkkijonon pisimmän päätteen pituuden , joka on myös koko merkkijonon pääte . Käyttämällä taulukkoa lasketaan sitten haluttu taulukon jälkimuutos[0..m] (katso kuvaus alla). Jokaisella viimeisen silmukan iteraatiolla se pienenee 1:llä ja jokaisessa siihen sisäkkäisen silmukan iteraatiossa se pienenee yhdellä. Siksi koska , , ja Z-funktion laskenta-algoritmi toimii (ks. esim. , vastaava artikkeli sekä artikkeli [5] ), tämän algoritmin kokonaisajoaika on . $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)$

Esitetyn koodin oikeellisuuden todistamiseksi on kätevää kuvitella, että merkkijono jäsennetään , mikä on yhtä suuri kuin käänteinen merkkijono . Suffshiftin määritelmän mukaan meillä on suffshift[ ] , jossa on pienin positiivinen luku siten, että joko 1) merkkijono on merkkijonon etuliite tai 2) merkkijono on yhtä suuri kuin ja merkit ja ovat erilaisia. Tapauksessa 2) määritelmän mukaan väistämättä täyttyy . Näin ollen silmukka 1 etsii kaikki säännöllä 2) saadut jälkisiirtymäarvot kohdasta 1:een . Laskeaksemme säännöllä 1) saadut suffshift-arvot huomaamme, että ensinnäkin, jos on etuliite , niin se välttämättä täyttyy , ja toiseksi, jos suffshift[ ] = joillekin , niin se on välttämättä . Näiden kahden havainnon perusteella silmukka #2 laskee jäljellä olevat alustamattomat suffshift-arvot (eli sellaiset, että 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]$ ${\näyttötyyli j+z[j]=m}$ $r$ $j$ $r$ $r\leq j$

Algoritmin toteutus

Lasketaan tietyn mallin muutosten joukko suffshift[0..m] . Sitten Boyer-Moore-algoritmin C++-toteutus tekstin ensimmäisen esiintymän löytämiseksi ajassa ilman stop-merkkiheuristiikkaa on seuraava [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 += jälkisiirto [ j + 1 ]) { for ( j = m - 1 ; j > = 0 && s [ j ] == teksti [ i + j ]; j -- ); if ( j < 0 ) raportti esiintymä ( i ); }

Tällainen algoritmi ei sovellu kaikkien kaavan esiintymien löytämiseen tekstistä ajoissa. Jos poistamme ehdon "j >= 0" ulkosilmukasta, niin algoritmi löytää kaikki esiintymät, mutta pahimmassa tapauksessa se voi suorittaa operaatioita, jotka on helppo nähdä ottamalla huomioon vain kirjaimista koostuva merkkijono " a". Kaikkien esiintymien etsimiseen käytetään seuraavaa muunnelmaa, joka toimii ajan niin sanotun Galilin säännön [6] vuoksi : $O(m+n)$ $O(mn)$ $O(n+m)$

int j , sidottu = 0 ; //aina joko sidottu = 0 tai sidottu = m - suffshift[0] for ( int i = 0 ; i <= n - m ; i += suffshift [ j + 1 ]) { for ( j = m - 1 ; j > = sidottu && s [ j ] == teksti [ i + j ]; j -- ); if ( j < sidottu ) { raportti_esiintymä ( i ); sidottu = m - jälkisiirto [ 0 ]; j = -1 _ //asettaa j ikään kuin lukisimme koko kuvion s, ei vain sidottuun asti } else { sidottu = 0 ; } }

Galilin sääntö perustuu seuraavaan yksinkertaiseen havaintoon. Jos esiintymä löytyy sijainnista , niin seuraava haku yrittää löytää kuvion esiintymän sijainnissa suffshift[0] ja suffshiftin määritelmän mukaan merkkien tiedetään jo vastaavan merkin suffshift[0] merkkejä . Joten suoritettaessa oikealta vasemmalle -hakua sen määrittämiseksi, esiintyykö kuvio paikassa , ei ole mitään järkeä tarkistaa merkkien suffshift[0] . Sitä varten "sidottu" muuttuja on tarkoitettu. On todistettu, että tällainen heuristiikka auttaa saamaan aikaa etsiä kaikki kuvion esiintymät merkkijonosta [6] . $s$ $i$ $i'=i+$ $s[i'],s[i'{+}1],\ldots ,s[i{+}m{-}1]$ ${\displaystyle s[0],s[1],\ldots ,s[m{-))$ ${-}1]$ $minä'$ ${\displaystyle s[0],s[1],\ldots ,s[m{-))$ ${-}1]$ $O(n+m)$

Pysäytyssymboliheuristiikan ottamiseksi käyttöön riittää i += suffshift[j+1], että rivi " " korvataan seuraavalla lausekkeella pääsilmukan lopussa:

if ( j < sidottu ) i += jälkisiirto [ j + 1 ]; else i += max ( jälkisiirto [ j + 1 ], j - Pysäytystaulukko [ teksti [ i + j ]]);

Esimerkki algoritmin toiminnasta

Haluttu kuvio on " abbad". Pysäytysmerkkitaulukko näyttää tältä (tässä esimerkissä on helpompi käyttää numerointia yhdestä)

Symboli abd [muut] Paikka 4 3 5 0

Suffiksitaulukko kaikille mahdollisille jälkiliitteille (paitsi tyhjälle) antaa maksimisiirron 5.

abeccaabadbabbad Abad

Asetamme näytteen linjalle. Suffiksia ei löydy - päätetaulukko antaa yhden paikan siirtymän. Lähdemerkkijonon " с" (5. paikka) yhteensopimattomalle merkille kirjoitetaan stop-merkkitaulukkoon 0. Siirrä kuviota oikealle 5-0=5paikkojen mukaan.

abeccaabadbabbad Abad

Symbolit 3-5 sopivat, mutta toinen ei. Kohteen " " heuristiikka аei toimi ( 2-4=-2). Mutta koska jotkin merkit sopivat yhteen, osuvan jälkiliitteen heuristisuus tulee voimaan, jolloin kuviota siirretään viidellä paikalla kerralla!

abeccaabadbabbad Abad

Jälleen kerran, ei ole vastaavaa päätettä. Pysäytysmerkkitaulukon mukaisesti siirrämme näytettä yhdellä asemalla ja saamme halutun näytteen esiintymisen:

abeccaabadbabbad Abad

Todiste oikeellisuudesta

Algoritmin oikeellisuuden todistamiseksi riittää, kun osoitetaan, että jos jokin heuristiikka ehdottaa siirtymistä useamman kuin yhden paikan verran oikealle, kuviota ei löydy puuttuvista kohdista.

Olkoon siis pääte S täsmää , mallimerkkijono on yhtä suuri kuin PbS , stop-merkki on a (tästä eteenpäin pienet kirjaimet ovat symboleja, suuret kirjaimet merkkijonoja).

Merkkijono: * * * * * * * * a [-- S --] * * * * Kuvio: [--- P ---] b [-- S --]

Lopeta symboliheuristiikka. Toimii , kun merkkijonossa V ei ole merkkiä . Jos P=WaV ja merkkijonossa V ei ole merkkiä , stop-merkkiheuristiikka ehdottaa siirtoa | V |+1 sijainti.

Merkkijono: * * * * * * * * * * * * * a [-- S --] * * * * * * * * Kuvio: [- W -] a [--- V ---] b [-- S --] Ohita: [- W -] a [--- V ---] b [-- S --] Uusi vaihe: [- W -] a [--- V ---] b [-- S --]

Itse asiassa, jos merkkijono V ei sisällä kirjainta a , puuttuvan | v | asemat.

Jos kuviossa ei ole merkkiä , stop-merkkiheuristiikka ehdottaa siirtymistä | P |+1 asema - eikä myöskään ole mitään järkeä kokeilla puuttuvaa | P |.

Merkkijono: * * * * * * * * * a [-- S --] * * * * * * * * Kuvio: [--- P ---] b [-- S --] Ohita: [--- P ---] b [-- S --] Uusi vaihe: [--- P ---] b [-- S --]

Vastaava jälkiliitteen heuristiikka. Itse epävirallinen lause - "pienin määrä, jonka kuviota on siirrettävä oikealle, jotta se täsmää uudelleen, mutta merkki ennen annettua vastaavuutta S:n kanssa (jos sellainen on olemassa) olisi erilainen kuin b" - sanoo, että pienempi vuorot ovat turhia.

Vaihtoehdot

Boyer-Moore-Horspool-algoritmi

Boyer-Moore-Horspool (ABMH) -algoritmi toimii paremmin kuin Boyer-Moore-algoritmi (ABM) satunnaisissa teksteissä - keskimääräinen arvio on sille parempi.

ABMX käyttää vain stop-symbolin heuristiikkaa; stop-merkki otetaan syötemerkkijonon merkiksi, joka vastaa kuvion viimeistä merkkiä, riippumatta siitä, missä epäsuhta esiintyi .

Koska todellisilla hakunäytteillä on harvoin tasainen jakautuminen , ABMS voi antaa sekä voittoa että tappiota verrattuna ABM:ään.

Zhu-Takaoka-algoritmi

Lyhyissä aakkosissa (esim. DNA -segmenttejä verrattaessa aakkoset koostuvat vain neljästä merkistä: A , T , G , C ) stop-merkkiheuristiikka epäonnistuu jo lyhyillä jälkiliitteillä. Yksinkertaisin tapa parantaa ABM:n suorituskykyä tällaisissa olosuhteissa on rakentaa taulukko merkkiparille yhden pysähdysmerkin sijaan: sille, joka ei täsmää, ja sille, joka tulee sitä edeltävälle [7] . Tällaista algoritmia kutsuttiin Zhu-Takaoka-algoritmiksi.

Esikäsittely vie aikaa. $O(m+|\Sigma |^{2})$

Turbo-Boyer-Moore-algoritmi

Turbo-Boyer-Moore-algoritmin on kehittänyt M. Kroshmoren johtama tutkijaryhmä , se tarjoaa erilaisen lähestymistavan lyhyisiin aakkosiin ja samalla ratkaisee toisen ongelman - pahimmassa tapauksessa neliöllisen monimutkaisuuden.

Pysäytysmerkkiheuristiikan ja sovitetun suffiksiheuristiikan lisäksi käytetään kolmatta heuristia, turboshift-heuristiikkaa [8] .

Anna jälkiliitteen UV osua ensimmäisellä kerralla (ja jälkiliitteen heuristinen toimi, tarjoten tämän päätteen täydellisen päällekkäisyyden), toisella kerralla - lyhyempi V (mahdollisesti V = ∅).

! ! syötemerkkijono: * * * * * * * * * * # [-U-] [V] * * * * * * * * # [V] * * * * * * 1. Vastaava UV: * [-U-] [V] * * * * [-U-] [V] 2. Sitten V osui: * [-U-] [V] * * * * * * [-U-] [V] Suffiksin heuristinen muutos: * [-U-] [V] * * * * * * [-U-] [V] Turboshift: * [-U-] [V] * * * * * * [-U-] [V]

Kuvasta näkyy, että pienin mahdollinen siirtymä on | U |. Muuten huutomerkeillä merkityt kaksi merkkiä ovat erilaiset syöttömerkkijonossa, mutta samat kuviossa. Tämä on turboshift-heuristiikka.

Algoritmi tekee työnsä vertailujen ensimmäiseen otteluun pahimmassa tapauksessa. $2n$

Vertailu muihin algoritmeihin

Edut

Boyer-Moore-algoritmi on erittäin nopea "hyvillä" tiedoilla.[ selventää ] , ja "huonojen" tietojen ilmaantumisen todennäköisyys on erittäin pieni. Siksi se on optimaalinen useimmissa tapauksissa, kun ei ole mahdollista esikäsitellä tekstiä, jossa haku suoritetaan [9] . Ellei lyhyillä teksteillä vahvistus oikeuta alustavia laskelmia.

Haitat

Boyer-Moore-perheen algoritmit eivät laajene likimääräiseen hakuun, minkä tahansa merkkijonon etsimiseen useista.

Vertailu ei ole " musta laatikko " (vain jos käytetään stop-merkkiheuristiikkaa), joten nopeinta hakua toteutettaessa täytyy joko luottaa siihen, että optimoija toimii onnistuneesti tai optimoida haku manuaalisesti assembly-kielellä.

Jos teksti muuttuu harvoin ja haku suoritetaan usein (esimerkiksi hakukoneella ), voit indeksoida tekstin. Hakemistohakualgoritmi on nopeampi[ selventää ] Boyer-Moore-algoritmi.

Suurissa aakkosissa (kuten Unicodessa ) stop-merkkitaulukko voi viedä paljon muistia. Tällaisissa tapauksissa joko tiivistetaulukoista luovutaan tai aakkoset jaetaan, kun esimerkiksi 4-tavuinen merkki on kaksitavuisten merkkien pari, tai (joka on yksinkertaisin) käytetään Boyerin muunnelmaa. -Mooren algoritmi ilman stop-merkkien heuristiikkaa.

Boyer-Moore-algoritmiin on olemassa useita muunnelmia, joiden tavoitteena on vielä suurempi kiihtyvyys - esimerkiksi turbo-algoritmi, käänteinen Colussi-algoritmi [10] ja muut.

Katso myös

Muistiinpanot

↑ 12 Boyer , Moore, 1977 .
↑ 1 2 3 4 5 6 Crochemore, Rytter, 2002 .
↑ Cole, 1994 .
↑ Gasfield, 2003 .
↑ 1 2 3 MAXimaalinen :: algo :: Merkkijono Z-funktio ja sen laskenta . Haettu 14. maaliskuuta 2017. Arkistoitu alkuperäisestä 26. huhtikuuta 2017. (määrätön)
↑ 12 Galil , 1979 .
↑ Zhu-Takaoka-algoritmi Arkistoitu 16. joulukuuta 2008 Wayback Machinessa
↑ Turbo-BM-algoritmi Arkistoitu 16. joulukuuta 2008 Wayback Machinessa
↑ Tarkat merkkijonojen sovitusalgoritmit - Johdanto Arkistoitu 16. joulukuuta 2008 Wayback Machinessa
↑ Reverse Colussi -algoritmi Arkistoitu 9. maaliskuuta 2016 Wayback Machinessa

Kirjallisuus

Kormen T. H. , Leyzerson C. E. , Rivest R. L. , Stein K. Algoritmit: rakentaminen ja analyysi = Introduction to Algorithms / toim. S. N. Triguba ; per. englannista. I. V. Krasikov , N. A. Orekhov ,N. Romanov - 2. painos - M .: Williams, 2005. - 801 s. — ISBN 5-8459-0857-4 .
Crochemore M. , Rytter W. Jewels of Stringology. Singapore: World Publishing Scientific Co. Pte. Ltd., 2002. - 310 s. — ISBN 981-02-4782-6 .
Boyer RS , Moore JS Nopea merkkijonohakualgoritmi // ACM:n viestintä . - 1977. - T. 20 , nro 10 . - S. 762-772 . doi :/ 359842.359859 .
Cole R. Tiukat rajat Boyer-Mooren merkkijonovastaavuusalgoritmin monimutkaisuuteen // SIAM Journal on Computing . - 1994. - T. 23 , nro 5 . - S. 1075-1091 . - doi : 10.1137/S0097539791195543 .
Galil Z. Boyer-Mooren merkkijonojen sovitusalgoritmin huonoimman tapauksen ajoajan parantamisesta // ACM:n viestintä . - 1979. - T. 22 , nro 9 . - S. 505-508 . - doi : 10.1145/359146.359148 .
Gasfield D. Merkkijonot, puut ja sekvenssit algoritmeissa: tietojenkäsittelytiede ja laskennallinen biologia = Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology / käänn. englannista. I. V. Romanovski . - Pietari. : Nevskin murre, 2003. - 654 s. — ISBN 5-7940-0103-8 .

jouset
Merkkijonojen samankaltaisuusmitat	Etäisyys Damerausta Loewensteiniin Levenshtein etäisyys Hammingin etäisyys Jaro-Winkler yhtäläisyydet
Alimerkkijonohaku	Boyer-Mooren algoritmi Boyer-Moore-Horspool-algoritmi Knuth-Morris-Pratt-algoritmi Rabin-Karp algoritmi etuliitetoiminto Z-toiminto Algoritmi Aho - Korasik
palindromit	palindromipuu Manakerin algoritmi
Jakson tasaus	Needleman-Wunsha-algoritmi Smith-Waterman-algoritmi
Suffiksirakenteet	Suffiksitaulukko Suffiksiautomaatti suffiksi puu etuliite puu
Muut	jäsentäminen Kuvioiden yhteensopivuus Suurin yhteinen osasarja Suurin yhteinen osamerkkijono