¿Cómo depende el tiempo de ejecución del algoritmo de Ukkonen del tamaño del alfabeto?

19

Me preocupa la cuestión del tiempo de ejecución asintótico del algoritmo de Ukkonen , quizás el algoritmo más popular para construir árboles de sufijos en tiempo lineal (?).

Aquí hay una cita del libro "Algoritmos sobre cadenas, árboles y secuencias" de Dan Gusfield (sección 6.5.1):

"... los algoritmos Aho-Corasick, Weiner, Ukkonen y McCreight requieren espacio , o el límite de tiempo O ( m ) debe reemplazarse con el mínimo de O ( m log m ) y O ( m log | Σ | ) ".Θ(m|Σ|)O(m)O(mlog⁡m)O(mlog⁡|Σ|)

[ es la longitud de la cadena y Σ es el tamaño del alfabeto]mΣ

No entiendo por qué eso es cierto.

  • Espacio: bueno, en caso de que representemos ramas fuera de los nodos usando matrices de tamaño , entonces, de hecho, terminamos con el uso de espacio Θ ( m | Σ | ) . Sin embargo, hasta donde puedo ver, también es posible almacenar las ramas usando tablas hash (por ejemplo, diccionarios en Python). Entonces tendríamos solo Θ ( m ) punteros almacenados en todas las tablas hash en conjunto (ya que hay Θ ( m ) bordes en el árbol), mientras aún pudiéramos acceder a los nodos hijos en O ( 1 )Θ(|Σ|)Θ(m|Σ|)Θ(m)Θ(m)O(1) tiempo, tan rápido como cuando se usan matrices.
  • Tiempo : como se mencionó anteriormente, el uso de tablas hash nos permite acceder a las ramas salientes de cualquier nodo en el tiempo . Dado que el algoritmo de Ukkonen requiere operaciones O ( m ) (incluido el acceso a nodos secundarios), el tiempo de ejecución general también sería O ( m ) .O(1)O(m)O(m)

Le estaría muy agradecido por cualquier pista sobre por qué estoy equivocado en mis conclusiones y por qué Gusfield tiene razón sobre la dependencia del algoritmo de Ukkonen en el alfabeto.

algorithms data-structures algorithm-analysis strings Mikhail Dubov
fuente
3
No creo que haya ninguna prueba de que sea imposible un límite de tiempo / espacio independiente del tamaño del alfabeto. Creo que Gusfield hizo la declaración porque no hay un método conocido para deshacerse del tiempo límite por completo. Para establecer uno, tendría que elaborar sus funciones hash con más detalle. Un verdadero tiempo de O (1) en el peor de los casos para la búsqueda de hash requiere un hash perfecto. No tengo claro cómo hacer esto durante el algoritmo (porque las entradas hash no son estáticas en ese punto).
jogojapan
(continuación) Podría hacerlo una vez que el árbol esté completo, pero entonces el tiempo límite para el algoritmo en sí no se modificará. (+1 para la pregunta sin embargo.)
jogojapan
1
Contexto útil: explicación del algoritmo de Ukkonen
FrankW

Respuestas:

2

Como @jogojapan menciona en los comentarios, el hasing generalmente solo se amortiza , por lo que solo obtendría límites amortizados para el algoritmo. Sin embargo, creo que ni siquiera obtienes esto: para obtener el hash O ( 1 ) amortizado , las tablas hash deben tener un tamaño ΩO(1)O(1) , por lo que aún tienesespacio Θ ( m Σ ) (y al mismo tiempo requisito de inicialización).Ω(Σ)Θ(mΣ)

Además, en la práctica, el tiempo para configurar todas estas tablas hash será mucho mayor que el tiempo para configurar matrices.

Es posible que le vaya mejor con el uso de una tabla hash global que está indexada con pares (nodo, carácter), pero al menos el argumento "solo amortizado" permanecerá.

FrankW
fuente