The mandate
Compression de données - Code de Hoffman

Compression de données - Code de Hoffman

Catégorie: Programmation.
Posté par le 13/03/2012.
Dernière mise à jour le 01/05/2014.

<<Tutoriel précédent    Tutoriel suivant>>

Description

Ce tutoriel vous expliquera le fonctionnement de la compression de données en utilisant une technique basée sur une pré-analyse. Celle-ci se nomme, le code de Hoffman.

Introduction

Lorsque l’on veut représenter une chaine de caractère qui est représentée sous forme d’une séquence de bit, un problème se pose :

Si la forme compressée de a, b, c, d et e sont représenté par les séquences de bits suivantes :

  • a = 01
  • b = 011
  • c = 10
  • d = 0
  • e = 1

Comment différencier les chaines « ac » et « b » qui valent toutes les deux 011 ?

Une solution consisterait à utiliser un caractère spécial pour séparer chaque caractère. Mais cela engendrerait un surplus de mémoire. Une autre solution consisterait à encoder les différents caractères dans un code préfix-free (aucun encodage n’est le préfixe d’un autre). Cela s’appelle le Code de Hoffman.

Exemple :

  • a = 001
  • b = 0001
  • c = 0000
  • d = 1
  • e = 01

Pour ce faire, nous utilisons un tri dont chaque feuille contient un caractère.

Tries

Génération du trie

Voici la technique permettant de générer le tri :

  1. On détermine le nombre d’occurrence de chaque caractère dans la chaine d’entrée.
  2. On construit le tri par le bas. L’idée est de créer une feuille par symbôle et on regroupe les deux nœuds de poids le plus faible.

Technique d’encodage

w -> w’ {w’’ + code} se fait via une traversée en ordre préordre de l’arbre. Voici un exemple :

Tri :

Tries 2

Code : 1d01e01a01b0c

On reconstruit le tri à l’aide du code:

  • 0 : on va à gauche
  • 1 : on va à droite
  • Une lettre : on l’écrit et on revient au parent

Voilà ce que ça nous donne:

Tries 2

Tu as aimé ce tutoriel ?
Aide nous à améliorer le site ! Deviens partenaire officiel ou suis nous sur facebook !

<<Tutoriel précédent    Tutoriel suivant>>

Commentaires[0]

Tu as aimé ce tutoriel ? Alors partage-le avec tes amis !
Partager sur Facebook Partager sur Twitter Partager sur Myspace Partager sur Stumbleupon Soumettre sur Reddit Partager sur Digg Ajouter à vos favoris Technorati Ajouter à vos favoris Live Ajouter à vos favoris Google Ajouter sur vos favoris Yahoo Voir le flux rss

Mots Clés: code de Hoffman Compression de données pre-analyse Programmation trie

Veve :
(11/04/2013 - 17:19:44)
il faut juste mettre "sudo" à la place de "su" pour exécuter la commande en root

Veve :
(11/04/2013 - 17:18:56)
Salut tu peux aller lire ce tutoriel: http://www.tutorielsenfolie.com/tutoriels-63-installation-configuration-opennebula.html Il fonctionne aussi sous ubuntu

safa.souissi4 :
(10/04/2013 - 20:58:13)
s'il vous plait c urgent :(

safa.souissi4 :
(10/04/2013 - 20:56:25)
bonsoir,je cherche un tutos pour installer opennebula.org sous ubuntu 12.

Veve :
(18/03/2013 - 20:07:49)
oui, j'essaye de voir d'ou viens le problème.

sonde :
(18/03/2013 - 13:29:57)
re merci (j apprend un peu plus) je crois que j ai trouver pourquoi je peu pas poster si il y a ligne code impossible de poster lol

Veve :
(17/03/2013 - 21:34:49)
Salut, j'espère que ça t'a aidé.

sonde :
(17/03/2013 - 09:59:02)
pour ton aide

sonde :
(17/03/2013 - 09:57:36)
slt Veve impossible de laisser com

sonde :
(17/03/2013 - 09:56:55)
??

Demi-dieu :
(15/03/2013 - 18:41:13)
salut ^^

sonde :
(13/03/2013 - 14:49:35)
un petit coucou

Tanamoureuse :
(29/09/2011 - 06:11:08)
Je t'aime

Faire un don

Ma Publicité ici


Faire un don