Similitud de cadenas: ¿cómo funciona exactamente Bitap?

Question

Estoy tratando de entender el algoritmo Bitap, pero tengo problemas para entender las razones detrás de los pasos del algoritmo.

entiendo la premisa básica del algoritmo, que es (corríjanme si me equivoco):

Two strings:  PATTERN (the desired string) 
       TEXT (the String to be perused for the presence of PATTERN) 

Two indices:  i (currently processing index in PATTERN), 1 <= i < PATTERN.SIZE 
       j (arbitrary index in TEXT) 

Match state S(x): S(PATTERN(i)) = S(PATTERN(i-1)) && PATTERN[i] == TEXT[j], S(0) = 1 

En términos ingleses, PATTERN.substring(0,i) coincide con una subcadena de texto si la subcadena anterior PATTERN.substring(0, i-1) fue emparejado con éxito y el personaje en PATTERN[i] es el mismo que el personaje en TEXT[j].

Lo que no entiendo es la implementación de cambio de bit de esto. The official paper detailing this algorithm basically lays it out, pero parece que no puedo visualizar lo que se supone que debe suceder. La especificación del algoritmo es sólo los primeros 2 páginas del periódico, pero voy a resaltar las partes importantes:

Aquí está la versión de desplazamiento de bits del concepto:

Aquí está T [texto] para una cadena de búsqueda de ejemplo:

Y aquí es una traza del algoritmo.

En concreto, no entiendo lo que significa la tabla T, y la razón detrás de OR ing una entrada en ella con el estado actual.

Estaría agradecido si alguien puede ayudar a entender lo que está pasando exactamente en

Answer 1

Lo sentimos por no permitir que ninguna otra persona para responder, pero estoy bastante seguro de que he averiguado ahora.

El concepto esencial para descifrar el algoritmo es la representación de los estados de coincidencia (definidos en la publicación original) en binario. El artículo en la publicación original lo explica formalmente; Voy a intentarlo de forma coloquial:

Tengamos STR, que es una Cadena creada con caracteres de un alfabeto dado.

Representemos STR con un conjunto de dígitos binarios: STR_BINARY. El algoritmo requiere que esta representación sea hacia atrás (por lo tanto, la primera letra corresponde al último dígito, la segunda letra con el penúltimo dígito, etc.).

Supongamos que RANDOM se refiere a una cadena con caracteres aleatorios del mismo alfabeto STR se crea desde.

En STR_BINARY, un 0 a un índice dado indica que, RANDOM partidos STR de STR[0] a

STR[(index of letter in STR that the 0 in STR_BINARY corresponds to)]. Los espacios vacíos cuentan como coincidencias. A 1 indica que RANDOM no coincide con STR dentro de esos mismos límites.

El algoritmo se vuelve más simple de aprender una vez que se entiende esto.

Answer 2

T es un poco confuso, ya que normalmente las posiciones número en el patrón de izquierda a derecha:

0 1 2 3 4 
a b a b c 

... mientras que los bits se numeran normalmente de derecha a izquierda.

Pero escribir el patrón hacia atrás por encima de los bits deja claro:

 
    bit: 4 3 2 1 0 

     c b a b a 
T[a] = 1 1 0 1 0 

     c b a b a 
T[b] = 1 0 1 0 1 

     c b a b a 
T[c] = 0 1 1 1 1 

     c b a b a 
T[d] = 1 1 1 1 1 

Bit n de T[x] es 0 si x aparece en la posición n , o 1 si no lo hace.

De manera equivalente, se puede pensar en esto como diciendo que si el carácter actual en la cadena de entrada es x, y se ve un 0 en la posición n de T[x], entonces solamente puede ser posiblemente coincida con el patrón si el partido comenzó n caracteres anteriormente.

---

Ahora al procedimiento correspondiente. Un 0 en el bit n del estado significa que empezamos a coincidir con el patrón n caracteres atrás (donde 0 es el carácter actual). Inicialmente, nada coincide.

[start] 
1 1 1 1 1 

Como consumimos personajes tratando de igualar, el estado se desplaza a la izquierda (que desplaza un cero en el bit a fondo, el bit 0) y O-ed con la entrada de tabla para el carácter actual. El primer carácter es a; Desplazamiento de la izquierda y O-ing en T[a] da:

 a 
1 1 1 1 0 

El bit 0 que se movió en que se conserva, porque un personaje actual de a puede iniciar una coincidencia del patrón. Para cualquier otro carácter, el bit se habría establecido en 1.

El hecho de que el bit 0 del estado sea ahora 0 significa que comenzamos a hacer coincidir el patrón en con el carácter actual; continua, obtenemos:

 a b 
1 1 1 0 1 

... porque el bit 0 se ha desplazado a la izquierda - pensar en él como diciendo que empezamos coincida con el patrón Hace 1 carácter - y T[b] tiene un 0 en la misma posición, contando que ver un b en la posición actual es bueno si empezamos a coincidir con 1 carácter atrás.

a b d 
1 1 1 1 1 

d no se puede encontrar en ningún lado; todos los bits se vuelven a establecer en 1.

a b d a 
1 1 1 1 0 

Como antes.

a b d a b 
1 1 1 0 1 

Como antes.

b d a b a 
1 1 0 1 0 

a es bueno si el partido comenzó bien Hace 2 caracteres o en el carácter actual.

d a b a b 
1 0 1 0 1 

b es bueno si el partido comenzó bien hace 1 ó 3 caracteres. El 0 en el bit 3 significa que casi hemos ajustado todo el patrón ...

a b a b a 
1 1 0 1 0 

... pero el siguiente carácter es a, que no es bueno que el partido comenzó hace 4 caracteres . Sin embargo, las coincidencias más cortas aún pueden ser buenas.

b a b a b 
1 0 1 0 1 

Sigue buscando buena.

a b a b c 
0 1 1 1 1 

Por último, c es bueno si el partido comenzó antes de 4 caracteres. El hecho de que a 0 haya llegado hasta la parte superior significa que tenemos una coincidencia.