Binární podřetězcový vyhledávací algoritmus

Binární podřetězcový vyhledávací algoritmus (také bitap algorithm , shift-nebo algorithm ) je podřetězcový vyhledávací algoritmus , který využívá skutečnost, že bitový posun a bitové OR jsou atomické operace v moderních počítačích. Ve skutečnosti se jedná o primitivní vyhledávací algoritmus s trochou optimalizace, díky kterému je v jedné operaci provedeno až 32 porovnání současně (nebo až 64, v závislosti na bitovosti stroje). Snadno převést na přibližné vyhledávání.

Výpočetní složitost  - O (| jehla |·| kupka sena |) operace s extrémně malou konstantou. Pro předzpracování se používá O (| jehla |·|Σ|) operací a paměti , kde Σ je abeceda. Pokud délka vyhledávacího vzoru (ve znacích) nepřesahuje délku strojového slova (v bitech ), je složitost O (| kupka sena |) a O (| jehla |+|Σ|) .

Předpokládá se, že algoritmus vyvinul v roce 1964 Maďar Balint Dömölki. Oblibu si ale získal v 90. letech díky práci Chilana Ricarda Baez-Yatese a Uruguayce Gastona Gonneta. Slavný nástroj pro přibližné vyhledávání je založen na binárním algoritmu agrep.

Nápad

Jako vždy uvažujeme, že jehla („ jehla “) je řetězec, který hledáme, a kupka sena („haystack“) je řetězec, který hledáme. Délky těchto řetězců budeme označovat n a H . Znaky v řetězci jsou číslovány od 1, jako v Pascalu .

Sestavme takovou matici n × H : pokud se i -předpona jehly shoduje s kupkou sena na pozicích j−i+1 ... j , dáme 1 do matice na pozici ( i , j ) . Jinak nula. [1] [2]

kupka sena | 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 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

Vzor je nalezen, pokud je jeden nalezen v posledním řádku této matice. Matici budeme počítat dynamicky, po sloupcích. K tomu si položme otázku: jak převést ( j − 1) sloupec matice na j -tý ?

R [1, j ] = 1, pokud jehla [1] = kupka sena [ j ]. R [2, j ] = 1, pokud jehla [2] = kupka sena [ j ] a R [1, j − 1] = 1. R [3, j ] = 1, pokud jehla [3] = kupka sena [ j ] a R [2, j −1] = 1. R [4, j ] = 1, pokud jehla [4] = kupka sena [ j ] a R [3, j −1] = 1. … R [ n , j ] = 1, pokud jehla [ n ] = kupka sena [ j ] a R [ n −1, j − 1] = 1.

První vzorec napíšeme jako

R [1, j ] = 1, pokud jehla [1] = kupka sena [ j ] a PRAVDA.

Pokud toto vše spojíme do jedné binární n-tice R { j } délky n , dostaneme následující vzorec:

R { j } = (( R { j −1} << 1) | 00…001) & srovnávací_vektor [ kupka sena [ j ]].

Operace << je binární posun doleva , operace & je bitový AND , | - bitově NEBO . Porovnávací_vektor je konstruován následovně: v prvku na i -té pozici je 1, pokud je symbol a na jehlici na této pozici .

abeceda | 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

Toto je předzpracování podřetězce jehly .

Protože na skutečných počítačích s binárním posunem přichází na volné místo 0, často se role jedničky a nuly prohodí. Vzorec se ukazuje

T { j } = ( T { j −1} << 1) | porovnávací_vektor_neg [ kupka sena [ j ]].

Nebo v programovacím jazyce:

T = ( T << 1 ) | porovnávací_vektor_neg [ kupka sena [ j ]];

Odtud název „ Shift-Or “.

Původní text

Xi

Poznámka. Pracujeme s "převrácenými" bity (0 - odpovídá, 1 - ne).

// Velikost abecedy #define ASIZE 256 // Velikost strojového slova #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 ); návrat ( lim ); } /* x - jehla, délka m y - kupka sena, délka n */ void SO ( char * x , int m , char * y , int n ) { unsigned int lim , stav ; nepodepsané intS [ ASIZE ] ; int j ; if ( m > WORD ) error ( "SO: vyhledávací vzor je příliš dlouhý" ); /* Předzpracování */ lim = preSo ( x , m , S ); /* Vyhledávání */ for ( stav = ~ 0 , j = 0 ; j < n ; ++ j ) { stav = ( stav << 1 ) | S [ y [ j ]]; if ( stav < lim ) VÝSTUP ( j - m + 1 ); } }

Přibližná verze vyhledávání

Pro jednoduchost pracujeme s "převrácenými" bity (1 - neodpovídá, 0 - shoduje se). Předpokládá se, že jehla obsahuje nejvýše m chyb v Levenshteinově metrice . Potřebujeme m +1 kopií n-tice T . [3] [4]

q { j , k } = ( T { j −1, k } << 1) | porovnávací_vektor_neg [ kupka sena [ 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 },

kde j \u003d 1 ... H , k \u003d 0 ... m . Vektor T (*, −1) se skládá pouze z jedniček. Hledání je úspěšné, pokud alespoň jeden z vektorů T v řádku n obsahuje nulu. Odpovídající k  je počet chyb.

Porovnání s jinými algoritmy

Výhody

Velmi rychle na podřetězcích, jejichž délka (ve znacích) nepřesahuje délku strojového slova (v bitech). Neexistuje žádná regrese na "špatných" datech.

Algoritmus lze snadno převést na přibližné vyhledávání v Hammingově metrice a dokonce i v metrice Levenshtein , stejně jako na vyhledávání jednoho z několika řetězců [5] .

Nevýhody

Pro přesné vyhledávání nemá žádné zvláštní výhody oproti jiným algoritmům (například Boyer-Moore ).

Není jasné, co dělat na velkých abecedách (jako je Unicode ). Například jeden „dlouhý“ znak lze rozdělit na několik, zatímco na pozicích, které nejsou násobky délky znaku, R neobsahuje jedničku, ale nulu. Nebo můžete použít nějaký druh datové struktury, která by ukládala „ řídké “ pole.

Při přibližném vyhledávání algoritmus označuje konec místa, kde se shodoval. Začátek tohoto umístění je obtížnější najít, což vyžaduje O ( m n ) další paměť .

Verze pro dlouhé podřetězce je poněkud náročnější na programování. V jazycích na vysoké úrovni neexistuje koncept „ carry flag “, takže se musíte buď spolehnout na úspěšnou optimalizaci , nebo ručně optimalizovat kód v assembleru .

Poznámky

  1. ↑ Shift nebo algoritmus . Získáno 8. listopadu 2011. Archivováno z originálu 12. listopadu 2011.
  2. ↑ Popis činnosti algoritmu Shift-OR pro nalezení podřetězce v řetězci / Algoritmy / Habrahabr . Získáno 30. září 2016. Archivováno z originálu 7. srpna 2016.
  3. ↑ Fuzzy vyhledávání v textu a slovníku / Algoritmy / Habrahabr . Získáno 30. září 2016. Archivováno z originálu 7. srpna 2016.
  4. ↑ Implementace bitapového algoritmu v Pythonu s modifikacemi Wu-Manber . Získáno 7. října 2012. Archivováno z originálu 30. ledna 2016.
  5. ↑ K. Fredriksson, S. Grabowski. Průměr-Optimal String Matching. 2008 . Získáno 11. listopadu 2011. Archivováno z originálu 2. června 2016.