Table of Contents
La relation fondamentale entre tri et compression
La compression et la décompression des données sous-tendent tout, de la vidéo en streaming au stockage en nuage. Alors que la plupart des ingénieurs se concentrent sur le codage entropie, les méthodes de dictionnaire ou de transformer le codage, un accélérateur souvent surestimé est trié. Trier les algorithmes ne fait pas que réorganiser les données; ils réduisent l'entropie, permettent la détection de motifs et structurent les informations de sorte que les moteurs de compression puissent exploiter la redondance avec un minimum de frais généraux.
Les algorithmes de compression sans perte comme le codage Huffman, l'encodage de longueur d'exécution (RLE) et la transformation Burrows-Wheeeler (BWT) reposent sur des données triées ou partiellement triées pour atteindre des rapports de compression élevés. Même les codecs de perte comme JPEG‐2000 utilisent le tri des coefficients de vague pour une quantisation efficace.
Comment trier réduit l'entropie
L'entropie, en théorie de l'information, mesure la quantité moyenne d'information contenue dans une source. L'entropie élevée signifie que les données sont proches du hasard et difficiles à compresser. Le tri réduit l'entropie locale en regroupant des valeurs semblables. Lorsque des octets ou des jetons identiques apparaissent consécutivement, des schémas simples comme l'encodage de longueur d'exécution deviennent extrêmement efficaces. Par exemple, une séquence d'octets non triée pourrait ne pas avoir deux valeurs identiques adjacentes; après tri, la séquence devient des groupes de valeurs identiques, ce qui abaisse considérablement l'entropie par octet.
La réduction de l'entropie n'est pas globale; le tri introduit une structure différente. Le compresseur doit enregistrer l'ordre original (par une transformation inverse ou permutation) pour permettre une reconstruction sans perte. Mais le coût de stockage de cette permutation est généralement beaucoup plus bas que les économies de l'entropie abaissée.
Tri comme étape de prétraitement
De nombreux systèmes de compression appliquent le tri comme étape de prétraitement. La transformation Burrows-Wheeler divise l'entrée en blocs, puis trie toutes les rotations cycliques de chaque bloc. Le résultat est une chaîne hautement localisée — des caractères qui co-apparent souvent dans l'entrée deviennent adjacents. Cette sortie, après une transformation de transition vers le front, donne de nombreux octets à valeur zéro, qui sont ensuite compressés avec RLE et Huffman. De même, la transformation vers l'avant d'un arbre de paquets de vagues en types de compressions perdues a pour but de prioriser les grands coefficients de quantification.
Un autre exemple est l'utilisation du tri dans les méthodes du dictionnaire Lempel‐Ziv. Le dictionnaire est souvent implémenté comme table de hachage ou arbre. Si le dictionnaire est trié (par exemple, une liste triée de phrases), la recherche binaire réduit le temps de recherche de O(n) à O(log n). Cette accélération devient critique dans les pipelines de compression à haut débit, comme ceux utilisés dans la transmission de données en temps réel.
Algorithmes de tri couramment utilisés dans la compression
Tous les algorithmes de tri ne conviennent pas aussi bien aux charges de travail en compression. Le choix dépend de la taille des données, des contraintes de mémoire et de la possibilité de traiter l'entrée en place.
- Quicksort est largement utilisé pour le tri in-memory des blocs en raison de son temps moyen O(n log n) et de ses frais généraux bas. De nombreuses implémentations bzip2 utilisent Quicksort pour la construction de la matrice de suffixe BWT, bien que son pire cas O(n2) puisse être problématique pour les entrées adverses.
- Mergesort est stable et offre une durée garantie O(n log n), ce qui en fait un bon ajustement pour le tri externe lorsque les données dépassent la RAM. Certains outils de compression qui trient les grandes tables de symboles utilisent une variante de fusion externe.
- Radix Tri est linéaire dans le nombre de bits par clé, ce qui le rend attrayant pour le tri des entiers (par exemple, valeurs de pixels, nombre de fréquences). Il est utilisé dans certains compresseurs à usage spécial pour les données graphiques et scientifiques où les clés sont de largeur fixe. Son principal inconvénient est la consommation de mémoire pour les godets intermédiaires.
- Le tri introspectif (Introsort) commence par le tri rapide, mais passe au tri en masse lorsque la profondeur de récursion dépasse un seuil, combinant vitesse et sécurité. Il s'agit du tri par défaut dans la bibliothèque standard C++ et apparaît dans de nombreux pipelines de compression qui nécessitent un comportement robuste dans le pire des cas.
Tri dans les techniques de compression sans perte
Les algorithmes de compression sans perte exploitent la redondance sans détruire l'information. Le tri s'intègre naturellement à plusieurs d'entre eux, souvent comme une opération primitive au sein du codeur ou comme une pré-transformation.
Encodage de longueur d'exécution (RLE) avec données triées
Le tri de l'entrée peut d'abord convertir une séquence aléatoire en longues durées, ce qui augmente considérablement l'efficacité de la RLE. Par exemple, les images de fax en noir et blanc (compression du groupe 4) utilisent un codage à deux dimensions qui bénéficie de l'ordre naturel des lignes de balayage. Dans les compresseurs génériques, le tri est souvent combiné à un codeur de transition vers le front pour produire de longues durées zéro.
Codage Huffman et sortie triée
Le codage Huffman construit un préfixe optimal basé sur les fréquences de symboles. L'algorithme lui-même exige le tri des fréquences pour construire efficacement l'arbre binaire (généralement en utilisant une file d'attente prioritaire, qui est une structure triée). Par-delà cela, lorsque la sortie d'une transformation de tri est introduite dans le codage Huffman, la distribution de probabilité résultante est plus biaisée : les symboles à haute fréquence (comme les zéros) se produisent avec une probabilité encore plus élevée, permettant des mots de code très courts.
Algorithmes de Lempel-Ziv et dictionnaires triés
Les compresseurs basés sur un dictionnaire comme LZ77, LZ78 et leurs dérivés (LZW, LZMA) maintiennent une fenêtre coulissante ou un dictionnaire croissant de phrases. Les structures de données triées, comme les arbres équilibrés ou les touches de table de hachage triées, accélèrent la recherche la plus longue de tous les temps. Par exemple, zlib utilise une table de hachage dont la chaîne de hachage profite du tri des seaux de hachage.
Transformation des terriers-roues (BWT) et tri
La BWT est peut-être l'illustration la plus directe du rôle de tri en compression. Elle construit une matrice de toutes les rotations cycliques d'un bloc et trie les lignes lexicographiquement. La dernière colonne de cette matrice triée devient la sortie transformée. Le tri est le goulot d'étranglement computationnel; la qualité de la compression dépend entièrement de l'algorithme de tri utilisé pour créer le tableau suffixe. Les implémentations modernes utilisent un tri rapide modifié ou une construction de tableau suffixe linéaire (Lien DOI[. Après le BWT, les données sont très faciles à exécuter et à coder entropie. L'inverse BWT nécessite également le tri — il doit récupérer l'ordre original en reconstituant la première colonne de la dernière colonne, en utilisant le fait que la première colonne est la version triée de la dernière colonne.
Codage arithmétique et tri des probabilités
Si les probabilités des symboles varient selon le contexte, les contextes de tri peuvent améliorer la précision de l'estimation des probabilités. Les codeurs arithmétiques adaptatifs maintiennent souvent une liste triée de paires de symbols de contexte pour localiser rapidement la distribution des probabilités pertinente. Le tri de l'historique des contextes permet également une division plus rapide des intervalles, car les plages peuvent être calculées à l'aide de fréquences cumulatives stockées dans un arbre indexé binaire ou un tableau trié.
Le rôle du tri dans la vitesse de décompression
La décompression doit reconstruire rapidement les données originales, souvent avec une mémoire limitée. Le tri accélère cette reconstruction de plusieurs façons.
Décodage plus rapide avec structures de données triées
De nombreux formats compressés stockent les métadonnées (longueurs de code, décalages, nombres d'exécutions) dans l'ordre trié. Par exemple, les tables de code Huffman sont triées par longueur de code pour accélérer la recherche de décodeur. Lorsque les longueurs de code ne diminuent pas de façon monotonique, le décodeur peut utiliser un arbre canonique Huffman, qui réduit la recherche à un simple passage bit‐by‐bit en utilisant un tableau indexé par le nombre cumulatif.
Tri inverse et reconstruction
L'inverse BWT est un exemple remarquable : étant donné la dernière colonne L et un index pointant vers le premier caractère original, l'algorithme construit la première colonne en triant L. Cette étape de tri est la partie la plus longue de la décompression BWT. Les implémentations optimisées utilisent une liste indexée liée ou un tri de comptage (tranche de bucket) parce que l'alphabet est petit (généralement des octets). Le tri de comptage tourne en temps O(n+k), rendant la décompression très rapide. Sans un tel type de spécialisation, la transformation inverse serait O(n log n), ce qui est inacceptable pour les grands blocs.
Possibilités de parallélisation
Pour la décompression, la transformation inverse de chaque bloc peut être triée de manière indépendante. Des outils comme pbzip2 et pigz (parallèle gzip) permettent de l'utiliser en fractionnant l'entrée en morceaux, en comprimant chacun avec son propre stade de tri, puis en concaténant les blocs compressés. Cela permet de trier à l'échelle avec le nombre de cœurs, ce qui rend la compression et la décompression nettement plus rapide sur le matériel moderne. Par exemple, pigz permet une accélération presque linéaire sur les processeurs multi-core en parallèleant le pipeline de compression, y compris les étapes de tri à l'intérieur de chaque travailleur.
Analyse comparative des algorithmes de tri pour la compression
Choisir l'algorithme de tri approprié peut faire la différence entre un compresseur de qualité de production rapide et un compresseur lent. Ci-dessous, nous comparons les options les plus courantes.
Quicksort vs Mergesort vs Radix Tri
| Algorithm | Time Complexity | Space Complexity | Best Use Case |
|---|---|---|---|
| Quicksort | O(n log n) average, O(n²) worst | O(log n) in-place | In‑memory block sorting (BWT) |
| Mergesort | O(n log n) guaranteed | O(n) auxiliary | External sorting, stable requirements |
| Radix Sort | O(n * k) (k = bit width) | O(n + 2^k) | Fixed‑width integer keys (frequency, pixel values) |
Pour BWT, le speedsort est commun, mais les risques de débordement de la pile sur les données pathologiques. Certaines implémentations (par exemple, bzip2) basculent vers un repli si la profondeur de récursion dépasse une limite. Mergesort offre une prévisibilité au coût de mémoire supplémentaire. Le tri Radix excelle lorsque la plage de touches est petite (par exemple, trier des octets, qui sont 256 valeurs) — puis compter le tri devient tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri tri
Tri des grands ensembles de données : tri externe
Lors de la compression de fichiers plus grands que la RAM disponible, l'ensemble des données ne peut pas être trié en mémoire. Les algorithmes de tri externe (généralement une variante de fusion qui lit et écrit des fichiers temporaires) sont utilisés. Des outils de compression comme `bzip2` pour les grands fichiers cassent l'entrée en blocs (par exemple, 900 KB), trient chaque bloc en mémoire, puis écrivent les blocs compressés de façon séquentielle. Pour des ensembles de données encore plus grands — comme la compression génomique ou la compression de base de données — des types externes plus sophistiqués utilisant plusieurs passes sont nécessaires.
Tri adaptatif et son impact sur la compression
Certains compresseurs adaptent leur stratégie de tri en fonction des caractéristiques des données. Par exemple, un compresseur peut détecter que l'entrée est déjà presque triée (par exemple, texte après un BWT partiel) et utiliser le tri d'insertion comme un retour, car le tri d'insertion est O(n) sur des données presque triées. D'autres utilisent le timsort, un algorithme de tri stable hybride dérivé du tri de fusion et du tri d'insertion, qui est utilisé dans Python="list.sort()" et dans certaines bibliothèques de compression pour le prétraitement. Timsort exploite les résultats naturels dans les données, réduisant ainsi le nombre de comparaisons.
Applications pratiques et optimisations
La synergie entre tri et compression apparaît dans de nombreux systèmes du monde réel.
Tri dans la compression de la base de données
Les bases de données orientées colonne (p. ex. Apache Parquet, ORC) stockent chaque colonne séparément et trient souvent les lignes pour améliorer la compression. Le tri sur une colonne (ou un ensemble de colonnes) améliore grandement l'encodage de la longueur d'exécution : si la colonne est triée, toutes les valeurs identiques deviennent adjacentes, ce qui donne des longues séries qui compressent à quelques octets. Les systèmes modernes de bases de données utilisent également la compression de dictionnaires sur des dictionnaires triés, qui sont simplement triés des listes de valeurs distinctes. Le tri du dictionnaire accélère non seulement la recherche par recherche binaire, mais améliore également l'efficacité du dictionnaire lui-même en regroupant des clés similaires.
Compresse d'image et vidéo
Dans la compression par perte, les vagues se transforment (p. ex. JPEG‐2000, Dirac) en sous-bandes de coefficients. Ces coefficients sont ensuite quantifiés et codés. Le tri des coefficients par grandeur avant le codage (une étape appelée propagation de signification -) permet au codeur d'envoyer d'abord les coefficients les plus importants, en réalisant un flux de bits progressif. L'algorithme de l'ondelet zéro arbre (EZW) et la partition de l'arbre hiérarchique (SPIHT) sont tous deux basés sur des grandeurs de coefficient de tri. De même, dans la compression vidéo, les vecteurs de mouvement et les coefficients DCT peuvent être triés pour améliorer le codage arithmétique basé sur le contexte (comme dans le CABAC de H.264/AVC).
Compression du texte
Les compresseurs de texte comme PPM (prédiction par correspondance partielle) trient souvent les contextes dans lesquels un symbole apparaît. L'arborescence suffixe ou le tableau suffixe utilisé dans de nombreux schémas de compression de texte (par exemple, pour les corrélations à longue distance) nécessite le tri de tous les suffixes de l'entrée. Ceci est identique au BWT en principe. Les compresseurs tels que `szip` pour les données scientifiques utilisent des histoires de symboles triées pour construire des modèles Markov à ordre élevé. Le tri des listes de contextes est généralement fait avec le tri radix sur les niveaux de symbole, exploitant l'alphabet ASCII/octet de largeur fixe.
Compression des données réseau
Les protocoles réseau compressent souvent les en-têtes ou les charges utiles. Par exemple, la compression en-tête IP (RFC 2507) utilise le tri des champs d'en-tête pour identifier les deltas. Certains proxys de compression transparents trient les charges utiles de paquets dans un tampon avant d'appliquer la compression zippée. Bien que le coût du tri d'un petit tampon soit faible, les gains de taux de compression peuvent être significatifs parce que les charges utiles triées ont de longs cycles d'octets identiques.
Conclusion
Les algorithmes de tri sont bien plus que des exercices académiques; ce sont des moteurs pratiques qui accélèrent la compression des données et la décompression. En réduisant l'entropie, en permettant des transformations sophistiquées comme le BWT, et en accélérant les recherches de dictionnaires, le tri fournit la structure dont les algorithmes de compression ont besoin pour atteindre des ratios élevés.
Lors de la conception d'un pipeline de compression, les ingénieurs devraient envisager de choisir soigneusement l'algorithme de tri — équilibrer la vitesse, la mémoire et le comportement dans le pire des cas. Que ce soit en utilisant un tri rapide pour les transformations de blocs, un tri radix pour les opérations de niveau octet ou un tri de fusion externe pour les ensembles de données à échelle téraoctet, l'algorithme de tri approprié peut rendre un système à la fois rapide et efficace.
Pour plus de détails, voir l'article Burrows‐Wheeler transform sur Wikipedia, la bibliothèque Zstandard compression , et un document de recherche sur le tri rapide pour la compression des données (IEEE, 2015).