Ce chapitre explore les algorithmes fondamentaux qui constituent des piliers de l'informatique moderne. Nous nous concentrerons sur deux catégories essentielles : l'algorithme du plus court chemin de Dijkstra et l'algorithme de compression de Huffman. Ces algorithmes sont considérés comme des classiques en raison de leur élégance théorique et de leur importance pratique dans de nombreuses applications du quotidien.
1. Algorithme du plus court chemin de Dijkstra
L'algorithme de Dijkstra est une méthode efficace pour trouver le plus court chemin entre deux nœuds dans un graphe pondéré. Conçu par Edsger W. Dijkstra en 1956, cet algorithme est aujourd'hui à la base de nombreux systèmes de navigation et d'optimisation de réseaux.
Rappel sur les graphes
Un graphe est une structure de données composée de :
- Nœuds (ou sommets) : Les points du graphe, souvent représentés par des cercles
- Arêtes (ou arcs) : Les connexions entre les nœuds, pouvant être pondérées (avec un poids/coût)
- Types de graphes : Orientés (arcs à sens unique) ou non orientés (arêtes bidirectionnelles)
Description de l'algorithme
L'algorithme de Dijkstra suit une approche gloutonne pour trouver le plus court chemin :
- Initialisation : Attribuer une distance infinie à tous les nœuds sauf le nœud source (distance = 0)
- Sélection : Choisir le nœud non visité avec la plus petite distance connue
- Relaxation : Pour chaque voisin de ce nœud, calculer une nouvelle distance potentielle et la mettre à jour si elle est plus courte
- Répétition : Répéter les étapes 2 et 3 jusqu'à ce que tous les nœuds soient visités ou que le nœud cible soit atteint
L'algorithme
Implémentation de Dijkstra en TypeScript
/**
* Implémentation de l'algorithme de Dijkstra en TypeScript
* @param graph Représentation du graphe (matrice d'adjacence)
* @param source Nœud source
* @param target Nœud cible (optionnel)
* @returns Distances minimales et chemins
*/
function dijkstra(
graph: number[][],
source: number,
target: number = -1
): { distances: number[]; predecessors: number[] } {
const n = graph.length;
const distances: number[] = Array(n).fill(Infinity);
const predecessors: number[] = Array(n).fill(-1);
const visited: boolean[] = Array(n).fill(false);
// Distance à la source est 0
distances[source] = 0;
for (let i = 0; i < n; i++) {
// Trouver le nœud non visité avec la plus petite distance
let u = -1;
let minDist = Infinity;
for (let j = 0; j < n; j++) {
if (!visited[j] && distances[j] < minDist) {
u = j;
minDist = distances[j];
}
}
// Si on a atteint la cible, on peut s'arrêter
if (u === target) break;
// Si pas de nœud accessible, on s'arrête
if (u === -1) break;
// Marquer le nœud comme visité
visited[u] = true;
// Mettre à jour les distances des voisins
for (let v = 0; v < n; v++) {
if (
graph[u][v] > 0 && // Existence d'une arête
!visited[v] && // Nœud non visité
distances[u] + graph[u][v] < distances[v] // Chemin plus court
) {
distances[v] = distances[u] + graph[u][v];
predecessors[v] = u;
}
}
}
return { distances, predecessors };
}
/**
* Reconstruction du chemin à partir du tableau des prédécesseurs
*/
function reconstructPath(predecessors: number[], source: number, target: number): number[] {
if (target === -1 || source === target) return [source];
if (predecessors[target] === -1) return []; // Pas de chemin
const path: number[] = [];
let current = target;
while (current !== -1) {
path.unshift(current);
current = predecessors[current];
}
return path;
}
// Exemple d'utilisation
// Représentation du graphe par matrice d'adjacence
// 0 signifie "pas de connexion", les autres valeurs sont les poids
const exampleGraph = [
// A B C D E F
[ 0, 4, 0, 5, 0, 0 ], // A
[ 4, 0, 3, 3, 2, 0 ], // B
[ 0, 3, 0, 0, 4, 0 ], // C
[ 5, 3, 0, 0, 0, 6 ], // D
[ 0, 2, 4, 0, 0, 2 ], // E
[ 0, 0, 0, 6, 2, 0 ] // F
];
// Trouver le plus court chemin de A (0) à F (5)
const sourceNode = 0; // A
const targetNode = 5; // F
const { distances, predecessors } = dijkstra(exampleGraph, sourceNode, targetNode);
const path = reconstructPath(predecessors, sourceNode, targetNode);
console.log(`Distance minimale de A à F: ${distances[targetNode]}`);
console.log(`Chemin: ${path.map(n => String.fromCharCode(65 + n)).join(' → ')}`);
Application au calcul d'itinéraire
L'algorithme de Dijkstra est à la base de nombreux systèmes GPS et services de cartographie en ligne. Dans ces applications :
- Nœuds : Intersections, points d'intérêt
- Arêtes : Routes, chemins
- Poids : Distance, temps de trajet, coût (péage), trafic
Pour optimiser les calculs sur de grands réseaux routiers, plusieurs variantes sont utilisées :
- Dijkstra bidirectionnel : Recherche simultanée depuis l'origine et la destination
- A* : Amélioration de Dijkstra avec une heuristique (estimation de la distance restante)
- Contraction hierarchies : Pré-calcul d'une hiérarchie de routes pour accélérer la recherche
2. Algorithme de compression de données de Huffman
L'algorithme de Huffman est une méthode de compression de données sans perte qui utilise une approche gloutonne pour créer des codes à longueur variable. Développé par David Huffman en 1952, cet algorithme est à la base de nombreux formats de compression modernes.
Principe de la compression de données
La compression de données vise à réduire la taille d'un fichier sans perdre d'information (compression sans perte) ou en acceptant une perte contrôlée (compression avec perte). Le codage de Huffman est l'une des techniques les plus efficaces de compression sans perte, qui repose sur trois principes clés :
- Fréquence d'apparition : Les symboles (caractères, pixels, etc.) qui apparaissent plus fréquemment sont codés avec moins de bits
- Codes préfixes : Aucun code n'est le préfixe d'un autre, permettant un décodage sans ambiguïté
- Structure arborescente : Représentation des codes sous forme d'arbre binaire
Application concrète : La compression de Huffman est utilisée dans de nombreux formats de fichiers comme ZIP, JPEG, MP3 et PNG. Son principe fondamental permet d'économiser jusqu'à 20-90% d'espace selon le type de données.
Description de l'algorithme
L'algorithme de Huffman se déroule en trois phases principales :
- Analyse des fréquences : Calculer la fréquence d'apparition de chaque symbole dans les données
- Construction de l'arbre :
- Créer une file de priorité avec un nœud feuille pour chaque symbole
- Répétitivement extraire les deux nœuds de plus faible fréquence
- Les combiner en un nouveau nœud interne dont la fréquence est la somme des deux
- Réinsérer ce nœud dans la file de priorité
- Continuer jusqu'à ce qu'il ne reste qu'un seul nœud (la racine)
- Génération des codes : Parcourir l'arbre pour attribuer des codes binaires à chaque symbole (0 pour la branche gauche, 1 pour la branche droite)
Exemple de codage du texte "abracadabra"
En utilisant les codes générés dans l'arbre ci-dessus :
- Texte original : "abracadabra" (11 caractères × 8 bits = 88 bits)
- Texte encodé : 0 100 101 0 110 0 111 0 100 101 0 (23 bits)
- Taux de compression : ~74%
Point clé : La qualité de la compression dépend fortement de la distribution statistique des symboles. Plus la distribution est inégale (certains symboles très fréquents, d'autres rares), meilleure sera la compression.
Implémentation de l'algorithme de Huffman en TypeScript
/**
* Implémentation de l'algorithme de compression de Huffman en TypeScript
*/
// Structure de nœud pour l'arbre de Huffman
class HuffmanNode {
char: string | null;
frequency: number;
left: HuffmanNode | null;
right: HuffmanNode | null;
constructor(char: string | null, frequency: number) {
this.char = char;
this.frequency = frequency;
this.left = null;
this.right = null;
}
// Pour trier les nœuds par fréquence
static compare(a: HuffmanNode, b: HuffmanNode): number {
return a.frequency - b.frequency;
}
}
/**
* Calcule la fréquence de chaque caractère dans le texte
*/
function calculateFrequencies(text: string): Map<string, number> {
const frequencies = new Map<string, number>();
for (const char of text) {
const count = frequencies.get(char) || 0;
frequencies.set(char, count + 1);
}
return frequencies;
}
/**
* Construit l'arbre de Huffman à partir des fréquences
*/
function buildHuffmanTree(frequencies: Map<string, number>): HuffmanNode | null {
if (frequencies.size === 0) return null;
// Créer une file de priorité (tableau trié)
const priorityQueue: HuffmanNode[] = [];
// Initialiser avec des nœuds feuilles pour chaque caractère
for (const [char, freq] of frequencies.entries()) {
priorityQueue.push(new HuffmanNode(char, freq));
}
// Construire l'arbre en fusionnant les nœuds de plus faible fréquence
while (priorityQueue.length > 1) {
// Trier la file et prendre les deux nœuds de plus faible fréquence
priorityQueue.sort(HuffmanNode.compare);
const left = priorityQueue.shift()!;
const right = priorityQueue.shift()!;
// Créer un nouveau nœud interne avec ces deux enfants
const parent = new HuffmanNode(null, left.frequency + right.frequency);
parent.left = left;
parent.right = right;
// Ajouter le nouveau nœud à la file
priorityQueue.push(parent);
}
// Le dernier nœud est la racine de l'arbre
return priorityQueue[0];
}
/**
* Génère la table de codes Huffman à partir de l'arbre
*/
function generateHuffmanCodes(
node: HuffmanNode | null,
prefix: string = "",
codes: Map<string, string> = new Map()
): Map<string, string> {
if (node) {
// Si c'est une feuille (caractère), enregistrer son code
if (node.char !== null) {
codes.set(node.char, prefix);
} else {
// Sinon, parcourir récursivement les sous-arbres
generateHuffmanCodes(node.left, prefix + "0", codes);
generateHuffmanCodes(node.right, prefix + "1", codes);
}
}
return codes;
}
/**
* Compresse un texte en utilisant l'algorithme de Huffman
*/
function huffmanCompress(text: string): {
compressedData: string;
codes: Map<string, string>;
tree: HuffmanNode | null;
} {
if (!text) {
return { compressedData: "", codes: new Map(), tree: null };
}
// Calculer les fréquences des caractères
const frequencies = calculateFrequencies(text);
// Construire l'arbre de Huffman
const tree = buildHuffmanTree(frequencies);
// Générer les codes pour chaque caractère
const codes = generateHuffmanCodes(tree);
// Encoder le texte
let compressedData = "";
for (const char of text) {
compressedData += codes.get(char);
}
return { compressedData, codes, tree };
}
/**
* Décompresse des données encodées avec Huffman
*/
function huffmanDecompress(
compressedData: string,
tree: HuffmanNode | null
): string {
if (!tree || !compressedData) return "";
let decompressedText = "";
let currentNode = tree;
// Parcourir les bits et suivre le chemin dans l'arbre
for (const bit of compressedData) {
if (bit === "0") {
currentNode = currentNode.left!;
} else if (bit === "1") {
currentNode = currentNode.right!;
}
// Si on atteint une feuille, ajouter le caractère et revenir à la racine
if (currentNode.char !== null) {
decompressedText += currentNode.char;
currentNode = tree;
}
}
return decompressedText;
}
// Exemple d'utilisation
function demonstrateHuffmanCompression(text: string): void {
console.log(`Texte original: "${text}"`);
console.log(`Taille originale: ${text.length * 8} bits (${text.length} caractères × 8 bits)`);
const { compressedData, codes, tree } = huffmanCompress(text);
console.log("\nCodes Huffman générés:");
for (const [char, code] of codes.entries()) {
console.log(`'${char}': ${code}`);
}
console.log(`\nDonnées compressées: ${compressedData}`);
console.log(`Taille compressée: ${compressedData.length} bits`);
const compressionRatio = (1 - compressedData.length / (text.length * 8)) * 100;
console.log(`Taux de compression: ${compressionRatio.toFixed(2)}%`);
const decompressedText = huffmanDecompress(compressedData, tree);
console.log(`\nTexte décompressé: "${decompressedText}"`);
console.log(`Décompression réussie: ${text === decompressedText}`);
}
// Exécuter la démonstration
demonstrateHuffmanCompression("abracadabra");
Applications et variantes de l'algorithme de Huffman
- Compression JPEG : Utilise le codage de Huffman pour la compression des coefficients DCT après quantification
- Format ZIP : Emploie une variante appelée "Huffman dynamique" qui s'adapte au flux de données
- Codage arithmétique : Une extension qui peut atteindre des taux de compression encore meilleurs mais plus complexe à implémenter
- Compression DEFLATE : Combine Huffman avec LZ77 dans les formats PNG, ZIP et GZIP