algorithm - arboles de sufijos
Complejidad de construir un Árbol de sufijos (1)
Para construir un árbol de sufijos, en el peor de los casos si todas las letras de la cadena son diferentes, la complejidad sería algo así como
n + (n-1) + (n-2) ... 1 = n*(n+1)/2
que es O (n ^ 2).
Sin embargo, según http://en.wikipedia.org/wiki/Suffix_tree construir un árbol de sufijo toma O (n) tiempo. que me estoy perdiendo aqui?
Su intuición detrás de por qué el algoritmo debería ser Θ (n 2 ) es buena, pero la mayoría de los árboles sufijo están diseñados de una manera que elimina la necesidad de esta complejidad de tiempo. Intuitivamente, parece que necesitas Θ (n 2 ) nodos diferentes para contener todos los sufijos diferentes, porque necesitarías n + (n - 1) + ... + 1 nodos diferentes. Sin embargo, los árboles de sufijo se diseñan típicamente para que no haya un solo nodo por carácter en el sufijo. En cambio, cada borde está etiquetado normalmente con una secuencia de caracteres que son subcadenas de la cadena original. Todavía puede parecer que necesitarías Θ (n 2 ) tiempo para construir este árbol porque tendrías que copiar las subcadenas a estos bordes, pero normalmente esto se evita con un lindo truco, ya que todos los bordes están etiquetados con cadenas que son subcadenas de la entrada, los bordes pueden etiquetarse con una posición inicial y final, lo que significa que un borde que abarca Θ (n) caracteres se puede construir en O (1) tiempo y usando O (1) espacio.
Dicho esto, la construcción de árboles de sufijo todavía es muy difícil de hacer. Los algoritmos Θ (n) a los que se hace referencia en Wikipedia no son fáciles. Uno de los primeros algoritmos que se ha encontrado que funciona en tiempo lineal es el Algoritmo de Ukkonen , que se describe comúnmente en los libros de texto sobre algoritmos de cadenas (como Algoritmos en cadenas, Árboles y Secuencias ) . El documento original está vinculado en Wikipedia. Los enfoques más modernos funcionan construyendo primero un conjunto de sufijos y usándolo para luego construir el árbol de sufijos.
¡Espero que esto ayude!