Algoritm de căutare binar subșir

Un algoritm de căutare binar subșir (de asemenea , algoritm bitap , shift-sau algoritm ) este un algoritm de căutare subșir care exploatează faptul că deplasarea biților și OR pe biți sunt operații atomice în computerele moderne. De fapt, acesta este un algoritm de căutare primitiv cu puțină optimizare, datorită căruia se fac până la 32 de comparații simultan într-o singură operație (sau până la 64, în funcție de bitness-ul mașinii). Convertit cu ușurință în căutarea aproximativă.

Complexitate computațională - O (| ac |·| carul de fân |) operații cu o constantă extrem de mică. Operațiile și memoria O (| ac |·|Σ|) sunt folosite pentru preprocesare , unde Σ este alfabetul. Dacă lungimea modelului de căutare (în caractere) nu depășește lungimea cuvântului mașină (în biți ), complexitatea este O (| car de fân |) și , respectiv, O (| ac |+|Σ|) .

Se presupune că algoritmul a fost dezvoltat în 1964 de ungur Balint Dömölki. Dar a câștigat popularitate în anii 1990 datorită muncii chilianului Ricardo Baez-Yates și uruguayanului Gaston Gonnet. Celebrul utilitar de căutare aproximativă se bazează pe algoritmul binar agrep.

Idee

Ca întotdeauna, considerăm că acul („ ac ”) este sfoara pe care o căutăm, iar carul de fân („carul de fân”) este sfoara pe care o căutăm. Lungimile acestor șiruri vor fi notate cu n și H . Caracterele dintr-un șir sunt numerotate de la 1, ca în Pascal .

Să construim o astfel de matrice n × H : dacă i -prefixul acului coincide cu carul de fân în pozițiile j−i+1 ... j , puneți 1 în matrice la poziția ( i , j ) . Altfel, zero. [1] [2]

carul de fân | 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 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 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 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 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 0 A | 0 0 0 0 0 0 0 0 0 0 0 1 0 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 0

Modelul este găsit dacă unul se găsește în ultimul rând al acestei matrice. Vom calcula matricea dinamic, pe coloane. Pentru a face acest lucru, să ne punem o întrebare: cum să transformăm ( j − 1) -a coloană a matricei în j - a ?

R [1, j ] = 1 dacă acul [1] = carul de fân [ j ]. R [2, j ] = 1 dacă acul [2] = carul de fân [ j ] și R [1, j − 1] = 1. R [3, j ] = 1 dacă acul [3] = carul de fân [ j ] și R [2, j −1] = 1. R [4, j ] = 1 dacă acul [4] = carul de fân [ j ] și R [3, j −1] = 1. … R [ n , j ] = 1 dacă acul [ n ] = carul de fân [ j ] și R [ n −1, j − 1] = 1.

Scriem prima formulă ca

R [1, j ] = 1 dacă acul [1] = carul de fân [ j ] și TRUE.

Dacă combinăm toate acestea într-un tuplu binar R { j } de lungime n , obținem următoarea formulă:

R { j } = (( R { j −1} << 1) | 00…001) & vector_comparație [ carul de fân [ j ]].

Operația << este o deplasare binară la stânga , operația & este un AND , | - pe biți SAU . Vectorul_comparație este construit astfel: în elementul din poziția i -a, există 1, dacă simbolul a se află în acul în această poziție . $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

Aceasta este preprocesarea subșirului de ac .

Deoarece pe computerele reale, cu o schimbare binară, 0 vine pe locul vacant, adesea rolurile unu și zero sunt inversate. Formula se dovedește

T { j } = ( T { j −1} << 1) | comparison_vector_neg [ carul de fân [ j ]].

Sau, într-un limbaj de programare:

T = ( T << 1 ) | comparison_vector_neg [ carul de fan [ j ]];

De aici și numele „ Shift-Or ”.

Textul original

Xi

Notă. Lucrăm cu biți „inversați” (0 - potriviți, 1 - nu).

// Mărimea alfabetului #define ASIZE 256 // Mărimea cuvântului automat #define WORD (dimensiunea(unsigned int)*8) int preSo ( char * x , int m , unsigned int S []) { unsigned int j , lim ; int i ; pentru ( i = 0 ; i < ASIZE ; ++ i ) S [ i ] = ~ 0u ; pentru ( lim = i = 0 , j = 1 ; i < m ; ++ i , j <<= 1 ) { S [ x [ i ]] &= ~ j ; lim |= j ; } lim = ~ ( lim >> 1 ); întoarcere ( lim ); } /* x - ac, lungime m y - car de fân, lungime n */ void SO ( char * x , int m , char * y , int n ) { unsigned int lim , stare ; unsigned intS [ ASIZE ] ; int j ; if ( m > WORD ) eroare ( "SO: model de căutare prea lung" ); /* Preprocesare */ lim = preSo ( x , m , S ); /* Căutare */ pentru ( stare = ~ 0 , j = 0 ; j < n ; ++ j ) { stare = ( stare << 1 ) | S [ y [ j ]]; if ( stare < lim ) IEȘIRE ( j - m + 1 ); } }

Versiunea de căutare aproximativă

Pentru simplitate, lucrăm cu biți „inversați” (1 - nu se potrivește, 0 - se potrivește). Se presupune că acul conține cel mult m erori în metrica Levenshtein . Avem nevoie de m +1 copii ale tuplului T . [3] [4]

q { j , k } = ( T { j −1, k } << 1) | comparison_vector_neg [ carul de fan [ 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 },

unde j \u003d 1 ... H , k \u003d 0 ... m . Vectorul T (*, −1) constă numai din unii. Căutarea are succes dacă cel puțin unul dintre vectorii T din rândul n conține zero. k corespunzător este numărul de erori.

Comparație cu alți algoritmi

Beneficii

Foarte rapid pe subșiruri a căror lungime (în caractere) nu depășește lungimea unui cuvânt de mașină (în biți). Nu există regresie pentru datele „rele”.

Algoritmul poate fi ușor convertit într-o căutare aproximativă în metrica Hamming și chiar în metrica Levenshtein , precum și pentru a căuta unul din mai multe șiruri [5] .

Dezavantaje

Pentru căutarea exactă, nu are avantaje speciale față de alți algoritmi (de exemplu, Boyer-Moore ).

Nu este clar ce să faci cu alfabete uriașe (cum ar fi Unicode ). De exemplu, un caracter „lung” poate fi împărțit în mai multe, în timp ce în poziții care nu sunt multipli ai lungimii caracterului, R conține nu unul, ci zero. Sau puteți utiliza un fel de structură de date care ar stoca o matrice „ rară ”.

Într-o căutare aproximativă, algoritmul indică sfârșitul locului în care s-a potrivit. Începutul acestei locații este mai greu de găsit, necesitând O ( m n ) memorie suplimentară .

Versiunea pentru subșiruri lungi este ceva mai dificil de programat. Nu există conceptul de „ bandagul de transport ” în limbile de nivel înalt, așa că trebuie fie să vă bazați pe optimizarea de succes , fie să optimizați manual codul în asamblare .

Note

↑ Shift sau algoritm . Consultat la 8 noiembrie 2011. Arhivat din original pe 12 noiembrie 2011. (nedefinit)
↑ Descrierea funcționării algoritmului Shift-OR pentru găsirea unui subșir într-un șir / Algoritmi / Habrahabr . Preluat la 30 septembrie 2016. Arhivat din original la 7 august 2016. (nedefinit)
↑ Căutare neclară în text și dicționar / Algoritmi / Habrahabr . Preluat la 30 septembrie 2016. Arhivat din original la 7 august 2016. (nedefinit)
↑ Implementarea Python a algoritmului bitap cu modificări Wu-Manber . Consultat la 7 octombrie 2012. Arhivat din original la 30 ianuarie 2016. (nedefinit)
↑ K. Fredriksson, S. Grabowski. Potrivire medie-optimă șiruri. 2008 . Consultat la 11 noiembrie 2011. Arhivat din original pe 2 iunie 2016. (nedefinit)