> golomb | compression | optimale <
// Codage Golomb - Compression optimale des entiers avec diviseur flexible
>> fonctionnalités
Diviseur flexible
Choisissez n'importe quelle valeur de M pour une efficacité de compression maximale.
Binaire tronqué
Utilise un nombre minimal de bits pour coder le reste.
Usage général
Fonctionne avec toute distribution d'entiers non négatifs.
>> informations techniques
Comment fonctionne le codage Golomb
Le codage Golomb divise chaque entier n par un diviseur M pour obtenir un quotient q et un reste r. Le quotient est codé en unaire et le reste en binaire tronqué, en utilisant le nombre minimal de bits nécessaire pour représenter les M valeurs possibles. Cela crée un code optimal pour les distributions géométriques de paramètre p = 1/M.
Exemple de codage Golomb (M=5)
M=5, b=⌈log₂(5)⌉=3, c=2³-5=3 0 → q=0, r=0 → 0|00 → 000 (2 bits pour r<3) 1 → q=0, r=1 → 0|01 → 001 (2 bits pour r<3) 2 → q=0, r=2 → 0|10 → 010 (2 bits pour r<3) 3 → q=0, r=3 → 0|110 → 0110 (3 bits pour r≥3) 4 → q=0, r=4 → 0|111 → 0111 (3 bits pour r≥3) 5 → q=1, r=0 → 10|00 → 1000 6 → q=1, r=1 → 10|01 → 1001 7 → q=1, r=2 → 10|10 → 1010 Binaire tronqué : r<3 utilise 2 bits, r≥3 utilise 3 bits
Pourquoi utiliser le codage Golomb
- Optimal pour les distributions géométriques
- Paramètre M flexible
- Utilisation minimale de bits
- Implémentation simple
- Optimalité démontrée
>> questions fréquentes
Qu'est-ce que le codage Golomb ?
Le codage Golomb est un code optimal, préfixe libre et à longueur variable pour les distributions géométriques. Il divise les entiers avec un paramètre ajustable M, code le quotient en unaire et le reste en binaire tronqué, obtenant une compression optimale pour les données suivant P(n) = (1-p)^n × p.
Comment choisir le paramètre M ?
Le M optimal dépend du paramètre géométrique p de vos données. Pour des données de moyenne μ, un M optimal est approximativement μ + 1. Pour des probabilités décroissantes exponentiellement de paramètre p, le M optimal est M = ⌈-1/log₂(1-p)⌉. Utilisez la fonction d'analyse pour trouver le meilleur M pour vos données.
Qu'est-ce que le binaire tronqué ?
Le binaire tronqué minimise le nombre de bits lors du codage de l'un des M valeurs possibles. Si M est une puissance de 2, on utilise le binaire standard. Sinon, certaines valeurs utilisent ⌊log₂M⌋ bits et d'autres ⌈log₂M⌉ bits, garantissant une décodabilité unique avec longueur moyenne minimale.
Où le codage Golomb est-il utilisé ?
Le codage Golomb est utilisé dans la compression d'images JPEG-LS, dans le codage vidéo H.264 (sous forme d'Exp-Golomb) et dans des formats audio sans perte. Il est idéal pour le codage des longueurs de séries, des résidus après prédiction et pour toute donnée suivant une distribution géométrique ou exponentielle.