Estructuras de datos sucintas

• Mientras leía artículos para optimizar el rendimiento, me encontré por primera vez con el concepto de Succinct Data Structures (estructuras de datos sucintas)
• Mientras buscaba artículos relacionados, terminé intercambiando mensajes directamente con el reconocido investigador Gonzalo Navarro
• A diferencia de arreglos, hash maps y árboles tradicionales, me surgió la duda de por qué estas estructuras de datos no se usan más ampliamente
• Quiero dar una explicación breve sobre esto

Panorama general de las Succinct Data Structures

• Al igual que la compresión de datos convencional, almacenan los datos de forma comprimida, pero además pueden usarse directamente aun en estado comprimido
• Diferencia frente a la compresión tradicional: se puede acceder y manipular la información sin descomprimirla
• Es un campo en el que se ha investigado activamente durante los últimos 25 años

Uso en Rust

• En la programación de sistemas, el rendimiento y el uso de memoria son importantes, por lo que estas estructuras de datos tienen mucho potencial
• La investigación existente se ha concentrado principalmente en C++, pero también han empezado a aparecer implementaciones en Rust
• Se presentan bibliotecas que pueden ser útiles para desarrolladores de Rust

Bit Vectors (vectores de bits)

• Ejemplo de arreglo de bits: [0, 1, 0, 1, 1, 0, 1, 0]
• En un sistema de 64 bits, es posible almacenar 64 bits en un solo entero, lo que ahorra espacio
• Un vector de bits por sí solo no es una estructura sucinta, pero existen formas de aprovecharlo eficientemente

Rank/Select Bit Vector

• Operación Rank: calcula cuántas veces aparece un 1 antes de un índice determinado
  • Ejemplo: rank(3) → 2
• Operación Select: devuelve la posición en la que aparece el 1 número n
  • Ejemplo: select(2) → 3
• Puede ejecutarse con complejidad temporal O(1)
• Tiene poco overhead de memoria y resulta útil al trabajar con cadenas grandes
• Casos de uso
  • Es útil al dividir y almacenar una cadena grande en unidades de cadenas más pequeñas
  • Permite encontrar de forma eficiente a qué subcadena pertenece un índice específico
  • Gracias al almacenamiento comprimido, reduce el uso de memoria y mantiene búsquedas rápidas
• Bibliotecas de Rust
  • vers: ofrece alto rendimiento y un overhead mínimo
  • sucds: ofrece implementaciones dispersas como SArray
  • vers destaca por la creación eficiente de estructuras de datos y planea agregar soporte para implementaciones dispersas más adelante

Wavelet Matrix (matriz wavelet)

• Extiende el concepto de Rank/Select a datos con alfabetos más grandes
• Ejemplo: análisis de secuencias de ADN (A, C, G, T) o búsqueda de texto (caracteres UTF-8, 256 símbolos)
• Funciona sobre la base de vectores de bits Rank/Select
• Bibliotecas de Rust
  • vers incluye una implementación de matriz wavelet

FM-Index (índice comprimido de cadenas)

• Permite almacenar grandes volúmenes de texto de forma comprimida mientras mantiene funciones de búsqueda
• Funciones principales:
  • count(pattern): calcula cuántas veces aparece un patrón (cadena) específico
  • locate(pattern): devuelve todos los índices donde aparece ese patrón
• Es útil para la búsqueda en secuencias de ADN y la búsqueda de texto a gran escala
• Bibliotecas de Rust
  • Se puede usar la biblioteca fm-index
  • Antes se usaba fid, pero tras migrar a vers mejoró el rendimiento

Balanced Parentheses (representación de paréntesis balanceados)

• Permite comprimir una estructura de árbol hasta un nivel de 2 bits por nodo
• Árbol de ejemplo:

   a  
 /   \  
b     c  

• Puede representarse como (()())
• También puede convertirse a 1 (paréntesis de apertura) y 0 (paréntesis de cierre): 110100
• Usa operaciones Rank/Select para optimizar las operaciones de recorrido dentro del árbol
• Bibliotecas de Rust
  • Se está implementando en la rama dev-bp de vers

Aplicación: almacenamiento y procesamiento de XML

• Es posible almacenar XML usando una representación de paréntesis balanceados
• Para procesar eficientemente etiquetas XML (p, div, etc.), se utilizan vectores de bits Rank/Select
• Se puede usar FM-Index para mejorar el rendimiento de búsqueda de texto

Conclusión

• Las estructuras de datos sucintas ofrecen al mismo tiempo bajo uso de memoria y operaciones rápidas
• Aunque se ha investigado mucho en C++, también se están implementando activamente en Rust
• Al colaborar con investigadores y desarrolladores de código abierto, se han descubierto muchas posibilidades
• Es muy probable que en el futuro se usen más ampliamente en diversos campos de las ciencias de la computación

[qwqwhs]

Las estructuras comprimidas que aprovechan wavelet se usan muy bien como estándar en Djvu. La compresión de imágenes es realmente excelente.

[GN⁺]

Opiniones de Hacker News

• Le envió un correo a Gonzalo Navarro para hacerle una pregunta, y eso terminó en que escribieran un artículo juntos

  • Otro de sus artículos trata una implementación simple de rank/select sobre bitvectors combinando varias ideas elegantes
  • En esa época se interesó mucho por las estructuras de datos sucintas y escribió una biblioteca en Rust que implementa varios tipos de bitvectors y wavelet matrices
  • Desde la perspectiva de la visualización de datos, se preguntaba si las estructuras de datos eficientes en espacio podrían mejorar de forma fundamental la exploración interactiva de grandes conjuntos de datos del lado del cliente

• Lleva más de 30 años en este campo, pero era la primera vez que escuchaba el término "estructuras de datos sucintas"

  • Probablemente no lo habría sabido si no hubiera visto esta publicación
  • Si esta estructura de datos tiene aplicaciones prácticas en el procesamiento de grafos, podría ser un hallazgo importante
  • El tema le resulta atractivo

• Las estructuras de datos sucintas podrían no ser más rápidas que las estructuras tradicionales cuando el conjunto de datos cabe en memoria

  • Pero en conjuntos de datos grandes, como el tiempo de acceso al almacenamiento domina, las estructuras de datos sucintas resultan ventajosas
  • Los árboles sucintos son como obras de arte

• Escuchó por primera vez el concepto de estructuras de datos sucintas a través de Edward Kmett

  • Es un famoso desarrollador de bibliotecas de Haskell y hace mucho dio una charla sobre estructuras de datos sucintas

• Las estructuras de datos sucintas son muy divertidas

  • Las implementó en Zig, y la implementación principal es una función hash perfecta mínima que usa elementos de menos de 4 bits
  • Implementar estos algoritmos se siente como magia

• El libro de Navarro es una excelente obra de referencia

  • La clase de Erik Demaine sobre estructuras de datos sucintas también es excelente

• Pasó la mañana aprendiendo sobre estructuras de datos sucintas, y la eficiencia de memoria le sorprendió

  • Está consumiendo mucha RAM en un proyecto para analizar archivos XML grandes
  • El concepto de wavelet matrix parece prometedor para trabajos centrados en texto

• Hay una forma de hacer eficiente la representación en memoria de nodos dentro de estructuras grandes

  • Se asignan offsets para campos de uso poco frecuente y se usa una máscara de bits para indicar la presencia de cada campo
  • El enmascaramiento y popcount permiten un acceso rápido

• Marisa trie es una estructura de datos sucinta muy genial y útil

  • También se menciona en el libro High Performance Python

• Mi biblioteca base para estructuras de datos sucintas es SDSL-Lite