Pesquisa eficiente de árvores de Huffman enquanto se lembrava do caminho

Question

Como uma pergunta de acompanhamento relacionada ao meu Pergunta sobre uma maneira eficiente de armazenar o huffman árvore Eu queria saber qual seria a maneira mais rápida e eficiente de pesquisar uma árvore binária (com base na saída de codificação do Huffman) e armazenar o caminho levado para um nó específico.

Isso é o que eu tenho atualmente:

• Adicionar nó raiz à fila
• Enquanto a fila não estiver vazia, o item pop off off
  • Verifique se é o que estamos olhando
    • Sim: siga um ponteiro de cabeça de volta ao nó raiz, enquanto em cada nó visitamos verificar se é a esquerda ou a direita e fazendo uma anotação.
    • sair da pesquisa
  • enquadre para a esquerda e o nó direito

Como essa é uma árvore de Huffman, todas as entradas que procuro existirão. O exposto acima é uma primeira pesquisa em largura, que é considerada a melhor para as árvores de Huffman, pois os itens que estão na fonte com mais frequência são mais altos na árvore para obter melhor compressão, no entanto, não consigo descobrir uma boa maneira de acompanhar Como chegamos a um nó específico sem voltar atrás usando o ponteiro da cabeça que coloquei no nó.

Nesse caso, também estou recebendo todos os caminhos direito/esquerdo em ordem inversa, por exemplo, se seguirmos a cabeça para a raiz, e descobrirmos que, da raiz, ela está à direita, à esquerda, à esquerda, fomos à esquerda , esquerda direita. ou 001 em binário, quando o que estou procurando é obter 100 de maneira eficiente.

Armazenar o caminho da raiz para o nó como um valor separado dentro do nó também foi sugerido, no entanto, isso quebraria se tivéssemos uma árvore que fosse maior do que muitos bits a variável que criamos para esse propósito poderia conter e nesse sentido O armazenamento de pontos também adotaria enormes quantidades de memória.

Answer 1

Crie um dicionário de valor -> cordão de bits, que daria a pesquisa mais rápida.

Se os valores tiverem um tamanho conhecido, você provavelmente poderá ter apenas uma variedade de rupturas e procurar os valores pelo índice.

Answer 2

Se você estiver decodificando dados codificados por Huffman um pouco de cada vez, seu desempenho será ruim. Por mais que você queira evitar o uso de tabelas de pesquisa, esse é o único caminho a percorrer se você se preocupa com o desempenho. A maneira como os códigos do Huffman são criados, eles são únicos da esquerda para a direita e se prestam perfeitamente a uma pesquisa de mesa rápida.