Bitapový algoritmus - Bitap algorithm

The bitapový algoritmus (také známý jako posun-nebo, shift-and nebo Baeza-Yates – Gonnet algoritmus) je přibližná shoda řetězců algoritmus. Algoritmus říká, zda daný text obsahuje podřetězec, který je „přibližně stejný“ s daným vzorem, kde je přibližná rovnost definována z hlediska Levenshteinova vzdálenost - pokud jsou podřetězec a vzor v dané vzdálenosti k navzájem, pak je algoritmus považuje za rovnocenné. Algoritmus začíná předpočítáním sady bitové masky obsahující jeden bit pro každý prvek vzoru. Pak je schopen dělat většinu práce s bitové operace, které jsou extrémně rychlé.

Bitapový algoritmus je možná nejlépe známý jako jeden ze základních algoritmů Unix nástroj souhlas, napsáno Udi Manber, Sun Wu, a Burra Gopal. Původní práce Manbera a Wu poskytuje rozšíření algoritmu pro řešení fuzzy shody obecně regulární výrazy.

Vzhledem k datovým strukturám požadovaným algoritmem funguje nejlépe na vzorcích menších než je konstantní délka (obvykle délka slova daného stroje) a také upřednostňuje vstupy před malou abecedou. Jakmile je implementován pro danou abecedu a délku slova m, nicméně, jeho provozní doba je zcela předvídatelný - běží Ó (mn) operace, bez ohledu na strukturu textu nebo vzor.

Algoritmus bitap pro přesné vyhledávání řetězců vynalezl Bálint Dömölki v roce 1964[1][2] a rozšířen R. K. Shyamasundarem v roce 1977[3], než je znovuobjeví Ricardo Baeza-Yates a Gaston Gonnet[4] v roce 1989 (jedna kapitola disertační práce prvního autora[5]) který jej také rozšířil na zpracování tříd znaků, zástupných znaků a neshod. V roce 1991 byla prodloužena o Manber a Wu [6][7] zpracovávat také vkládání a mazání (prohledávání celého fuzzy řetězce). Tento algoritmus byl později vylepšen Baeza-Yatesem a Navarro v roce 1996[8] a později Gene Myers pro dlouhé vzory v roce 1998.[9]

Přesné vyhledávání

Algoritmus bitap pro přesné vyhledávání řetězců v plné obecnosti vypadá v pseudokódu takto:

algoritmus bitap_search je    vstup: text jako řetězec. vzor jako řetězec. výstup: tětiva m : = délka (vzor)    -li m = 0 pak        vrátit se text    / * Inicializovat bitové pole R. * / R := Nový pole [m+1] z bit, zpočátku všech 0 R[0] := 1    pro i := 0; i text); i += 1 dělat        / * Aktualizujte bitové pole. * / pro k := m; k ≥ 1; k -= 1 dělat            R[k]: = R[k - 1] & (text[i] = vzor[k - 1])        -li R[m] pak            vrátit se (text + i - m) + 1    vrátit se nula

Bitap se odlišuje od ostatních dobře známých algoritmů prohledávání řetězců ve svém přirozeném mapování na jednoduché bitové operace, jako v následující modifikaci výše uvedeného programu. Všimněte si, že v této implementaci, neintuitivně, každý bit s hodnotou nula označuje shodu a každý bit s hodnotou 1 označuje neshodu. Stejný algoritmus lze napsat s intuitivní sémantikou pro 0 a 1, ale v takovém případě musíme do vnitřní smyčka nastavit R | = 1. V této implementaci využíváme výhody faktu, že posunutí hodnoty doleva posune nuly vpravo, což je přesně to chování, které potřebujeme.

Všimněte si také, že požadujeme CHAR_MAX další bitové masky za účelem převodu (text [i] == vzor [k-1]) podmínka v obecné implementaci do bitových operací. Proto algoritmus bitap funguje lépe, když je aplikován na vstupy přes menší abecedy.

 #zahrnout <string.h> #zahrnout <limits.h>  konst char *bitap_bitwise_search(konst char *text, konst char *vzor) {     int m = strlen(vzor);     nepodepsaný dlouho R;     nepodepsaný dlouho vzor_maska[CHAR_MAX+1];     int i;      -li (vzor[0] == '\0') vrátit se text;     -li (m > 31) vrátit se „Vzor je příliš dlouhý!“;       / * Inicializovat bitové pole R * /     R = ~1;      / * Inicializovat vzorové bitové masky * /     pro (i=0; i <= CHAR_MAX; ++i)         vzor_maska[i] = ~0;     pro (i=0; i < m; ++i)         vzor_maska[vzor[i]] &= ~(1UL << i);      pro (i=0; text[i] != '\0'; ++i) {         / * Aktualizujte bitové pole * /         R |= vzor_maska[text[i]];         R <<= 1;          -li (0 == (R & (1UL << m)))             vrátit se (text + i - m) + 1;     }      vrátit se NULA; }

Fuzzy vyhledávání

Chcete-li provádět fuzzy vyhledávání řetězců pomocí algoritmu bitap, je nutné rozšířit bitové pole R do druhé dimenze. Místo toho, abychom měli jediné pole R které se mění po celé délce textu, nyní máme k odlišná pole R1..k. Pole Ri má zastoupení předpon prefixu vzor které odpovídají jakékoli příponě aktuálního řetězce s i nebo méně chyb. V této souvislosti může být „chybou“ vložení, odstranění nebo nahrazení; vidět Levenshteinova vzdálenost Další informace o těchto operacích.

Níže uvedená implementace funguje fuzzy shoda (návrat prvního zápasu až do k chyby) pomocí algoritmu fuzzy bitap. Věnuje však pozornost pouze substitucím, nikoli vložením nebo odstraněním - jinými slovy, a Hammingova vzdálenost z k. Stejně jako dříve je sémantika 0 a 1 obrácena od jejich konvenčních významů.

 #zahrnout <stdlib.h> #zahrnout <string.h> #zahrnout <limits.h>  konst char *bitap_fuzzy_bitwise_search(konst char *text, konst char *vzor, int k) {     konst char *výsledek = NULA;     int m = strlen(vzor);     nepodepsaný dlouho *R;     nepodepsaný dlouho vzor_maska[CHAR_MAX+1];     int i, d;      -li (vzor[0] == '\0') vrátit se text;     -li (m > 31) vrátit se „Vzor je příliš dlouhý!“;      / * Inicializovat bitové pole R * /     R = malloc((k+1) * velikost *R);     pro (i=0; i <= k; ++i)         R[i] = ~1;      / * Inicializovat vzorové bitové masky * /     pro (i=0; i <= CHAR_MAX; ++i)         vzor_maska[i] = ~0;     pro (i=0; i < m; ++i)         maska_vzorku[vzor[i]] &= ~(1UL << i);      pro (i=0; text[i] != '\0'; ++i) {         / * Aktualizujte bitová pole * /         nepodepsaný dlouho old_Rd1 = R[0];          R[0] |= vzor_maska[text[i]];         R[0] <<= 1;          pro (d=1; d <= k; ++d) {             nepodepsaný dlouho tmp = R[d];             / * Střídání je vše, na čem nám záleží * /             R[d] = (old_Rd1 & (R[d] | vzor_maska[text[i]])) << 1;             old_Rd1 = tmp;         }          -li (0 == (R[k] & (1UL << m))) {             výsledek = (text+i - m) + 1;             přestávka;         }     }      volný, uvolnit(R);     vrátit se výsledek; }

Viz také

Externí odkazy a reference

  1. ^ Bálint Dömölki, Algoritmus pro syntaktickou analýzu, Computational Linguistics 3, Maďarská akademie věd, str. 29–46, 1964.
  2. ^ Bálint Dömölki, Univerzální kompilátorový systém založený na produkčních pravidlech, BIT Numerická matematika, 8 (4), str. 262–275, 1968. doi:10.1007 / BF01933436
  3. ^ R. K. Shyamasundar, Precedence parsing using Dömölki's algorithm, International Journal of Computer Mathematics, 6 (2), str. 105–114, 1977.
  4. ^ Ricardo Baeza-Yates. "Efektivní vyhledávání textu." Disertační práce, University of Waterloo, Kanada, květen 1989.
  5. ^ Udi Manber, Sun Wu. "Rychlé vyhledávání textu s chybami." Technická zpráva TR-91-11. Ústav výpočetní techniky, University of Arizona, Tucson, červen 1991. (gzipovaný PostScript )
  6. ^ Ricardo Baeza-Yates, Gastón H. Gonnet. „Nový přístup k vyhledávání textu.“ Komunikace ACM, 35 (10): str. 74–82, říjen 1992.
  7. ^ Udi Manber, Sun Wu. "Rychlé textové vyhledávání umožňující chyby." Komunikace ACM, 35 (10): s. 83–91, říjen 1992, doi:10.1145/135239.135244.
  8. ^ R. Baeza-Yates a G. Navarro. Rychlejší algoritmus pro přibližnou shodu řetězců. V Dan Hirchsberg a Gene Myers, redaktoři, Kombinatorické porovnávání vzorů (CPM'96), LNCS 1075, strany 1–23, Irvine, CA, červen 1996.
  9. ^ G. Myers. "Rychlý bitový vektorový algoritmus pro přibližnou shodu řetězců založenou na dynamickém programování." Deník ACM 46 (3), květen 1999, 395–415.
  10. libbitap, bezplatná implementace, která ukazuje, jak lze algoritmus snadno rozšířit pro většinu regulárních výrazů. Na rozdíl od výše uvedeného kódu neomezuje délku vzoru.
  11. Ricardo Baeza-Yates, Berthier Ribeiro-Neto. Moderní vyhledávání informací. 1999. ISBN  0-201-39829-X.
  12. bitap.py - Pythonová implementace bitapového algoritmu s úpravami Wu-Manbera.