¿Cómo se pueden calcular los parámetros óptimos para un esquema de codificación de inicio-paso-parada?

Question

Un código de inicio-paso-parada es una técnica de compresión de datos que se utiliza para comprimir números relativamente pequeños.

El código funciona de la siguiente manera: tiene tres parámetros, inicio, paso y parada. El inicio determina la cantidad de bits utilizados para calcular los primeros números. El paso determina cuántos bits se agregarán a la codificación cuando nos agotemos y paremos determina la cantidad máxima de bits utilizados para codificar un número.

Entonces, la longitud de una codificación está dada por l = inicio + paso * i.

El " i " El valor de un código en particular se codifica usando unario. Es decir, un número de 1 bits seguido de un bit de terminación 0. Si hemos llegado a parar, podemos descartar el bit 0 de terminación. Si i es cero, solo escribimos el bit 0.

Por lo tanto, un código de inicio-paso-parada (1, 2, 5) funcionaría de la siguiente manera:

Valor 0, codificado como: 0 0
Valor 1, codificado como: 0 1
Valor 2, codificado como: 10 000
Valor 9, codificado como: 10 111
Valor 10, codificado como: 11 00000
Valor 41, codificado como: 11 11111

Entonces, dado un archivo que contiene varios números, ¿cómo podemos calcular los códigos de inicio-paso-parada óptimos para ese archivo? Los parámetros óptimos se definen como aquellos que resultarán en la mayor relación de compresión.

Answer 1

Estos " start-step-stop " los códigos parecen una forma diferente de llamar a códigos de Huffman . Consulte la técnica básica para obtener un resumen del pseudocódigo para calcularlos.

Esencialmente esto es lo que hace el algoritmo:

Antes de comenzar con la codificación Huffman, debe recopilar las estadísticas de cada símbolo que va a comprimir (su frecuencia total en el archivo para comprimir).

Después de que haya creado un árbol binario utilizando esa información tal que la más frecuente los símbolos utilizados están en la parte superior del árbol (y, por lo tanto, usan menos bits) y de tal manera que ninguna codificación tenga un prefijo código . Dado que si una codificación tiene un prefijo común, podría haber ambigüedades descomprimidas.

Al final de la codificación Huffman, su valor de inicio será la profundidad del nodo de hoja más superficial, su paso siempre será 1 (lógicamente esto tiene sentido, ¿por qué forzar más bits de los que necesita, solo agregue uno a la vez?) ,) y su valor de parada será la profundidad del nodo de hoja más profundo.

Si las estadísticas de frecuencia no están ordenadas, tomará O (nlog n), si se ordenan por frecuencia, se puede hacer en O (n).

Se garantiza que los códigos de Huffman tienen la mejor compresión promedio para este tipo de codificación:

  

Huffman fue el que más pudo diseñar   método de compresión eficiente de este   tipo: ningún otro mapeo de individuo   fuente de símbolos a cadenas únicas de   bits producirá un promedio más pequeño   tamaño de salida cuando el símbolo real   Las frecuencias concuerdan con las utilizadas para   crear el código.

Esto debería ayudarte a implementar la solución ideal para tu problema.

Editar: Aunque es similar, esto no es lo que buscaba el OP.

Este documento académico del creador de estos códigos describe una generalización de códigos de inicio-paso-parada, códigos de inicio-parada. Sin embargo, el autor describe brevemente cómo obtener un inicio, un paso y una parada óptimos cerca del final de la sección 2. Se trata de utilizar una variable aleatoria estadística, o la financiación de la fuerza bruta, la mejor combinación. Sin ningún conocimiento previo del archivo, el algoritmo es O ((log n) ^ 3).

Espero que esto ayude.

Answer 2

El enfoque que utilicé fue una solución de fuerza bruta simple. El algoritmo siguió estos pasos básicos:

1. Cuente la frecuencia de cada número en el archivo. En el mismo paso, calcule la cantidad total de números en el archivo y determine el mayor número como maxNumber.

2. Calcule la probabilidad de cada número según su frecuencia dividida por la cantidad total de números en el archivo.

3. Determine " óptimoStop " como igual a log2 (maxNumber). Este es el número ideal de bits que se debe usar para representar maxNumber como en la teoría de la información de Shannon y, por lo tanto, una estimación razonable de la cantidad máxima óptima de bits utilizados en la codificación de un número particular.

4. Para cada " inicio " valor de 1 a " óptimoStop " repita los pasos 5 - 7:

5. Para cada " paso " el valor de 1 a (" óptimoStop " - " inicio ") / 2, repita el paso 6 & amp; 7:

6. Calcula el " parada " valor más cercano a " óptimoStop " que satisface stop = inicio + paso * i para algunos enteros i.

7. Calcule el número promedio de bits que esta codificación usaría. Esto se puede calcular como la probabilidad de cada número multiplicada por su longitud de bit en la codificación dada.

8. Elija la codificación con el número promedio más bajo de bits.