La respuesta corta es que a veces las constantes son importantes.
Desde un punto de vista asintótico, todas las variaciones de trie tienen aproximadamente el mismo rendimiento: la cantidad de espacio consumido es lineal en la longitud total de las palabras almacenadas, y el tiempo necesario para insertar / buscar una palabra es lineal en su longitud.
Sin embargo, también hay otro parámetro que a veces es importante: el tamaño de su alfabeto. Aunque el tamaño del alfabeto es a menudo una constante, existe una diferencia entre las constantes 2 (sus caracteres son 0 y 1), 4 (CGAT) y 95 (ASCII imprimible de 7 bits). Además, hay algunas situaciones muy específicas en las que el tamaño del alfabeto es realmente proporcional a la longitud total de la entrada. Por lo tanto, tiene sentido considerar el tamaño del alfabeto (sigma) como una segunda variable al analizar la complejidad temporal y espacial de los intentos.
- ¿Por qué mi código solo pasa números pequeños y no los grandes (con respecto a subconjuntos no divisibles)?
- ¿Cómo usamos la función de crecimiento de un algoritmo para determinar su orden?
- ¿Cómo podemos demostrar que el reconocimiento de objetos basado en la visión es un problema np completo?
- ¿Qué es el hashing perfecto?
- ¿Cuál es la complejidad de esta recursividad F (1, n)?
Por ejemplo, en su búsqueda básica, el tiempo de búsqueda no depende del tamaño del alfabeto, pero la complejidad del espacio sí: en realidad es la longitud total de todas las palabras por el tamaño del alfabeto, porque cada nodo almacena punteros O (sigma).
Muchos usos de los intentos están en entornos donde el consumo de memoria es el cuello de botella. La búsqueda es lo suficientemente rápida por un amplio margen, por lo que puede optar por una compensación: ralentice la búsqueda ligeramente pero ahorre mucha memoria. En algunos casos (p. Ej., Cuando esto ayuda a ajustar todo su trie en su RAM), esta compensación puede incluso conducir a un mejor rendimiento práctico.
Probablemente la forma más extrema de hacer esta compensación es la representación del niño izquierdo / hermano derecho (LCRS). En este trie, cada nodo solo almacena dos bordes salientes en lugar de sigma. Por ejemplo, si su vainilla contiene un nodo A con hijos B, C, D, E, en esta representación, el puntero hijo izquierdo de A apunta a B, el puntero hermano derecho de B apunta a C, el hermano derecho de C es D, y así sucesivamente.
En estos árboles, la búsqueda se reduce a O (sigma * longitud de palabra), pero la complejidad del espacio ya no depende de sigma.
Los intentos de búsqueda ternaria van más allá de este espectro de compensación: pueden ser un poco más rápidos, pero su consumo de memoria es ligeramente mayor. (Más precisamente, la complejidad del espacio aún no depende de sigma, el peor caso de búsqueda es el mismo que en los intentos de LCRS, pero el caso promedio de búsqueda es O (log sigma * longitud de palabra) si las palabras se insertaron en orden aleatorio, y esto incluso puede convertirse en el peor de los casos si el trie es estático).
Su propuesta es almacenar un BST equilibrado de enlaces secundarios en cada nodo del trie. Esto está aún más abajo en la línea. El consumo de memoria aún no depende de sigma, pero está desperdiciando más memoria que en las soluciones anteriores: el factor constante es peor porque cada BST tiene un montón de punteros NULL adicionales. Las búsquedas serán buenas, aproximadamente tan rápido como en un trie de búsqueda ternario construido de manera óptima, pero las inserciones pueden ser más lentas en la práctica: la sobrecarga de equilibrar un nodo puede ser fácilmente más que el tiempo necesario para encontrar y modificar el lugar correcto simplemente siguiendo algunos consejos y luego cambiándolos localmente en tiempo constante. Realmente no puedo imaginar una situación en la que esta implementación particular sería deseable.
Además, para la mayoría de los usos de los intentos, el orden de los nodos secundarios en realidad no importa, y es mejor usar una pequeña tabla hash en lugar del BST.
De todos modos, el propósito de todas estas variaciones es tener una opción. Analice su situación, descubra cuáles son los cuellos de botella y elija en consecuencia.
