Cómo crear mi propio algoritmo de compresión básico para archivos

En primer lugar, ¡bienvenido al maravilloso mundo de la teoría de la información! Esta pregunta es una pregunta increíblemente amplia que muchos científicos de investigación están intentando abordar. Para empezar, no existe un algoritmo de compresión singular, el algoritmo utilizado a menudo está vinculado a los datos que se están comprimiendo.

La mejor manera de aprender sobre la compresión es estudiar la investigación actual y el trabajo que ya se ha realizado sobre la compresión. Tal vez comience con algo básico como simplemente investigar cómo funciona la compresión de datos en teoría. Una vez que comprenda los principios subyacentes, puede comenzar a experimentar con diferentes formas de representar los datos.

También puede ver los algoritmos de compresión existentes (como Run Length Encoding o Huffman) e intentar implementarlo usted mismo en el idioma que elija.

La esencia de la compresión es “tokenizar” secuencias comunes de bit / byte.

Reemplace una secuencia repetida con una ficha que represente esa secuencia con una secuencia más corta. Por ejemplo, si tiene un carácter en blanco (X’20 ‘en ASCII, por ejemplo) repetido 40 veces seguidas en una línea impresa, reemplácelo con un “token” de repetición único seguido del carácter real, seguido del número de veces Se repite. Hay muchas variaciones sobre este tema, pero el principal es el mismo.

Depende del tipo de archivo que desea comprimir.

Escribí mi propio RLE en los años 90 para comprimir datos gráficos, estas fueron imágenes dibujadas que usaron 32 colores (más tarde 256 colores), pero eso es simple, ya que básicamente buscas largas filas repetidas del mismo color que era común en las imágenes de el tiempo.

También noté que los datos de audio eran muy secuenciales, por lo que un archivo de audio se podía comprimir en gran medida si en lugar de almacenar cada muestra, todo lo que se almacenaba era la diferencia entre dos muestras, a velocidades de muestreo altas, la diferencia a menudo no podía ser más de 16, ¡Oportunidad perfecta para almacenar un nibble delta de 4 bits en lugar de una muestra de 16 bits! Reservé un valor en la secuencia de compresión como centinela para indicar que el siguiente valor era una muestra de 16 bits, esto era necesario para permitir transitorios rápidos (que superarían el delta). ¡El archivo resultante sería aproximadamente un tercio del original!

Para los datos de nivel, generalmente solo una secuencia de números, creé una búsqueda multipass que intentaría encontrar patrones que tenían 4, 5, 6, 7 y 8 bytes de largo y luego los reemplazaría con un byte reservado donde aparecieran en la secuencia, esto no fue tan efectivo como esperaba, pero funcionó. En este punto me di cuenta de que era un aficionado experto, en lugar de un profesional de la compresión, y recurrí a bibliotecas preescritas.

Voy a tirar algo que hice: estaba trabajando para una compañía de juegos y me encargaron escribir el compresor / descompresor para cargar mapas de bits.

Terminé con al menos una docena de métodos diferentes. En el encabezado del archivo de salida puse el método para usar para la descompresión, mientras que el código de compresión probó cada método diferente y eligió el que mejor funcionó.

En el caso de los gráficos, podría adivinar diferentes tipos de compresión, como tomar el ancho del gráfico y omitir tantos píxeles para realizar el tipo de compresión de longitud de ejecución, pero en función de la línea de exploración, no píxeles adyacentes.

Puede ser muy creativo: pruebe diferentes enfoques y luego use el mejor.

Sugerencia: uno de los métodos debería ser “ninguno”. A veces, los datos se comprimen en un archivo más grande con el que comenzó, por lo que ninguno termina siendo la mejor manera de comprimir / descomprimir.

Lea mi libro en línea, Explicación de la compresión de datos, luego comience a codificar sus ideas.

Google “algoritmos de compresión”.

RLE (codificación de longitud de ejecución) es uno que es muy fácil de aprender, pero no muy eficiente.

Sin embargo, es un buen punto de partida.

Después de eso, pruebe la familia de algoritmos de compresión LZ, que se basan en índices de una tabla de búsqueda de secuencias de bytes comunes.