Enveloppe convexe des codes de Huffman finis, The convex hull of Huffman codes

Thanh Hai Nguyen

Description

Sous la direction de Viet Hung Nguyen, Jean-François Maurras
Thèse soutenue le 10 décembre 2010: Aix Marseille 2
Dans cette thèse, nous étudions l'enveloppe convexe des arbres binaires à racine sur n feuilles.Ce sont les arbres de Huffman dont les feuilles sont labellisées par n caractères. à chaque arbre de Huffman T de n feuilles, nous associons un point xT , appelé point de Huffman, dans l'espace Qn où xT est le nombre d'arêtes du chemin reliant la feuille du ième caractère et la racine.L'enveloppe convexe des points de Huffman est appelé Huffmanoèdre. Les points extrêmes de ce polyèdre sont obtenus dans un premier temps en utilisant l'algorithme d'optimisation qui est l'algorithme de Huffman. Ensuite, nous décrivons des constructions de voisinages pour un point de Huffman donné. En particulier, une de ces constructions est principalement basée sur la construction des sommets adjacents du Permutoèdre. Puis, nous présentons une description partielle du Huffmanoèdre contenant en particulier une famille d'inégalités définissant des facettes dont les coefficients, une fois triés, forment une suite de Fibonacci. Cette description bien que partielle nous permet d'une part d'expliquer la plupart d'inégalités définissant des facettes du Huffmanoèdre jusqu'à la dimension 8, d'autre part de caractériser les arbres de Huffman les plus profonds, i.e. une caractérisation de tous les facettes ayant au moins un plus profond arbre de Huffman comme point extrême. La contribution principale de ce travail repose essentiellement sur les liens que nous établissons entre la construction des arbres et la génération des facettes
-Arbre de Huffman
-Code de Huffman
-Enveloppe convexe
-Polytope
-Polyèdre combinatoire
-Hyperplan
-Facette
-Fibonacci
In this thesis, we study the convex hull of full binary trees of n leaves. There are the Huffman trees, the leaves of which are labeled by n characters. To each Huffman tree T of n leaves, we associate a point xT , called Huffman point, in the space Qn where xT i is the lengths of the path from the root node to the leaf node marked by the ith character. The convex hull of the Huffman points is called Huffmanhedron. The extreme points of the Huffmanhedron are first obtained by using the optimization algorithm which is the Huffman algorithm. Then, we describe neighbour constructions given a Huffman point x. In particular, one of these constructions is mainly based on the neighbour construction of the Permutahedron. Thereafter, we present a partial description of the Huffmanhedron particularly containing a family of inequalities-defining facets whose coeficients follows in some way the law of the well-known Fibonacci sequence. This description allows us, on the one hand, to explain the most of inequalities-defining facets of the Huffmanhedron up to the dimension 8, on the other hand, to characterize the Huffman deepest trees, i.e a linear characterization of all the facets containing at least a Huffman deepest tree as its extreme point. The main contribution of this work is essentially base on the link what we establish between the Huffman tree construction and the facet generation.
-Polyhedral combinatorics
-Polytope
-Huffman code
-Huffman tree
-Hyperplane
-Facet
-Fibonacci
Source: http://www.theses.fr/2010AIX22130/document

Sujets

• Codage de Huffman
• Enveloppe convexe
• Polytope
• Hyperplan
• Leonardo Fibonacci

Informations

• Publié par: Thesee
• Nombre de lectures: 82
• Langue: Français
• Poids de l'ouvrage: 1 Mo

Extrait

´UNIVERSITE AIX–MARSEILLE
U.F.R. SCIENCES DE LUMINY
´ ´ECOLE DOCTORALE DE MATHEMATIQUES ET INFORMATIQUE, E.D. 184
`THESE
pr´esent´ee et soutenue publiquement le 10 D´ecembre 2010
pour l’obtention du grade de
´Docteur de l’Universite Aix–Marseille
Sp´ecialit´e :Informatique
par
Thanh Hai NGUYEN
sous la direction des Pr. Jean - Fran¸cois MAURRAS et Viet Hung NGUYEN.
Titre :
ENVELOPPE CONVEXE DES CODES DE HUFFMAN FINIS
Composition du jury
M. David AVIS Professeur, McGill University Rapporteur
M. Ali Ridha MAHJOUB Universit´e Paris Dauphine Rapp
M. Victor CHEPOI Universit´e Aix-Marseille Examinateur
M. Mohamed Didi BIHA Professeur, Universit´e Caen
`M. Yann VAXES Professeur, Universit´e Aix-Marseille
M. Jean - Fran¸cois MAURRAS Universit´e Aix - Marseille Directeur
M. Viet Hung NGUYEN Maˆıtre de Conf´erences, Universit´e Paris VI Directeur
Laboratoire d’Informatique Fondamentale de Marseille – CNRS UMR 6166
Facult´e des Sciences de Luminy – Universit´e Aix–MarseilleMis en page avec la classe thloria.i
`A mes parents
`A la m´emoire de ma sœur
˜ˆNGUYEN Thi Loan (1972 - 1982)iiiii
Life has to suffer from the storm,
but never lower our heads before the storm
N.A.OSTROTSKY
Ce que l’on connaˆıt n’est qu’une goutte d’eau,
ce que l’on ne connaˆıt pas encore est un grand oc´ean.
I. NEWTONivv
Remerciements
Je tiens a` exprimer toute ma gratitude a` mes directeurs de th`ese Viet Hung Nguyen et Jean-
Franc¸ois Maurras pour avoir dirig´e mon travail avec une disponibilit´e exceptionnelle et m’avoir
fait partager leurs savoir-faires, leur rigueur scientifique, ainsi que leurs multiples comp´etences.
Je souhaite les remercier pour leurs permanents encouragements pendant les moments cruciales
et leurs pr´ecieux conseils qui m’ont aid´e `a structurer mes id´ees et donner forme `a cette th`ese.
J’esp`ere que cette th`ese sera un remerciement suffisant au soutien et a` la confiance sans cesse
renouvel´ee dont ils ont fait preuve en mon ´egard.
Je voudrais adresser mes plus sinc`eres remerciements `a David Avis et Ali Ridha Mahjoub qui
m’ont fait l’honneur d’accepter de juger ce travail malgr´e un emploi du temps surcharg´e en cette
p´eriode de fin d’ann´ee. Leurs suggestions et les fructueuses discussions que nous avons´echang´ees
(pendant les conf´erences de JPOC avec Ridha, dans la salle de biblioth`eque et dans le bureau de
Jean-Fran¸cois avec David) me permettront d’am´eliorer nos r´esultats. Je suis tr`es reconnaissant
a` Mohamed Didi Biha d’avoir accept´e de faire partie de mon jury de th`ese. Je tiens ´egalement a`
remercier Victor Chepoi et Yann Vax`es pour leurs conseils et leurs disponibilit´es. Un immense
merci, bien qu’insuffisant `a Victor de m’avoir aid´e a` structurer mes articles et ma th`ese, ainsi
que pour tout ce qu’il m’apport´e depuis ma licence 3. Ce que j’ai obtenu aujourd’hui, c’est entre
autres graceˆ a` lui.
Je souhaite remercier l’ensemble des membres du d´epartement d’informatique de Luminy (DIL)
et du laboratoire d’informatique fondamentale de Marseille (LIF) pour les formations de bonne
´qualit´es que j’ai suivies. Je remercie en particulier Elisabeth Godbert pour avoir ´ecout´e mes
besoins et mes attentes en tant qu’enseignements. Grˆace `a toi, ma recherche et mes enseigne-
ments sont toujours dans d’excellents conditions. Merci encore a` Yann d’avoir su organiser mon
planning d’enseignements pendant les derniers mois afin que je puisse terminer ma r´edaction
de th`ese. Je tiens ´egalement `a remercier G´erard Cornu´ejols pour tes encouragements et les dis-
cussions int´eressantes, Pierre Bonami qui m’a accept´e de participer `a votre projet (avec Viet),
Karim Nouioua qui m’a donn´e des remarques int´eressantes pour la preuve des sommets adja-
cents, Bertrand Estellon pour les critiques sur le jeu en ligne PES que nous avons discut´ees et
aussi pour les servies que tu m’as donn´es, Paul Sabatier pour la recherche des bouquins dans
la biblioth`eque, Jean-Luc Massat, Bernard Fichet et Pascal Pr´ea pour votre patience d’avoir
´ecout´e ma pr´esentation pendant la r´eunion d’´equipe (ACRO), Claude Sabatier et Line Jakubiec
´qui sont toujours prˆets `a me r´epondre des questions SQL/Oracle, Edouard Thiel qui m’a com-
muniqu´e sa passion pour Linux, Henri Garreta qui m’a enseign´e des cours de compilateur avec
bonne qualit´e de la p´edagogie, Nadia Creignou et Laurent Tichit pour votre gentillesse, Michael
Zock pour les discussions sur les matchs de l’´equipe d’Allemagne. Enfin, je souhaite adresser
mes remerciements a` Benjamin L´evˆeque, R´egis Barbanchon, Christian Aperghis, Jacques Gis-
pert,St´ephaneGrandcolas,JacquesGuizol,R´emiMorin,AlexisNasr,Jean-Fran¸coisPique,Jean
Royaut´e, Claude Lai, Camilla Schwind, Marie-H´el`ene St´efanini, Franc¸ois Brucker, Laure Brieus-
sel,MichelVanCaneghempourtouteslesdiscussionsint´eressantesquej’aieuavecvouspendant
trois ans de th`ese.
Un grand merci a` Sylvie Calabr`ese, Brigitte Garabedian, Antonio Merenda, Nadine Comes pour
les sourires et les services quevous m’avez donn´es. Merci a` Manuel Bertrand et Ga¨ella Lote pour
vos disponibilit´es et vos gentillesses.vi
”Faire une th`ese”est un ”chapitre”tr`es long mais tr`es court au milieux de compagnons de for-
tune. On ne se rend pas toujours compte `a quel point ils peuventˆetre importants dans le travail
et dans la vie, jusqu’au jour ou` nos chemins se s´eparent. Je ne remercierais pas Nicolas Catusse,
Daniela Maftuleac et Fabien Rebatel, je me contenterais de regretter les moments inoubliables
que nous avons pass´es ensembles. Merci pour les matchs du foot dans lesquels nous ´etions le
noyau dur (d’apr`es Yann). Merci Sebastien Imbrosciano qui a toujours cru en moi.
Finalement j’adresse un grand merci a` toute ma famille, en particulier `a ma femme, pour leur
irrempla¸cable et inconditionnel soutien. Ils ont ´et´e pr´esents pour ´ecarter les doutes, soigner les
blessures et partager les joies. Cette th`ese est un peu la leur aussi. Merci ´egalement `a Florence
et Louis Bonardo d’ˆetre toujours a` cˆot´e de moi.R´esum´e
Dans cette th`ese, nous ´etudions l’enveloppe convexe des arbres binaires a` racine sur n feuilles.
`Ce sont les arbres de Huffman dont les feuilles sont labelis´ees par n caract`eres. A chaque arbre
Tde Huffman T de n feuilles, nous associons un point x , appel´e point de Huffman, dans l’es-
n T `emepaceQ ou` x est le nombre d’arˆetes du chemin reliant la feuille du i caract`ere et la racine.
i
L’enveloppe convexe des points de Huffman est appel´e Huffmano`edre. Les points extrˆemes de
ce poly`edre sont obtenus dans un premier temps en utilisant l’algorithme d’optimisation qui
est l’algorithme de Huffman. Ensuite, nous d´ecrivons des constructions de voisinages pour un
point de Huffman donn´e. En particulier, une de ces constructions est principalement bas´ee surla
construction des sommets adjacents du Permuto`edre. Puis, nous pr´esentons une description par-
tielle du Huffmano`edre contenant en particulier une famille d’in´egalit´es d´efinissant des facettes
dont les coefficients, une fois tri´es, forment une suite de Fibonacci. Cette description bien que
partielle nous permet d’une part d’expliquer la plupart d’in´egalit´es d´efinissant des facettes du
Huffmano`edre jusqu’`a la dimension 8, d’autre part de caract´eriser les arbres de Huffman les plus
profonds, i.e. une caract´erisation de tous les facettes ayant au moins un plus profond arbre de
Huffman comme point extrˆeme. La contribution principale de ce travail repose essentiellement
sur les liens que nous ´etablissons entre la construction des arbres et la g´en´eration des facettes.
Mots-cl´es: arbre de Huffman, code de Huffman, enveloppe convexe, polytope, poly`edre combi-
natoire, hyperplan, facette, Fibonacci.Abstract
In this thesis, we study the convex hull of full binary trees of n leaves. There are the Huffman
trees, the leaves of which are labeled by n characters. To each Huffman tree T of n leaves,
T n Twe associate a point x , called Huffman point, in the space Q where x is the lengths ofi
ththe path from the root node to the leaf node marked by the i character. The convex hull of
the Huffman points is called Huffmanhedron. The extreme points of the Huffmanhedron are first
obtainedbyusingtheoptimizationalgorithmwhichistheHuffmanalgorithm.Then,wedescribe
neighbour constructions given a Huffman point x. In particular, one of these constructions is
mainly based on the neighbour construction of the Permutahedron. Thereafter, we present a
partialdescriptionoftheHuffmanhedronparticularlycontainingafamilyofinequalities-defining
facets whose coefficients follows in some way the law of the well-known Fibonacci sequence. This
description allows us, on the one hand, to explain the most of inequalities-defining facets of the
Huffmanhedron up to the dimension 8, on the other hand, to characterize the Huffman deepest
trees, i.e a