Construção online de wavelet tree no formato da árvore de Huffman

Abstract

A wavelet tree é uma estrutura de dados bastante utilizada para representar longas cadeias de caracteres de forma otimizada e permitir consultas de rank e select. Alguns estudos já exploraram como modificar o formato dessa árvore para melhorar a complexidade de consultas e de espaço de armazenamento e mostram que o formato da árvore de Huffman é ótimo no quesito memória. Apesar de ser uma estrutura conhecida, poucos algoritmos de construções online foram propostos e este trabalho tem como objetivo propor um algoritmo online para a construção da wavelet tree no formato da árvore de Huffman, que tem como principal vantagem o fato de que o texto de referência não precisa ser armazenado em memória principal, o que pode ser um requisito desejável, ou mesmo necessário, em aplicações de streams de dados. O método proposto consiste na adaptação de uma algoritmo para construção online do Código de Huffman, representado por uma árvore estritamente binária com topologia variável. A mudança na forma da árvore implica em modificações nos bitvectors representados pelos nós, com impacto significativo no desempenho do algoritmo. O método foi implementado e testado em textos de diferentes características, e os resultados sugerem que pode representar uma alternativa viável, especialmente em memória, porém previsivelmente menos eficiente em tempo com respeito à construção offline tradicional.