Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixe

Développement d’une nouvelle technique decompression pour les codes variables à fixes
quasi-instantanés
Danny Dubé
Fatma Haddad
Université Laval

24 Mars 2017

Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

1 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixe

Plan
1

2

3

4

Introduction
Les concepts géneraux
Les types de code
La technique de Tunstall
Présentation de la technique de Tunstall
L’algorithme de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Présentation des codes AIVF
L’algorithme de Yamamoto et Yokoo
Les deux modes de la technique de Yamamoto et Yokoo
Amélioration de l’encodage variable à fixe
Le problème de la racine complète en le mode multi-arbre
Le problème de l’exécution complète de l’option II
La technique par programmation dynamiqueDéveloppement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

2 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixe

Les concepts géneraux
Les types de code

La compression des données

La compression de données : La compression de données est effectuée à l’aide de deux opérations :L’opération de compression, Compress ∶ Σ∗IN → Σ∗OUT .

L’opération de décompression, Decompress ∶ Σ∗OUT → Σ∗IN .
L’alphabet d’entrée, ΣIN , et l’alphabet de sortie, ΣOUT , peuvent êtredifférents.

Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

3 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixe

Les concepts géneraux
Les types de code

Cadre des travaux présentésCas particulier :Compression de données sans perte, i.e. :Decompress(Compress(w )) = w ,pour tout w ∈ Σ∗IN .

Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

4 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixe

Les concepts géneraux
Les types de codeCas particulier :Encodage par sous-chaînes de gauche à droite :( ∈ Σ∗IN )

w
=
u1

⋅

↧C1
=

v1

⋅

u2

⋅ ... ⋅

un

↧C2

...

↧Cn

v2

⋅ ... ⋅

vn

Compress(w )( ∈ Σ∗OUT )Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

5 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixe

Les concepts géneraux
Les types de codeCas particulier :Encodage statique (≡ dictionnaires constants) :(w ∈ Σ∗IN )

w
=
u1

⋅

↧C
=

v1

⋅

u2

⋅ ... ⋅

un

↧C

...

↧C

v2

⋅ ... ⋅

vn

Compress(w )(ui ∈ D)(vi ∈ E )(v ∈ Σ∗OUT )où
D ⊆ Σ∗IN est le dictionnaire d’entrée,E ⊆ Σ∗OUT est le dictionnaire de mots de code etC ∶ D → E est définie sur tout D.
Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

6 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixe

Les concepts géneraux
Les types de codeCas particulier :Fonction d’encodage C variable à fixe (VF) :
∣v ∣

=

l

∈

N,

pour tout v ∈ E .

Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

7 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixe

Les concepts géneraux
Les types de code

Définitions

Code : synonyme de dictionnaire.
Encodage (fonction d’) : fonction d’un dictionnaire vers un autre(par exemple, C ∶ D → E ).

Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

8 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixe

Les concepts géneraux
Les types de code

Soit D ⊆ Σ∗ un code.
Code préfixe : D est un code préfixe si, pour tous les mots u, v ∈ Dtels que u est un préfixe de v , on a u = v .
Par exemple,
le code {00, 01, 1} est préfixe maisle code {0, 00, 01, 1} n’est pas préfixe.
Définition alternative :Code préfixe : D est un code préfixe si, pour tout w ∈ Σ∞ , il existe
au plus un mot u ∈ D tel que u est un préfixe de w .

Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

9 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixe

Les concepts géneraux
Les types de code

Soit D ⊆ Σ∗ un code.
Code exhaustif : D est un code exhaustif si, pour tout w ∈ Σ∞ , ilexiste au moins un mot u ∈ D tel que u est un préfixe de w .
Par exemple, pour Σ = {0, 1}
le code {1, 01, 00} est exhaustif maisle code {00, 10, 11} n’est pas exhaustif.

Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

10 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixe

Les concepts géneraux
Les types de code

Soient D ⊆ Σ∗IN et E ⊆ Σ∗OUT deux codes et C ∶ D → E une fonctiond’encodage.
Encodage valide : C est une fonction d’encodage valide si
C est définie sur tout D,
C est injective,
D est exhaustif et
E est préfixe.

Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

11 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixe

Les concepts géneraux
Les types de code

(Soient D ⊆ Σ∗IN , E ⊆ Σ∗OUT et C ∶ D → E .)La 1ère condition est nécessaire :si C n’est pas définie sur tout D,
alors on ne pourra pas tout encoder.
Par exemple :ΣIN = {a, b}, D = {aa, ab, ba, bb}, C pas définie sur ba et
w = aabaa . . .

Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

12 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixe

Les concepts géneraux
Les types de code

(Soient D ⊆ Σ∗IN , E ⊆ Σ∗OUT et C ∶ D → E .)La 2ème condition est nécessaire :si C n’est pas injective
on ne pourra pas décoder correctement.
Par exemple :ΣIN = {a, b}, ΣOUT = {0, 1}, D = {aa, ab, ba, bb}, E = {0, 10, 11},C (aa) = 0, C (ab) = 0, C (ba) = 10, C (bb) = 11,
w = aabba . . . et w ′ = abbba . . .

Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

13 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixe

Les concepts géneraux
Les types de code

(Soient D ⊆ Σ∗IN , E ⊆ Σ∗OUT et C ∶ D → E .)La 3ème condition est nécessaire :si D n’est pas exhaustif,alors on ne pourra pas tout encoder.
Par exemple :ΣIN = {a, b}, D = {a, aa, aaa} et w = aabaa . . .

Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

14 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixe

Les concepts géneraux
Les types de code

(Soient D ⊆ Σ∗IN , E ⊆ Σ∗OUT et C ∶ D → E .)La 4ème condition est nécessaire :si E n’est pas préfixe,
on ne pourra pas décoder correctement.
Par exemple :ΣIN = {a, b}, ΣOUT = {0, 1}, D = {aa, ab, ba, bb},
E = {0, 1, 10, 11},C (aa) = 0, C (ab) = 1, C (ba) = 10, C (bb) = 11,
w = abaa . . . et w ′ = ba . . .

Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

15 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixe

Les concepts géneraux
Les types de code

Longueur moyenne des mots d’entrée / de code :Soit ΣIN = {a1 , . . . , an } l’alphabet d’entrée,soient p(a1 ), . . . , p(an ) les probabilités des symboles etsoit p(u) la probabilité d’un mot u ∈ D(on suppose l’indépendance des symboles consécutifs entre eux).
Longueur moyenne des mots d’entrée : ∑ p(u) ∗ ∣u∣u∈DLongueur moyenne des mots de code : ∑ p(u) ∗ ∣C (u)∣u∈D

Pour calculer la longueur moyenne, les probabilités utilisées sonttoujours celle des mots d’entrée.

Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

16 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixe

Les concepts géneraux
Les types de code

Les types de code
Soient ΣIN et ΣOUT , D ⊆ Σ∗IN , E ⊆ Σ∗OUT et C ∶ D → E .
Encodage fixe à variable (FV) : C est FV s’il existe k ∈ N
tel que ∣u∣ = k, pour tout u ∈ D.
Il faut minimiser la longueur moyenne des mots de code.
Encodage variable à fixe (VF) : C est VF s’il existe l ∈ N
tel que ∣v ∣ = l, pour tout v ∈ E .
Il faut maximiser la longueur moyenne des mots d’entrée.
Encodage fixe à fixe (FF) : . . .
Encodage variable à variable (VV) : . . .

Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

17 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixe

Les concepts géneraux
Les types de code

Exemples des différents types de code.
Encodage fixe à variable (FV) : Huffman.
Encodage variable à fixe (VF) : Objet de ces travaux.
Encodage fixe à fixe (FF) : Souvent utilisé pour détecter etcorriger des erreurs (rarement en compression de données).
Encodage variable à variable (VV) : LZ77, LZ78, LZW,
LZSS.

Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

18 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixePrésentation de la technique de Tunstall
L’algorithme de Tunstall

Plan
1

2

3

4

Introduction
Les concepts géneraux
Les types de code
La technique de Tunstall
Présentation de la technique de Tunstall
L’algorithme de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Présentation des codes AIVF
L’algorithme de Yamamoto et Yokoo
Les deux modes de la technique de Yamamoto et Yokoo
Amélioration de l’encodage variable à fixe
Le problème de la racine complète en le mode multi-arbre
Le problème de l’exécution complète de l’option II
La technique par programmation dynamiqueDéveloppement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

19 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixePrésentation de la technique de Tunstall
L’algorithme de Tunstall

Hypothèses de travail
Comme nous nous concentrons sur les encodages VF, nous laissons
l’alphabet de sortie (ΣOUT ), les mots de code (E ) et leur longueur(l) implicites.
Nous laissons aussi la fonction d’encodage C implicite.
Nous nous concentrons sur la conception de D, pour une certaine
taille M désirée, et la longueur moyenne des mots d’entrée.
Dorénavent, nous appelons l’alphabet d’entrée Σ.
Nous supposons que les symboles d’entrée, {a1 , . . . an } = Σ, sonttriés par probabilité :p(a1 ) ≥ . . . ≥ p(an ).
Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

20 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixePrésentation de la technique de Tunstall
L’algorithme de Tunstall

Hypothèses de travail

Correspondance code ⇔ arbre.
Notation : #T .
Notation T + {w }.
Notation π(T ).
Maximal-munch parsing.

Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

21 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixePrésentation de la technique de Tunstall
L’algorithme de Tunstall

Présentation de la technique de Tunstall
En 1967, Brian Parker Tunstall a inventé un nouvel algorithme decompression.
Appartient à la famille des codes variables à fixes (VF).
Adopte le principe de dictionnaire pour construire son code.
Contient un ensemble de mots, appelé mots du dictionnairequi sont associés aux différents symboles sources.
⇒ Le nombre du mots de code dépend de la taille du dictionnaire.
Le dictionnaire de Tunstall respecte :Crée un code qui respecte la propriété préfixe.
Crée un arbre complet, où chaque mot de code est assigné à
une feuille de l’arbre.
Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

22 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixePrésentation de la technique de Tunstall
L’algorithme de Tunstall

L’algorithme de Tunstall

Algorithm 1 : Algorithme de Tunstall avec M mots de code
Require: M ≥ ∣Σ∣
1: Tnew ← racine
2: repeat3:
Told ← Tnew
4:
Tnew ← Option I (Told )5: until #Tnew > M
6: return Told

Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

23 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixePrésentation de la technique de Tunstall
L’algorithme de Tunstall

Algorithm 2 : Option I
Require: T un arbre représentant D
1: V ← noeuds incomplets dans T
2: nmax ← arg max n∈V p(n)3: W ← {π(nmax ) ⋅ a ∣ a ∈ Σ}
4: return T + W

Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

24 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixePrésentation de la technique de Tunstall
L’algorithme de Tunstall

ExempleSoit Σ = {a1 , a2 , a3 } où p(a1 ) = 0.6, p(a2 ) = 0.3 et p(a3 ) = 0.1. Soit
M = 7.

Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

25 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixe

Mot du dictionnairea 1 a1 a 1a 1 a1 a 2a 1 a1 a 3a 1 a2a 1 a3a2
a3

Présentation de la technique de Tunstall
L’algorithme de Tunstall

Probabilité
0.216
0.108
0.036
0.18
0.06
0.3
0.1

Mot de code
A
B
C
D
E
F
G

Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

26 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixePrésentation des codes AIVF
L’algorithme de Yamamoto et Yokoo
Les deux modes de la technique de Yamamoto et Yokoo

Plan
1

2

3

4

Introduction
Les concepts géneraux
Les types de code
La technique de Tunstall
Présentation de la technique de Tunstall
L’algorithme de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Présentation des codes AIVF
L’algorithme de Yamamoto et Yokoo
Les deux modes de la technique de Yamamoto et Yokoo
Amélioration de l’encodage variable à fixe
Le problème de la racine complète en le mode multi-arbre
Le problème de l’exécution complète de l’option II
La technique par programmation dynamiqueDéveloppement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

27 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixePrésentation des codes AIVF
L’algorithme de Yamamoto et Yokoo
Les deux modes de la technique de Yamamoto et Yokoo

Les codes VF quasi-instantanés
En 2001, Hirosuke Yamamoto et Hidetoshi Yokoo ont présenté unnouvel encodage VF basé sur les codes quasi-instantanés (AIVF).
Le dictionnaire D est un code quasi-instantané.
Un code quasi-instantané est complet mais n’est pas
nécessairement préfixe.
L’arbre correspondant au code peut avoir des noeuds internes
incomplets.
Les mots de code sont assignés aux noeuds incomplets (i.e. lesfeuilles et les noeuds internes incomplets).
⇒ Dans certaines situations, les codes AIVF surpassent les codes
VF préfixes de Tunstall.
Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

28 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixePrésentation des codes AIVF
L’algorithme de Yamamoto et Yokoo
Les deux modes de la technique de Yamamoto et Yokoo

Les codes VF quasi-instantanés

La technique de Yamamoto et Yokoo repose sur deux stratégies :La première stratégie, appelée option I, est la même que cellede la technique de Tunstall.
La deuxième stratégie, appelée option II, propose un prochain
noeud : celui qui est le plus probable parmi tous les noeuds
pas encore créés.

Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

29 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixePrésentation des codes AIVF
L’algorithme de Yamamoto et Yokoo
Les deux modes de la technique de Yamamoto et Yokoo

L’algorithme de Yamamoto et Yokoo

Algorithm 3 : Option II
Require: T un arbre représentant D
1: U ← {π(n) | noeud n dans T }2: V ← U ⋅ Σ
3: W ← V − U
4: wmax ← arg max w ∈W p(w )5: return T + {wmax }Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

30 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixePrésentation des codes AIVF
L’algorithme de Yamamoto et Yokoo
Les deux modes de la technique de Yamamoto et Yokoo

L’algorithme principal fait croître un arbre en faisant rivaliser les
propositions faites par les deux options.
Algorithm 4 : Algorithme de Y&Y avec M mots de code etinformation partielle sur le prochain symbole ( ∉ {a1 , . . . , ai })Require: i où 0 ≤ i ≤ ∣Σ∣ − 2
Require: M ≥ ∣Σ∣ − i
1: Tnew ← racine + {ai+1 , ⋯, a∣Σ∣ }2: repeat3:
Told ← Tnew
4:
TI ← Option I (Told )5:
TII ← Option II#TI −#Told (Told )6:
Tnew ← le meilleur arbre entre TI et TII
7: until #Tnew > M
8: return Option IIM−#Told (Told )Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

31 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixePrésentation des codes AIVF
L’algorithme de Yamamoto et Yokoo
Les deux modes de la technique de Yamamoto et Yokoo

Les deux modes de la technique de Yamamoto et Yokoo

Mode mono-arbre : Un arbre nommé T0 utilisé en tout
temps. L’arbre présume ne disposer d’aucune information sur
l’entrée.
Mode multi-arbre : Une famille d’arbres Ti spécialisés selonl’information détenue sur le prochain symbole de l’entrée,pour 0 ≤ i ≤ ∣Σ∣ − 2. L’arbre Ti présume que le prochain
symbole de l’entrée ne peut pas être a1 , a2 , . . . ,ai . Cette
connaissance se traduit par l’interdiction de certaines branchesà partir de la racine.

Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

32 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixePrésentation des codes AIVF
L’algorithme de Yamamoto et Yokoo
Les deux modes de la technique de Yamamoto et Yokoo

Exemple en mode mono-arbre

Soit Σ = {a1 , a2 , a3 } où p(a1 ) = 0.6, p(a2 ) = 0.3 et p(a3 ) = 0.1.
Soit M = 7.
(Même situation que dans l’exemple pour l’algorithme de Tunstall.)On ne crée que T0 .

Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

33 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixePrésentation des codes AIVF
L’algorithme de Yamamoto et Yokoo
Les deux modes de la technique de Yamamoto et Yokoo

Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

34 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixePrésentation des codes AIVF
L’algorithme de Yamamoto et Yokoo
Les deux modes de la technique de Yamamoto et Yokoo

Comparaison entre le mode mono-arbre et l’arbre deTunstallL’arbre T0 est différent de l’arbre de Tunstall. Nous remarquons
que T0 a la meilleure longueur moyenne L70 = 1.996
comparativement à l’arbre de Tunstall, qui a L7 = 1.960.

Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

35 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixePrésentation des codes AIVF
L’algorithme de Yamamoto et Yokoo
Les deux modes de la technique de Yamamoto et Yokoo

Exemple en mode multi-arbre
Soit Σ = {a1 , a2 , a3 } où p(a1 ) = 0.6, p(a2 ) = 0.3 et p(a3 ) = 0.1.
Soit M = 7.
T0 est construit comme en mode mono-arbre.
Il reste à construire T1 .

Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

36 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixePrésentation des codes AIVF
L’algorithme de Yamamoto et Yokoo
Les deux modes de la technique de Yamamoto et Yokoo

Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

37 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixe

Le problème de la racine complète en le mode multi-arbre
Le problème de l’exécution complète de l’option II
La technique par programmation dynamique

Plan
1

2

3

4

Introduction
Les concepts géneraux
Les types de code
La technique de Tunstall
Présentation de la technique de Tunstall
L’algorithme de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Présentation des codes AIVF
L’algorithme de Yamamoto et Yokoo
Les deux modes de la technique de Yamamoto et Yokoo
Amélioration de l’encodage variable à fixe
Le problème de la racine complète en le mode multi-arbre
Le problème de l’exécution complète de l’option II
La technique par programmation dynamiqueDéveloppement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

38 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixe

Le problème de la racine complète en le mode multi-arbre
Le problème de l’exécution complète de l’option II
La technique par programmation dynamique

Le problème de la racine complète en le mode multi-arbre

Problème : La technique de Yamamoto et Yokoo exige la créationd’une racine complète lors de l’initialisation.
Solution : Enlever l’obligation d’utiliser l’option I pour créer lesenfants de la racine.

Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

39 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixe

Le problème de la racine complète en le mode multi-arbre
Le problème de l’exécution complète de l’option II
La technique par programmation dynamique

Exemple montrant le problème
Soit Σ = {a, b, c} où p(a) = 0.7, p(b) = 0.2 et p(c) = 0.1. Soit
M = 4. (Erreur dans l’image !)Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

40 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixe

Le problème de la racine complète en le mode multi-arbre
Le problème de l’exécution complète de l’option II
La technique par programmation dynamique

Le problème de l’exécution complète de l’option II

Problème : L’adoption de la proposition faite suite à plusieurs utilisations de l’option II est sous-optimale. (Rappel : l’option II est
exécuté autant de fois qu’il y a de mots de code consommés parl’option I.)
Solution : Notre solution consiste à ne pas exécuter la proposition
complète de l’option II. Nous ajoutons seulement la branche la plus
probable.

Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

41 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixe

Le problème de la racine complète en le mode multi-arbre
Le problème de l’exécution complète de l’option II
La technique par programmation dynamique

Exemple montrant le problème
Nous construisons T0 en mode mono-arbre.
Soit Σ = {a, b, c, d, e} où31p(a) = 31 , p(b) = 41 , p(c) = 16 , p(d) = 20
, p(e) = 10.
Soit M = 10.
Résultats avec/sans exécution complète :Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

42 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixe

Le problème de la racine complète en le mode multi-arbre
Le problème de l’exécution complète de l’option II
La technique par programmation dynamique

Trace de la construction avec adoption partielle de la proposition
de l’option II.

Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

43 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixe

Le problème de la racine complète en le mode multi-arbre
Le problème de l’exécution complète de l’option II
La technique par programmation dynamiqueDéveloppement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

44 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixe

Le problème de la racine complète en le mode multi-arbre
Le problème de l’exécution complète de l’option II
La technique par programmation dynamique

La technique par programmation dynamique

Nous présentons une nouvelle technique pour la construction descodes AIVF en mode multi-arbre.
Cette technique est basée sur la programmation dynamique.
Elle construit des codes AIVF optimaux.

Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

45 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixe

Le problème de la racine complète en le mode multi-arbre
Le problème de l’exécution complète de l’option II
La technique par programmation dynamique

L’algorithme par programmation dynamique

Algorithm 5 : Programmation dynamiqueRequire: M ≥ 1
1: for N = 1 to M do
2:
for i = 0 to ∣Σ∣ − 1 do
3:
TiN ← Création de l’arbre (N, i)
4:
end for
5: end for

Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

46 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixe

Le problème de la racine complète en le mode multi-arbre
Le problème de l’exécution complète de l’option II
La technique par programmation dynamique

Algorithm 6 : Création de l’arbre
Require: N ≥ 1
Require: i ≤ ∣Σ∣ − 1
1: if i = ∣Σ∣ − 1 thenN2:
return T∣Σ∣−1// Cas récursif trivial
3: else if N = 1 then4:
return Ti1// Cas de base
5: else6:
return TiN ← arg maxt∈TN LongMoy(t)// Cas récursifiRoù Ti N = {T0L ⊕ Ti+1
∣L + R = N, L ≥ 1, R ≥ 1}
8: end if

7:

Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

47 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixe

Le problème de la racine complète en le mode multi-arbre
Le problème de l’exécution complète de l’option II
La technique par programmation dynamique

L’algorithme 6 considère trois cas.
Le cas de base :i ≤ ∣Σ∣ − 2 et N = 1.
Le prochain symbole peut être l’un de ai+1 , . . . , a∣Σ∣ .
Il n’est pas connu avec certitude.
Donc, Ti1 est :Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

48 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixe

Le problème de la racine complète en le mode multi-arbre
Le problème de l’exécution complète de l’option II
La technique par programmation dynamique

Le cas récursif trivial :i = ∣Σ∣ − 1.
Le prochain symbole ne peut être que a∣Σ∣ .
N
Donc, T∣Σ∣−1
est :Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

49 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixe

Le problème de la racine complète en le mode multi-arbre
Le problème de l’exécution complète de l’option II
La technique par programmation dynamique

Le cas récursif non-trivial :i ≤ ∣Σ∣ − 2 et N ≥ 2.
Le prochain symbole peut être l’un de ai+1 , . . . , a∣Σ∣ .
Il y a plusieurs façons de construire TiN .
Néanmoins, TiN doit avoir la forme : (Erreur dans l’image !)RRdénotée T0L ⊕ Ti+1
, où L + R = N et T0L et Ti+1
sont optimaux.
Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

50 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixe

Le problème de la racine complète en le mode multi-arbre
Le problème de l’exécution complète de l’option II
La technique par programmation dynamique

Exemple de construction par programmation dynamique
Soit Σ = {a1 , a2 , a3 } où p(a1 ) = 0.6, p(a2 ) = 0.3 et p(a3 ) = 0.1. Soit
M = 3.

Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

51 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixe

Le problème de la racine complète en le mode multi-arbre
Le problème de l’exécution complète de l’option II
La technique par programmation dynamiqueDéveloppement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

52 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixe

Le problème de la racine complète en le mode multi-arbre
Le problème de l’exécution complète de l’option II
La technique par programmation dynamique

Conclusion

Contributions :Identification de deux défauts dans la technique de Y&Y.
Proposition de correctifs aux deux défauts.
Proposition d’un algorithme par programmation dynamique.
Questions restantes :Technique de Y&Y + deux correctifs = technique optimale ?
Véritable définition d’optimalité en mode multi-arbre.

Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

53 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixe

Le problème de la racine complète en le mode multi-arbre
Le problème de l’exécution complète de l’option II
La technique par programmation dynamique

Merci !
Questions ?

Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

54 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixe

Le problème de la racine complète en le mode multi-arbre
Le problème de l’exécution complète de l’option II
La technique par programmation dynamiqueRéférences I[1] Mitsuharu Arimura and Ken-ichi Iwata.
The minimum achievable redundancy rate of fixed-to-fixed
length source codes for general sources.
In Information Theory and its Applications (ISITA), 2010
International Symposium on, pages 595–600. IEEE, 2010.
[2] David A Huffman et al.
A method for the construction of minimum-redundancy codes.
Proceedings of the IRE, 40(9) :1098–1101, 1952.
[3] Brian Parker Tunstall.
Synthesis of Noiseless Compression Codes.
Ph.D. dissertation, Georgia Institute of Technology, Atlanta,
GA, USA, September 1967.
Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

55 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixe

Le problème de la racine complète en le mode multi-arbre
Le problème de l’exécution complète de l’option II
La technique par programmation dynamiqueRéférences II[4] Terry A. Welch.
A technique for high-performance data compression.
Computer, 17(6) :8–19, 1984.
[5] Hirosuke Yamamoto and Hidetoshi Yokoo.
Average-sense optimality and competitive optimality for almost
instantaneous VF codes.
Les IEEE Transactions on Information Theory, 47 :2174–2184,
2001.
[6] Jacob Ziv and Abraham Lempel.
A universal algorithm for sequential data compression.
IEEE Transactions on information theory, 23(3) :337–343,
1977.
Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

56 / 57

Introduction
La technique de Tunstall
Les codes variables à fixes quasi-instantanés (AIVF)
Amélioration de l’encodage variable à fixe

Le problème de la racine complète en le mode multi-arbre
Le problème de l’exécution complète de l’option II
La technique par programmation dynamiqueRéférences III[7] Jacob Ziv and Abraham Lempel.
Compression of individual sequences via variable-rate coding.
IEEE transactions on Information Theory, 24(5) :530–536,
1978.

Développement d’une nouvelle technique de compression pour les codes variables à fixes quasi-instantanés

57 / 57