Bitap -algoritm - Bitap algorithm
Den bitap algoritm (även känd som skift-eller , skift-och eller Baeza-Yates-Gonnet algoritm) är en approximativ strängmatchningsalgoritm. Algoritmen berättar om en given text innehåller en delsträng som är "ungefär lika" med ett givet mönster, där ungefärlig jämlikhet definieras i termer av Levenshtein -avstånd - om delsträngen och mönstret ligger inom ett givet avstånd k från varandra, då algoritmen anser dem lika. Algoritmen börjar med att beräkna en uppsättning bitmaskar som innehåller en bit för varje element i mönstret. Då kan den göra det mesta av arbetet med bitvisa operationer , som är extremt snabba.
Den bitap algoritmen är kanske mest känd som en av de underliggande algoritmerna för Unix verktyget agrep , skriven av Udi Manber , Sun Wu och Burra Gopal . Manber och Wus originalpapper ger förlängningar av algoritmen för att hantera oklar matchning av allmänna reguljära uttryck .
På grund av att datastrukturerna som krävs av algoritmen utför den bäst på mönster mindre än en konstant längd (typiskt den ordlängd av maskinen i fråga), och även föredrar ingångar över en liten alfabetet. När den väl har implementerats för ett givet alfabet och ordlängd m , är dess körtid dock helt förutsägbar - den körs i O ( mn ) -operationer, oavsett textens struktur eller mönster.
Bitap-algoritmen för exakt strängsökning uppfanns av Bálint Dömölki 1964 och förlängdes av RK Shyamasundar 1977, innan den återuppfanns av Ricardo Baeza-Yates och Gaston Gonnet 1989 (ett kapitel i första författarens doktorsavhandling) som också utvidgades till att hantera klasser av tecken, jokertecken och felaktigheter. 1991 utökades det av Manber och Wu för att hantera även infogningar och raderingar (full suddig strängsökning). Denna algoritm förbättrades senare av Baeza-Yates och Navarro 1996 och senare av Gene Myers för långa mönster 1998.
Exakt sökning
Bitap -algoritmen för exakt strängsökning , i sin helhet, ser ut så här i pseudokod:
algorithm bitap_search is
input: text as a string.
pattern as a string.
output: string
m := length(pattern)
if m = 0 then
return text
/* Initialize the bit array R. */
R := new array[m+1] of bit, initially all 0
R[0] := 1
for i := 0; i < length(text); i += 1 do
/* Update the bit array. */
for k := m; k ≥ 1; k -= 1 do
R[k] := R[k - 1] & (text[i] = pattern[k - 1])
if R[m] then
return (text + i - m) + 1
return null
Bitap skiljer sig från andra välkända strängsökningsalgoritmer i sin naturliga kartläggning till enkla bitvisa operationer, som i följande modifiering av ovanstående program. Lägg märke till att i denna implementering, kontraintuitivt, anger varje bit med värde noll en matchning, och varje bit med värde 1 indikerar en icke-matchning. Samma algoritm kan skrivas med den intuitiva semantiken för 0 och 1, men i så fall måste vi införa en annan instruktion i den inre slingan för att ställa in R |= 1. I denna implementering utnyttjar vi det faktum att ett vänsterförskjutande värde ändrar nollor till höger, vilket är just det beteende vi behöver.
Lägg också märke till att vi behöver CHAR_MAXytterligare bitmaskar för att konvertera (text[i] == pattern[k-1])villkoret i den allmänna implementeringen till bitvisa operationer. Därför fungerar bitapalgoritmen bättre när den appliceras på ingångar över mindre alfabet.
#include <string.h>
#include <limits.h>
const char *bitap_bitwise_search(const char *text, const char *pattern)
{
int m = strlen(pattern);
unsigned long R;
unsigned long pattern_mask[CHAR_MAX+1];
int i;
if (pattern[0] == '\0') return text;
if (m > 31) return "The pattern is too long!";
/* Initialize the bit array R */
R = ~1;
/* Initialize the pattern bitmasks */
for (i=0; i <= CHAR_MAX; ++i)
pattern_mask[i] = ~0;
for (i=0; i < m; ++i)
pattern_mask[pattern[i]] &= ~(1UL << i);
for (i=0; text[i] != '\0'; ++i) {
/* Update the bit array */
R |= pattern_mask[text[i]];
R <<= 1;
if (0 == (R & (1UL << m)))
return (text + i - m) + 1;
}
return NULL;
}
Lurigt sökande
För att utföra suddig strängsökning med hjälp av bitap -algoritmen är det nödvändigt att utöka bitmatrisen R till en andra dimension. Istället för att ha en enda array R som ändras över textens längd har vi nu k distinkta matriser R 1 .. k . Array R i har en representation av prefixen för mönster som matchar valfritt suffix för den aktuella strängen med i eller färre fel. I detta sammanhang kan ett "fel" vara en infogning, radering eller substitution; se Levenshtein -avståndet för mer information om dessa operationer.
Implementeringen nedan utför fuzzy matching (returnerar den första matchningen med upp till k -fel) med hjälp av fuzzy bitap -algoritmen. Det är dock bara uppmärksamt på substitutioner, inte på infogningar eller raderingar - med andra ord ett Hamming -avstånd på k . Som tidigare är semantiken 0 och 1 omvänd från sina konventionella betydelser.
#include <stdlib.h>
#include <string.h>
#include <limits.h>
const char *bitap_fuzzy_bitwise_search(const char *text, const char *pattern, int k)
{
const char *result = NULL;
int m = strlen(pattern);
unsigned long *R;
unsigned long pattern_mask[CHAR_MAX+1];
int i, d;
if (pattern[0] == '\0') return text;
if (m > 31) return "The pattern is too long!";
/* Initialize the bit array R */
R = malloc((k+1) * sizeof *R);
for (i=0; i <= k; ++i)
R[i] = ~1;
/* Initialize the pattern bitmasks */
for (i=0; i <= CHAR_MAX; ++i)
pattern_mask[i] = ~0;
for (i=0; i < m; ++i)
pattern_mask[pattern[i]] &= ~(1UL << i);
for (i=0; text[i] != '\0'; ++i) {
/* Update the bit arrays */
unsigned long old_Rd1 = R[0];
R[0] |= pattern_mask[text[i]];
R[0] <<= 1;
for (d=1; d <= k; ++d) {
unsigned long tmp = R[d];
/* Substitution is all we care about */
R[d] = (old_Rd1 & (R[d] | pattern_mask[text[i]])) << 1;
old_Rd1 = tmp;
}
if (0 == (R[k] & (1UL << m))) {
result = (text+i - m) + 1;
break;
}
}
free(R);
return result;
}
Se även
Externa länkar och referenser
- ^ Bálint Dömölki, En algoritm för syntaktisk analys, Computational Linguistics 3, Hungarian Academy of Science s. 29–46, 1964.
- ^ Bálint Dömölki, Ett universellt kompilatorsystem baserat på produktionsregler,BIT Numerical Mathematics, 8 (4), sid 262–275, 1968.doi:10.1007/BF01933436
- ^ RK Shyamasundar, Prioritetsparsing med Dömölkis algoritm,International Journal of Computer Mathematics, 6 (2) s 105–114, 1977.
- ^ Ricardo Baeza-Yates. "Effektiv textsökning." Doktorsavhandling, University of Waterloo, Kanada, maj 1989.
- ^ Udi Manber, Sun Wu. "Snabb textsökning med fel." Teknisk rapport TR-91-11. Institutionen för datavetenskap,University of Arizona, Tucson, juni 1991. (gzipped PostScript)
- ^ Ricardo Baeza-Yates, Gastón H. Gonnet. "En ny metod för textsökning." Communications of the ACM , 35 (10): s. 74–82, oktober 1992.
- ^ Udi Manber, Sun Wu. "Snabb textsökning som tillåter fel." Communications of the ACM , 35 (10): s. 83–91, oktober 1992,doi:10.1145/135239.135244.
- ^ R. Baeza-Yates och G. Navarro. En snabbare algoritm för ungefärlig strängmatchning. I Dan Hirchsberg och Gene Myers, redaktörer,Combinatorial Pattern Matching(CPM'96), LNCS 1075, sidorna 1–23, Irvine, CA, juni 1996.
- ^ G. Myers. "En snabb bitvektoralgoritm för ungefärlig strängmatchning baserad på dynamisk programmering." Journal of the ACM 46 (3), maj 1999, 395–415.
- libbitap , en gratis implementering som visar hur algoritmen enkelt kan förlängas för de flesta reguljära uttryck. Till skillnad från koden ovan sätter den ingen gräns för mönsterlängden.
- Ricardo Baeza-Yates, Berthier Ribeiro-Neto. Modern informationshämtning . 1999. ISBN 0-201-39829-X .
- bitap.py - Python -implementering av Bitap -algoritm med Wu -Manber -modifieringar.
