Cómo ordenar los sufijos de matriz en la clasificación de bloques

Question

Estoy leyendo el algoritmo de clasificación del bloque de las madrigueras y el papel de ruedas. Este es un paso del algoritmo:

Supongamos que S = Abracadabra

Inicializar una matriz w de n palabras w [0, ..., n - 1], tal que w [i] contiene los caracteres s '[i, ..., i + k - 1] dispuestos para que las comparaciones enteras en Las palabras están de acuerdo con las comparaciones lexicográficas en las cuerdas K-caracteres. Empacar caracteres en palabras tiene dos beneficios: permite que dos prefijos se comparen k bytes a la vez utilizando accesos de memoria alineados, y permite eliminar muchos casos lentos

(Nota: S' es el original S con k EOF personajes que se adjuntan, K es el número de caracteres que encajan en una palabra de máquina (estoy en una máquina de 32 bits, así que k=4)

EOF = '$'

Corrígeme si me equivoco:

S'= abracadabra$$$$  
W= abra brac raca acad cada adab dabr abra bra$ ra$$ a$$$

Entonces, el algoritmo dice que debes ordenar la matriz de sufijo de S (llamado V), por indexación en la matriz W.

No entiendo completamente cómo puede clasificar los sufijos indexando en W. Por ejemplo: en algún momento de la clasificación, suponga que obtienes dos sufijos, i y j, y tienes que compararlos. Dado que estás indexando en W, estás revisando 4 caracteres en ese momento.
Supongamos que tienen ambos los mismos primeros 4 caracteres. Luego, tendría que verificar, para cada sufijo sus próximos 4 caracteres, y lo hace accediendo desde la cuarta posición de cada sufijo en W. ¿Es esto correcto? ¿Este "empacar personajes en palabras" realmente acelera las cosas?

Answer 1

La forma en que lo describe en la pregunta es completamente precisa. Y sí, acelera las cosas porque, como dijiste, compara cuatro personajes a la vez.

Sin embargo, hay dos comentarios que hacer:

1. Cuando comparas los sufijos I y J, como en tu ejemplo, compara las entradas w [i] y w [j] de hecho. El resultado de esto es el mismo que si hubiera comparado lexicográficamente el cuádruple de los caracteres S [i..i+3] y S [j..j+3], por lo que ha ahorrado tiempo de computación equivalente a tres comparaciones de caracteres. Y sí, si el resultado indica que las dos cuadruplas son idénticas, debe continuar comparando w [i+1] y w [j+1], sin embargo: No lo haces de inmediato. La forma en que funciona su algoritmo es la de un tipo de radix. Es decir, coloca los sufijos en cubos justo después de la comparación inicial (posiblemente ambos en el mismo cubo), y luego ordene internamente los cubos, recursivamente.
2. El algoritmo descrito en el documento original por Burrows y Wheeler (de donde cita; hay una copia aquí Por ejemplo), que es de 1994, no es el algoritmo de construcción de matriz de sufijo óptimo. En primer lugar, en 2003 se descubrieron varios métodos de construcción directos; En segundo lugar, desde entonces, se realizaron muchas mejoras adicionales a la implementación. El núcleo del documento de 1994 es la idea de usar la transformación Burrows-Wheeler como base para la compresión de cadenas, no la forma exacta en que se genera la transformación en sí.

Answer 2

La matriz v no es una matriz de sufijo, sino una variedad de índices en W. Una vez que se completa la clasificación, V debe mantener los índices en w de modo que si

V[i] <= V[j]

después

 W[V[i]] <= W[V[j]].

Espero haberlo dicho bien :) Tenerlos exactamente no es un problema y cualquiera de los pedidos está bien. El punto es que cuando aplica la transformación inversa debe poder recuperar W para recuperar la cadena original, y los elementos idénticos de W no causarán un problema con eso.