> golomb | compresión | óptima <
// Codificación Golomb - Compresión óptima de enteros con divisor flexible
>> características
Divisor flexible
Elige cualquier valor M para lograr la máxima eficiencia de compresión.
Binario truncado
Utiliza el número mínimo de bits para codificar el resto.
Uso general
Funciona con cualquier distribución de enteros no negativos.
>> información técnica
Cómo funciona la codificación Golomb
La codificación Golomb divide cada entero n por un divisor M para obtener el cociente q y el resto r. El cociente se codifica en unario y el resto se codifica con binario truncado, usando el número mínimo de bits necesario para representar los valores de M. Esto crea un código óptimo para distribuciones geométricas con parámetro p = 1/M.
Ejemplo de codificación Golomb (M=5)
M=5, b=⌈log₂(5)⌉=3, c=2³-5=3 0 → q=0, r=0 → 0|00 → 000 (2 bits para r<3) 1 → q=0, r=1 → 0|01 → 001 (2 bits para r<3) 2 → q=0, r=2 → 0|10 → 010 (2 bits para r<3) 3 → q=0, r=3 → 0|110 → 0110 (3 bits para r≥3) 4 → q=0, r=4 → 0|111 → 0111 (3 bits para r≥3) 5 → q=1, r=0 → 10|00 → 1000 6 → q=1, r=1 → 10|01 → 1001 7 → q=1, r=2 → 10|10 → 1010 Binario truncado: r<3 usa 2 bits, r≥3 usa 3 bits
Por qué usar codificación Golomb
- Óptimo para distribuciones geométricas
- Parámetro M flexible
- Uso mínimo de bits
- Implementación sencilla
- Optimalidad demostrada
>> preguntas frecuentes
¿Qué es la codificación Golomb?
La codificación Golomb es un código óptimo, libre de prefijos y de longitud variable para distribuciones geométricas. Divide los enteros mediante un parámetro ajustable M, codificando el cociente en unario y el resto en binario truncado, logrando una compresión óptima para datos que siguen P(n) = (1-p)^n × p.
¿Cómo elegir el parámetro M?
El valor óptimo de M depende del parámetro geométrico p de tus datos. Para datos con media μ, M óptimo ≈ μ + 1. Para probabilidades que decrecen exponencialmente con parámetro p, el M óptimo es ⌈-1/log₂(1-p)⌉. Usa la función de análisis para encontrar el mejor M para tus datos.
¿Qué es el binario truncado?
El binario truncado minimiza el número de bits al codificar uno de los M valores posibles. Si M es una potencia de 2 se usa binario estándar. De lo contrario, algunos valores usan ⌊log₂M⌋ bits y otros usan ⌈log₂M⌉ bits, garantizando decodificación única con longitud media mínima.
¿Dónde se usa la codificación Golomb?
La codificación Golomb se usa en la compresión de imágenes JPEG-LS, en la codificación de vídeo H.264 (como Exp-Golomb) y en formatos de audio sin pérdida. Es ideal para la codificación de longitudes de rachas, residuos tras la predicción y cualquier dato con distribuciones geométricas o exponenciales.