Codage arithmétique.

Ce soir j'ai compris pourquoi le codage arithmétique (une méthode de compression des données sans perte) fonctionne. Et ce en précision fixe, malgré la description théorique qui laisse entendre que tout se passe avec des intervalles réels et qu'en pratique "on se débrouille" (insérer ici l'agitage de main habituel). Comme par hasard pour montrer que tout se passe bien on choisit des exemples où les seules divisions qui apparaissent se font par une puissance de la base, donc forcément tout va bien.

Cet article introductif explique un peu mieux ce qu'il se passe que l'article wikipedia. Et pour finir, il suffisait tout simplement de lire l'article original Arithmetic coding for data compression de Witten, Neal et Cleary qui prouve de façon élémentaire la correction du décodage. À noter le petit shoot d'archéologie en lisant que l'algorithme a été implémenté par les auteurs sur VAX-11/780 en assembleur...