| FazBrowse Wikipedia Viewer | Main Page | | |
| Viewing: https://en.wikipedia.org/wiki/Bitap_algorithm |
The bitap algorithm (also known as the shift-or, shift-and or Baeza-Yates–Gonnet algorithm) is an approximate string matching algorithm. The algorithm tells whether a given text contains a substring which is "approximately equal" to a given pattern, where approximate equality is defined in terms of Levenshtein distance\n \n const char *bitap_bitwise_search(const char *text, const char *pattern)\n {\n int m = strlen(pattern);\n unsigned long R;\n unsigned long pattern_mask[CHAR_MAX+1];\n int i;\n \n if (m == 0) return text;\n if (m > 31) throw \"The pattern is too long!\";\n \n /* Initialize the bit array R */\n R = ~1;\n \n /* Initialize the pattern bitmasks */\n for (i=0; i <= CHAR_MAX; ++i)\n pattern_mask[i] = ~0;\n for (i=0; i < m; ++i)\n pattern_mask[pattern[i]] &= ~(1UL << i);\n \n for (i=0; text[i] != '\\0'; ++i) {\n /* Update the bit array */\n R |= pattern_mask[text[i]];\n R <<= 1;\n \n if (0 == (R & (1UL << m)))\n return (text + i - m) + 1;\n }\n \n return NULL;\n }\n"}}'>#include<string.h> #include<limits.h> constchar*bitap_bitwise_search(constchar*text,constchar*pattern) { intm=strlen(pattern); unsignedlongR; unsignedlongpattern_mask[CHAR_MAX+1]; inti; if(m==0)returntext; if(m>31)throw"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; } returnNULL; }
To perform fuzzy string searching using the bitap algorithm, it is necessary to extend the bit array R into a second dimension. Instead of having a single array R that changes over the length of the text, we now have k distinct arrays R1..k. Array Ri holds a representation of the prefixes of pattern that match any suffix of the current string with i or fewer errors. In this context, an "error" may be an insertion, deletion, or substitution; see Levenshtein distance for more information on these operations.
The implementation below performs fuzzy matching (returning the first match with up to k errors) using the fuzzy bitap algorithm. However, it only pays attention to substitutions, not to insertions or deletions^ Bálint Dömölki, A universal compiler system based on production rules, BIT Numerical Mathematics, 8(4), pp 262–275, 1968. doi:10.1007/BF01933436
| View original on Wikipedia | Back | FazBrowse Home |