Wavelet tree

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.

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.

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.

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

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 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 $i$ de un vector de bits $b$ corresponde a la cantidad de unos que aparecen en las primeras $i$ posiciones de $b$ . Dado que el rank se puede calcular en $O(1)$ usando diccionarios sucintos​, se puede acceder a cualquier S[i] en la cadena S en tiempo $O(\log \sigma )$ ​, siempre y cuando el árbol esté balanceado.

Referencias

• Datos: Q2552862
• Multimedia: Wavelet Tree / Q2552862