Détermination du meilleur algorithme de compression à utiliser pour une série d'octets

Question

Pour un projet personnel, j’écris une petite classe dans laquelle compresser et décompresser à partir d’un format plutôt obscur. J'ai les spécifications complètes, mais ce n'est pas là que réside le problème.

Premièrement, ce "format" utilise un ensemble de 6 types de compression différents, ainsi que des blocs non compressés de données d'octet. Les formats sont RLE, une ramification de RLE où le nombre incrémente chaque octet (par exemple 3, 4, 5, ...), une RLE 16 bits, une copie LZ, une copie inversée et une copie LZ Xor ' d avec 255. Ce n’est pas la plus pure des spécifications, mais je ne l’ai pas conçue non plus.

Ma routine de compression est supposée prendre un tableau de 1 à 65 535 octets, et (espérons-le) le compresser autant que possible. Ma précédente tentative avait simplement calculé, en partant de tout index du flux non compressé, laquelle des techniques de compression ci-dessus fournissait la meilleure compression, puis comprenait le nombre d'octets compressés par la méthode dans le tableau d'octets compressés avant d'être répété à partir du nouvel index 'non compressé', par exemple:

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

L'algorithme lirait d'abord qu'il y avait trois zéros au début, puis sortirait le codage RLE correspondant à la spécification utilisée, puis à partir du quatrième élément, lirait que l'incrémentation de RLE couvrirait les '1,2 , 3,4 ', et compressez-le avant de revenir.

Le problème résumé est que, bien que nous essayions de trouver la meilleure spécification à utiliser, la routine est très très lente, même sur de petits tableaux (de 20 à 30). Quelqu'un peut-il m'aider pour des conseils sur la manière dont je pourrais envisager l'optimisation ou sur d'autres informations que je pourrais vous fournir pour vous aider?

Answer 1

On dirait que ce que vous essayez de faire est de définir un grand nombre de possibilités de compression pour chaque segment possible (appelons vos segments de blocs de longueur variable 1-64K) du fichier. Corrigez-moi si je me trompe, mais vous recherchez la meilleure compression pour le premier segment parmi les choix suivants (la méthode 0 n'est pas compressée):

• méthode de compression 0, longueur 1 octet.
• méthode de compression 1, longueur 1 octet.
• :::::
• méthode de compression 6, longueur 1 octet.
• méthode de compression 0, longueur 2 octets.
• méthode de compression 1, longueur 2 octets.
• :::::
• méthode de compression 6, longueur 65534 octets.
• méthode de compression 0, longueur 65535 octets.
• méthode de compression 1, longueur 65535 octets.
• méthode de compression 2, longueur 65535 octets.
• méthode de compression 3, longueur 65535 octets.
• méthode de compression 4, longueur 65535 octets.
• méthode de compression 5, longueur 65535 octets.
• méthode de compression 6, longueur 65535 octets.

Cela prendra énormément de temps (environ 420 000 tentatives de compression par segment). Si vous le faites, mieux vaut choisir une taille de segment unique (64 Ko, par exemple) et y appliquer chacune des sept méthodes de compression pour choisir la meilleure. Ensuite, pour chaque segment, indiquez la "méthode". octet suivi des données compressées.