Codage entropique d'un flux binaire

Question

Je souhaite compresser un flux binaire. Je sais qu'après chaque '1' il y a une plus grande probabilité de trouver un '0', et après chaque '0' il y a une plus grande probabilité de trouver un '1'. Comment dois-je l'encoder? Je pensais aux codes de Rice, mais je n'étais pas si loin ... Merci d'avance pour toute réponse.

Answer 1

Avez-vous essayé un simple codage de huffman? Peut-être que cela n'économisera pas beaucoup, mais si l'un des codes '10' et '01' a des probabilités beaucoup plus élevées que '00' ou '11', vous pouvez le remapper à '0' et les autres à '10' , '110' et '111'.

Bien sûr, ce ne sera pas le meilleur choix car il divise votre flux en morceaux de 2 bits et optimise seulement un cas. Cependant, il peut être affiné en calculant/mesurant des probabilités pour un ensemble d'entrée plus grand, comme 4 ou 8 bits, f.e. Dans le cas 8 bits 10101010 et 01010101 seront utilisés plus souvent que 00000000 et 11111111.

Vous pourriez obtenir des résultats encore meilleurs avec le codage arithmétique ou une compression qui utilise vraiment un modèle basé sur les probabilités de bits.

Une autre approche simple consisterait à inverser tous les deux bits. Comme la probabilité que vous mentionnez aura tendance à beaucoup de parties de flux en alternance comme 0101010, cela vous donnera beaucoup de parties de flux comme 111111 qui peut généralement être mieux compressé par les algorithmes de compression habituels. Mais le succès de cette méthode dépend de la taille de l'écart de probabilité.