Eficiente búsqueda en el árbol de Huffman mientras se recuerda el camino tomado

Question

Como una pregunta de seguimiento relacionada con mi acerca de la manera eficiente de almacenar el árbol de Huffman Me preguntaba cuál sería la forma más rápida y eficiente de buscar un árbol binario (según la salida de codificación de Huffman) y de almacenar la ruta de acceso a un nodo en particular.

Esto es lo que tengo actualmente:

• Agregar nodo raíz a la cola
• mientras que la cola no está vacía, saque el elemento de la cola
  • compruebe si es lo que estamos buscando
    • sí: Siga un puntero de cabeza al nodo raíz, mientras que en cada nodo visitamos para verificar si está a la izquierda o a la derecha y tomar nota de ello.
    • salir de la búsqueda
  • encolar a la izquierda y al nodo derecho

Dado que este es un árbol Huffman, todas las entradas que estoy buscando existirán. Lo primero es una amplia búsqueda en primer lugar, que se considera la mejor para los árboles Huffman, ya que los elementos que se encuentran en la fuente con más frecuencia están en la parte superior del árbol para obtener una mejor compresión, sin embargo, no puedo encontrar una buena manera de realizar un seguimiento de cómo llegamos a un nodo en particular sin retroceder usando el puntero de cabeza que puse en el nodo.

En este caso, también obtengo todas las rutas derecha / izquierda en orden inverso, por ejemplo, si seguimos la cabeza hacia la raíz y descubrimos que desde la raíz es derecha, izquierda, izquierda, Nos quedamos a la izquierda, a la izquierda, a la derecha. o 001 en binario, cuando lo que busco es obtener 100 de manera eficiente.

También se sugirió almacenar la ruta desde la raíz hasta el nodo como un valor separado dentro del nodo, sin embargo, esto se descompondría si alguna vez tuviéramos un árbol que fuera más grande que la cantidad de bits que la variable que creamos para ese propósito pudiera contener, y en ese punto, almacenar los datos también consumiría enormes cantidades de memoria.

Answer 1

Crea un diccionario de valor - > cadena de bits, que le daría la búsqueda más rápida.

Si los valores son de un tamaño conocido, es probable que pueda arreglárselas solo con una serie de cadenas de bits y busque los valores por su índice.

Answer 2

Si está decodificando datos codificados de Huffman un bit a la vez, su rendimiento será bajo. Por mucho que quiera evitar el uso de tablas de búsqueda, esa es la única manera de hacerlo si le importa el rendimiento. La forma en que se crean los códigos de Huffman, son únicos de izquierda a derecha y se prestan perfectamente para una búsqueda rápida en la tabla.