Boyer-Moore-Horspool algoritme

Boyer-Moore-Horspool-algoritmen  er en algoritme til at finde en understreng i en streng , en forenklet version af Boyer-Moore-algoritmen . ABMX fungerer bedre end Boyer-Moore algoritmen på tilfældige tekster, den gennemsnitlige score er fra til til et tegn i teksten [1] . Derudover er den beregningsintensive matchende suffiksheuristik udeladt.

Estimatet ( i værste fald på ikke-periodiske skabeloner) for ABMX er dog | nål |·| høstak | (i stedet for 3 | høstak | for Boyer-Moore).

Beskrivelse af algoritmen

Algoritmen er en modifikation af Boyer-Moore-algoritmen . Ideen med algoritmen er denne.

1. Scanning fra venstre mod højre, sammenligning i "sort boks"-tilstand. Som i den primitive algoritme kombineres begyndelsen af ​​teksten og skabelonen, en sammenligning foretages ved hjælp af den sædvanlige " sammenlign hukommelsessektioner " procedure . Hvis alle tegnene i mønsteret matchede de overlejrede tegn i strengen, så er understrengen fundet, og søgningen er slut.

Hvis et tegn i mønsteret ikke matcher strengens tilsvarende karakter, flyttes mønsteret et par tegn til højre. Disse "få" er valgt ud fra en sådan heuristik.

2. Ændret stopsymbol heuristik. Vi tager karakteren af ​​teksten, der dukkede op over det sidste tegn i mønsteret (uanset hvor uoverensstemmelsen skete!). Det er "b" på billedet.

↓ stopkarakter Tekst abadb * * * * abbad mønster Næste abbad-tjek

Vi flytter skabelonen, så bogstavet "b" i skabelonen er under stopsymbolet. Dette implementeres ved hjælp af en offset-tabel: For hvert tegn i alfabetet gemmer vi det maksimalt mulige skift, der ikke springer et stoptegn over. Det vil sige (når linjer nummereres med 1): skift ( c ) = | needle |−lastpos( c , needle [1..| needle |−1]) , hvor lastpos er den sidste forekomst af et tegn i strengen, nål [ a .. b ]  er delstrengsoperationen.

For "abbad"-mønsteret ser bordet sådan ud.

Symbol -en b (Andet)
Partiskhed en 2 5

For symboler, der ikke er inkluderet i skabelonen, sættes offsetværdien lig med længden af ​​skabelonen - 5. Skabelonens sidste symbol tages ikke i betragtning ved beregning af offsettabellen (den er fyldt med looping ).

Det er mere bekvemt at beregne tabellen ved at gennemgå alle skabelonens symboler:

for c=MIN_CHAR..MAX_CHAR skift[c] = |nål| for i=1..|nål|-1 skift[nål[i]] = |nål|-i

Et eksempel på, hvordan algoritmen fungerer

Det ønskede mønster er "abbad" (tabellen til dette mønster er bygget ovenfor).

abeccacbadbabbad abbad

Vi pålægger en prøve på linjen. Det sidste tegn i kildestrengen "c" er ikke indeholdt i mønsteret. Skift mønsteret til højre med 5 positioner i henhold til offsetværdien for "c":

abeccacbadbabbad abbad

Tre tegn i mønsteret matchede, men den fjerde gjorde det ikke. Skift mønsteret til højre med 5 positioner i henhold til offsetværdien for "d":

abeccacbadbabbad abbad

Det sidste tegn i strengen "a" matcher ikke mønstertegnet. Skift mønsteret til højre med 1 i henhold til offsetværdien for "a" og få den ønskede forekomst af mønsteret:

abeccacbadbabbad abbad

Indstillinger

Sandi's algoritme

For stopkarakteren tager vi karakteren efter nålen .

Wrights algoritme

En empirisk algoritme optimeret til engelske tekster. Sammenligner det sidste tegn, så det første, så det midterste, så alle de andre; i tilfælde af mismatch, Horspool skift.

Fordele

Meget hurtigt i gennemsnit[ angiv ] . Let at implementere. Bruger standardfunktionen til at sammenligne hukommelsesområder, som regel optimeret på assembler-niveau for en specifik processor.

Ulemper

Ligesom andre algoritmer i Boyer-Moore-familien er den ikke ændret til omtrentlig søgning, samtidig søgning efter flere strenge.

Regression på "dårlige" data sker noget oftere end i Boyer-Moore-algoritmen. Jo mere forskelligartede karaktererne i kildeteksten er, jo bedre opfører ABMX sig.

Litteratur

Noter

  1. ↑ Horspool-algoritme . Hentet 12. august 2012. Arkiveret fra originalen 29. august 2012.

Links

 Strenge
String lighedsmål
Understrengssøgning
palindromer
Sekvensjustering
Suffiksstrukturer
Andet