tipos texto son redes perdida métodos huffman ejemplos digitales datos compresión compresion algoritmos algoritmo c++ c algorithm compression signal-processing

c++ - texto - son métodos de compresión de datos digitales html



Algoritmos de compresión de datos (5)

Me preguntaba si alguien tiene una lista de algoritmos de compresión de datos. Básicamente, no sé nada sobre la compresión de datos y esperaba aprender más sobre diferentes algoritmos y ver cuáles son los más nuevos y aún no se han desarrollado en muchos ASIC.

Espero implementar un ASIC de compresión de datos que sea independiente del tipo de datos que se reciban (audio, video, imágenes, etc.)

Si mi pregunta es demasiado abierta, por favor avíseme y la revisaré. Gracias

Aquí hay algunos algoritmos sin pérdida (pueden recuperar perfectamente los datos originales con estos):

  • Código de Huffman
  • LZ78 (y variación LZW)
  • LZ77
  • Codificación aritmética
  • Sequitur
  • predicción con coincidencia parcial (ppm)

Muchos de los formatos conocidos como png o gif utilizan variantes o combinaciones de estos.

Por otro lado, también hay algoritmos con pérdida (compromete la precisión para comprimir sus datos, pero a menudo funciona bastante bien). Las técnicas de vanguardia con pérdida combinan ideas de codificación diferencial, cuantificación y DCT, entre otras.

Para obtener más información sobre la compresión de datos, recomiendo https://www.elsevier.com/books/introduction-to-data-compression/sayood/978-0-12-809474-7 . Es un texto de introducción muy accesible. La tercera edición que hay en pdf en línea.

Hay un montón de algoritmos de compresión por ahí. Lo que necesitas aquí es un algoritmo de compresión sin pérdida. Un algoritmo de compresión sin pérdida comprime los datos de manera que se pueden descomprimir para lograr exactamente lo que se dio antes de la compresión. Lo contrario sería un algoritmo de compresión con pérdida. La compresión con pérdida puede eliminar datos de un archivo. Las imágenes PNG usan compresión sin pérdida, mientras que las imágenes JPEG pueden usar y con frecuencia usan compresión con pérdida.

Algunos de los algoritmos de compresión más conocidos incluyen:

Los archivos ZIP utilizan una combinación de codificación de Huffman y LZ77 para proporcionar tiempos de compresión y descompresión rápidos y relaciones de compresión razonablemente buenas.

LZ77 es más o menos una forma generalizada de RLE y a menudo producirá resultados mucho mejores.

Huffman permite que los bytes más repetidos representen el menor número de bits. Imagina un archivo de texto que se parece a esto:

aaaaaaaabbbbbcccdd

Una implementación típica de Huffman resultaría en el siguiente mapa:

Bits Character 0 a 10 b 110 c 1110 d

Así que el archivo estaría comprimido a esto:

00000000 10101010 10110110 11011101 11000000 ^^^^^ Padding bits required

Los 18 bytes bajan a 5. Por supuesto, la tabla debe incluirse en el archivo. Este algoritmo funciona mejor con más datos: P

Alex Allain tiene un buen artículo sobre el algoritmo de compresión de Huffman en caso de que el Wiki no sea suficiente.

No dude en pedir más información. Este tema es bastante amplio.

Hay una gran cantidad de algoritmos de compresión de datos alrededor. Si está buscando algo enciclopédico, recomiendo el Manual de compresión de datos de Salomon et al, que es tan completo como es probable que obtenga (y tiene buenas secciones sobre los principios y la práctica de la compresión de datos, también) .

Mi mejor conjetura es que la compresión basada en ASIC generalmente se implementa para una aplicación en particular, o como un elemento especializado de un SoC, en lugar de como un chip de compresión independiente. También dudo que buscar el formato de compresión "más reciente y mejor" sea el camino a seguir aquí: esperaría que la estandarización, la madurez y la aptitud para un propósito en particular sean más importantes.