Árbol de ondículas

El árbol Wavelet es una estructura de datos concisa para almacenar cadenas en un espacio comprimido. Generaliza las operaciones y definidas en vectores de bits a alfabetos arbitrarios. ${\displaystyle \mathbf {rango} _{q}}$${\displaystyle \mathbf {seleccionar} _{q}}$

Originalmente introducido 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 vector de bits 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 frecuencia y alta frecuencia.

Sea un alfabeto finito con . Al utilizar diccionarios sucintos en los nodos, se puede almacenar una cadena en , donde es la entropía empírica de orden 0 de . ${\estilo de visualización \Sigma}$${\displaystyle \sigma ={|\Sigma |}}$${\displaystyle s\en \Sigma ^{*}}$${\displaystyle {|s|}H_{0}(s)+o({|s|}\log \sigma )}$$Estilo de visualización H_{0}(s)$${\estilo de visualización s}$

Si el árbol está equilibrado, las operaciones , y pueden soportarse a tiempo. ${\displaystyle \mathbf {acceso} }$${\displaystyle \mathbf {rango} _{q}}$${\displaystyle \mathbf {seleccionar} _{q}}$${\displaystyle O(\log \sigma )}$

Un árbol wavelet contiene una representación en mapa de bits de una cadena. Si conocemos el conjunto de letras, entonces se puede inferir la cadena exacta rastreando bits a lo largo del árbol. Para encontrar la letra en la posición i ^de la cadena:

Acceso al algoritmo
  Aporte:
    - La posición i en la cadena de la que queremos saber la letra, comenzando en 1.
    - El nodo superior W del árbol wavelet que representa la cadena
  Salida: La letra en la posición i

    si  W.isLeafNode  devuelve  W.letter 
    si  W.bitvector[i] = 0 devuelve acceso( i - rango( W.bitvector , i ), W.izquierda )
     de lo contrario  devuelve acceso(rango( W.bitvector , i ), W.derecha )

En este contexto, el rango de una posición en un vector de bits es la cantidad de unos que aparecen en las primeras posiciones de . Debido a que el rango se puede calcular en O(1) mediante el uso de diccionarios sucintos , se puede acceder a cualquier S[i] en la cadena S en tiempo ^[3] , siempre que el árbol esté equilibrado. ${\estilo de visualización i}$${\estilo de visualización b}$${\estilo de visualización i}$${\estilo de visualización b}$${\displaystyle O(\log \sigma )}$

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: el Wavelet Trie ^[5] explota la estructura trie en un alfabeto de cadenas para permitir modificaciones dinámicas del árbol.

• Árboles de ondículas. Una publicación de blog que describe la construcción de un árbol de ondículas, con ejemplos.

• Medios relacionados con el árbol Wavelet en Wikimedia Commons