Bitap

Definición

El algoritmo Bitap es un algoritmo de búsqueda aproximada de patrones en texto, que usa operaciones bitwise para representar el estado de coincidencias entre el patrón y partes del texto.

Originalmente fue pensado como un algoritmo de búsqueda exacta pero puede adaptarse a búsqueda aproximada al permitir una cantidad determinada de errores (considerando inserciones, eliminaciones o sustituciones) lo que es el Bitap Aproximado.

Esta implementación de búsqueda aproximada retorna un acierto si la distancia de Levenshtein entre el patron y un substring del texto es menor a un valor K dado.

Funcionamiento

El algoritmo empieza creando una mascara de bits de los caracteres del patrón a buscar.

Ejemplo para el patrón "ABCA"

Patron	A	B	C	A	Bitmask
Char	b1	b2	b3	b4	b4b3b2b1
A	0	1	1	0	0110
B	1	0	1	1	1101
C	1	1	0	1	1011

Luego para realizar las operaciones de bits y encontrar coincidencias se tiene k+1 vectores de bits de forma(los bits se inicializan en 1):

R[0] = coincidencias con 0 errores
R[1] = coincidencias con 1 error
...
R[k] = coincidencias con K errores.

Luego se recorre el texto en que se esta buscando el patrón, y por cada carácter recorrido se realizan operaciones de bits sobre entre la mascara de bits del carácter actual y todos los vectores de coincidencias bajo estas reglas de actualización:

R[0] = ((R[0] << 1) ) | char_mask( C )
Caso sin errores permitidos: se shiftean los bits del arreglo de coincidencias y se realiza operación Or contra la mascara de bits del carácter que se esta evaluando, si el bit correspondiente a la posición del carácter en el patrón es 1 se detiene el ciclo y se reinicia la búsqueda empezando del carácter consecutivo, si el bit se vuelve 0 se continua ejecutando, si al final del ciclo el bit mas significativo es 0 entonces se encontró el patrón.
Caso con k errores Equivalente al anterior pero en caso de que dentro de un paso el valor del bit correspondiente no cambie a 0 se sigue ejecutando hasta que la cantidad de errores llegue a K.

Ejemplo simple sin errores: Patrón: "ABCA", Texto: "BABCA".

	R[0]	Shift <<	Mask	Operación	Resultado
B	1111	1110	1101	1110 or 1101	1111 X
A	1111	1110	0110	1110 or 0110	1110
B	1110	1100	1101	1100 or 1101	1101
C	1101	1010	1011	1010 or 1011	1011
A	1011	0110	0110	0110 or 0110	0110

Ultimo bit significativo al final de la ejecucion es igual a 0! se encontró el patron dentro del texto.

Implementación

Código en python

def bitap_search_approximate(text: str, pattern: str, max_errors: int):
  """
    Algoritmo Bitap para búsqueda aproximada (fuzzy search)
    :param text: texto donde buscar
    :param pattern: patrón a buscar
    :param max_errors: número máximo de errores permitidos
    :return: lista de posiciones donde se encontró el patrón (aproximadamente)
    """
  m = len(pattern)
  n = len(text)
  if m == 0:
    return []

    # Crear máscaras de bits para cada carácter del patrón
    masks = {}
    for i, ch in enumerate(pattern):
      if ch not in masks:
        masks[ch] = 0
        masks[ch] |= 1 << i  # activa el bit en la posición i

    # Inicializar los vectores R[d] (d = 0..max_errors)
    # Cada bit representa qué prefijos coinciden con <= d errores
    R = [~1 for _ in range(max_errors + 1)]
    match_mask = 1 << (m - 1)
    results = []

    # Iterar sobre cada carácter del texto
    for i, ch in enumerate(text):
      # obtener máscara del carácter actual
      char_mask = masks.get(ch, 0)

      # R[0] (sin errores)
      old_Rd1 = R[0]
      R[0] = ((R[0] << 1) | 1) & char_mask

      # R[d] (con hasta d errores)
      for d in range(1, max_errors + 1):
        tmp = R[d]
        R[d] = (((R[d] << 1) | 1) & char_mask) | (old_Rd1 << 1) | old_Rd1 | R[d - 1]
        old_Rd1 = tmp

        # Si el bit final está en 0, hay coincidencia
        if (R[max_errors] & match_mask) != 0 and i >= m - 1:
          results.append(i - m + 1)

    return results

Referencias

[1] Wikipedia Bitap algorithm, https://en.wikipedia.org/wiki/Bitap_algorith