vince Le 03/04/2012 à 21:01 Voilà, j'ai des lignes à compresser
La ligne d'origine est sous la forme de N valeurs successives situées dans une espèce de tableau (donc on récupère la valeur au nième index sans problème)
L'algo doit marcher pour des valeurs sur 1, 2 ou 4 bits (l'ensmble des lignes est exprimée sur le même nombre de bits)
La "compression" est proche du format RLE :
- On précise sur un bit un mode pour le bloc à venir (0 pour compact, 1 pour littéral)
------ Si c'est le mode 0
---------- 4bits de répétition (+1)
---------- les bits (1,2ou4) de la valeur à répéter
------ Si c'est le mode 1
---------- 4bits de comptage (+1)
---------- les bits (1,2ou4) de la valeur n°0
---------- les bits (1,2ou4) de la valeur n°1
---------- les bits (1,2ou4) de la valeur n°2
---------- les bits (1,2ou4) de la valeur n°N...
le problème est donc de trouver la méthode optimale pour encoder une ligne en une suite de bits la plus courte possible...
pour vous faire une idée, si j'ai :
0123000000111231322222
je peux coder ça
1 - litéral
0011 - 3+1 pixels
00
01
10
11
0 - compact
0101 - 5+1 répétitions
00
0 - compact
0010 - 2+1 répétitions
01
1 - litéral
0011 3+1 pixels
10
11
01
11
0 - compact
0100 4+1 répétitions
10
merci d'avance si vous avez des idées...
RHJPP Le 03/04/2012 à 23:17 Tu dois pouvoir trouver la compression optimale* avec l'algorithme de Viterbi.
n est le nombre de bits par valeur et m est la longueur en bits des longueurs dans ton codage.
Il y a 1 + 2n états à chaque instant dans le treillis qui représentent le type d'écriture courant : l'état d'écriture littérale et les 2n états d'écriture d'une valeur particulière.
Les transitions entre deux états du même type ont un coût de n bits pour l'écriture littérale alors que le coût est de 0 bit pour les valeurs particulières. Les transitions entre des types d'état différents ont un coût de 1 + m + n bits.
Bien sûr, les transitions impossibles (comme celles qui amènent aux types d'état de valeur particulière qui ne correspondent pas à la valeur courante) ont un coût infini.
Pour prendre en compte m, on peut ajouter une variable d'état qui est un compteur représentant la longueur du type courant. Cette variable est incrémentée et est propagée au travers des transitions lorsque le type reste le même. Si lors d'une telle transition, la variable dépasse sa valeur limite, alors elle est remise à 0 et le coût de la transition est incrémenté de 1 + m bits pour la valeur littérale et de 1 + m + n bits pour les valeurs particulières. Attention, dans ce cas, l'algorithme n'est plus optimal mais les résultats devraient être très bons.
*Dans le cas où tu n'as jamais besoin de plus de m bits pour représenter une longueur.
vince Le 04/04/2012 à 00:40 Je ne connais pas du tout Viterbi, je jetterai un coup d'oeil
