Los sufijos de una cadena contienen (casi) toda la información sobre todas las posibles subcadenas de una cadena. Por ejemplo, suponga que está pensando en la subcadena “racada” de la cadena “ab racada bra”. Oh, mira, existe el sufijo “sujetador racada ” que comienza con tu subcadena. Eso es casi lo mismo.
¿Porque es esto importante? Porque hay subcadenas [math] \ Theta (n ^ 2) [/ math] en una cadena de letras [math] n [/ math], pero solo sufijos no vacíos [math] n [/ math]. Por ejemplo, sería bastante costoso ordenar todas las subcadenas posibles: para producir su orden ordenado, sin duda necesitaría [math] \ Omega (n ^ 2) [/ math] pasos porque debe, al menos, generar cada uno de ellos . Por otro lado, en teoría podría ser posible ordenar solo los sufijos más rápido que eso.
Y una vez que la gente se dio cuenta de que en realidad es posible y se le ocurrieron algoritmos eficientes e inteligentes para hacerlo, nació la matriz de sufijos.
- Cómo resolver UVA 10407
- ¿Qué aplicaciones no son adecuadas para quicksort y por qué?
- ¿Pueden los algoritmos predecir el futuro?
- ¿Cuál es el mejor algoritmo de clasificación manual? Por ejemplo, si tuviera una pila de papeles que quisiera ordenar alfabéticamente, ¿cuál sería la forma más eficiente de hacerlo? ¿Qué pasaría si estuvieras de acuerdo con que uno o dos se alejen de su posición ordenada?
- ¿Funciona la siguiente implementación para encontrar la subcadena común más larga dentro de dos cadenas?
La matriz de sufijos es simplemente una representación compacta de la lista ordenada de todos los sufijos. Por ejemplo, considere la cadena “banana”. Hay seis sufijos no vacíos: “banana”, “anana”, “nana”, “ana”, “na” y “a”. Podemos llamarlos 0, 1, 2, 3, 4 y 5, en este orden. (El número de un sufijo es el índice del carácter donde comienza en la cadena original). Si clasificamos (*) estos sufijos, obtenemos el siguiente orden: “a”, “ana”, “anana”, “banana “,” na “y” nana “. En otras palabras, (5,3,1,0,4,2). Esta es la matriz de sufijos para la cadena “banana”.
(*) Tenga en cuenta que los algoritmos eficientes en realidad no construyen todos los sufijos y luego los ordenan usando un algoritmo general, eso sería demasiado lento. En cambio, usan trucos inteligentes basados en el hecho de que sabemos que las cadenas que estamos ordenando son sufijos de la misma cadena. El truco básico aquí: cualquier sufijo de un sufijo es simplemente otro sufijo de la cadena original. Por ejemplo, si sabe que los sufijos 23 y 47 comparten las mismas 4 primeras letras, puede compararlos comparando los sufijos 23 + 4 y 47 + 4.
Una vez que tengamos la matriz de sufijos, podemos usarla para responder muchos tipos de consultas sobre la cadena original. Para un ejemplo simple, considere el problema de búsqueda de subcadenas estándar: aquí hay una nueva cadena de caracteres cortos (“la aguja”), ¿aparece en alguna parte de la cadena original de caracteres largos (“el pajar”)?
Sin la matriz de sufijos (o una estructura de datos precalculada similar), lo mejor que puede hacer es un algoritmo de búsqueda de cadenas estándar como Knuth-Morris-Pratt o Boyer-Moore, todos los cuales son lineales en la longitud del pajar.
Sin embargo, si conocemos la matriz de sufijos para el pajar, acabamos de ordenar todos sus sufijos (y, por lo tanto, casi ordenamos todas las subcadenas posibles). Y buscar en una lista ordenada es fácil, ¿verdad? ¡Podemos usar la búsqueda binaria! Es decir, comenzamos comparando la aguja con el sufijo que aparece en el medio de la matriz de sufijos. Si tenemos suerte y el sufijo actualmente considerado comienza con la aguja, acabamos de encontrar una aparición de la aguja. (Y si hay más ocurrencias, deben corresponder a los sufijos inmediatamente anteriores y / o siguientes). De lo contrario, simplemente procedemos como en una búsqueda binaria estándar: desechamos la primera mitad de los sufijos si la aguja es más grande que el sufijo actual y la segunda mitad en el otro caso.
Usando algunos trucos más (por ejemplo, el cálculo de la matriz de prefijos comunes más largos ), la complejidad temporal de una sola búsqueda se puede reducir a la longitud de la aguja, más el logaritmo del tamaño del pajar.
¿Por qué es esto súper útil? Piense en bioinformática, por ejemplo. Su pajar es un pedazo de ADN: una secuencia de bases muy larga pero fija. Usted calcula su matriz de sufijos una vez. Luego, cada vez que desee encontrar una secuencia particular de bases en su pajar, puede hacer la búsqueda extremadamente rápido, sin siquiera mirar la mayor parte del pajar.
