TD d’algorithmique numéro 7 Olivier Bodini et Natacha Portier

lundi 5 novembre 2001

Question 1 ⋆ codage de Huffman ⋆

Soit Σ un alphabet, c’est à dire un ensemble fini, que l’on suppose de cardinal au moins deux. Ses éléments sont appelés des lettres. Un codage binaire est une application injective de Σ dans l’ensemble des suites finies de 0 et de 1. Il s’étend de manière naturelle par concaténation à une application définie sur l’ensemble Σ^{∗} des mots de Σ, c’est à dire des suites finies de Σ. Un codage est de longueur fixe si tous les caractères sont codés par un mot binaire de même longueur. Il est préfixe si aucun mot du code n’est préfixe d’un autre mot du code.

Question 1.1

Le décodage d’un codage de longueur fixe est unique. Montrer qu’il en est de même pour un codage préfixe.

Question 1.2

Représenter un codage préfixe par un arbre binaire dont les feuilles sont les lettres de l’alphabet.

On considère un texte dans lequel chaque caractère c apparaît avec une fréquence f(c) non nulle. À chaque codage préfixe de ce texte, représenté par un arbre T, est associé un coût, défini par

B(T) = ∑_{c∈Σ} f(c)d_{T} (c) ,

où d_{T} (c) est la taille du mot binaire codant c. Un codage préfixe représenté par l’arbre T est optimal si pour ce texte il minimise la fonction B. Montrer qu’à un codage préfixe optimal correspond un arbre binaire complet, i.e. dans lequel tout noeud interne a deux fils. Montrer qu’un tel arbre a |Σ| feuilles et a |Σ| − 1 nœuds internes.

Question 1.3

Montrer qu’il existe un code préfixe optimal pour lequel les deux caractères de plus faible fréquence sont frères, i.e. leurs codes sont de même longueur et ne diffèrent que par le dernier bit (propriété du choix glouton).

Soit T l’arbre d’un codage binaire optimal pour la fréquence f sur l’alphabet Σ. Soient x et y deux lettres soeurs et soit z une lettre fraîche avec laquelle on étiquette leur mère. Alors, en considérant z comme un caractère de fréquence f(z) = f(x) + f(y) montrer que l’arbre T′ = T − {x, y} représente un codage préfixe optimal pour l’alphabet Σ′ = Σ − {x, y} ∪ {z} (propriété de sous-structure optimale).

Question 1.4

Donner un algorithme pour trouver un codage optimal. Trouver le codage minimal pour Σ = {a, b, c, d, e, g} et f(a) = 45, f(b) = 13, f(c) = 12, f(d) = 16, f(e) = 9 et f(g) = 5.

Question 2 ⋆ chaînes d’une permutation ⋆

On considère une permutation p = (p[1], …, p[n]) de [1, …, n]. On pose p_{i} = (i, p[i]) ∈ ℕ^{2}; on dit que p_{i} domine p_{j} si i ≥ j et p[i] ≥ p[j]. On écrit cela p_{i} ≥ p_{j}, et on note p_{i} > p_{j} pour p_{i} ≥ p_{j} et p_{i} ≠ p_{j}.

On vérifie aisément que la relation ≥ est un ordre partiel.

Une chaîne est une suite p_{i_{1}}, …, p_{i_{k}} telle que p_{i_{1}} > ⋯ > p_{i_{k}}. On définit la hauteur de p_{i} comme la longueur maximale d’une chaîne dans l’ensemble des p_{j} tels que p_{i} ≥ p_{j}. Soit S_{h} l’ensemble des points de hauteur h.

Question 2.1

On fixe i, et on note h la hauteur de p_{i}. Montrer que le point de S_{h−1} le plus à droite parmi ceux qui sont à gauche de p_{i} est dominé par p_{i} (les p_{i} sont vus comme des points du plan).

Question 2.2

Proposer un algorithme pour calculer les hauteurs des éléments d’un ensemble de n points.

Comment exhibe-t-on une chaîne de longueur maximale?