Binær understreng søgealgoritme

En binær understrengssøgningsalgoritme (også bitapalgoritme , shift-eller algoritme ) er en understrengssøgningsalgoritme , der udnytter det faktum, at bitforskydning og bitvise OR er atomoperationer i moderne computere. Faktisk er dette en primitiv søgealgoritme med lidt optimering, på grund af hvilken der foretages op til 32 sammenligninger samtidigt i en operation (eller op til 64, afhængigt af maskinens bithed). Nemt konverteret til omtrentlig søgning.

Beregningsmæssig kompleksitet - O (| nål |·| høstak |) operationer med en ekstremt lille konstant. O (| nål |·|Σ|) operationer og hukommelse bruges til forbehandling , hvor Σ er alfabetet. Hvis længden af søgemønsteret (i tegn) ikke overstiger længden af maskinordet (i bits ), er kompleksiteten henholdsvis O (| høstak |) og O (| nål |+|Σ|) .

Det antages, at algoritmen blev udviklet i 1964 af ungareren Balint Dömölki. Men det vandt popularitet i 1990'erne takket være arbejdet fra chileneren Ricardo Baez-Yates og uruguayanske Gaston Gonnet. Det berømte omtrentlige søgeværktøj er baseret på den binære algoritme agrep.

Idé

Som altid mener vi, at nål (" nål ") er den streng, vi leder efter, og høstak ("høstak") er den streng, vi leder efter. Længderne af disse strenge vil blive angivet med n og H . Tegnene i en streng er nummereret fra 1, som i Pascal .

Lad os bygge sådan en n × H- matrix : Hvis nålens i - præfiks falder sammen med høstakken ved positionerne j−i+1 ... j , indsæt 1 i matricen ved position ( i , j ) . Ellers nul. [1] [2]

høstak | G C A T C G C A G A G A G T A T A C A G T A C G -------------------------------------------------- ------ n Г | 1 0 0 0 0 1 0 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 e C | 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 e A | 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 d Г | 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 l A | 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 e Г | 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 A | 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 G | 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0

Mønsteret findes, hvis der findes et i den sidste række af denne matrix. Vi vil beregne matrixen dynamisk efter kolonner. For at gøre dette, lad os stille os selv et spørgsmål: hvordan gør vi ( j − 1) kolonnen i matricen til j - th ?

R [1, j ] = 1 hvis nål [1] = høstak [ j ]. R [2, j ] = 1 hvis nål [2] = høstak [ j ] og R [1, j − 1] = 1. R [3, j ] = 1 hvis nål [3] = høstak [ j ] og R [2, j −1] = 1. R [4, j ] = 1 hvis nål [4] = høstak [ j ] og R [3, j −1] = 1. … R [ n , j ] = 1 hvis nål [ n ] = høstak [ j ] og R [ n −1, j − 1] = 1.

Vi skriver den første formel som

R [1, j ] = 1 hvis nål [1] = høstak [ j ] og SAND.

Hvis vi kombinerer alt dette til en binær tupel R { j } af længden n , får vi følgende formel:

R { j } = (( R { j −1} << 1) | 00…001) & sammenligningsvektor [ høstak [ j ]].

<<-operationen er et binært venstreskift , &-operationen er en bitvis AND , | - bitvis ELLER . Comparison_vector er konstrueret som følger: i elementet i den i -te position er der 1, hvis symbolet a er i nålen i denne position . $a\in\Sigma$

alfabet | A G T C ----------- n Г | 0 1 0 0 e C | 0 0 0 1 e A | 1 0 0 0 d Г | 0 1 0 0 l A | 1 0 0 0 e Г | 0 1 0 0 A | 1 0 0 0 G | 0 1 0 0

Dette er forbehandlingen af nåleunderstrengen .

Da der på rigtige computere, med et binært skift, kommer 0 til den ledige plads, er rollerne som en og nul ofte byttet om. Formlen viser sig

T { j } = ( T { j −1} << 1) | comparison_vector_neg [ høstak [ j ]].

Eller på et programmeringssprog:

T = ( T << 1 ) | comparison_vector_neg [ høstak [ j ]];

Deraf navnet " Shift-Or ".

Originaltekst

Xi

Bemærk. Vi arbejder med "inverterede" bits (0 - matcher, 1 - gør ikke).

// Alfabetstørrelse #define ASIZE 256 // Maskinordstørrelse #define WORD (sizeof(unsigned int)*8) int preSo ( char * x , int m , unsigned int S []) { unsigned int j , lim ; int i ; for ( i = 0 ; i < ASIZE ; ++ i ) S [ i ] = ~ 0u ; for ( lim = i = 0 , j = 1 ; i < m ; ++ i , j <<= 1 ) { S [ x [ i ]] &= ~ j ; lim |= j ; } lim = ~ ( lim >> 1 ); returnere ( lim ); } /* x - nål, længde m y - høstak, længde n */ void SO ( char * x , int m , char * y , int n ) { unsigned int lim , state ; usignerede intS [ ASIZE ] ; int j ; if ( m > WORD ) fejl ( "SO: søgemønster for langt" ); /* Forbehandling */ lim = preSo ( x , m , S ); /* Søg */ for ( tilstand = ~ 0 , j = 0 ; j < n ; ++ j ) { tilstand = ( tilstand << 1 ) | S [ y [ j ]]; if ( tilstand < lim ) OUTPUT ( j - m + 1 ); } }

Omtrentlig søgeversion

For nemheds skyld arbejder vi med "inverterede" bits (1 - matcher ikke, 0 - matcher). Det antages, at nålen højst indeholder m fejl i Levenshtein-metrikken . Vi har brug for m +1 kopier af tuple T . [3] [4]

q { j , k } = ( T { j −1, k } << 1) | comparison_vector_neg [ høstak [ j ]]; Ins { j , k } = q { j , k } & T { j −1, k − 1}; Del { j , k } = q { j , k } & ( T { j , k -1} << 1); Repl { j , k } = q { j , k } & ( T { j −1, k − 1} << 1); T { j , k } = Ins { j , k } & Del { j , k } & Repl { j , k },

hvor j \u003d 1 ... H , k \u003d 0 ... m . Vektoren T (*, −1) består kun af enere. Søgningen er vellykket, hvis mindst én af vektorerne T i række n indeholder nul. Det tilsvarende k er antallet af fejl.

Sammenligning med andre algoritmer

Fordele

Meget hurtigt på understrenge, hvis længde (i tegn) ikke overstiger længden af et maskinord (i bits). Der er ingen regression på "dårlige" data.

Algoritmen kan let konverteres til en omtrentlig søgning i Hamming-metrikken og endda i Levenshtein-metrikken , samt til at søge efter en af flere strenge [5] .

Ulemper

For nøjagtig søgning har den ikke nogen særlige fordele i forhold til andre algoritmer (for eksempel Boyer-Moore ).

Det er ikke klart, hvad man skal gøre på store alfabeter (som Unicode ). For eksempel kan et "langt" tegn opdeles i flere, mens R i positioner, der ikke er multipla af tegnets længde, ikke indeholder én, men nul. Eller du kan bruge en form for datastruktur, der ville gemme et " sparsomt " array.

I en omtrentlig søgning angiver algoritmen slutningen af det sted, hvor den matchede. Starten på denne placering er sværere at finde, hvilket kræver O ( m n ) ekstra hukommelse .

Udgaven til lange understrenge er noget sværere at programmere. Der er intet koncept for " bæreflag " i sprog på højt niveau, så du skal enten stole på vellykket optimering eller manuelt optimere koden i assembler .

Noter

↑ Skift eller algoritme . Hentet 8. november 2011. Arkiveret fra originalen 12. november 2011. (ubestemt)
↑ Beskrivelse af driften af Shift-OR-algoritmen til at finde en understreng i en streng / Algoritmer / Habrahabr . Hentet 30. september 2016. Arkiveret fra originalen 7. august 2016. (ubestemt)
↑ Fuzzy søgning i tekst og ordbog / Algoritmer / Habrahabr . Hentet 30. september 2016. Arkiveret fra originalen 7. august 2016. (ubestemt)
↑ Python-implementering af bitap-algoritmen med Wu-Manber-modifikationer . Hentet 7. oktober 2012. Arkiveret fra originalen 30. januar 2016. (ubestemt)
↑ K. Fredriksson, S. Grabowski. Gennemsnitlig-Optimal String Matching. 2008 . Hentet 11. november 2011. Arkiveret fra originalen 2. juni 2016. (ubestemt)