Codage Elias Delta

Le codage Elias Delta est un algorithme de compression entropique permettant d'encoder des entiers strictement positifs ($ n \ge 1 $) sous forme binaire compacte.

C'est un code universel préfixe : aucun mot de code n'est le préfixe d'un autre, ce qui permet un décodage sans ambiguïté et sans séparateur.

Il est conçu pour représenter des entiers sans connaître leur distribution de probabilité a priori, en utilisant des mots de code dont la longueur croît approximativement comme $ \log_2 n + 2\log_2\log_2 n $

Le principe comporte deux étapes. D'abord, l'utilisateur calcule $ L = \lfloor \log_2 n \rfloor $, c'est-à-dire la position du bit de poids fort de $ n $.

La partie haute est définie comme $ H = L + 1 $ (la longueur binaire de $ n $), qui est ensuite encodée avec Elias Gamma.

La partie basse correspond aux $ L $ bits de $ n $ après suppression du bit de poids fort.

Le code Delta est la concaténation de Gamma($ H $) suivi de ces $ L $ bits.

Elias Gamma encode directement $ n $, tandis qu'Elias Delta encode d'abord la longueur binaire de $ n $, ce qui réduit la surcharge pour les grands entiers.

La longueur du code Gamma est $ 2\lfloor \log_2 n \rfloor + 1 $

La longueur du code Delta est $ \lfloor \log_2 n \rfloor + 2\lfloor \log_2(\lfloor \log_2 n \rfloor + 1) \rfloor + 1 $

Ainsi, quand $ n $ devient très grand, le terme dominant de Delta croît plus lentement que celui de Gamma, ce qui le rend plus efficace pour des valeurs étendues et très variables.

Gamma reste plus simple et souvent préférable pour des petits entiers.

Pour décoder, l'utilisateur commence par décoder le préfixe Elias Gamma, ce qui donne $ H $ (la longueur binaire de $ n $).

L'utilisateur pose ensuite $ L = H - 1 $. Il lit alors les $ L $ bits suivants, qui constituent la partie basse. L'entier est reconstruit par $ n = 2^L + \text{partie basse} $.

L'utilisateur peut privilégier Elias Delta pour :

— la compression d'index ou d'écarts dans des algorithmes comme LZ77 ;

— le stockage compact d'identifiants ou d'offsets dans des bases de données ;

— la transmission de paquets contenant des entiers de grande amplitude.

Pour des très petits entiers (typiquement $ n \le 4 $), Elias Gamma ou un codage unaire peuvent être plus efficaces.

Si la distribution des entiers est connue et très déséquilibrée, un code adaptatif (ex : Huffman ou Golomb-Rice) sera généralement supérieur.

Si $ n = 2^k $, alors $ L = k $ et la partie basse vaut $ 0 $. Le code Delta est alors simplement Gamma($ k+1 $) suivi de $ k $ zéros.

Elias Delta est défini uniquement pour les entiers strictement positifs ($ n \ge 1 $), car le calcul de $ \lfloor \log_2 n \rfloor $ est impossible pour $ n = 0 $

Pour inclure $ 0 $, l'utilisateur peut appliquer un décalage systématique avant encodage.

La méthode la plus simple consiste à coder $ n' = n + 1 $ avec Elias Delta. Ainsi : $ n = 0 $ devient $ n' = 1 $ et est encodé normalement ; $ n = 1 $ devient $ n' = 2 $, etc.

Au décodage, l'utilisateur applique l'opération inverse : si Delta retourne $ n' $, alors l'entier original est $ n = n' - 1 $

Cette transformation est bijective et n'altère pas les propriétés préfixes du code.

Elias Delta ne peut coder que des entiers positifs. Pour encoder des entiers signés, l'utilisateur applique d'abord un codage zigzag, qui transforme chaque entier relatif $ x $ en un entier non négatif $ z(x) $ en alternant positifs et négatifs autour de zéro.

La transformation standard est : $ z(x) = 2|x| $ si $ x < 0 $, $ z(x) = 2x + 1 $ si $ x \ge 0 $

Cela donne la correspondance : $ 0 \mapsto 1 $, $ -1 \mapsto 2 $, $ 1 \mapsto 3 $, $ -2 \mapsto 4 $, $ 2 \mapsto 5 $, etc.

L'utilisateur encode ensuite $ z(x) $ avec Elias Delta (après éventuellement un décalage pour inclure $ 0 $ si nécessaire). Au décodage, l'opération inverse reconstruit $ x $ :

$ x = \lfloor z/2 \rfloor $ si $ z $ est pair (négatif original)

$ x = (z - 1)/2 $ si $ z $ est impair (positif original)

Le zigzag est particulièrement adapté aux codes d'Elias car il évite que les petits nombres négatifs produisent de très grands codes, en gardant les valeurs proches de zéro représentées par de petits entiers.