La wavelet tree es una estructura de datos sucinta para almacenar cadenas en el espacio comprimido. Generaliza la y operaciones definidas en vectores de bits a alfabetos arbitrarios.
Introducido originalmente para representar matrices de sufijos comprimidos , [1] ha encontrado aplicación en varios contextos. [2] [3] El árbol se define dividiendo recursivamente el alfabeto en pares de subconjuntos; las hojas corresponden a símbolos individuales del alfabeto, y en cada nodo un bitvector almacena si un símbolo de la cadena pertenece a un subconjunto o al otro.
El nombre deriva de una analogía con la transformada wavelet para señales, que descompone recursivamente una señal en componentes de baja y alta frecuencia.
Propiedades
Dejar ser un alfabeto finito con . Mediante el uso de diccionarios sucintos en los nodos, una cadena se puede almacenar en , dónde es la entropía empírica de orden 0 de.
Si el árbol está equilibrado, las operaciones , , y se puede apoyar en hora.
Operación de acceso
Un árbol de ondículas contiene una representación de mapa de bits de una cadena. Si conocemos el conjunto alfabético, entonces la cadena exacta se puede inferir rastreando bits por el árbol. Para encontrar la letra en la i- ésima posición en la cadena: -
Si el i- ésimo elemento en la raíz es 0, nos movemos al hijo de la izquierda, de lo contrario, nos movemos al hijo de la derecha. Ahora nuestro índice en el nodo hijo es el rango del bit respectivo en el nodo padre. Este rango se puede calcular en O (1) utilizando diccionarios sucintos . Además de pasar a un niño, también refinamos nuestro alfabeto al subconjunto respectivo. Estos pasos se repiten hasta llegar a una hoja, donde nos queda solo una letra en nuestro alfabeto, que es la que estábamos buscando. Por lo tanto, para un árbol equilibrado, se puede acceder a cualquier S [i] en la cadena S en [3] tiempo.
Extensiones
En la literatura se han presentado varias extensiones de la estructura básica. Para reducir la altura del árbol, se pueden utilizar nodos multiarios en lugar de binarios. [2] La estructura de datos se puede hacer dinámica, admitiendo inserciones y eliminaciones en puntos arbitrarios de la cadena; esta característica permite la implementación de índices FM dinámicos . [4] Esto se puede generalizar aún más, permitiendo que las operaciones de actualización cambien el alfabeto subyacente: Wavelet Trie [5] explota la estructura trie en un alfabeto de cadenas para permitir modificaciones dinámicas del árbol.
Otras lecturas
- Árboles Wavelet . Una publicación de blog que describe la construcción de un árbol de wavelets, con ejemplos.
Referencias
- ^ R. Grossi, A. Gupta y JS Vitter, índices de texto comprimido de entropía de alto orden , Actas del 14 ° Simposio anual SIAM / ACM sobre algoritmos discretos (SODA) , enero de 2003, 841-850.
- ^ a b P. Ferragina, R. Giancarlo, G. Manzini, Las innumerables virtudes de los árboles Wavelet , Información y Computación , Volumen 207, Número 8, Agosto de 2009, Páginas 849-866
- ^ H.-L. Chan, W.-K. Hon, T.-W. Lam y K. Sadakane, índices comprimidos para colecciones de texto dinámicas , ACM Transactions on Algorithms , 3 (2), 2007
- ^ R. Grossi y G. Ottaviano, The Wavelet Trie: mantenimiento de una secuencia indexada de cadenas en un espacio comprimido , en las actas del 31 ° Simposio sobre los principios de los sistemas de bases de datos (PODS) , 2012
enlaces externos
- Medios relacionados con Wavelet Tree en Wikimedia Commons