Eu extrai o código contido nesta resposta deste artigo, e a análise do código é de minha autoria.
Segue abaixo o código em C para acompanhar o raciocínio da análise. Observação:
Neste código os valores de 1 e 0 são semanticamente opostos.
#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;
}
Análise
A inicialização ocorre até o terceiro loop for
. O terceiro loop faz com que todas as posições de análise de erros para cada tentativa indiquem "falha" para efeito de inicialização.
O último for
, que possui um for
aninhado, faz comparações caractere-a-caractere para verificar erros. O for
interno limita o escopo de verificações à distância máxima estabelecida na chamada do algoritmo.
Uma vez que o vetor R esteja todo preenchido de 1
, a palavra resultado é retornada.