Section courante

A propos

Section administrative du site

 Langage  Elément  Bibliothèque  Module  Annexe  Aide 
ABAP/4
Ada
Assembleur
Assembly & bytecode
ASP (Active Server Pages)
Basic
C
C++
C# (C Sharp)
Cobol
ColdFusion
Fortran
HTML
Java
JavaScript
LISP
Logo
LotusScript
Oberon
Pascal
Perl
PHP
PL/1
Prolog
Python
Rebol
REXX
Ruby
SAS
NoSQL
SQL
Swift
X++ (Axapta)
GNAT
SMALLAda
VHDL
Assembleur 370
Assembleur 1802
Assembleur 4004
Assembleur 6502
Assembleur 6800
Assembleur 68000
Assembleur 8080 et 8085
Assembleur 8089
Assembleur 80x86
Assembleur AGC4
Assembleur ARM
Assembleur DPS 8000
Assembleur i860
Assembleur Itanium
Assembleur MIPS
Assembleur PDP-11
Assembleur PowerPC
Assembleur RISC-V
Assembleur SPARC
Assembleur SuperH
Assembleur UNIVAC I
Assembleur VAX
Assembleur Z80
Assembleur Z8000
Assembleur z/Architecture
ASSEMBLER/MONITOR 64
Micol Assembler
GFA Assembler
A86
MASM (Macro Assembler)
TASM (Turbo Assembler)
CIL
Jasmin
LLVM
MSIL
Parrot
P-Code (PCode)
SWEET16
G-Pascal
ASP 1.0
ASP 2.0
ASP 3.0
ASP.NET
ASP.NET Core
ABasiC (Amiga)
Adam SmartBASIC
Altair BASIC
AmigaBASIC (Amiga)
AMOS Basic (Amiga)
Atari Basic (Atari 400, 600 XL, 800, 800XL)
Basic Apple II (Integer BASIC/APPLESOFT)
Basic Commodore 64 (CBM-BASIC)
Basic Commodore 128 (BASIC 7.0)
Basic Commodore VIC-20 (CBM-BASIC 2.0)
Basic Coco 1 (Color Basic)
Basic Coco 2 (Extended Color Basic)
Basic Coco 3 (Extended Color Basic 2.0)
BASICA (PC DOS)
Basic Pro
BBC BASIC
Blitz BASIC (Amiga)
DarkBASIC
Dartmouth BASIC
GFA-Basic (Atari ST/Amiga)
GWBASIC (MS-DOS)
Liberty BASIC
Locomotive BASIC (Amstrad CPC)
MSX-Basic
Omikron Basic (Atari ST)
Oric Extended Basic
Power Basic
Quick Basic/QBasic (MS-DOS)
Sinclair BASIC (ZX80, ZX81, ZX Spectrum)
ST BASIC (Atari ST)
Turbo Basic
Vintage BASIC
VBScript
Visual Basic (VB)
Visual Basic .NET (VB .NET)
Visual Basic pour DOS
Yabasic
BeckerBASIC
SIMONS' BASIC
Basic09 d'OS-9
Disk Extended Color Basic
Basic09 d'OS-9
Disk Extended Color Basic
Access
Excel
Visual Basic pour Windows
Visual Basic .NET pour Windows
C Shell Unix (csh)
C pour Amiga
C pour Atari ST
C pour DOS
C pour Falcon030
C pour GEMDOS (Atari ST)
C pour Linux
C pour PowerTV OS
C pour OS/2
C pour Unix
C pour Windows
Aztec C
CoCo-C
GNU C
HiSoft C
IBM C/2
Introl-C
Lattice C
Microsoft C
MinGW C
MSX-C
Open Watcom C
OS-9 C Compiler
Pure C
Quick C
Turbo C
HiSoft C for Atari ST
HiSoft C for CP/M (Amstrad CPC)
C++ pour OS/2
C++ pour Windows
Borland C++
C++Builder
IBM VisualAge C++
Intel C++
MinGW C++
Open Watcom C++
Symantec C++
Turbo C++
Visual C++
Visual C++ .NET
Watcom C++
Zortech C++
C# (C Sharp) pour Windows
Apple III Cobol
Microsoft Cobol
BlueDragon
Lucee
OpenBD
Railo
Smith Project
Microsoft Fortran
WATFOR-77
CSS
FBML
Open Graph
SVG
XML
XSL/XSLT
LESS
SASS
GCJ (GNU)
JSP
Jython
Visual J++
Node.js
TypeScript
AutoLISP
ACSLogo
LotusScript pour Windows
Amiga Oberon
Oberon .NET
Apple Pascal
Delphi/Kylix/Lazarus
Free Pascal
GNU Pascal
HighSpeed Pascal
IBM Personal Computer Pascal
Lisa Pascal
Maxon Pascal
MPW Pascal
OS-9 Pascal
OSS Personal Pascal
Pascal-86
Pascal du Cray Research
Pascal/VS
Pascal-XT
PURE Pascal
QuickPascal
RemObjets Chrome
Sun Pascal
THINK Pascal
Tiny Pascal (TRS-80)
Turbo Pascal
UCSD Pascal
VAX Pascal
Virtual Pascal
Turbo Pascal for CP/M-80
Turbo Pascal for DOS
Turbo Pascal for Macintosh
Turbo Pascal for Windows
CodeIgniter (Cadre d'application)
Drupal (Projet)
Joomla! (Projet)
Phalanger (PHP .NET)
phpBB (Projet)
Smarty (balise)
Twig (balise)
Symfony (Cadre d'application)
WordPress (Projet)
Zend (Cadre d'application)
PL360
PL/M-80
PL/M-86
Turbo Prolog
CPython
IronPython
Jython
PyPy
AREXX
Regina REXX
JMP
Btrieve
Cassandra
Clipper
CouchDB
dBASE
Hbase
Hypertable
MongoDB
Redis
Access
BigQuery
DB2
H2
Interbase
MySQL
Oracle
PostgreSQL
SAP HANA
SQL Server
Sybase
U-SQL
Introduction
Compression
Cryptographie
Encodage
CCITT Group 3
Huffman
LZ77
LZW
PackBits
AES
DES
MD5
SHA-1
base64
CryptoAuthLib
CryptoLib4Pascal
Delphi-OpenSSL
HashLib4Pascal
OpenSSL
hashlib
Structure de fichiers compressé
ARC
ARJ
CAB
JAR
gz
PAK
RAR
SWG
WAR
ZIP
ZOO
Préface
Notes légal
Dictionnaire
Recherche

Huffman

En parcourant les normes, la compression de Huffman est une technique vénérable, décrite pour la première fois par D. A. Huffman en 1952. Elle demeure néanmoins une technique de compression importante et utile et est spécifiée par la norme de CCITT Group 3 Facsimile, étant prise en charge par le format d'image TIFF. La norme du Group 3 spécifie en fait une variante de l'algorithme Huffman classique, mais est toujours généralement appelée compression Huffman. La compression Huffman code un flux d'octets en une séquence de codes binaires de longueur variable. Le principe derrière l'algorithme est de déterminer la fréquence statistique des différents symboles dans le flux d'entrée et de coder le message en utilisant des codes de bits courts pour les symboles les plus fréquents et des codes de bits plus longs pour les symboles moins fréquents. À titre d'illustration, considérons un fichier ASCII codé comme une séquence de codes 8 bits de longueur fixe. La lettre A est codée comme 01000001 (41h) et la lettre Z est codée comme 01011010 (5Ah). Cependant, en moyenne, la lettre A apparaît plus fréquemment que la lettre Z. Donc, si nous codons A avec un code court, disons 011, et Z avec un code plus long, disons 0111111, alors nous aurons réduit le nombre de bits nécessaires pour représenter un fichier. La technique, appelée codage de longueur variable comme codage de longueur variable, n'est pas ce que Huffman a réellement décrit. La contribution de Huffman était un algorithme pour déterminer l'ensemble de codes optimal pour un ensemble de données donné à coder. Cette situation se fait en ordonnant les symboles d'entrée par fréquence, puis en construisant un arbre binaire à partir d'eux. Le code bit pour un symbole donné est ensuite déterminé par le chemin d'accès à ce symbole dans l'arborescence. À chaque niveau, une branche gauche contribue 1 bit au codage des symboles et une branche droite contribue 0 bit. Lorsqu'un noeud terminal est atteint, le symbole d'entrée s'y trouvant est codé avec le motif binaire construit à partir du chemin vers ce symbole. Pendant le décodage, les bits sont lus dans le flux d'entrée et sont utilisés pour parcourir l'arborescence. Lorsqu'un noeud terminal est atteint, le symbole associé à ce noeud est émis vers le flux décodé. L'arbre réel, appelé arbre de Huffman, est construit de bas en haut, en commençant par tous les noeuds terminaux ordonnés en augmentant la fréquence. Les deux noeuds avec la fréquence la plus basse sont combinés pour former un noeud parent dont la fréquence est définie comme étant la somme des fréquences de ses deux noeuds enfants. Le processus est répété jusqu'à ce qu'un seul noeud, la racine de l'arbre, soit atteint. Notez que l'arborescence utilisée pour coder un flux de données est requise pour décoder la représentation compressée du flux de données. Deux problèmes avec la compression Huffman sont qu'elle nécessite deux passages sur un fichier, un pour déterminer la fréquence du symbole et un pour le codage réel, et le second problème c'est que la manipulation au niveau du bit requise de la représentation codée est plus coûteuse en calcul que l'octet de manipulation orientée. Le premier problème peut être résolu en supposant une distribution de fréquence de symboles standard et un ensemble de codes binaires, ce qui est le cas avec la norme Group 3 Facsimile Standard.

Algorithme

* Entrée : Liste de symboles avec leurs fréquences d'apparition
* Sortie : Code binaire de Huffman pour chaque symbole

MODULE Huffman(Symboles)
   * Initialiser une file de priorité Q avec tous les symboles et leurs fréquences
   BOUCLE TANT QUE taille de Q > 1 FAIRE
      Extraire le noeud x avec la plus petite fréquence de Q
      Extraire le noeud y avec la plus petite fréquence de Q (après x)
      Créer un nouveau noeud z avec :
         La fréquence de z ← fréquence de x + fréquence de y
         Le noeud x comme enfant gauche
         Le noeud y comme enfant droit
      Ajouter z dans Q
   FIN BOUCLE TANT QUE
   * Le seul noeud restant dans Q est la racine de l'arbre de Huffman

   BOUCLE POUR CHAQUE arbre de Huffman pour générer les codes FAIRE
      Initialiser un dictionnaire vide 'codes'
      BOUCLE POUR CHAQUE feuille (symbole) dans l'arbre FAIRE
         Assigner le code en fonction du chemin (0 pour gauche, 1 pour droite)
         Ajouter le symbole et son code dans 'codes'
      FIN BOUCLE POUR CHAQUE
   FIN BOUCLE POUR CHAQUE
   RETOURNE 'codes'


PARTAGER CETTE PAGE SUR
Dernière mise à jour : Samedi, le 18 mai 2019