LZW
Esta calculadora comprime/descomprime una cadena utilizando el algoritmo Lempel-Ziv-Welch (LZW).
Esta página existe gracias a los esfuerzos de las siguientes personas:
Anton
| |
 | Juan Manuel Gimenez
|
 | Timur
|
Las calculadoras de este artículo se utilizan para comprimir y descomprimir una cadena utilizando el algoritmo LZW. El método LZW es simple y fiable, ya que no requiere almacenar un diccionario. El diccionario se genera dinámicamente durante la compresión y la descompresión.
Para estudiar el funcionamiento del algoritmo, marque la casilla "Mostrar detalles". Las calculadoras mostrarán el registro de trabajo y los diccionarios de frases generados.
Compresión de texto LZW
El vaciado binario o el archivo binario generado por la calculadora anterior se puede pasar a la siguiente calculadora, que restaurará la cadena original. Es necesario establecer el método de formación del diccionario de origen de la misma manera que para la calculadora de compresión. (elegir la misma codificación o especificar explícitamente el mismo diccionario).
Descompresión LZW
- Arrastre los archivos aquí
Algoritmo Lempel-Ziv-Welch
El algoritmo de compresión sin pérdidas LZ78 fue publicado en 1978 por Abraham Lempel y Jacob Ziv y luego modificado por Terry Welch en 1984. Tras la publicación de Welch, el algoritmo pasó a llamarse LZW por las primeras letras de los apellidos de los autores (Lempel, Ziv, Welch). El algoritmo ha sido patentado, pero ahora todas las patentes han expirado, lo que nos da una gran oportunidad para publicar nuestra implementación aquí.
Descripción del algoritmo LZW
- Crear el diccionario inicial que contiene todos los caracteres posibles.
- Poner el primer carácter a la frase de entrada W.
- Leer el siguiente carácter K.
- Si es EOF, devuelva W, si no:
Si la frase WK ya está en el diccionario, W ⟵ WK, pasar a 3 ,
Si no, devolver el código de W , añadir WK al diccionario, W ⟵ K. Pasar a 3.
Para decodificar los datos generados de esta manera, no es necesario almacenar el diccionario, se recrea por sí mismo en el proceso de la descompresión:
- Crear el diccionario inicial que contenga todos los caracteres posibles.
- Poner el primer código a la frase de entrada W.
- Leer el siguiente código K.
- Si es EOF, devuelva el carácter que tiene el código W, si no:
Si la frase con el código WK no está en el diccionario, devuelva la frase con el código W, y añada la frase con el código WK al diccionario.
Si no, asigne el código WK a la frase de entrada y pase al punto 3.
El artículo original de Welch pretendía codificar una frase en un diccionario con un código de tamaño fijo de 12 bits, pero para los mensajes pequeños este enfoque puede incluso aumentar la longitud del mensaje codificado en comparación con el texto original. Por lo tanto, es bastante común utilizar una longitud de código dinámica, que cambia cada vez que se alcanza el límite del diccionario.
Manejo del crecimiento del tamaño del diccionario
En el algoritmo de compresión descrito anteriormente, el tamaño del diccionario no está limitado. En la práctica, esto puede llevar a limitaciones de recursos cuando se empaquetan grandes cantidades de datos.
Existen modificaciones conocidas del algoritmo que intentan solucionar este problema:
- LZC - la implementación del algoritmo en la utilidad de compresión limita el tamaño máximo del diccionario a 16 bits. Cuando se alcanza el tamaño máximo, el diccionario deja de cambiar. El algoritmo monitoriza el ratio de compresión y, si se degrada significativamente, reinicia el diccionario y comienza a formarlo de nuevo.
- LZT - en caso de desbordamiento, elimine del diccionario la frase que no se ha utilizado durante más tiempo.
Nuestras características de implementación
Diccionario inicial
Nuestras calculadoras implementan un vocabulario de crecimiento infinito, lo que puede ser demasiado costoso para datos muy grandes. El tamaño de los códigos de frase comienza en 8 bits para el diccionario inicial especificado por la codificación estándar, o menos para un diccionario introducido a mano. En este último caso, el tamaño de los códigos de frase es el número mínimo de bits necesario para expresar el número de caracteres del diccionario. Longitud de bits.
Codificaciones multibyte
Algunas codificaciones pueden tomar más de 1 byte por carácter, por ejemplo, la codificación UTF-8 contiene caracteres de longitud variable de 1 a 4 bytes. En cualquier caso, el diccionario inicial contendrá 256 elementos con códigos de 0 a 255 para cualquier codificación que elija.
Para las codificaciones multibyte, un diccionario generado dinámicamente tendrá un aspecto bastante exótico: sus frases estarán inevitablemente compuestas por diferentes partes de caracteres adyacentes. En este caso, para mayor claridad en las tablas de salida, utilizamos un marcador de bytes faltantes (por defecto, es el carácter '~'). Por ejemplo, al comprimir la frase "9 €", representada en codificación UTF-8, el diccionario dinámico puede llenarse con combinaciones de los siguientes caracteres:
9 - nueve,
' ' - espacio,
€~~ - primer byte del símbolo del euro,
~€~ - segundo byte del símbolo del euro,
~~€ - tercer byte del símbolo del euro,
€~ - los dos primeros bytes del símbolo del euro,
~€ - los dos últimos bytes del símbolo del euro,
€ - los tres bytes del símbolo del euro.
Hemos introducido esta descripción de caracteres solo por comodidad. Recuerde que las partes constituyentes de muchos caracteres multibyte son solo bytes de 8 bits cada uno, y pueden ser las mismas para diferentes caracteres.
Por ejemplo:
€ ~~ - el primer byte del símbolo del euro, su código en utf-8 = 226
₽ ~~ - el primer byte del símbolo del rublo, su código en utf-8 = 226
Terminación con ceros
El algoritmo de compresión puede producir una matriz de bits cuyo tamaño no sea un múltiplo de 8. En este caso, la calculadora de compresión rellena el final con bits cero. Dado que nuestra implementación utiliza un tamaño variable del código de la frase, este enfoque puede causar problemas si el diccionario inicial establecido manualmente es muy pequeño.
En este ejemplo, el mensaje final tendrá solo 18 bits y habría que rellenar 6 bits con ceros para almacenar el mensaje completo en un archivo binario.
Como con los parámetros especificados, el tamaño del código de la frase es de solo 4 bits, entonces la palabra extra será leída durante la descompresión, y si creáramos el diccionario original con el código del primer carácter = 0, entonces el carácter extra sería descomprimido.
Resolvemos este problema añadiendo un carácter nulo al principio del diccionario, que se suele interpretar como el final de una cadena.
Cuando se utiliza la codificación como diccionario inicial, este problema no se plantea nunca, ya que el tamaño del código de la frase es siempre de al menos 8 bits.
Comentarios