Boyer-Moore-Horspool-algoritmi

Boyer-Moore-Horspool-algoritmi  on algoritmi alimerkkijonon löytämiseksi merkkijonosta , yksinkertaistettu versio Boyer-Moore-algoritmista . ABMX toimii paremmin kuin Boyer-Moore-algoritmi satunnaisissa teksteissä, keskimääräinen pistemäärä on välillä - yhteen tekstin merkkiin [1] . Lisäksi laskennallisesti intensiivinen sovituspääteheuristiikka jätetään pois.

Kuitenkin arvio ( pahimmassa tapauksessa ei-jaksollisilla malleilla) ABMX:lle on | neula |·| heinäsuovasta | (3 sijasta | heinäsuovasta | Boyer-Moorelle).

Algoritmin kuvaus

Algoritmi on muunnos Boyer-Moore-algoritmista . Algoritmin idea on tämä.

1. Skannaus vasemmalta oikealle, vertailu "musta laatikko" -tilassa. Kuten primitiivisessä algoritmissa, tekstin alku ja malli yhdistetään, vertailu tehdään tavallisella " vertaa muistiosia " -menettelyä . Jos kaikki kuvion merkit vastasivat merkkijonon päällekkäisiä merkkejä, osamerkkijono on löydetty ja haku on päättynyt.

Jos jokin kuvion merkki ei vastaa merkkijonon vastaavaa merkkiä, kuviota siirretään muutaman merkin verran oikealle. Nämä "harvat" valitaan tällaisen heuristiikan mukaan.

2. Pysäytyssymbolin heuristiikka muutettu. Otamme tekstin luonteen, joka ilmestyi kuvion viimeisen merkin yläpuolelle (riippumatta siitä, missä yhteensopimattomuus tapahtui!). Kuvassa on "b".

↓ pysäytyssymboli Teksti abadb * * * * lakattu kuvio Seuraava abbad check

Siirrämme mallia niin, että mallin kirjain "b" on stop-symbolin alla. Tämä toteutetaan offset-taulukon avulla: tallennamme jokaiselle aakkoston merkille suurimman mahdollisen siirtymän, joka ei ohita stop-merkkiä. Eli (kun numeroidaan rivejä 1:llä): siirto ( c ) = | neula |−lastpos( c , neula [1..| neula |−1]) , jossa lastpos on merkin viimeinen esiintyminen merkkijonossa, neula [ a .. b ]  on osamerkkijonotoiminto.

"Abbad"-kuviolle taulukko näyttää tältä.

Symboli a b (muu)
Puolueellisuus yksi 2 5

Symboleille, jotka eivät sisälly malliin, offset-arvo asetetaan yhtä suureksi kuin mallipohjan pituus - 5. Mallin viimeistä symbolia ei oteta huomioon laskettaessa offset-taulukkoa (se on täynnä silmukoita ).

Taulukon laskeminen on helpompaa käymällä läpi kaikki kuvion symbolit:

c=MIN_CHAR..MAX_CHAR vaihto[c] = |neula| i=1..|neula|-1 vaihto[neula[i]] = |neula|-i

Esimerkki algoritmin toiminnasta

Haluttu kuvio on "abbad" (tämän kuvion taulukko on rakennettu yllä).

abeccacbadbabbad Abad

Asetamme näytteen linjalle. Lähdemerkkijonon "c" viimeinen merkki ei sisälly kuvioon. Siirrä kuviota oikealle 5 asemaa "c":n siirtymäarvon mukaan:

abeccacbadbabbad Abad

Kuvion kolme merkkiä sopivat, mutta neljäs ei. Siirrä kuviota oikealle 5 asemaa "d":n siirtymäarvon mukaan:

abeccacbadbabbad Abad

Merkkijonon "a" viimeinen merkki ei vastaa kuviomerkkiä. Siirrä kuviota oikealle 1:llä "a":n siirtymäarvon mukaan ja hanki kuvion haluttu esiintyminen:

abeccacbadbabbad Abad

Vaihtoehdot

Sandin algoritmi

Pysäytysmerkillä otamme neulaa seuraavan merkin .

Wrightin algoritmi

Empiirinen algoritmi , joka on optimoitu englanninkielisille teksteille. Vertaa viimeistä merkkiä, sitten ensimmäistä, sitten keskimmäistä ja sitten kaikkia muita; yhteensopimattomuuden sattuessa Horspool-vuoro.

Edut

Keskimäärin erittäin nopea[ määritä ] . Helppo toteuttaa. Käyttää vakiotoimintoa muistialueiden vertailuun, pääsääntöisesti optimoituna kokoonpanotasolla tietylle prosessorille.

Haitat

Kuten muutkin Boyer-Moore-perheen algoritmit, sitä ei ole muokattu likimääräistä hakua varten, useiden merkkijonojen samanaikaista hakua varten.

Regressio "huonoihin" tietoihin tapahtuu jonkin verran useammin kuin Boyer-Moore-algoritmissa. Mitä monipuolisempia merkkejä lähdetekstissä on, sitä paremmin ABMX käyttäytyy.

Kirjallisuus

Muistiinpanot

  1. ↑ Horspool-algoritmi . Haettu 12. elokuuta 2012. Arkistoitu alkuperäisestä 29. elokuuta 2012.

Linkit

 jouset
Merkkijonojen samankaltaisuusmitat
Alimerkkijonohaku
palindromit
Jakson tasaus
Suffiksirakenteet
Muut