Baidu para obtener algunos conceptos básicos de matrices de sufijo. En pocas palabras, la matriz de sufijo es una colección de todos los tamaños de sufijo de una cadena. Entonces podemos lograr varias necesidades basadas en algunas propiedades de la matriz de sufijo.
clase pública mySuffixArrayTest {public char [] sufix; // String original public int n; // string longitud public int [] rank; // clasificación de sufijo [i] en todo sufijo int [] sa; // sufijo [sa [1]] <sufijo [sa [2]] ... <sufix [sa [len]], es decir, el sufix con el ranking i es sufix [sa [sa [i] // (es una operación [sa [len]], es decir, el sufix con el ranking i es sufix [sa [sa] Rango) público int [] altura; // indica sufijo [sa [i]] y sufijo [sa [i - 1]], es decir, el prefijo público más largo de dos sufijos adyacentes, público int [] h; // es igual a la altura [rango [i]]], es el prefijo público más largo del sufijo [i] y el sufix de su sufix de su sufijo público anterior. Y; // Segunda matriz de rango de palabras clave int [] x; // matriz auxiliar de rango}Las siguientes explicaciones toman la cadena "aabaaaab" como ejemplo. Primero mostremos los resultados. Consulte este resultado para su comprensión y análisis (copié la imagen de otra persona de este resultado. Por favor, subíndice 1 de forma predeterminada, porque mi matriz comienza con el subíndice 0)
Sufijo: la matriz de cadenas original supone que la cadena original es "aabaaaab", entonces el valor correspondiente de esta matriz debe ser {'a', 'a', 'b', 'a', 'a', 'a', 'b'}
N: la longitud de la cadena aquí es 8
Rango: la matriz de clasificación de la matriz de sufijo es equivalente a la clasificación correspondiente al sufijo i-th. Por ejemplo, el rango [0] se refiere a la clasificación del sufijo "aabaaaaab" rango [1] se refiere a la clasificación del sufijo "abaaaab"
SA: Esta es una matriz que está inversa para la matriz de rango. ¿El nodo X almacena el sufijo? O para dar un ejemplo para ilustrar que SA [0] se refiere a la matriz de sufijo del primer clasificado, es decir, 3. Es decir, el rango correspondiente [3] de la matriz es 0. Por favor, asegúrese de comprender la fórmula SA [Rank [i]] = i. Si comprende la relación entre SA y Rank, también debe entenderla.
Altura: la altura [i] es la longitud del prefijo común más grande de la matriz de sufijo SA [i] y la altura de la matriz de sufijo SA [i-1] [1] se refiere a los primeros prefijos comunes más grandes y más grandes SA [1] y SA [0] es decir, los prefijos comunes más grandes de "AAAB" y "AAAAB", ver la altura de la altura [1] = 3 en un glance en un glance en un glance.
H: H [i] se refiere al sufijo I-Th y el prefijo público más grande del anterior H [0] se refiere a la primera matriz de sufijo, a saber, "aabaaaab" y el prefijo público más grande del anterior, a saber, "AAB", es decir, altura [rango [0]] = altura [3] = 3 Esto es un poco difícil de entender. No puedes entender por el momento y continuar leyendo.
WS: Nada que decir, cuente la clasificación de la matriz auxiliar
Y: El segundo tipo de palabra clave es la matriz SA con la segunda palabra clave ordenada equivalente a la segunda palabra clave
X: Puedes entenderlo como una copia de seguridad de la matriz de rango. Inicialmente usa la copia de seguridad de la matriz de rango, y luego registra la matriz de rango después de cada bucle
Primero, veamos el código para la matriz SA. Explicaré la función del código uno por uno y adjuntaré el código total a lo siguiente
rank = new int [n]; sa = nuevo int [n]; ws = nuevo int [255]; y = nuevo int [n]; x = nuevo int [n]; // bucle la cadena original para convertir el valor int en la matriz de rango para (int i = 0; i <n; i ++) {rank [i] = (int) sufijo [i]; }La función del código anterior es inicializar la matriz y realizar el primer recuento y clasificación. El primer bucle es asignar el valor inicial a la matriz de rango. Después de la ejecución, el valor correspondiente de la matriz de rango es {97, 97, 98, 97, 97, 97, 97, 98}. Debería ver que el valor inicial de la matriz de rango es el código ASCII correspondiente a la letra.
Los siguientes tres ciclos son la primera clasificación de conteo. Si no comprende contar la clasificación, por favor Baidu. Déjame hablar sobre el proceso de estos tres ciclos
para (int i = 0; i <n; i ++) {ws [rank [i]] ++; x [i] = rango [i]; } para (int i = 1; i <ws.length; i ++) {ws [i]+= ws [i - 1]; }Lo que hacen estos dos bucles es contar todos los valores de ocurrencia y hacer una copia de seguridad de la matriz de rango a la matriz X. Después de ejecutar el primer bucle, ws [97] = 6, ws [98] = 2, y después de ejecutar el segundo bucle, ws [97] = 6, ws [98] = 8
para (int i = n-1; i> = 0; i--) {sa [-ws [rank [i]] = i; }El párrafo anterior es el código específico para contar y clasificar para encontrar la matriz SA. Todos deben haber entendido mal la primera vez que lo leen. ¿Por qué encontraron la SA? También estaba confundido por primera vez, pero tenga paciencia y comprenda este código con cuidado. ¿Todavía recuerdas la fórmula mencionada anteriormente sa [rank [i]] = I por ejemplo, para el sufijo "b", le preguntamos a su sa, es decir, sa [rango [7]] = sa [98] = 7. Obviamente, SA [98] no existe, pero hemos registrado el número de veces 98 aparece en la matriz WS, por lo que WS [98] debería ser la clasificación correspondiente de "B". Por favor, no olvide restar 1 para convertirse en sa [-ws [rango [i]]] = i. En cuanto a por qué necesita atravesar de regreso a adelante, debe entenderlo cuidadosamente aquí, de lo contrario, definitivamente estará completamente cegado por la forma en que lo clasifica de acuerdo con la segunda palabra clave. ¿Cómo lo clasificas si hay dos valores de rango que son los mismos? Debe aparecer primero frente a la matriz SA. Si piensa en este bucle y los cambios en el valor de la matriz WS, comprenderá que el orden del bucle for en realidad representa el orden de disposición cuando el valor de rango es el mismo. El recorrido de regreso a delantero significa que la clasificación de sufijo también es más baja cuando el valor de rango es el mismo.
Lo anterior es solo la primera clasificación de conteo, que es equivalente a comparar solo la primera letra de cada matriz de sufijo para encontrar una SA. El resultado correspondiente es como se muestra en la figura a continuación.
// clasificación de combinación de bucle para (int j = 1, p = 0; j <= n; j = j << 1) {// Si necesita llenarlo, agregue la matriz de clasificación primero yp = 0; para (int i = n - j; i <n; i ++) {y [p ++] = i; } // Rango de la segunda palabra clave de acuerdo con la primera palabra clave sa para (int i = 0; i <n; i ++) {if (sa [i]> = j) {y [p ++] = sa [i] - j; }} // Ordenar las dos palabras clave para (int i = 0; i <ws.length; i ++) {ws [i] = 0; } para (int i: x) {ws [i] ++; } para (int i: x) {ws [i] ++; } para (int i = 1; i <ws.length; i ++) {ws [i]+= ws [i - 1]; } para (int i = n-1; i> = 0; i--) {sa [-ws [x [y [i]]] = y [i]; y [i] = 0; } // Calcule la matriz de rango de SA int xb [] = new int [n]; // x copia de seguridad de matriz para (int i = 0; i <n; i ++) {xb [i] = x [i]; } int número = 1; x [sa [0]] = 1; para (int i = 1; i <n; i ++) {if (xb [sa [i]! = xb [sa [i - 1]]) {x [sa [i]] = ++ número; } else if (sa [i] + j> = n && sa [i - 1] + j> = n) {x [sa [i]] = number; } else if (sa [i] + j <n && sa [i - 1] + j> = n) {x [sa [i]] = ++ número; } else if (xb [sa [i] + j]! = xb [sa [i - 1] + j]) {x [sa [i]] = ++ número; } else {x [sa [i]] = número; } if (número> = n) ruptura; }}Este es el código más difícil de entender al encontrar la matriz SA. En primer lugar, debe comprender la idea del algoritmo de multiplicación. Después de la primera orden de conteo, ¿ya sabemos la clasificación de la primera letra inicial de todas las matrices de sufijo? Dado que sabemos que la clasificación de la primera carta inicial es equivalente a la orden de su segunda carta (tenga en cuenta la diferencia entre clasificación y orden. La clasificación es que sabemos en cuál está fijado. La orden es que solo conocemos el orden en que aparece, pero no sabemos cuál está clasificado específicamente). Esto es, por supuesto, porque son originarios de una cadena, y para cada sufijo, también se puede usar como sufijo para su sufijo anterior. Hablando de ello, por ejemplo, para "Baaaab", el orden de su primera letra corresponde al segundo orden de palabras clave de "abaaaab". Con el orden de la primera palabra clave y el tipo de palabra clave, podemos encontrar el tipo combinado de las dos palabras clave. Según el resultado del tipo de combinación, aún podemos usar la idea anterior. Después de la primera combinación de "Baaaab", ordenamos el orden de las dos primeras letras "BA", por lo que también puede usar el orden de la segunda palabra clave de "Aabaaaab". La lógica de todo el tipo se hace referencia a continuación
Luego analizaremos el código en segmentos
para (int i = n - j; i <n; i ++) {y [p ++] = i; } // Seleccione la segunda palabra clave de acuerdo con la primera palabra clave SA para (int i = 0; i <n; i ++) {if (sa [i]> = j) {y [p ++] = sa [i] - j; }}El código anterior es encontrar el SA, es decir, la matriz Y de la segunda palabra clave, con el valor inicial de P siendo 0, y el primer bucle es clasificar el sufijo que debe llenarse en el frente de la matriz.
Debe comprender la lógica del segundo bucle en combinación con el diagrama lógico anterior. Traveremos el resultado de clasificación de la primera palabra clave SA. If (sa [i]> = j) determina si el sufijo se puede usar como la segunda palabra clave para otros sufijos. Tomar el primer bucle j = 1 como ejemplo, cuando SA [i] = 0 representa la matriz de sufijo "aabaaaab", obviamente no se puede usar como la segunda palabra clave para otros sufijos. Para la segunda palabra clave que se puede usar como otros sufijos, el orden de su SA es la segunda palabra clave correspondiente. SA [i] - J encuentra el sufijo suyo como la segunda palabra clave y la pone en la matriz Y, y p ++. Necesitas entender aquí lentamente.
// fusionar el tipo de dos palabras clave para (int i = 0; i <ws.length; i ++) {ws [i] = 0; } para (int i: x) {ws [i] ++; } para (int i = 1; i <ws.length; i ++) {ws [i]+= ws [i - 1]; } para (int i = n-1; i> = 0; i--) {sa [-ws [x [y [i]]]] = y [i]; y [i] = 0; }Lo anterior es encontrar la clasificación de combinación basada en la primera palabra clave que clasifica SA y la segunda clasificación de palabras clave y. Este código es bastante oscuro. Primero no podemos entender el código, pero entender una idea. Para la clasificación de dos palabras clave, las reglas reales son similares a la clasificación de dos números. Por ejemplo, 11 y 12 comparan el tamaño, 10 bits son la primera palabra clave y los bits únicos son la segunda palabra clave. Después de comparar 10 bits, encontramos 11 = 12, y luego comparamos los bits individuales, sabemos que 11 <12. Si los 10 bits son los mismos, el orden de los bits individuales es el orden de tamaño. Dije la primera vez que cuento la clasificación anterior que el orden de clasificación de recuento para bucle en realidad representa el orden de disposición cuando los valores de rango son los mismos. Entonces, ¿cómo encontramos el pedido después de que las dos palabras clave se fusionan en una clasificación de un recuento? Déjame decirte mi entendimiento. Un tipo de recuento en realidad contiene dos tipos, uno es el tipo de valores numéricos, y el otro es el tipo de orden de ocurrencia. Las reglas son equivalentes al ejemplo anterior de comparación de 11 y 12. El tipo de valores numéricos es de 10 bits, y el tipo de orden de ocurrencia es un bits. En este punto, tenemos una idea. La clasificación de valores se clasifica por la primera palabra clave, y la clasificación de ocurrencias se clasifica mediante la segunda palabra clave, para que podamos contar y clasificar a la vez para encontrar la clasificación después de que se combinen las dos palabras clave. El código anterior es la implementación de esta idea. La matriz X es la matriz de rango de la primera palabra clave, y la contamos.
para (int i = n-1; i> = 0; i--) {sa [-ws [x [y [i]]]] = y [i]; y [i] = 0; }Este bucle es la implementación de todas las ideas anteriores. Traveremos la segunda matriz de palabras clave y desde la parte posterior. Para y [i], calculamos la clasificación de recuento de su primera palabra clave. Esta clasificación de recuento es la clasificación de y [i], y el recuento final se reduce en 1. El tipo de palabra clave fusionada se encontró con éxito.
Creo que si comprende todos los códigos anteriores, definitivamente se sorprenderá. También estaba emocionado cuando pensé en este código una y otra vez, y simplemente estaba convencido. Este es el encanto de los algoritmos.
Con la matriz SA, podemos encontrar la matriz de rango. Esto no es difícil, por lo que no lo explicaremos. Todos los códigos para encontrar SA se adjuntan a continuación.
public static void main (string [] args) {string str = "aabaaaab"; MySuffixArrayTest ArrayTest = new MySuffixArrayTest (str.ToString ()); arrayTest.initsa (); // encontrar sa array} public void initsa () {rank = new int [n]; sa = nuevo int [n]; ws = nuevo int [255]; y = nuevo int [n]; x = nuevo int [n]; // bucle la cadena original para convertir el valor int en la matriz de rango para (int i = 0; i <n; i ++) {rank [i] = (int) sufijo [i]; } // Primero de cuenta clasificación para (int i = 0; i <n; i ++) {ws [rank [i]] ++; x [i] = rango [i]; } para (int i = 1; i <ws.length; i ++) {ws [i]+= ws [i - 1]; } para (int i = n-1; i> = 0; i--) {sa [-ws [rank [i]]] = i; } // orden de combinación de bucle para (int j = 1, p = 0; j <= n; j = j << 1) {// Si necesita llenar, agregue la matriz ordenada primero yp = 0; para (int i = n - j; i <n; i ++) {y [p ++] = i; } // Rango de la segunda palabra clave de acuerdo con la primera palabra clave sa para (int i = 0; i <n; i ++) {if (sa [i]> = j) {y [p ++] = sa [i] - j; }} // Ordenar las dos palabras clave para (int i = 0; i <ws.length; i ++) {ws [i] = 0; } para (int i: x) {ws [i] ++; } para (int i = 1; i <ws.length; i ++) {ws [i]+= ws [i - 1]; } para (int i = n-1; i> = 0; i--) {sa [-ws [x [y [i]]] = y [i]; y [i] = 0; } // Calcule la matriz de rango basada en sa int xb [] = new int [n]; // x copia de seguridad de matriz para (int i = 0; i <n; i ++) {xb [i] = x [i]; } int número = 1; x [sa [0]] = 1; para (int i = 1; i <n; i ++) {if (xb [sa [i]! = xb [sa [i - 1]]) {x [sa [i]] = ++ número; } else if (sa [i] + j> = n && sa [i - 1] + j> = n) {x [sa [i]] = number; } else if (sa [i] + j <n && sa [i - 1] + j> = n) {x [sa [i]] = ++ número; } else if (xb [sa [i] + j]! = xb [sa [i - 1] + j]) {x [sa [i]] = ++ número; } else {x [sa [i]] = número; } if (número> = n) ruptura; }}}}Resumir
Lo anterior es el código de ejemplo para las matrices SAC de las matrices de sufijo Java que se le presentan. Espero que te sea útil. Si tiene alguna pregunta, déjame un mensaje y el editor le responderá a tiempo. ¡Muchas gracias por su apoyo al sitio web de Wulin.com!