Determinar el mejor algoritmo de compresión para usar para una serie de bytes

Question

Para un proyecto personal mío, estoy escribiendo una pequeña clase para comprimir y descomprimir desde un formato bastante oscuro. Tengo la especificación completa, pero ese no es el problema.

Primero, este 'formato' utiliza un conjunto de 6 tipos de compresión diferentes, así como bloques de datos de bytes no comprimidos. Los formatos son RLE, una derivación de RLE donde el número aumenta cada byte (por ejemplo, 3, 4, 5, ...), un RLE de 16 bits, Copia LZ, una copia LZ inversa y Copia LZ Xor ' d con 255. No es la especificación más limpia, pero tampoco la diseñé.

Se supone que mi rutina de compresión toma una matriz de 1 a 65535 bytes, y (con suerte) la comprime tanto como sea posible. Mi intento anterior en esto simplemente calculó, comenzando desde cualquier índice en el flujo sin comprimir, cuál de las técnicas de compresión anteriores proporcionará la mejor compresión, y luego comprime los bytes que el método comprima a la matriz de bytes comprimidos antes de repetir desde el Nuevo índice 'sin comprimir', por ejemplo:

{0,0,0,1,2,3,4}

El algoritmo leería primero que había tres ceros al comienzo, y luego emitiría la codificación RLE para ellos que la especificación usaba, y luego a partir del cuarto elemento, leería que el incremento de RLE cubriría el '1,2 , 3,4 'lo suficientemente bien y comprime eso antes de regresar.

El problema resumido es que, al tratar de encontrar la mejor especificación para usar, la rutina es muy lenta incluso en matrices de bytes pequeñas (20-30). ¿Alguien puede ayudar con sugerencias sobre cómo podría optimizar esto o si hay más información que pueda proporcionar para ayudar?

Answer 1

Parece que lo que estás tratando de hacer es calcular una gran cantidad de posibilidades de compresión para cada segmento posible (llamemos segmentos de bloques de 1-64K de longitud variable) del archivo. Corríjame si me equivoco, pero ¿está trabajando en la mejor compresión para el primer segmento a partir de las siguientes opciones (el método 0 no está comprimido)?

• método de compresión 0, longitud 1 byte.
• método de compresión 1, longitud 1 byte.
• :::::
• método de compresión 6, longitud 1 byte.
• método de compresión 0, longitud 2 bytes.
• método de compresión 1, longitud 2 bytes.
• :::::
• método de compresión 6, longitud 65534 bytes.
• método de compresión 0, longitud 65535 bytes.
• método de compresión 1, longitud 65535 bytes.
• método de compresión 2, longitud 65535 bytes.
• método de compresión 3, longitud 65535 bytes.
• método de compresión 4, longitud 65535 bytes.
• método de compresión 5, longitud 65535 bytes.
• método de compresión 6, longitud 65535 bytes.

Eso llevará una enorme cantidad de tiempo (aproximadamente 420,000 intentos de compresión por segmento). Si eso es lo que estás haciendo, será mejor que elijas un tamaño de segmento único (por ejemplo, 64K) y le apliques cada uno de los siete métodos de compresión para elegir el mejor. Luego, para cada segmento, muestre el " método " byte seguido de los datos comprimidos.