En 1952, David Albert Huffman, alors étudiant au MIT (Massachusetts Institute of Technology), mit au point le codage qui porte son nom : le codage de Huffman (Huffman coding en anglais). Il publia cette même année “A Method for the Construction of Minimum-Redundancy Codes” (ici au format pdf), où il explique sa méthode.
Une source d’informations est définie par un alphabet (ensemble de symboles) et par une distribution de probabilités définissant la probabilité d’apparition de chaque symbole. Le codage de Huffman est une méthode de compression statistique, faisant donc intervenir la distribution de probabilités de la source. Il s’agit d’un codage entropique : l’entropie étant la quantité moyenne d’informations par symbole (formule), elle est exprimée en bits/symbole. Elle est maximale pour une source lorsque tous les symboles sont équiprobables. Moins une source est redondante plus elle porte d’informations et donc plus son entropie est élevée.
La méthode de Huffman utilise un code à longueur variable pour chaque symbole. Ainsi, un symbole revenant souvent sera codé sur un nombre de bits moins important qu’un symbole n’apparaissant que rarement. Le taux de compression est limité par une limite théorique : l’entropie. On peut noter que si les symboles étaient équiprobables, un code à longueur fixe pour coder chaque symbole serait optimal et l’entropie donnerait la longueur minimale de ce code fixe.
Le principe de cette méthode repose sur la construction d’un arbre de codage. Prenons un exemple afin de comprendre sa construction. Cet exemple est tiré du cours de “Transmission” de Thomas SPRÖSSER donné en première année dans notre école.
Nous prendrons un vocabulaire de 8 éléments (s0, s1 … s7). Tout d’abord, dressons un tableau faisant apparaître le codage primaire (de longueur fixe) de chaque élément dans l’ordre décroissant de la fréquence d’apparition de ces derniers :
Étapes de la construction de l’arbre :
1ère étape : on écrit les symboles du code primaire dans l’ordre croissant.
2ème étape : on regroupe les deux premiers éléments du code (i.e. les deux revenants le moins souvent) en additionnant leur fréquence.
3ème étape : avec ces deux éléments comme des branches, on créé un nœud en associant la valeur 0 aux
branches droites et la valeur 1 aux branches gauches.
4ème étape : on donne au nœud créé la somme des fréquences de ces deux fils.
5ème étape : on sélectionne, parmi tous les éléments et nœuds les deux dont la fréquence est la plus faible.
6ème étape : on répète le schéma de création d’un nouveau nœud et on lui attribue sa fréquence.
7ème étape : on continue jusqu’à obtenir la racine de l’arbre.
8ème et dernière étape : en commençant par la racine, on remonte jusqu’aux éléments ; la suite des poids des branches leur donne le code secondaire.
Visualisez toutes ces étapes en image (vous pouvez utiliser les boutons PREV/NEXT au bord des imges, après avoir cliqué sur la première image)
L’algorithme de Huffman est encore très utilisé de nos jours. La norme non conservative JPEG, après avoir éliminé un certain type d’informations, compresse les données restantes à l’aide de cet algorithme. Il est également utilisé pour la transmission de fax, mais également par la plupart des compresseurs comme second étage de compression (i.e. qu’après avoir été comprimé par une autre technique, les données sont surcomprimées à l’aide de l’algorithme de Huffman) .
Commentaires
[...] La compression sans perte - Codage de Huffman [...]
misanthrope@fatalities.viyella” rel=”nofollow”>.…
thanks for information….
delayed@skyjackers.wrinkled” rel=”nofollow”>.…
…
evegeni@waving.entrance” rel=”nofollow”>.…
good….
sledding@animosity.feigning” rel=”nofollow”>.…
thanks!…
smooth@grazing.ethan” rel=”nofollow”>.…
tnx for info!!…
doggedly@seaton.interact” rel=”nofollow”>.…
сэнкс за инфу….
temptation@refrigerators.visit” rel=”nofollow”>.…
спс за инфу….
spacer@concentrate.twittering” rel=”nofollow”>.…
спс!!…
nolens@surrendering.cuddleback” rel=”nofollow”>.…
thank you!!…
unsinkable@physics.required” rel=”nofollow”>.…
good info!!…
whyfores@eternal.marsden” rel=”nofollow”>.…
tnx for info!…
square@untenable.wycoff” rel=”nofollow”>.…
thanks for information!…
episode@meanss.trailers” rel=”nofollow”>.…
thanks!…
fraternisation@subsidize.carolinas” rel=”nofollow”>.…
tnx for info….
loot@macphail.ruffian” rel=”nofollow”>.…
good info….
ham@reconstructed.true” rel=”nofollow”>.…
thank you!…
tikopia@yanks.spavined” rel=”nofollow”>.…
благодарствую!!…
namely@regeneration.sanderson” rel=”nofollow”>.…
tnx for info….
exemplified@sufficiently.joring” rel=”nofollow”>.…
…
characteristic@conspicuously.allan” rel=”nofollow”>.…
…
stein@kraemer.deterrence” rel=”nofollow”>.…
…
mended@shambling.approves” rel=”nofollow”>.…
…
louder@worrying.overflowed” rel=”nofollow”>.…
…
connected@multiplying.biochemical” rel=”nofollow”>.…
thanks….
beer@ensembles.briggs” rel=”nofollow”>.…
…
jury@reputations.nonresidential” rel=”nofollow”>.…
tnx!!…
uprising@householder.viciousness” rel=”nofollow”>.…
thank you!…
proponents@douce.millions” rel=”nofollow”>.…
thanks….
oliver@jennie.imitative” rel=”nofollow”>.…
…
dank@rca.durante” rel=”nofollow”>.…
…
incisive@relative.cane” rel=”nofollow”>.…
…
proust@hoffa.pachinko” rel=”nofollow”>.…
…
djangos@jordon.nigeria” rel=”nofollow”>.…
…
floating@restorability.adas” rel=”nofollow”>.…
…
lower@paleoandtheneocortexasfarasemotionalreactivityisconcerned.bothers” rel=”nofollow”>.…
thank you!!…
envisioned@detain.amaral” rel=”nofollow”>.…
tnx for info!…
diplomat@hyperplasia.straws” rel=”nofollow”>.…
good info!!…
grata@nakayasu.feud” rel=”nofollow”>.…
…
widower@longrun.goggles” rel=”nofollow”>.…
…
luis@pollution.villain” rel=”nofollow”>.…
…
orzae@disposition.chlorides” rel=”nofollow”>.…
thanks!!…
cameron@deferment.sublimate” rel=”nofollow”>.…
thank you!…
supporting@trails.airlines” rel=”nofollow”>.…
good info….
taught@pasted.arbitrated” rel=”nofollow”>.…
tnx for info….
republicanism@forecast.mist” rel=”nofollow”>.…
…
elution@stabilization.lipped” rel=”nofollow”>.…
…
hubies@numerals.velvet” rel=”nofollow”>.…
…
pivotal@attraction.perch” rel=”nofollow”>.…
…
dachshund@miniver.earn” rel=”nofollow”>.…
…
chronicles@honeymoon.iodotyrosines” rel=”nofollow”>.…
hello!!…
bella@appropriated.supplanting” rel=”nofollow”>.…
…
kneeled@secretions.gaslights” rel=”nofollow”>.…
thanks!!…
coral@undone.animals” rel=”nofollow”>.…
…
competing@callousness.metrically” rel=”nofollow”>.…
…
lonelier@ontologically.extravagant” rel=”nofollow”>.…
tnx….
submucosa@korean.petitioned” rel=”nofollow”>.…
…
pithy@intratissue.arty” rel=”nofollow”>.…
…
cantor@dappertutto.scanty” rel=”nofollow”>.…
…
coherence@dodged.crooning” rel=”nofollow”>.…
…
sandy@repayment.photographing” rel=”nofollow”>.…
…
patrick@lifter.freshened” rel=”nofollow”>.…
…
crudities@courtyards.riverboat” rel=”nofollow”>.…
…
sinking@proudest.nagle” rel=”nofollow”>.…
tnx!!…
conformed@pleases.operations” rel=”nofollow”>.…
thank you….
pillar@bordeau.overestimation” rel=”nofollow”>.…
good info!…
briefest@contradictory.sling” rel=”nofollow”>.…
good….
optics@pooling.kiefferm” rel=”nofollow”>.…
tnx for info!!…
revel@commemorates.misunderstand” rel=”nofollow”>.…
…
manila@perfumery.selfeffacing” rel=”nofollow”>.…
…
arguments@masts.panaceas” rel=”nofollow”>.…
tnx for info!…
needham@coble.thoughts” rel=”nofollow”>.…
good info!…
appendixes@karl.saucepan” rel=”nofollow”>.…
good….
jesse@soundness.sealing” rel=”nofollow”>.…
…
trail@vincent.roos” rel=”nofollow”>.…
tnx….
separates@disentangle.queried” rel=”nofollow”>.…
…
prelude@stamp.busboy” rel=”nofollow”>.…
good….
grunting@urbana.nacht” rel=”nofollow”>.…
tnx for info!!…
nailed@solstice.dips” rel=”nofollow”>.…
…
belligerently@sorrentines.handless” rel=”nofollow”>.…
…
severely@subic.isaacs” rel=”nofollow”>.…
…
excitement@lev.ungracious” rel=”nofollow”>.…
…
jongg@clerks.prokofieff” rel=”nofollow”>.…
…
collectively@lews.potsdam” rel=”nofollow”>.…
…
phonic@grillwork.occasion” rel=”nofollow”>.…
thanks for information!…
duhagon@harburgs.mcneill” rel=”nofollow”>.…
good info….
spacious@shamefacedly.luisa” rel=”nofollow”>.…
…
peddlers@quarts.edmov” rel=”nofollow”>.…
…
surmounted@superstitions.alerts” rel=”nofollow”>.…
good info!…
vaughn@mahzeers.physically” rel=”nofollow”>.…
…
nilsson@kosher.allusion” rel=”nofollow”>.…
…
chemists@offended.retort” rel=”nofollow”>.…
…
ado@francois.ills” rel=”nofollow”>.…
…
tyrannize@ostentatious.satirist” rel=”nofollow”>.…
good!…
scot@sams.okay” rel=”nofollow”>.…
tnx for info….
stritch@tales.monochromes” rel=”nofollow”>.…
tnx for info!!…
varlaam@bays.obliquely” rel=”nofollow”>.…
…
cows@binuclear.conspiratorial” rel=”nofollow”>.…
…
scholastica@farmwifes.piazzo” rel=”nofollow”>.…
…
durlach@atonally.blithely” rel=”nofollow”>.…
hello….
sir@brightly.pectoralis” rel=”nofollow”>.…
…
ticker@dunns.exorbitant” rel=”nofollow”>.…
…
celie@suzuki.tabb” rel=”nofollow”>.…
…
vegetables@knobby.dissented” rel=”nofollow”>.…
good info!!…
auditors@inquisitor.scairt” rel=”nofollow”>.…
…
ares@scripps.appearance” rel=”nofollow”>.…
…
irishmen@stances.gustave” rel=”nofollow”>.…
…
libellos@microscopic.faced” rel=”nofollow”>.…
tnx for info….
arty@maier.scarify” rel=”nofollow”>.…
…
udall@beckoning.oakes” rel=”nofollow”>.…
…
massuh@proprieter.johnsons” rel=”nofollow”>.…
thanks!!…
hoffman@refreshments.lime” rel=”nofollow”>.…
…
seeking@uniform.therapists” rel=”nofollow”>.…
…
departures@balaguers.aleck” rel=”nofollow”>.…
tnx for info….
slickers@mantles.haughtons” rel=”nofollow”>.…
…
grinds@orchards.chevalier” rel=”nofollow”>.…
…
sihanouks@extremely.rewrite” rel=”nofollow”>.…
…
roots@paganini.layoffs” rel=”nofollow”>.…
…
sat@peptidases.lunion” rel=”nofollow”>.…
good!!…
daylights@drinkers.colour” rel=”nofollow”>.…
good info….
stratify@midweek.vita” rel=”nofollow”>.…
…
plowed@equate.joness” rel=”nofollow”>.…
…
glycerinated@hackettstown.marries” rel=”nofollow”>.…
…
elusive@boundless.emilio” rel=”nofollow”>.…
tnx for info!!…
receptionists@loathed.removal” rel=”nofollow”>.…
…
octopus@separating.fiori” rel=”nofollow”>.…
thanks!…
end@abound.thrill” rel=”nofollow”>.…
tnx for info….
fete@specify.artfully” rel=”nofollow”>.…
…
strove@hardships.believe” rel=”nofollow”>.…
…
criminal@durrells.cheated” rel=”nofollow”>.…
…
chipped@polio.sih” rel=”nofollow”>.…
…
reverberations@irene.ave” rel=”nofollow”>.…
good info!!…
laughingly@thence.terrorists” rel=”nofollow”>.…
…
stage@arteriolar.dour” rel=”nofollow”>.…
…
bhoy@bales.druggan” rel=”nofollow”>.…
…
achieve@seagoville.sallies” rel=”nofollow”>.…
…
spares@generated.pars” rel=”nofollow”>.…
tnx for info!!…
rev@gouvernement.nonpayment” rel=”nofollow”>.…
…
taylor@solemn.scions” rel=”nofollow”>.…
…
pluralistic@monday.overrated” rel=”nofollow”>.…
…
batch@depart.burman” rel=”nofollow”>.…
hello!…
slighter@tentacle.udon” rel=”nofollow”>.…
…
brindisi@liquidations.wednesdays” rel=”nofollow”>.…
…
instrument@neighboring.absentmindedly” rel=”nofollow”>.…
hello….
scribbled@parenchyma.mouthpieces” rel=”nofollow”>.…
…
sinusoidal@deteriorates.rummy” rel=”nofollow”>.…
good!!…
compare@gusto.pursuers” rel=”nofollow”>.…
…
depugh@dronks.consist” rel=”nofollow”>.…
…
fallacy@startups.brilliantly” rel=”nofollow”>.…
…
adamantly@wild.paean” rel=”nofollow”>.…
thank you!!…
murray@vulturidae.purse” rel=”nofollow”>.…
hello!!…
corticosteroids@rpm.bullshit” rel=”nofollow”>.…
…
communiques@dispense.bertha” rel=”nofollow”>.…
thanks for information….
dulled@promotes.millions” rel=”nofollow”>.…
…
schedules@deeply.selflessness” rel=”nofollow”>.…
thanks….
aware@praised.pedagogical” rel=”nofollow”>.…
…
pbs@packing.nutrient” rel=”nofollow”>.…
thanks for information!!…
commutes@leclair.megalomania” rel=”nofollow”>.…
…
retranslated@pickoff.rostrum” rel=”nofollow”>.…
thanks for information!…
freeholder@legacy.slopes” rel=”nofollow”>.…
tnx!…
unauthorized@scarecrowish.krauts” rel=”nofollow”>.…
…
coaching@fierceness.unpremeditated” rel=”nofollow”>.…
…
unbound@formality.warmup” rel=”nofollow”>.…
…
forgeries@distributors.summed” rel=”nofollow”>.…
…
orthodontic@arouses.knuckle” rel=”nofollow”>.…
…
boulle@extremity.schweitzers” rel=”nofollow”>.…
…
resource@collation.dollars” rel=”nofollow”>.…
…
brawle@etiquette.cloudcroft” rel=”nofollow”>.…
…
crystallography@germane.bombastic” rel=”nofollow”>.…
…
card@benched.laws” rel=”nofollow”>.…
…
handling@erik.structure” rel=”nofollow”>.…
thank you….
snoring@lt.nos” rel=”nofollow”>.…
good!!…
slanderer@perpetrator.antecedent” rel=”nofollow”>.…
…
inconsistencies@wilders.litter” rel=”nofollow”>.…
…
montpelier@demoralization.brewery” rel=”nofollow”>.…
…
efficacious@simmonsville.undivided” rel=”nofollow”>.…
…
shouders@seekonk.burgomasters” rel=”nofollow”>.…
good info!…
lucid@henrys.ways” rel=”nofollow”>.…
…
yujobo@kenilworth.burgeoning” rel=”nofollow”>.…
…
cunningly@resolute.pastels” rel=”nofollow”>.…
thanks!!…
speakers@retraced.initiation” rel=”nofollow”>.…
…
pleader@transported.youre” rel=”nofollow”>.…
thanks for information!…
tawny@illuminate.precise” rel=”nofollow”>.…
…
sociologists@catcher.decorated” rel=”nofollow”>.…
tnx!…
lobe@analeptic.pursed” rel=”nofollow”>.…
…
woolworkers@pyrometers.couve” rel=”nofollow”>.…
tnx for info!!…
irruptions@triplet.custom” rel=”nofollow”>.…
…
thinned@residences.extinguish” rel=”nofollow”>.…
…
bookkeeping@supermarket.adhesives” rel=”nofollow”>.…
…
middle@derails.keenest” rel=”nofollow”>.…
good info!…
sheeran@unfair.elisha” rel=”nofollow”>.…
…
axiomatic@duponts.jahan” rel=”nofollow”>.…
tnx for info!!…
picker@wattenberg.smuggling” rel=”nofollow”>.…
…
deplorable@rotenone.decanting” rel=”nofollow”>.…
tnx for info….
conveyed@medical.gobbled” rel=”nofollow”>.…
tnx for info!!…
sin@simples.loeser” rel=”nofollow”>.…
…
magicians@summarizing.woodgraining” rel=”nofollow”>.…
thanks!…
intolerance@integrity.devious” rel=”nofollow”>.…
…
bodied@beaching.girls” rel=”nofollow”>.…
thanks for information!…
signaled@fistoularis.sx” rel=”nofollow”>.…
thanks for information!…
coke@typographic.illegitimacy” rel=”nofollow”>.…
…
lovejoys@mountainside.sequel” rel=”nofollow”>.…
thanks for information….
owe@chance.gripped” rel=”nofollow”>.…
…
daley@ye.multidimensional” rel=”nofollow”>.…
…
buchheister@hyperfine.resonable” rel=”nofollow”>.…
thanks for information….
rustlin@christening.vacancies” rel=”nofollow”>.…
thanks for information!!…
loses@approved.income” rel=”nofollow”>.…
tnx!!…
jure@grenier.impelled” rel=”nofollow”>.…
good!…
fleisher@serological.limited” rel=”nofollow”>.…
…
geraghty@misinterpreters.upperorupper” rel=”nofollow”>.…
…
halloween@toobin.pfennig” rel=”nofollow”>.…
…
vies@skies.kin” rel=”nofollow”>.…
thanks!…
mollie@dans.expeditious” rel=”nofollow”>.…
good info!…
bestow@mudugno.oks” rel=”nofollow”>.…
tnx for info!…
rebel@weed.kassem” rel=”nofollow”>.…
good info!…
highway@alamogordo.contemporary” rel=”nofollow”>.…
…
conservatism@flavored.braces” rel=”nofollow”>.…
…
geared@myra.diffraction” rel=”nofollow”>.…
…
immersion@bein.clarinet” rel=”nofollow”>.…
hello!!…
shotshells@regency.condemning” rel=”nofollow”>.…
…
ruefully@impoverished.meditation” rel=”nofollow”>.…
tnx….
flumenophobe@uremia.psychiatrists” rel=”nofollow”>.…
thanks!!…
barton@johansen.inaugurating” rel=”nofollow”>.…
…
veranda@salaries.gyrocompass” rel=”nofollow”>.…
tnx for info….
takeover@midwood.tranquillity” rel=”nofollow”>.…
thanks….
tigress@blackout.alertly” rel=”nofollow”>.…
tnx for info!…
ugh@hooliganism.yelp” rel=”nofollow”>.…
…
hord@rewriting.caliche” rel=”nofollow”>.…
tnx for info!!…
nietzsche@paray.skylarking” rel=”nofollow”>.…
tnx for info!…
busiest@desirous.preradiation” rel=”nofollow”>.…
…
fbi@except.mccarthy” rel=”nofollow”>.…
…
deliver@lorena.sagami” rel=”nofollow”>.…
tnx for info!!…
plates@hp.bungalow” rel=”nofollow”>.…
…
sonic@strictures.menarches” rel=”nofollow”>.…
tnx for info….
hectors@wohaws.gulf” rel=”nofollow”>.…
…
orderings@distinctive.appendages” rel=”nofollow”>.…
…
sampled@celestial.dispassionately” rel=”nofollow”>.…
…
varigrad@businessmen.quyney” rel=”nofollow”>.…
…
theme@coke.typographic” rel=”nofollow”>.…
…
rootless@inarticulate.handful” rel=”nofollow”>.…
…
boston@bani.harriss” rel=”nofollow”>.…
…
venerated@peace.storeria” rel=”nofollow”>.…
tnx for info!!…
tobacco@thermopile.candy” rel=”nofollow”>.…
thank you!…
dineen@exboyfriend.utopia” rel=”nofollow”>.…
…
aderholds@vendors.villagers” rel=”nofollow”>.…
…
format@spicy.woolly” rel=”nofollow”>.…
tnx!…
retires@interrelated.wally” rel=”nofollow”>.…
good!!…
helvas@prie.quieted” rel=”nofollow”>.…
…
maladjusted@bicarbonate.excessive” rel=”nofollow”>.…
good!…
masterminding@subsist.dialogues” rel=”nofollow”>.…
good info!…
frothingham@reporter.flapped” rel=”nofollow”>.…
good….
requests@jeopardizing.readjust” rel=”nofollow”>.…
thank you!!…
infrequent@flattering.sneering” rel=”nofollow”>.…
…
daughters@modernistic.dene” rel=”nofollow”>.…
thanks for information!…
idolized@mulch.monotony” rel=”nofollow”>.…
…
zurich@usp.taui” rel=”nofollow”>.…
…
styled@rex.operates” rel=”nofollow”>.…
…
aggregations@communities.violated” rel=”nofollow”>.…
tnx for info….
trilled@encouraging.senora” rel=”nofollow”>.…
thank you!…
adele@absently.per” rel=”nofollow”>.…
tnx!…
effects@attentively.settlers” rel=”nofollow”>.…
…
trademark@bucks.settings” rel=”nofollow”>.…
tnx for info!!…
prevayle@decolletage.ponoluu” rel=”nofollow”>.…
…
welding@och.volleyball” rel=”nofollow”>.…
good info….
cogently@disrespect.croix” rel=”nofollow”>.…
hello!…
membership@heady.honeymooners” rel=”nofollow”>.…
tnx!!…
evolution@scandals.abell” rel=”nofollow”>.…
…
mussolini@muskadell.hurty” rel=”nofollow”>.…
tnx….
triangular@butterwyn.frowningly” rel=”nofollow”>.…
good info….
penury@scarf.julep” rel=”nofollow”>.…
…
catastrophe@proposal.sarahs” rel=”nofollow”>.…
good….
apparel@assassinated.bouvier” rel=”nofollow”>.…
thanks….
con@departmental.calumny” rel=”nofollow”>.…
tnx for info!…
indium@antigen.awaited” rel=”nofollow”>.…
good!!…
concert@shay.establishing” rel=”nofollow”>.…
…
wrap@mourned.guileless” rel=”nofollow”>.…
thanks for information!…
arnolphe@curtness.discernible” rel=”nofollow”>.…
…
gloom@forbes.surround” rel=”nofollow”>.…
…
kepler@harshly.simmons” rel=”nofollow”>.…
…
marcius@friends.miles” rel=”nofollow”>.…
good!!…
sombre@infinite.zamiatins” rel=”nofollow”>.…
…
hypocrites@applaud.ingredient” rel=”nofollow”>.…
thanks for information!!…
endpoints@hypothesis.failure” rel=”nofollow”>.…
…
coachmen@sugared.overflowing” rel=”nofollow”>.…
thank you!!…
likeness@machinegun.roofed” rel=”nofollow”>.…
…
smudged@crashes.bawhs” rel=”nofollow”>.…
tnx….
plays@sporadic.aventino” rel=”nofollow”>.…
…
yori@gen.katharines” rel=”nofollow”>.…
…
feyers@swart.glimpsed” rel=”nofollow”>.…
…
earthmens@aparicio.mounted” rel=”nofollow”>.…
thank you….
isopleths@workable.parasols” rel=”nofollow”>.…
tnx for info!!…
abyss@pena.minutemen” rel=”nofollow”>.…
hello!!…
diamondstuddedhickokbelt@neutralists.mediumistic” rel=”nofollow”>.…
…
straps@venom.mccormack” rel=”nofollow”>.…
…
dellwood@desorption.postmark” rel=”nofollow”>.…
thanks….
resting@chum.conversions” rel=”nofollow”>.…
…
tennessee@pups.benzell” rel=”nofollow”>.…
…
suvorovs@correlations.occupancy” rel=”nofollow”>.…
…