Árbol de ondículas

Un árbol wavelet en 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 solo se almacenan los vectores de bits; las cadenas en los nodos solo se utilizan con fines ilustrativos.

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 {rank} _{q}}$ ${\displaystyle \mathbf {select} _{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.

Propiedades

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 . ${\displaystyle \Sigma }$ ${\displaystyle \sigma ={|\Sigma |}}$ ${\displaystyle s\in \Sigma ^{*}}$ ${\displaystyle {|s|}H_{0}(s)+o({|s|}\log \sigma )}$ ${\displaystyle H_{0}(s)}$ ${\displaystyle s}$

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

Operación de acceso

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 )

• "←" denota asignación . Por ejemplo, " el elemento más grande ← " significa que el valor del elemento más grande cambia al valor del elemento .
• " return " finaliza el algoritmo y genera el siguiente valor.

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. ${\displaystyle i}$ ${\displaystyle b}$ ${\displaystyle i}$ ${\displaystyle b}$ ${\displaystyle O(\log \sigma )}$

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

Lectura adicional

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

Referencias

1. R. Grossi, A. Gupta y JS Vitter, Índices de texto comprimidos por entropía de alto orden, Actas del 14º Simposio anual SIAM/ACM sobre algoritmos discretos (SODA) , enero de 2003, 841-850.
2. 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
3. G. Navarro, Árboles wavelet para todos, Actas del 23.º Simposio anual sobre comparación de patrones combinatorios (CPM) , 2012
4. H.-L. Chan, W.-K. Hon, T.-W. Lam y K. Sadakane, Índices comprimidos para colecciones de texto dinámico, ACM Transactions on Algorithms , 3(2), 2007
5. R. Grossi y G. Ottaviano, The Wavelet Trie: mantenimiento de una secuencia indexada de cadenas en un espacio comprimido, en Actas del 31.º Simposio sobre los principios de los sistemas de bases de datos (PODS) , 2012

Enlaces externos

• Medios relacionados con el árbol Wavelet en Wikimedia Commons