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

boyer moore

Question

Estoy tratando de envolver mi cabeza alrededor del 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ígeme 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 en inglés, PATTERN.substring(0,i) coincide con una subcadena de TEXT si la subcadena anterior PATTERN.substring(0, i-1) coincidió con éxito y el carácter en PATTERN[i] es el mismo que el carácter en TEXT[j] .

Lo que no entiendo es la implementación de este cambio de bits. El documento oficial que detalla este algoritmo básicamente lo establece , pero parece que no puedo visualizar lo que se supone que debe continuar. La especificación del algoritmo es solo las 2 primeras páginas del documento , pero resaltaré las partes importantes:

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

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

Y aquí hay un rastro del algoritmo.

Específicamente, no entiendo lo que significa la tabla T y la razón detrás de OR ingresar una entrada en ella con el estado actual.

Estaría agradecido si alguien me puede ayudar a entender qué es exactamente lo que está pasando

Answer 1

Lo siento por no permitir que nadie más responda, pero estoy bastante seguro de que ya lo he descubierto.

El concepto esencial para asimilar el algoritmo es la representación de estados de coincidencia (definidos en la publicación original) en binario. El artículo en el post original lo explica formalmente; Intentaré hacerlo de manera coloquial:

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

Vamos a representar 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 segundo a último dígito, etc.).

Supongamos que RANDOM refiere a una Cadena con caracteres aleatorios del mismo alfabeto desde el que se creó STR .

En STR_BINARY , un 0 en un índice dado indica que, RANDOM coincidir STR de STR[0] con

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

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

Answer 2

T es un poco confuso porque normalmente se numeran las posiciones 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 al revés sobre los bits lo 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

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

De manera equivalente, puede pensar que esto indica que si el carácter actual en la cadena de entrada es x , y ve un 0 en la posición n de T[x] , entonces es posible que solo coincida con el patrón si la coincidencia comenzó con n caracteres. previamente.

Ahora para el procedimiento de coincidencia. Un 0 en el bit n del estado significa que comenzamos 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

A medida que consumimos los caracteres que intentan coincidir, el estado se desplaza a la izquierda (lo que desplaza un cero al bit inferior, bit 0) y se ejecuta con OR en la entrada de la tabla para el carácter actual. El primer personaje es a ; moviéndose a la izquierda y OR-ing en T[a] da:

 a
1 1 1 1 0

El bit 0 que se cambió se conserva, porque un carácter actual de a puede comenzar 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 ahora sea 0 significa que comenzamos a hacer coincidir el patrón en el carácter actual; Continuando, obtenemos:

 a b
1 1 1 0 1

... porque el bit 0 se ha desplazado a la izquierda. Piense en esto como si dijéramos que empezamos a coincidir con el patrón que estaba hace 1 carácter, y T[b] tiene un 0 en la misma posición, lo que nos indica que ver una b en la corriente la posición es buena si empezamos a hacer coincidir 1 carácter hace

 a b d
1 1 1 1 1

d no puede coincidir en ninguna parte; Todos los bits se ponen de nuevo 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 la coincidencia comenzó 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ó hace 1 o 3 caracteres. El 0 en el bit 3 significa que casi hemos igualado todo el patrón ...

a b a b a
1 1 0 1 0

... pero el siguiente carácter es a , lo cual no es bueno si la coincidencia comenzó hace 4 caracteres. Sin embargo, los partidos más cortos aún pueden ser buenos.

b a b a b
1 0 1 0 1

Todavía se ve bien.

a b a b c
0 1 1 1 1

Finalmente, c es bueno si el partido comenzó 4 caracteres antes. El hecho de que un 0 haya llegado hasta el bit superior significa que tenemos una coincidencia.