transpuesta - matriz inversa en c++

Algoritmo de matriz de sufijos (1)

Después de leer un poco, he descubierto lo que representa una matriz de sufijos y una matriz LCP.

Conjunto de sufijos : representa el rango _iloicográfico de cada sufijo de una matriz.

Arreglo LCP : contiene la coincidencia de prefijo de máxima longitud entre dos sufijos consecutivos, después de que se ordenan lexicográficamente .

He estado tratando de entender desde hace un par de días cómo funciona el arreglo de sufijos y el algoritmo LCP.

Aquí está el código, que está tomado de Codeforces :

/* Suffix array O(n lg^2 n) LCP table O(n) */ #include <cstdio> #include <algorithm> #include <cstring> using namespace std; #define REP(i, n) for (int i = 0; i < (int)(n); ++i) namespace SuffixArray { const int MAXN = 1 << 21; char * S; int N, gap; int sa[MAXN], pos[MAXN], tmp[MAXN], lcp[MAXN]; bool sufCmp(int i, int j) { if (pos[i] != pos[j]) return pos[i] < pos[j]; i += gap; j += gap; return (i < N && j < N) ? pos[i] < pos[j] : i > j; } void buildSA() { N = strlen(S); REP(i, N) sa[i] = i, pos[i] = S[i]; for (gap = 1;; gap *= 2) { sort(sa, sa + N, sufCmp); REP(i, N - 1) tmp[i + 1] = tmp[i] + sufCmp(sa[i], sa[i + 1]); REP(i, N) pos[sa[i]] = tmp[i]; if (tmp[N - 1] == N - 1) break; } } void buildLCP() { for (int i = 0, k = 0; i < N; ++i) if (pos[i] != N - 1) { for (int j = sa[pos[i] + 1]; S[i + k] == S[j + k];) ++k; lcp[pos[i]] = k; if (k)--k; } } } // end namespace SuffixArray

No puedo, simplemente no puedo ver cómo funciona este algoritmo. Traté de trabajar en un ejemplo usando lápiz y papel, y escribí los pasos a seguir, pero perdí el vínculo entre ellos ya que es demasiado complicado, al menos para mí.

Cualquier ayuda con respecto a la explicación, usando un ejemplo tal vez, es muy apreciada.

Visión de conjunto

Este es un algoritmo O (n log n) para la construcción del arreglo de sufijos (o más bien, sería, si en lugar de ::sort sort se hubiera usado una clasificación de cubo de 2 pasos).

Funciona ordenando primero los 2 gramos ^(*) , luego los 4 gramos, luego los 8 gramos, y así sucesivamente, de la cadena original S , de modo que en la i-ésima iteración, ordenamos los 2 ⁱ -grams . Obviamente no puede haber más que log ₂ (n) tales iteraciones, y el truco es que ordenar los 2 ⁱ -gramos en el i-ésimo paso se facilita asegurándose de que cada comparación de dos 2 ⁱ -gramos se haga en O (1) tiempo (en lugar de O (2 ⁱ ) tiempo).

¿Como hace esto? Bueno, en la primera iteración ordena los 2 gramos (también conocidos como bigrams), y luego realiza lo que se denomina cambio de nombre lexicográfico . Esto significa que crea una nueva matriz (de longitud n ) que almacena, para cada bigrama, su rango en la clasificación bigram.

Ejemplo de cambio de nombre lexicográfico: Digamos que tenemos una lista ordenada de algunos bigrams {''ab'',''ab'',''ca'',''cd'',''cd'',''ea''} . Luego asignamos rangos (es decir, nombres lexicográficos) yendo de izquierda a derecha, comenzando con el rango 0 e incrementando el rango cada vez que encontramos un nuevo cambio de bigramo. Entonces los rangos que asignamos son los siguientes:

ab : 0 ab : 0 [no change to previous] ca : 1 [increment because different from previous] cd : 2 [increment because different from previous] cd : 2 [no change to previous] ea : 3 [increment because different from previous]

Estos rangos se conocen como nombres lexicográficos .

Ahora, en la siguiente iteración , ordenamos 4 gramos. Esto implica muchas comparaciones entre diferentes 4 gramos. ¿Cómo comparamos dos 4 gramos? Bueno, podríamos compararlos carácter por personaje. Eso sería hasta 4 operaciones por comparación. Pero, en cambio, los comparamos buscando en las filas de los dos bigrams que contienen, usando la tabla de rangos generada en los pasos anteriores. Ese rango representa el rango lexicográfico del tipo anterior de 2 gramos, por lo que si para cualquier 4-gram dado, su primer 2-gram tiene un rango más alto que el primer 2-gram de otro 4-gram, entonces debe ser lexicográficamente mayor en algún lugar de los primeros dos personajes . Por lo tanto, si para dos 4 gramos el rango del primer 2-gram es idéntico, deben ser idénticos en los primeros dos caracteres . En otras palabras, dos búsquedas en la tabla de rangos son suficientes para comparar los 4 caracteres de los dos 4 gramos.

Después de ordenar, creamos nuevos nombres lexicográficos nuevamente, esta vez para los 4 gramos.

En la tercera iteración, tenemos que ordenar por 8 gramos. De nuevo, dos búsquedas en la tabla de rangos lexicográficos del paso anterior son suficientes para comparar los 8 caracteres de dos dados 8 gramos.

Etcétera. Cada iteración i tiene dos pasos:

Clasificando por 2 ⁱ -gramos, usando los nombres lexicográficos de la iteración anterior para permitir comparaciones en 2 pasos (es decir, O (1) tiempo) cada uno
Creando nuevos nombres lexicográficos

Repetimos esto hasta que los 2 ⁱ -gramos sean diferentes. Si eso sucede, hemos terminado. ¿Cómo sabemos si todos son diferentes? Bueno, los nombres lexicográficos son una secuencia creciente de enteros, comenzando con 0. Entonces, si el nombre lexicográfico más alto generado en una iteración es el mismo que n-1 , entonces cada 2 ⁱ -gram debe tener su propio nombre lexicográfico distinto. .

Implementación

Ahora veamos el código para confirmar todo esto. Las variables utilizadas son las siguientes: sa[] es la matriz de sufijos que estamos construyendo. pos[] es la tabla de búsqueda de rango (es decir, contiene los nombres lexicográficos), específicamente, pos[k] contiene el nombre lexicográfico del k -ésimo m-gramo del paso anterior. tmp[] es una matriz auxiliar utilizada para ayudar a crear pos[] .

Daré más explicaciones entre las líneas de código:

void buildSA() { N = strlen(S); /* This is a loop that initializes sa[] and pos[]. For sa[] we assume the order the suffixes have in the given string. For pos[] we set the lexicographic rank of each 1-gram using the characters themselves. That makes sense, right? */ REP(i, N) sa[i] = i, pos[i] = S[i]; /* Gap is the length of the m-gram in each step, divided by 2. We start with 2-grams, so gap is 1 initially. It then increases to 2, 4, 8 and so on. */ for (gap = 1;; gap *= 2) { /* We sort by (gap*2)-grams: */ sort(sa, sa + N, sufCmp); /* We compute the lexicographic rank of each m-gram that we have sorted above. Notice how the rank is computed by comparing each n-gram at position i with its neighbor at i+1. If they are identical, the comparison yields 0, so the rank does not increase. Otherwise the comparison yields 1, so the rank increases by 1. */ REP(i, N - 1) tmp[i + 1] = tmp[i] + sufCmp(sa[i], sa[i + 1]); /* tmp contains the rank by position. Now we map this into pos, so that in the next step we can look it up per m-gram, rather than by position. */ REP(i, N) pos[sa[i]] = tmp[i]; /* If the largest lexicographic name generated is n-1, we are finished, because this means all m-grams must have been different. */ if (tmp[N - 1] == N - 1) break; } }

Acerca de la función de comparación

La función sufCmp se usa para comparar dos (2 * gap) -grams lexicográficamente. Entonces en la primera iteración compara bigrams, en la segunda iteración 4 gramos, luego 8 gramos y así sucesivamente. Esto está controlado por gap , que es una variable global.

Una implementación ingenua de sufCmp sería esta:

bool sufCmp(int i, int j) { int pos_i = sa[i]; int pos_j = sa[j]; int end_i = pos_i + 2*gap; int end_j = pos_j + 2*gap; if (end_i > N) end_i = N; if (end_j > N) end_j = N; while (i < end_i && j < end_j) { if (S[pos_i] != S[pos_j]) return S[pos_i] < S[pos_j]; pos_i += 1; pos_j += 1; } return (pos_i < N && pos_j < N) ? S[pos_i] < S[pos_j] : pos_i > pos_j; }

Esto compararía el (2 * gap) -gram al comienzo del i-ésimo sufijo pos_i:=sa[i] con el que se encuentra al comienzo del j-ésimo sufijo pos_j:=sa[j] . Y los compararía carácter por carácter, es decir, comparando S[pos_i] con S[pos_j] , luego S[pos_i+1] con S[pos_j+1] y así sucesivamente. Continúa mientras los personajes sean idénticos. Una vez que difieren, devuelve 1 si el carácter en el i-ésimo sufijo es más pequeño que el que está en el j-ésimo sufijo, 0 en caso contrario. (Tenga en cuenta que return a<b en una función que devuelve int significa que devuelve 1 si la condición es verdadera y 0 si es falsa).

La condición de aspecto complicado en la declaración de devolución se refiere al caso en que uno de los (2 * gap) -grams se encuentra al final de la cadena. En este caso, pos_i o pos_j llegarán a N antes de que se hayan comparado todos los caracteres (2 * gap), incluso si todos los caracteres hasta ese punto son idénticos. Luego devolverá 1 si el sufijo i-ésimo está al final, y 0 si el sufijo j-ésimo está al final. Esto es correcto porque si todos los caracteres son idénticos, el más corto es lexicográficamente más pequeño. Si pos_i ha llegado al final, el i-ésimo sufijo debe ser más corto que el j-ésimo sufijo.

Claramente, esta implementación ingenua es O (gap), es decir, su complejidad es lineal en la longitud de los (2 * gap) -grams. La función utilizada en su código, sin embargo, usa los nombres lexicográficos para llevar esto a O (1) (específicamente, hasta un máximo de dos comparaciones):

bool sufCmp(int i, int j) { if (pos[i] != pos[j]) return pos[i] < pos[j]; i += gap; j += gap; return (i < N && j < N) ? pos[i] < pos[j] : i > j; }

Como puede ver, en lugar de buscar los caracteres individuales S[i] y S[j] , verificamos el rango lexicográfico del sufijo i-th y j-th. Los rangos lexicográficos se calcularon en la iteración anterior para gap-grams. Entonces, si pos[i] < pos[j] , entonces el i-ésimo sufijo sa[i] debe comenzar con un gap-gram que sea lexicográficamente menor que el gap-gram al comienzo de sa[j] . En otras palabras, simplemente al buscar pos[i] y pos[j] y compararlos, hemos comparado los primeros caracteres de brecha de los dos sufijos.

Si los rangos son idénticos, continuamos comparando pos[i+gap] con pos[j+gap] . Esto es lo mismo que comparar los siguientes caracteres de brecha del (2 * gap) -grams, es decir, la segunda mitad . Si los rangos son idénticos de nuevo, los dos (2 * gap) --gramas son idénticos, entonces devolvemos 0. De lo contrario, devolvemos 1 si el i-ésimo sufijo es menor que el j-ésimo sufijo, 0 en caso contrario.

Ejemplo

El siguiente ejemplo ilustra cómo funciona el algoritmo y demuestra en particular el papel de los nombres lexicográficos en el algoritmo de clasificación.

La cadena que queremos ordenar es abcxabcd . Se necesitan tres iteraciones para generar la matriz de sufijo para esto. En cada iteración, mostraré S (la cadena), sa (el estado actual de la matriz de sufijos) y tmp y pos , que representan los nombres lexicográficos.

Primero, iniciamos:

S abcxabcd sa 01234567 pos abcxabcd

Observe cómo los nombres lexicográficos, que inicialmente representan el rango lexicográfico de los unigramas, son simplemente idénticos a los caracteres (es decir, los unigrams) en sí mismos.

Primera iteración:

Clasificando sa , usando bigrams como criterio de clasificación:

sa 04156273

Los dos primeros sufijos son 0 y 4 porque esas son las posiciones de bigram ''ab''. Luego 1 y 5 (posiciones de bigram ''bc''), luego 6 (bigram ''cd''), luego 2 (bigram ''cx''). luego 7 (bigram ''d'' incompleto), luego 3 (bigram ''xa''). Claramente, las posiciones corresponden a la orden, basadas únicamente en bigrams de caracteres.

Generando los nombres lexicográficos:

tmp 00112345

Como se describe, los nombres lexicográficos se asignan como números enteros crecientes. Los dos primeros sufijos (ambos que comienzan con bigram ''ab'') obtienen 0, los siguientes dos (ambos comienzan con bigram ''bc'') obtienen 1, luego 2, 3, 4, 5 (cada uno es un bramido diferente).

Finalmente, asignamos esto de acuerdo con las posiciones en sa , para obtener pos :

sa 04156273 tmp 00112345 pos 01350124

(La forma en que se genera pos es la siguiente: recorra sa de izquierda a derecha y use la entrada para definir el índice en pos . Use la entrada correspondiente en tmp para definir el valor para ese índice. Entonces pos[0]:=0 , pos[4]:=0 , pos[1]:=1 , pos[5]:=1 , pos[6]:=2 , y así sucesivamente. El índice proviene de sa , el valor de tmp .)

Segunda iteración:

Ordenamos sa nuevo, y de nuevo vemos bigrams desde pos (que representan una secuencia de dos birams de la cadena original).

sa 04516273

Observe cómo ha cambiado la posición de 1 5 en comparación con la versión anterior de sa . Solía ser 15, ahora es 51. Esto es porque el bigram en pos[1] y el bigram en pos[5] solían ser idénticos (ambos bc ) durante la iteración anterior, pero ahora el bigram en pos[5] es 12 , mientras que el bigram en pos[1] es 13 . Entonces la posición 5 viene antes de la posición 1 . Esto se debe al hecho de que los nombres lexicográficos ahora representan barras grandes de la cadena original: pos[5] representa bc y pos[6] representa ''cd''. Entonces, juntos representan bcd , mientras que pos[1] representa bc y pos[2] representa cx , de modo que juntos representan bcx , que es de hecho lexicográficamente mayor que bcd .

De nuevo, generamos nombres lexicográficos al seleccionar la versión actual de sa de izquierda a derecha y comparando los bigrams correpondentes en pos :

tmp 00123456

Las primeras dos entradas siguen siendo idénticas (ambas 0), ya que los correspondientes bigrams en pos son ambos 01 . El resto es una secuencia estrictamente creciente de enteros, porque todos los demás bigrams en pos son únicos.

Realizamos el mapeo a la nueva pos como antes (tomando índices de sa y valores de tmp ):

sa 04516273 tmp 00123456 pos 02460135

Tercera iteración:

Ordenamos sa nuevamente, tomando bigramas de pos (como siempre), que ahora representan una secuencia de 4 birrams de la cadena original.

sa 40516273

Notará que ahora las dos primeras entradas han cambiado de posición: 04 ha convertido en 40 . Esto se debe a que el bigram en pos[0] es 02 mientras que el que está en pos[4] es 01 , siendo el último obviamente lexicográficamente menor. La razón profunda es que estos dos representan abcx y abcd , respectivamente.

Generar rendimientos de nombres lexicográficos:

tmp 01234567

Todos son diferentes, es decir, el más alto es 7 , que es n-1 . Entonces, hemos terminado, porque la clasificación ahora se basa en m-grams que son todos diferentes. Incluso si continuamos, el orden de clasificación no cambiaría.

Sugerencia de mejora

El algoritmo utilizado para clasificar los 2 ⁱ -gramos en cada iteración parece ser el tipo incorporado (o std::sort ). Esto significa que es un tipo de comparación, que toma el tiempo O (n log n) en el peor de los casos, en cada iteración . Dado que hay log n iteraciones en el peor de los casos, esto lo convierte en un algoritmo O (n (log n) ² ) -time. Sin embargo, la clasificación podría realizarse utilizando dos pasadas de clasificación de ordenación, ya que las claves que utilizamos para la comparación de clasificación (es decir, los nombres lexicográficos del paso anterior) forman una secuencia entera creciente. De modo que esto podría mejorarse con un algoritmo real O (n log n) -time para la clasificación de sufijos.

Observación

Creo que este es el algoritmo original para la construcción de matrices de sufijo que se sugirió en el documento de 1992 de Manber and Myers ( enlace en Google Scholar ; debería ser el primer hit, y puede tener un enlace a un PDF allí). Esto (al mismo tiempo, pero independientemente de un artículo de Gonnet y Baeza-Yates) fue lo que introdujo los arreglos de sufijos (también conocidos como arreglos de pat en el momento) como una estructura de datos interesante para su posterior estudio.

Los algoritmos modernos para la construcción de matrices de sufijos son O (n), por lo que lo anterior ya no es el mejor algoritmo disponible (al menos no en términos de complejidad teórica y de peor caso).

Notas a pie de página

^(*) Por 2 gramos quiero decir una secuencia de dos caracteres consecutivos de la cadena original. Por ejemplo, cuando S=abcde es la cadena, entonces ab , bc , cd , de son los 2 gramos de S Del mismo modo, abcd y bcde son los 4 gramos. En general, un m-gramo (para un entero positivo m) es una secuencia de m caracteres consecutivos. 1 gramo también se llama unigrams, 2 gramos se llaman bigrams, 3 gramos se llaman trigrams. Algunas personas continúan con tetragramas, pentagramas, etc.

Tenga en cuenta que el sufijo de S que comienza y la posición i , es un (ni) -gram de S Además, cada m-gramo (para cualquier m) es un prefijo de uno de los sufijos de S Por lo tanto, ordenar m-grams (para una m tan grande como sea posible) puede ser el primer paso para clasificar los sufijos.