Usuario:Airribarra/Árbol de ondas

Un wavelet tree sobre la cadena "abracadabra". En cada nodo, los símbolos de la cadena se proyectan en dos particiones del alfabeto, y un vector de bits indica a qué partición pertenece cada símbolo. Tenga en cuenta que sólo se almacenan los vectores de bits, las cadenas de los nodos tienen sólo fines ilustrativos.

El wavelet tree es una estructura de datos sucinta para almacenar cadenas en un espacio comprimido. Generaliza $\mathbf {rank} _{q}$ y $\mathbf {select} _{q}$ , operaciones definidas en vectores de bits a alfabetos arbitrarios.

Originalmente diseñado para representar arreglos de sufijos comprimidos, ​ el wavelet tree ha encontrado aplicaciones en diversos contextos​ ​ . 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.

Propiedades

Sea $\Sigma$ un alfabeto finito con $\sigma ={|\Sigma |}$ . Al utilizar vectores de bits comprimidos en los nodos, una cadena $s\in \Sigma ^{*}$ se puede almacenar en ${|s|}H_{0}(s)+o({|s|}\log \sigma )$, dónde $H_{0}(s)$ es la entropía empírica de orden 0 de $s$ .

Si el árbol está balanceado, las operaciones $\mathbf {access}$, $\mathbf {rank} _{q}$, y $\mathbf {select} _{q}$ puede ser soportadas en tiempo $O(\log \sigma )$.

Operación de acceso

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 desde 1.
    - El nodo raíz W del wavelet tree que representa a la cadena.
    Salida: El símbolo en la posición i 

    si W.esHoja retornar W.simbolo
    si W.bitvector[i] = 0 retornar access(i - rank(W.bitvector, i), W.left)
    sino retornar access(rank(W.bitvector, i), W.right)

En este contexto, el rank de la posición $i$ en un vector de bits $b$ corresponde a la cantidad de unos que aparecen en las primeras $i$ posiciones de $b$ . Debido a que el rank se puede calcular en $O(1)$ usando bitvectors sucintos​, se puede acceder a cualquier S[i] en la cadena S en tiempo $O(\log \sigma )$ ​, siempre que el árbol esté balanceado.

Referencias

[[Categoría:Árboles (estructura)]]