modelo - Boyer-Moore heurística de buenos sufijos

modelo heuristico

Question

Entiendo cómo funcionan las heurísticas del mal carácter. Cuando encuentre la letra x no coincidente, simplemente desplace el patrón de modo que la x más a la derecha en el patrón se alinee con la x en la cadena. Y es fácil de implementar en código.

Creo que también entiendo cómo funcionan las heurísticas de buen sufijo. Cuando encontremos un buen sufijo s , encuentre el mismo sufijo en una ubicación diferente en el patrón y muévalo para que el s en el patrón se alinee con el s en la cadena. Pero no entiendo cómo hacerlo en código. ¿Cómo encontramos si existe el mismo sufijo en otro lugar en patrón? ¿Y cómo sabemos su posición? El código:

void bmPreprocess1()
{
int i=m, j=m+1;
f[i]=j;
while (i>0)
{
while (j<=m && p[i-1]!=p[j-1])
{
if (s[j]==0) s[j]=j-i;
j=f[j];
}
i--; j--;
f[i]=j;
}
}

de http://www.iti.fh-flensburg.de/lang/algorithmen/pattern/bmen.htm no tiene sentido para mí ... ¿Podría alguien escribir un pseudo código tan simple como sea posible para esta tarea? ¿O explicar de alguna manera?

Answer 1

Primero, usaré p[i] indicar un carácter en el patrón, m la longitud del patrón, $ el último carácter en el patrón, es decir, $ = p[m-1] .

Hay dos escenarios para el caso 1 de las heurísticas de sufijo bueno.

Situación 1

Considere el siguiente ejemplo,

 leading TEXT cXXXbXXXcXXXcXXX rest of the TEXT
cXXXbXXXcXXXcXXX
^
| mismatch here

Entonces, la sub cadena XXX en el patrón cXXXbXXXcXXXcXXX es el sufijo bueno. El desajuste se produce en el carácter c . Entonces, después del desajuste, ¿deberíamos cambiar 4 a la derecha o 8?

Si cambiamos 4 como se muestra a continuación, entonces volverá a aparecer la misma inestabilidad ( b mismathes c ),

 leading TEXT cXXXbXXXcXXXcXXX rest of the TEXT
cXXXbXXXcXXXcXXX
^
| mismatch occurs here again

Así que en realidad podemos cambiar 8 caracteres a la derecha en esta situación.

Situación 2

Veamos otro ejemplo.

 leading TEXT cXXXcXXXbXXXcXXX rest of the TEXT
cXXXXcXXXbXXXcXXX
^
| mismatch happens here

¿Podemos cambiar 4 u 8 o más aquí? Obviamente, si cambiamos 8 o más, perderemos la oportunidad de hacer coincidir el patrón con el texto. Así que solo podemos cambiar 4 caracteres a la derecha en esta situación.

Entonces, ¿cuál es la diferencia entre estas dos situaciones?

La diferencia es que en el primer caso, el carácter no coincidente c más el sufijo bueno XXX , que es cXXX , es el mismo que el siguiente (contar desde la derecha) para XXX más el carácter anterior. Mientras que en la segunda situación, cXXX no es lo mismo que la próxima coincidencia (contar desde la derecha) más el carácter antes de esa coincidencia.

Por lo tanto, para cualquier BUEN SUFIX (llamémoslo XXX ), debemos determinar el cambio en estas dos situaciones, (1) el carácter (llamémoslo c ) antes del BUEN SUFFIX más el BUEN SUFIX, en el patrón es también coincide con la próxima coincidencia (contar desde la derecha) del sufijo bueno + el carácter anterior, (2) el carácter más el BUEN SUFIX no coincide

Para la situación (1), por ejemplo, si tiene un patrón, 0XXXcXXXcXXXcXXXcXXXcXXX , si después de la primera prueba de c falla, puede desplazar 20 caracteres a la derecha y alinear 0XXX con el texto que se ha probado.

Así es como se calcula el número 20,

 1 2
012345678901234567890123
0XXXcXXXcXXXcXXXcXXXcXXX
^ ^

La posición en la que se produce la discrepancia es 20, la cadena secundaria 0XXX desplazada tomará la posición del 20 al 23. Y 0XXX comienza con la posición 0, por lo que 20 - 0 = 20.

Para la situación (2), como en este ejemplo, 0XXXaXXXbXXXcXXX , si después de la primera prueba de c falla, puede desplazar solo 4 caracteres a la derecha y alinear bXXX con el texto que se ha probado.

Así es como se calcula el número 4 ,

 0123456789012345
0XXXaXXXbXXXcXXX

La posición donde se produce el desajuste es 12, la siguiente subcadena para tomar ese lugar es bXXX que comienza con la posición 8, 12 - 8 = 4. Si establecemos j = 12 i = 8 , entonces el cambio es j - i , que es s[j] = j - i; en el codigo

Frontera

Para considerar todo el sufijo bueno, primero debemos entender qué se llama un border . Un borde es una subcadena que es tanto un prefijo proper como un sufijo proper de una cadena. Por ejemplo, para una cadena XXXcXXX , X es un borde, XX es un borde, XXX también. Pero XXXc no lo es. Necesitamos identificar el punto de inicio del borde más ancho del sufijo del patrón y esta información se guarda en la matriz f[i] .

¿Cómo determinar f[i] ?

Supongamos que sabemos f[i] = j y para todos los demás f[k] s con i < k < m , lo que significa que el borde más ancho para el sufijo que comienza desde la posición i comenzó en la posición j . Queremos encontrar f[i-1] basado en f[i] .

Por ejemplo, para un patrón aabbccaacc , en la posición i=4 , el sufijo es ccaacc , y el borde más ancho para eso es cc ( p[8]p[9] ), entonces j = f[i=4] = 8 . Y ahora queremos saber f[i-1] = f[3] según la información que tenemos para f[4] , f[5] , ... Para f[3] , el sufijo ahora es bccaacc . En la posición, j-1=7 , es a ! = p[4-1] que es b . Así que bcc no es una frontera.

Sabemos que cualquier borde con ancho> = 1 de bccaacc tiene que comenzar con b más el borde del sufijo que comienza con positin j = 8 , que es cc en este ejemplo. cc tiene el borde más ancho c en la posición j = f[8] que es 9 . Entonces continuamos nuestra búsqueda comparando p[4-1] contra p[j-1] . Y no vuelven a ser iguales. Ahora el sufijo es p[9] = c y solo tiene un borde de longitud cero en la posición 10 . entonces ahora j = f[9] y es 10 . Entonces continuamos nuestra búsqueda comparando p[4-1] contra p[j-1] , no son iguales y ese es el final de la cadena. Entonces f[3] solo tiene un borde de longitud cero que lo hace igual a 10.

Describir el proceso en un sentido más general.

Por lo tanto, f[i] = j significa algo como esto,

 Position: 012345 i-1 i j - 1 j m
pattern: abcdef ... @ x ... ? x ... $ 

¿Si el carácter @ que en la posición i - 1 es lo mismo que el carácter ? en la posición j - 1 , sabemos que f[i - 1] = j - 1; , o --i; --j; f[i] = j; --i; --j; f[i] = j; . El borde es sufijo @x ... $ partir de la posición j-1 .

¿Pero si el carácter @ que en la posición i - 1 es diferente del carácter ? En la posición j - 1 , debemos continuar nuestra búsqueda hacia la derecha. Sabemos dos hechos: (1) sabemos que ahora el ancho del borde debe ser más pequeño que el que comenzó en la posición j , es decir, más pequeño que x...$ . Segundo, el borde debe comenzar con @... y terminar con el carácter $ o podría estar vacío.

Sobre la base de estos dos hechos, continuamos nuestra búsqueda dentro de la cadena secundaria x ... $ (de la posición j a m) para un borde que comience con x . Entonces el siguiente borde debe estar en j que es igual a f[j]; , es decir, j = f[j]; . Luego comparamos el carácter @ con el carácter anterior a x , que está en j-1 . Si son iguales, encontramos que el borde, si no, continúa el proceso hasta j> m. Este proceso se muestra en el siguiente código,

 while (j<=m && p[i-1]!=p[j-1])
{
j=f[j];
}
i--; j--;
f[i]=j;

Ahora mire la condición p[i -1] != P [j-1] , this is what we talked about in situation (2), p [i] matches p [j] , but p [i -1]! = p[j-1] , entonces cambiamos de i a j , eso es s[j] = j - i; .

Ahora lo único que queda por explicar no es la prueba if (s[j] == 0) que se producirá cuando un sufijo más corto tenga el mismo borde. Por ejemplo, tienes un patrón

 012345678
addbddcdd

Cuando calcule f[i - 1] e i = 4 , configurará s[7] . Pero cuando calcula f[i-1] para i = 1 , configurará s[7] nuevamente si no tiene la prueba if (s[j] == 0) . Esto significa que si tiene una discrepancia en la posición 6 , desplace 3 hacia la derecha (alinee bdd con las posiciones ocupadas por cdd ), no 6 (no cambie hasta que add a las posiciones ocupadas por cdd ).

Los comentarios para el código.

 void bmPreprocess1()
{
// initial condition, set f[m] = m+1;
int i=m, j=m+1;
f[i]=j;
// calculate f[i], s[j] from i = m to 0.
while (i>0)
{
// at this line, we know f[i], f[i+1], ... f[m].
while (j<=m && p[i-1]!=p[j-1]) // calculate the value of f[i-1] and save it to j-1
{
if (s[j]==0) s[j]=j-i; // if s[j] is not occupied, set it.
j=f[j]; // get the start position of the border of suffix p[j] ... p[m-1]
}
// assign j-1 to f[i-1]
i--; j--;
f[i]=j;
}
}