Usuario:Airribarra/Wavelet Tree
![](http://upload.wikimedia.org/wikipedia/commons/0/01/Wavelet_tree.png)
El wavelet tree es una estructura de datos sucinta para almacenar cadenas en un espacio comprimido. Generaliza y , operaciones definidas en vectores de bits a alfabetos arbitrarios.
Originalmente diseñado para representar arreglos de sufijos comprimidos, [1] el wavelet tree ha encontrado aplicaciones en diversos contextos[2] [3] . El árbol se define particionando recursivamente el alfabeto en pares de subconjuntos; las hojas del árbol corresponden a símbolos individuales del alfabeto, y en cada nodo interno un vector de bits almacena si un símbolo de la cadena pertenece a un subconjunto o al otro.
El nombre se origina de una analogía con la transformada wavelet para señales, la cual descompone recursivamente una señal en componentes de baja y alta frecuencia.
Propiedades
[editar]Sea un alfabeto finito con . Al utilizar vectores de bits comprimidos 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á balanceado, las operaciones , , y puede ser soportadas en tiempo .
Operación de acceso
[editar]Un wavelet tree representa una cadena a través de un vector de bits. Si conocemos el alfabeto, entonces se puede inferir la cadena recorriendo el árbol desde la raíz hasta las hojas. Para encontrar el símbolo en la i-ésima posición de la cadena :
Algoritmo access(i, W) Entrada: - La posición i en la cadena para la cual queremos conocer el símbolo, comenzando a indexar desde 1. - El nodo raíz W del wavelet tree sobre el cual realizamos la consulta Salida: El símbolo en la posición i if W.esHoja return W.simbolo if W.bitvector[i] = 0 return access(i - rank(W.bitvector, i), W.left) else return access(rank(W.bitvector, i), W.right)
En este contexto, el rank de la posición de un vector de bits corresponde a la cantidad de unos que aparecen en las primeras posiciones de . Dado que el rank se puede calcular en usando diccionarios sucintos[4], se puede acceder a cualquier S[i] en la cadena S en tiempo [3], siempre y cuando el árbol esté balanceado.
Referencias
[editar][[Categoría:Árboles (estructura)]]
- ↑ a b R. Grossi, A. Gupta, and J. S. Vitter, High-order entropy-compressed text indexes, Proceedings of the 14th Annual SIAM/ACM Symposium on Discrete Algorithms (SODA), January 2003, 841-850.
- ↑ a b P. Ferragina, R. Giancarlo, G. Manzini, The myriad virtues of Wavelet Trees, Information and Computation, Volume 207, Issue 8, August 2009, Pages 849-866
- ↑ Munro, J. Ian (1996). «Tables». En Chandru, V., ed. Foundations of Software Technology and Theoretical Computer Science. Lecture Notes in Computer Science (en inglés) (Springer): 37-42. ISBN 978-3-540-49631-1. doi:10.1007/3-540-62034-6_35. Consultado el 17 de octubre de 2023.