c++ performance huffman-code

c++ - Manera eficiente de almacenar el árbol Huffman



performance huffman-code (5)

Estoy escribiendo una herramienta de codificación / decodificación Huffman y estoy buscando una forma eficiente de almacenar el árbol Huffman que se creó para almacenar dentro del archivo de salida.

Actualmente hay dos versiones diferentes que estoy implementando.

  1. Éste lee el archivo completo en memoria carácter por carácter y crea una tabla de frecuencia para todo el documento. Esto solo requeriría generar el árbol una vez, y por lo tanto la eficiencia no es tan preocupante, excepto si el archivo de entrada es pequeño.
  2. El otro método que estoy usando es leer un trozo de datos, de aproximadamente 64 kilobytes de tamaño y ejecutar el análisis de frecuencia sobre eso, crear un árbol y codificarlo. Sin embargo, en este caso, antes de cada fragmento necesitaré generar mi árbol de frecuencias para que el decodificador pueda reconstruir su árbol y decodificar correctamente el archivo codificado. Aquí es donde entra en juego la eficiencia ya que quiero ahorrar tanto espacio como sea posible.

En mis búsquedas hasta ahora no he encontrado una buena manera de almacenar el árbol en el menor espacio posible, ¡espero que la comunidad de StackOverflow pueda ayudarme a encontrar una buena solución!

Como ya tiene que implementar el código para manejar una capa de bits en la parte superior de su secuencia / archivo organizado por bytes, esta es mi propuesta.

No almacene las frecuencias reales, no son necesarias para la decodificación. Sin embargo, necesitas el árbol real.

Entonces, para cada nodo, comenzando desde la raíz:

  1. Si leaf-node: Salida de 1 bit + carácter de N bit / byte
  2. Si no es un nodo de hoja, da salida a 0 bits. Luego codifique ambos nodos secundarios (primero a la izquierda y luego a la derecha) de la misma manera

Para leer, haz esto:

  1. Leer poco. Si es 1, lea el carácter / byte de N bits, regrese el nuevo nodo alrededor sin ningún elemento secundario
  2. Si el bit era 0, decodifica los nodos secundarios izquierdo y derecho de la misma manera, y devuelve un nuevo nodo alrededor de ellos con esos elementos secundarios, pero sin valor

Un nodo hoja es básicamente cualquier nodo que no tiene hijos.

Con este enfoque, puede calcular el tamaño exacto de su salida antes de escribirla, para averiguar si las ganancias son suficientes para justificar el esfuerzo. Esto supone que tiene un diccionario de pares clave / valor que contiene la frecuencia de cada carácter, donde la frecuencia es el número real de ocurrencias.

Pseudocódigo para el cálculo:

Tree-size = 10 * NUMBER_OF_CHARACTERS - 1 Encoded-size = Sum(for each char,freq in table: freq * len(PATH(char)))

El cálculo del tamaño del árbol tiene en cuenta los nodos hoja y no hoja, y hay un nodo menos en línea que caracteres.

SIZE_OF_ONE_CHARACTER sería el número de bits, y esos dos le darían el número total de bits que ocupará mi enfoque para el árbol + los datos codificados.

PATH (c) es una función / tabla que produciría la ruta de bits desde la raíz hasta ese carácter en el árbol.

Aquí hay un pseudo-código con aspecto de C # para hacerlo, que asume que un carácter es simplemente un byte simple.

void EncodeNode(Node node, BitWriter writer) { if (node.IsLeafNode) { writer.WriteBit(1); writer.WriteByte(node.Value); } else { writer.WriteBit(0); EncodeNode(node.LeftChild, writer); EncodeNode(node.Right, writer); } }

Para leerlo de nuevo en:

Node ReadNode(BitReader reader) { if (reader.ReadBit() == 1) { return new Node(reader.ReadByte(), null, null); } else { Node leftChild = ReadNode(reader); Node rightChild = ReadNode(reader); return new Node(0, leftChild, rightChild); } }

Un ejemplo (simplificado, uso de propiedades, etc.) Implementación del nodo:

public class Node { public Byte Value; public Node LeftChild; public Node RightChild; public Node(Byte value, Node leftChild, Node rightChild) { Value = value; LeftChild = leftChild; RightChild = rightChild; } public Boolean IsLeafNode { get { return LeftChild == null; } } }

Aquí hay un resultado de muestra de un ejemplo específico.

Entrada: AAAAAABCCCCCCDDEEEEE

Frecuencias:

  • A: 6
  • B: 1
  • C: 6
  • D: 2
  • E: 5

Cada personaje tiene solo 8 bits, por lo que el tamaño del árbol será 10 * 5 - 1 = 49 bits.

El árbol podría verse así:

20 ---------- | 8 | ------- 12 | 3 ----- | ----- A C E B D 6 6 5 1 2

Entonces las rutas para cada personaje son las siguientes (0 es left, 1 right):

  • A: 00
  • B: 110
  • C: 01
  • D: 111
  • E: 10

Entonces para calcular el tamaño de salida:

  • A: 6 ocurrencias * 2 bits = 12 bits
  • B: 1 ocurrencia * 3 bits = 3 bits
  • C: 6 ocurrencias * 2 bits = 12 bits
  • D: 2 ocurrencias * 3 bits = 6 bits
  • E: 5 ocurrencias * 2 bits = 10 bits

La suma de bytes codificados es 12 + 3 + 12 + 6 + 10 = 43 bits

Agregue eso a los 49 bits del árbol, y la salida será de 92 bits o 12 bytes. Compare eso con los 20 * 8 bytes necesarios para almacenar los 20 caracteres originales sin codificar, ahorrará 8 bytes.

El resultado final, incluido el árbol para comenzar, es el siguiente. Cada carácter en la secuencia (AE) se codifica como 8 bits, mientras que 0 y 1 es solo un bit. El espacio en la secuencia es solo para separar el árbol de los datos codificados y no ocupa espacio en el resultado final.

001A1C01E01B1D 0000000000001100101010101011111111010101010

Para el ejemplo concreto que tiene en los comentarios, AABCDEF, obtendrá esto:

Entrada: AABCDEF

Frecuencias:

  • A: 2
  • B: 1
  • C: 1
  • D: 1
  • E: 1
  • F: 1

Árbol:

7 ------------- | 4 | --------- 3 2 2 ----- ----- ----- A B C D E F 2 1 1 1 1 1

Caminos:

  • A: 00
  • B: 01
  • C: 100
  • D: 101
  • E: 110
  • F: 111

Árbol: 001A1B001C1D01E1F = 59 bits
Datos: 000001100101110111 = 18 bits
Suma: 59 + 18 = 77 bits = 10 bytes

Dado que el original tenía 7 caracteres de 8 bits = 56, tendrá demasiada información sobre esos pequeños datos.

El árbol generalmente se crea a partir de una tabla de frecuencias de los bytes. Así que guarde esa tabla, o solo los bytes mismos ordenados por frecuencia, y vuelva a crear el árbol sobre la marcha. Por supuesto, esto supone que está construyendo el árbol para representar bytes individuales, no bloques más grandes.

ACTUALIZACIÓN : como señaló j_random_hacker en un comentario, en realidad no puedes hacer esto: necesitas los valores de frecuencia por sí mismos. Se combinan y "burbuja" hacia arriba a medida que construyes el árbol. Esta página describe la forma en que se construye un árbol a partir de la tabla de frecuencias. Como beneficio adicional, también evita que se elimine esta respuesta mencionando una forma de guardar el árbol:

La forma más fácil de generar el árbol huffman es, desde la raíz, volcar primero el lado izquierdo y luego el lado derecho. Para cada nodo se genera un 0, para cada hoja se genera un 1 seguido de N bits que representan el valor.

Si tienes suficiente control sobre la generación del árbol, puedes hacer que funcione como un árbol canónico (de la misma forma que lo hace DEFLATE , por ejemplo), lo que básicamente significa que creas reglas para resolver cualquier situación ambigua al construir el árbol. Luego, al igual que DEFLATE, todo lo que tienes que almacenar son las longitudes de los códigos para cada personaje.

Es decir, si tuviera el árbol / códigos Lasse mencionado anteriormente:

  • A: 00
  • B: 110
  • C: 01
  • D: 111
  • E: 10

Entonces podrías almacenarlos como: 2, 3, 2, 3, 2

Y eso es en realidad información suficiente para regenerar la tabla huffman, asumiendo que siempre está usando el mismo conjunto de caracteres, por ejemplo, ASCII. (Lo que significa que no puede omitir las letras; debe incluir una longitud de código para cada una, incluso si es cero).

Si también pone una limitación en las longitudes de bits (digamos, 7 bits), puede almacenar cada uno de estos números usando cadenas binarias cortas. Entonces 2,3,2,3,2 se convierte en 010 011 010 011 010 - Que cabe en 2 bytes.

Si quieres volverte realmente loco, puedes hacer lo que hace DEFLATE, y hacer otra tabla huffman de la longitud de estos códigos, y almacenar sus longitudes de código de antemano. Sobre todo porque agregan códigos adicionales para "insertar cero N veces seguidas" para acortar aún más las cosas.

El RFC para DEFLATE no es tan malo, si ya está familiarizado con la codificación huffman: http://www.ietf.org/rfc/rfc1951.txt

Un mejor enfoque

Árbol: 7 ------------- | 4 | --------- 3 2 2 ----- ----- ----- ABCDEF 2 1 1 1 1 1: frecuencias 2 2 3 3 3 3: profundidad del árbol (bits de codificación)

Ahora solo obtenga esta tabla: número de profundidad de códigos

2 2 [A B] 3 4 [C D E F]

No necesita usar el mismo árbol binario, simplemente mantenga la profundidad de árbol calculada, es decir, el número de bits de codificación. Así que simplemente mantenga el vector de valores sin comprimir [ABCDEF] ordenado por profundidad de árbol, use índices relativos en su lugar para este vector separado. Ahora recrea los patrones de bits alineados para cada profundidad:

número de profundidad de códigos

2 2 [00x 01x] 3 4 [100 101 110 111]

Lo que inmediatamente ves es que solo el primer patrón de bits en cada fila es significativo. Obtienes la siguiente tabla de búsqueda:

first pattern depth first index ------------- ----- ----------- 000 2 0 100 3 2

Esta LUT tiene un tamaño muy pequeño (incluso si sus códigos Huffman pueden ser de 32 bits de largo, solo contendrá 32 filas), y de hecho el primer patrón siempre es nulo, puede ignorarlo por completo al realizar una búsqueda binaria de patrones en él (aquí solo será necesario comparar 1 patrón para saber si la profundidad del bit es 2 o 3 y obtener el primer índice en el que se almacenan los datos asociados en el vector). En nuestro ejemplo, deberá realizar una búsqueda binaria rápida de patrones de entrada en un espacio de búsqueda de 31 valores como máximo, es decir, un máximo de 5 comparaciones enteras. Estas 31 rutinas de comparación se pueden optimizar en 31 códigos para evitar todos los bucles y tener que administrar los estados al navegar el árbol de búsqueda binario entero. Toda esta tabla encaja en una pequeña longitud fija (la LUT solo necesita 31 filas para los códigos Huffman de no más de 32 bits, y las otras 2 columnas anteriores llenarán como máximo 32 filas).

En otras palabras, el LUT anterior requiere 31 entradas de 32 bits cada una, 32 bytes para almacenar los valores de profundidad de bits: pero puede evitarlo al implicar la columna de profundidad (y la primera fila para la profundidad 1):

first pattern (depth) first index ------------- ------- ----------- (000) (1) (0) 000 (2) 0 100 (3) 2 000 (4) 6 000 (5) 6 ... ... ... 000 (32) 6

Entonces su LUT contiene [000, 100, 000 (30 veces)]. Para buscar en él, debe encontrar la posición donde el patrón de bits de entrada se encuentra entre dos patrones: debe ser menor que el patrón en la siguiente posición en esta LUT, pero aún más alto o igual que el patrón en la posición actual (si ambas posiciones contienen el mismo patrón, la fila actual no coincidirá, el patrón de entrada se ajusta a continuación). Luego dividirás y conquistarás, y utilizarás 5 pruebas como máximo (la búsqueda binaria requiere un código único con 5 niveles incrustados si / luego / otros anidados, tiene 32 ramas, la rama alcanzada indica directamente la profundidad de bits que no necesita ser almacenado, entonces realiza una única búsqueda indexada directamente a la segunda tabla para devolver el primer índice, se deriva aditivamente el índice final en el vector de valores decodificados).

Una vez que obtiene una posición en la tabla de búsqueda (buscar en la primera columna), inmediatamente tiene la cantidad de bits que debe tomar desde la entrada y luego el índice de inicio con el vector. La profundidad de bits que obtiene puede usarse para derivar directamente la posición de índice ajustada, mediante el enmascaramiento de bits básico después de restar el primer índice.

En resumen: nunca almacene árboles binarios vinculados, y no necesita ningún bucle para realizar el lookup que solo requiera 5 if anidados que comparen patrones en posiciones fijas en una tabla de 31 patrones, y una tabla de 31 ints que contenga el offset de inicio dentro del vector de valores decodificados (en la primera rama de las pruebas anidadas if / then / else, el desplazamiento inicial al vector es implícito, siempre es cero, también es la rama más frecuente que se tomará ya que coincide con el código más corto) que es para los valores decodificados más frecuentes).

las ramas son 0 hojas son 1. Atraviesa la profundidad del árbol primero para obtener su "forma"

e.g. the shape for this tree 0 - 0 - 1 (A) | /- 1 (E) / 0 - 1 (C) /- 0 - 1 (B) /- 1 (D) would be 001101011

Sigue eso con los bits para los personajes en la misma profundidad AECBD de primer orden (al leer sabrás cuántos caracteres esperar de la forma del árbol). A continuación, emita los códigos para el mensaje. Luego tiene una larga serie de bits que puede dividir en caracteres para la salida.

Si lo estás fragmentando, puedes probar que almacenar el árbol para el próximo lanzamiento es tan eficiente como reutilizar el árbol para el trozo anterior y tener la forma del árbol como "1" como indicador para reutilizar el árbol del trozo anterior. .