Estruturas de dados sucintas

• Enquanto lia artigos para otimização de desempenho, tive meu primeiro contato com o conceito de Succinct Data Structures (estruturas de dados sucintas)
• Ao procurar artigos relacionados, acabei trocando mensagens diretamente com o renomado pesquisador, o professor Gonzalo Navarro
• Diferentemente de arrays, hash maps e árvores tradicionais, surgiu a dúvida de por que esse tipo de estrutura de dados não é mais usado
• Então, vou explicar isso brevemente

Visão geral de Succinct Data Structures

• Assim como na compressão de dados em geral, os dados são armazenados de forma comprimida, mas ainda podem ser usados diretamente nesse estado
• Diferença em relação aos métodos tradicionais de compressão: é possível acessar e manipular os dados sem descompactá-los
• É uma área com pesquisa ativa nos últimos 25 anos

Uso em Rust

• Em programação de sistemas, desempenho e uso de memória são importantes, então esse tipo de estrutura de dados tem grande potencial de utilidade
• As pesquisas existentes foram feitas principalmente em C++, mas implementações em Rust também começaram a aparecer
• Apresenta bibliotecas que podem ser úteis para desenvolvedores Rust

Bit Vectors (vetores de bits)

• Exemplo de array de bits: [0, 1, 0, 1, 1, 0, 1, 0]
• Em sistemas de 64 bits, é possível armazenar 64 bits em um único inteiro, economizando espaço
• O vetor de bits em si não é uma estrutura sucinta, mas existem formas eficientes de aproveitá-lo

Rank/Select Bit Vector

• Operação Rank: calcula quantas vezes 1 apareceu antes de um determinado índice
  • Exemplo: rank(3) → 2
• Operação Select: retorna a posição em que aparece o 1 de uma determinada ocorrência
  • Exemplo: select(2) → 3
• Pode ser executado com complexidade de tempo O(1)
• Tem baixo overhead de memória e é útil ao lidar com strings grandes
• Casos de uso
  • É útil ao armazenar uma string grande dividida em pequenas substrings
  • Permite encontrar com eficiência a qual substring um determinado índice pertence
  • Com armazenamento comprimido, reduz o uso de memória mantendo buscas rápidas
• Bibliotecas Rust
  • vers: oferece alto desempenho e overhead mínimo
  • sucds: oferece suporte a implementações esparsas (Sparse) como SArray
  • vers se destaca na criação eficiente de estruturas de dados e deve oferecer suporte a implementações esparsas no futuro

Wavelet Matrix (matriz wavelet)

• Expande o conceito de Rank/Select para dados com alfabetos maiores
• Ex.: análise de sequências de DNA (A, C, G, T) ou busca em texto (caracteres UTF-8, 256 símbolos)
• Funciona com base em vetores de bits Rank/Select
• Bibliotecas Rust
  • vers inclui uma implementação de matriz wavelet

FM-Index (índice de strings comprimido)

• Armazena grandes volumes de dados textuais de forma comprimida, mantendo funcionalidade de busca
• Funções principais:
  • count(pattern): calcula quantas vezes um determinado padrão (string) aparece
  • locate(pattern): retorna todos os índices em que esse padrão aparece
• É útil em busca de sequências de DNA e busca em grandes volumes de texto
• Bibliotecas Rust
  • É possível usar a biblioteca fm-index
  • Antes era usado fid, mas após a migração para vers, o desempenho melhorou

Balanced Parentheses (representação por parênteses balanceados)

• Permite armazenar uma estrutura de árvore comprimida em algo próximo de 2 bits por nó
• Árvore de exemplo:

   a  
 /   \  
b     c  

• Pode ser representada como (()())
• Também pode ser convertida para 1 (parêntese de abertura) e 0 (parêntese de fechamento): 110100
• Usa operações Rank/Select para otimizar operações de navegação na árvore
• Bibliotecas Rust
  • Em implementação no branch dev-bp de vers

Aplicação: armazenamento e processamento de XML

• É possível armazenar XML usando a representação por parênteses balanceados
• Vetores de bits Rank/Select são usados para processar com eficiência tags XML (p, div etc.)
• O FM-Index melhora o desempenho de busca em texto

Conclusão

• Estruturas de dados sucintas oferecem ao mesmo tempo baixo uso de memória e operações rápidas
• Há muita pesquisa em C++, mas implementações em Rust também estão avançando ativamente
• Ao colaborar com pesquisadores e desenvolvedores open source, foram descobertas muitas possibilidades
• Há grande chance de uso mais amplo em várias áreas da ciência da computação no futuro

[qwqwhs]

Estruturas comprimidas que utilizam wavelet são amplamente usadas como padrão no Djvu. A compressão de imagens é realmente excelente.

[GN⁺]

Comentários do Hacker News

• Enviei um e-mail para Gonzalo Navarro com uma pergunta, e isso acabou levando à escrita de um artigo em coautoria

  • Outro artigo dele trata de uma implementação simples de rank/select em bitvector ao combinar algumas ideias elegantes
  • Nessa época, fiquei muito interessado em estruturas de dados sucintas e escrevi uma biblioteca em Rust que implementa vários tipos de bitvector e uma wavelet matrix
  • Do ponto de vista de visualização de dados, eu queria saber se estruturas de dados com eficiência espacial poderiam melhorar fundamentalmente a exploração interativa de grandes conjuntos de dados no lado do cliente

• Estou nessa área há mais de 30 anos, mas foi a primeira vez que ouvi falar de "estruturas de dados sucintas"

  • Se eu não tivesse visto esta postagem, provavelmente não saberia disso
  • Se essa estrutura de dados tiver aplicações práticas em processamento de grafos, isso pode ser uma descoberta importante
  • Esse tema parece atraente

• Estruturas de dados sucintas podem não ser mais rápidas do que estruturas tradicionais quando o conjunto de dados cabe na memória

  • Mas, em conjuntos de dados grandes, o tempo de acesso ao armazenamento domina, então estruturas de dados sucintas levam vantagem
  • Árvores sucintas são como obras de arte

• Ouvi falar pela primeira vez do conceito de estruturas de dados sucintas por meio de Edward Kmett

  • Ele é um famoso desenvolvedor de bibliotecas Haskell e fez uma palestra sobre estruturas de dados sucintas há muito tempo

• Estruturas de dados sucintas são muito divertidas

  • Implementei isso em Zig, e a principal implementação é uma função de hash perfeita mínima que usa elementos com menos de 4 bits
  • Implementar esses algoritmos é como fazer mágica

• O livro do Navarro é um excelente levantamento

  • A aula de Erik Demaine sobre estruturas de dados sucintas também é excelente

• Passei a manhã estudando estruturas de dados sucintas, e a eficiência de memória é impressionante

  • Em um projeto de análise de arquivos XML grandes, estamos consumindo muita RAM
  • O conceito de wavelet matrix parece promissor para trabalhos centrados em texto

• Há formas de tornar eficiente a representação em memória de nós de structs grandes

  • Você atribui offsets para campos usados com pouca frequência e usa uma máscara de bits para indicar a presença dos campos
  • Masking e popcount permitem acesso rápido

• A Marisa trie é uma estrutura de dados sucinta muito elegante e útil

  • Também é mencionada no livro High Performance Python

• Minha biblioteca básica para estruturas de dados sucintas é a SDSL-Lite