¿Cuáles son algunas de las buenas fuentes para entender el árbol de sufijos, la matriz de sufijos y su implementación?

Answer 1

Hay muchos buenos recursos disponibles en internet.

---

Alerta
Antes de continuar, quisiera mencionar que hay grandes diferencias entre el árbol de sufijos y la matriz de sufijos. Sin embargo, construir el árbol de sufijos es un poco tedioso y lleva mucho tiempo. Además, el árbol de sufijos es un poco más lento que SA debido a la sobrecarga de las restricciones involucradas. Además, SA es una alternativa de espacio eficiente para el árbol de sufijos. Cada algoritmo de árbol de sufijos se puede reemplazar sistemáticamente con un algoritmo que utiliza una matriz de sufijos mejorada con información adicional (como la matriz LCP) y resuelve el mismo problema en la misma complejidad de tiempo. Por lo tanto, me gustaría explicar buenas fuentes para entender la matriz de sufijo, en lugar del árbol de sufijo.

---

Personalmente, me gustan las matrices de sufijos: un nuevo método para búsquedas de cadenas en línea, por Udi Manber y Gene Myers.
La implementación ordenada del documento anterior en C ++ se puede encontrar en TopCoder Forum .

Matrices de sufijos: un enfoque de concurso de programación es la mejor implementación / tutoriales de aplicación para matrices de sufijos en Internet.
Reúne tantos problemas como sea posible que se pueden resolver utilizando matrices de sufijos. Pasar por todos los problemas en la primera lectura parece bastante difícil para un lector que tuvo el primer contacto con matrices de sufijos al leer este documento. Con el fin de facilitar la conferencia, los problemas se arreglan en
Un orden de dificultad creciente.

Las implementaciones en C ++ de algunos de los problemas populares de Array de sufijo están disponibles en: mi blog .

La lectura de tutoriales y algunas implementaciones no lo ayudarán a comprender esta estructura de datos avanzada ni lo ayudarán a controlar este tema. Intente seleccionar y resolver varios problemas de spoj, codechef, topcoder, etc., en el tema de matriz de sufijo / árbol.

Estos son algunos de los problemas en la matriz de sufijos que había recopilado de spoj, codechef y codeforces.

Nombre del problema                              Juez / Concurso Online
1 cuentas de vidrio SPOJ

2 Nuevos Substrings Distintos SPOJ

3 Stammering Aliens Live Archive2009Europe – Southwestern

4 Substrings DistintosCategorías SPOJ

5 Suffix Array SPOJ

6 I Love Strings !! UVA

7 Rotaciones mínimas SPOJ

8 SPOJ más largo de CommonSubstring

9 GATTACA UVA

10 perlas de vidrio UVA

11 Búsqueda de subcadenas lexicográficas SPOJ

12 Petr # Codeforces

Código de 13 cuerdas

14 cuerdas marcianas Codeforces

15 Eliminación de repeticiones Codeforces

16 Código de ingeniería genética

17 StringCategories Codeforces

18 pequeños elefantes y cuerdas de código

19 Fuerzas de código de misiones cíclicas

20 Fuerzas de código de cercas

21 formas de vida UVA

22 Robo de Código UVA

23 Número de palíndromos SPOJ

24 palíndromos SPOJ

25 nivel de diferencia CODECHEF

26 cuerdas repetidas CODECHEF

27 Prefijos y sufijos ACM-SGU-RU

28 Lucy y las flores CODECHEF

Implementaciones más rápidas: en general, la complejidad general de la construcción de la matriz de sufijos es O (n * log n), pero existe un algoritmo importante llamado DC3 que calcula las matrices de sufijos en el tiempo lineal O (n). Por lo tanto, las matrices de sufijos se vuelven tan efectivas como el árbol de sufijos. El código fuente de este genial algoritmo DC3 súper elegante en C ++ está disponible en las últimas páginas de este PDF . El PDF general incluye una hermosa explicación del algoritmo. DC3 siempre me ayudó a lograr el mejor tiempo de ejecución en SPOJ.

Para resolver cualquier problema de la matriz de sufijos, necesitamos saber:

• Construcción de matriz de sufijo (paso básico)

• Búsqueda de los prefijos comunes más largos entre los sufijos adyacentes (construcciones de la matriz LCP estándar)

• Encontrar el LCP entre cualquiera de los dos sufijos por RMQ utilizando una matriz de LCP estándar derivada en el paso 2.

  He explicado los dos primeros pasos en uno de mis respuestas en la matriz de sufijos: http://qr.ae/TIoMQ

Answer 2

Esto debería hacerte comenzar:

• http://marknelson.us/1996/08/01/…
• http://stackoverflow.com/questio …
• http://www.csie.ntu.edu.tw/~kmch …
• http://www.cs.cmu.edu/~guyb/real …
• http://www.cs.helsinki.fi/u/ukko …
• http://www.amazon.com/Algorithms…

También recomendaría que aprendas sobre matrices de sufijos. Los arreglos de sufijos se pueden generar en la misma complejidad de tiempo asintótica que los árboles de sufijos, pero son mucho más eficientes en la memoria.

Answer 3

Otoño de 2011 – Algoritmos de cuerdas y Algroritmos en biología computacional – Gusfield

Los números de video 7 y 9 son lo que quieres. Combínelos, y puede crear fácilmente un árbol de sufijos en O (n) y mucho menos memoria de la que necesita para hacerlo directamente.

Answer 4

Lo he cumplido hace mucho tiempo aquí Cracking The Code

1.Suffix Tree Wikipedia
2. Una buena explicación
3. Su árbol de sufijo impresionante por Sahni
4. Revise estas cadenas
5. Algoritmos de búsqueda de cadenas
6. http://apps.topcoder.com/forums/…
7. http://www.stanford.edu/class/cs …

Aplicaciones del árbol de sufijo

1. El problema de subcadenas más largo
El problema de la subcadena repetida más larga es encontrar la subcadena más larga de una cadena que se produce al menos dos veces. Este problema se puede resolver en tiempo y espacio lineal construyendo un árbol de sufijos para la cadena y encontrando el nodo interno más profundo en el árbol. La cadena escrita por los bordes de la raíz a dicho nodo es la subcadena repetida más larga. El problema de encontrar la subcadena más larga con al menos k ocurrencias se puede encontrar primero preprocesando el árbol para contar el número de descendientes de hojas para cada nodo interno, y luego encontrar el nodo más profundo con al menos k descendientes.

Encuentra la subcadena más larga de S que aparece al menos m> 1 veces. Esta consulta se puede responder en tiempo O (| S |) de la siguiente manera:
(a) Recorra el árbol de sufijos etiquetando los nodos de la rama con la suma de las longitudes de las etiquetas desde la raíz y también con el número de nodos de información en la subtrie.
(b) Recorra el árbol de sufijos visitando los nodos de rama con el recuento de nodos de información> = m. Determine el nodo de rama visitado con la longitud de etiqueta más larga.
Tenga en cuenta que el paso (a) debe realizarse una sola vez. Después de esto, podemos hacer el paso (b) para tantos valores de m como se desee. Además, tenga en cuenta que cuando m = 2 podemos evitar determinar el número de nodos de información en los intentos secundarios. En un trie comprimido, cada subrie enraizada en un nodo de rama tiene al menos dos nodos de información en él.
Tenga en cuenta que el paso (a) debe realizarse una sola vez. Después de esto, podemos hacer el paso (b) para tantos valores de m como se desee. Además, tenga en cuenta que cuando m = 2 podemos evitar determinar el número de nodos de información en subtries. En un trie comprimido, cada subrie enraizada en un nodo de rama tiene al menos dos nodos de información en él.

2. Búsqueda de patrones / Búsqueda de sub-cadenas
Buscando una subcadena, pat [1..m], en txt [1..n], se puede resolver en tiempo O (m) (después de que el árbol de sufijos para txt se haya creado en tiempo O (n)).

3. La subcadena más larga repetida

4. Subsecuencia más larga común

5. Palíndromo más largo

Árboles de sufijo
Agregue un carácter especial de “fin de cadena”, por ejemplo `$ ‘, a txt [1..n] y genere un árbol de sufijos; la subcadena más larga repetida de txt [1..n] se indica mediante el nodo de bifurcación más profundo en el árbol de sufijos, donde la profundidad se mide por el número de caracteres atravesados ​​desde la raíz, es decir, `issi ‘en el caso de’ mississippi ‘. La subcadena repetida más larga se puede encontrar en O (n) tiempo utilizando un árbol de sufijos.
La subcadena común más larga de dos cadenas, txt1 y txt2, se puede encontrar al construir un árbol de sufijos generalizados para txt1 y txt2: cada nodo está marcado para indicar si representa un sufijo de txt1 o txt2 o ambos. El nodo más profundo marcado para txt1 y txt2 representa la subcadena común más larga.
De manera equivalente, se puede construir un árbol de sufijos (básico) para la cadena txt1 $ txt2 #, donde `$ ‘es un terminador especial para txt1 y` #’ es un terminador especial para txt2. La subcadena común más larga se indica mediante el nodo de bifurcación más profundo que tiene “… $ … ‘y” … # …’ (no $) debajo (inténtalo utilizando el FORMATO HTML de arriba).

Tenga en cuenta que el “problema más largo de la subcadena común” es diferente al “problema más largo de subsecuencias comunes” que está estrechamente relacionado con el “problema de la distancia de edición”: una instancia de una subsecuencia puede tener espacios donde aparece en txt1 y en txt2, pero una instancia de una subcadena no puede tener huecos.
Un palíndromo es una cuerda, P, tal que P = retroceder (P). por ejemplo, `abba ‘= reversa (` abba’). Por ejemplo, `ississi ‘es el palíndromo más largo en` mississippi’. El palíndromo más largo de txt [1..n] se puede encontrar en tiempo O (n), por ejemplo, al crear el árbol de sufijos para txt $ reverse (txt) # o al crear el árbol de sufijos generalizados para txt e inverso (txt).
(Intentalo.)

Algunos algoritmos / códigos impresionantes para la implementación del árbol de sufijo
1.por el Dr. Sartaj Sahni (Director del Departamento CISE en la Universidad de Florida)
Diccionario 2.NIST
3. Implementación ANSI C de un árbol de sufijo.
4. Biblioteca genérica de árboles de sufijos escrita en C
5.Perl vinculante a libstree
6. # una biblioteca de árbol de sufijos genéricos más rápida escrita en C (utiliza matrices en lugar de listas vinculadas)
7. Python vinculante a Strmat
8.Página en Cs

Answer 5

Una de las mejores explicaciones que he visto en la siguiente publicación:

¿El algoritmo del árbol de sufijos de Ukkonen en inglés simple?

Answer 6

Trie
Este es un buen punto de partida para comprender los conceptos de Tries e implementarlos.

Answer 7

Puede probar este enlace tiene una buena descripción de la matriz de sufijos Sufijo Array | Los algoritmos y yo.