Cet article peut intéresser ceux qui sont engagés dans la compression de données ou qui souhaitent écrire leur propre archiveur.
L'article est écrit principalement sur les matériaux du
blog , qui est maintenu par Fabian Giesen.
Présentation
La méthode de codage entropique rANS (
r ange + ANS) est le frère de l'algorithme FSE, dont j'ai
parlé plus tôt . L'abréviation ANS signifie
Asymmetric Numeral Systems , et la plage de mots dans le nom indique la similitude de cette méthode avec le
codage d'intervalle . L'auteur de rANS est
Yarek Duda .
La méthode rANS vous permet d'obtenir une compression presque optimale à très grande vitesse. Dans ce rANS n'est pas pire que FSE, ce qui n'est pas surprenant: les deux algorithmes sont basés sur une base théorique commune. Cependant, l'algorithme rANS est beaucoup plus simple à mettre en œuvre que FSE.
Il y aura d'abord une longue partie «théorique», puis nous essaierons d'écrire un simple archiveur.
Description de la méthode
Le fonctionnement de l'algorithme est déterminé par les formules simples suivantes:
Encodage: C(s,x): x := (x / Fs) * M + Bs + (x % Fs)Décodage: D(x): s = sym[x % M], x := Fs * (x / M) + (x % M) - BsAnalysons-les en détail.
La fonction de codage
C (s, x) reçoit le caractère
s à coder (que ce soit un entier) et l'état actuel du codeur
x (également un entier).
F s - fréquence du symbole
s . La division par Fs ci-dessus est un entier.
M est la somme des fréquences de tous les symboles de l'alphabet (
M = Σ
F s ).
En s , le début de l'intervalle correspondant au caractère codé (dans la figure ci-dessous).
x %
Fs est le reste de la division de
x par
F s .
Le principe de fonctionnement est le même qu'en
codage arithmétique : on prend le segment
[ 0,
M) et on le divise en parties pour que chaque caractère
s corresponde à un intervalle de taille égale à la fréquence du caractère
F s . L'occurrence de la valeur
x% M dans n'importe quel intervalle indique le codage du symbole correspondant.
Au début de l'encodage, initialisez
x avec une valeur arbitraire appropriée, puis calculez la fonction
C (s, x) pour tous les caractères encodés en séquence.
Chaque calcul de la fonction
C (s, x) augmente la valeur de
x . Quand il devient trop gros, vous devez vider les données en sortie:
while (x >= x_max) { writeToStream(x % b);
Cette étape est appelée
renormalisation . Après cela, vous pouvez continuer à coder.
Ci-dessus dans le code, de nouvelles constantes sont apparues:
x_max et
b . En théorie, les nombres
M ,
b et
x_max sont liés par certaines relations, mais en pratique, il est plus efficace d'utiliser les valeurs suivantes si l'état uint32 est utilisé pour l'état
x :
M = 2 ^
k , où
k <= 16
b = 2 ^ 16 (la moitié de la taille de uint32)
Le choix de
M = 2 ^
k est dû au fait qu'il y a division par
M dans la fonction de décodage, de sorte que la division avec le reste peut être remplacée par des opérations au niveau du bit.
La valeur de
k est choisie parmi les considérations suivantes: plus elle est grande, plus la précision de
F s est élevée et plus la compression est efficace. Dans ce cas, certains frais généraux pour le stockage de la table de fréquences doivent être pris en compte, il n'est donc pas toujours utile d'utiliser les valeurs maximales de
k .
La valeur de
x_max doit être telle qu'aucun débordement ne se produise. Sur la base de la fonction de codage, nous obtenons que
x <
uint32_max *
Fs /
M ou d'une manière légèrement différente:
x_max <= (
b *
L ) *
Fs /
M , où
L <=
uint32_max /
b . En code réel, la condition prend la forme x / b> = L / M * Fs pour éviter un débordement dans les calculs.
La valeur
b = 2 ^ 16 (la moitié de la taille de uint32) est choisie de telle manière que si
x dépasse
x_max , alors une division par
b suffit pour continuer à fonctionner. Par conséquent, la
while se terminera après la première itération, ce qui signifie qu'elle peut être remplacée par un simple
if .
Par conséquent, la fonction de codage prend la forme suivante:
typedef uint32_t RansState; constexpr uint32_t RANS_L = 1u << 16; constexpr uint32_t k = 10;
À la fin de l'encodage, vous devez enregistrer la valeur de
x , car le décodage commencera à partir de celui-ci. Et oui, nous allons décoder de la fin au début, c'est-à-dire du dernier caractère codé au premier. (Dans un article sur
FSE, ce point est expliqué de manière suffisamment détaillée.)
Je veux m'attarder un peu plus sur le fonctionnement de la formule d'encodage.
x := (x / Fs) * M + Bs + (x % Fs)
Après calcul (
x / Fs) * M , la variable
x contient les
k bits les moins significatifs (rappelons que
M = 2 ^
k ). L'ajout de
+ Bs + (x % Fs) écrit essentiellement sur ces bits une certaine valeur de l'
intervalle du caractère
s , car
Bs est le début de l'intervalle, et (x% Fs) est le nombre dans cet intervalle (la taille de l'intervalle est Fs). Ainsi, lors du décodage, nous pouvons déterminer le caractère codé par l'intervalle dans lequel il tombe (x% M).
DécodagePassons à la fonction de décodage.
D(x): s = sym[x % M], x := Fs * (x / M) + (x % M) - Bs
Comme nous l'avons déjà compris plus haut, le caractère souhaité
s est déterminé par le reste de la division
x %
M. Dans quel intervalle la valeur (x% M) est tombée, un tel caractère a été encodé.
Plus tôt, nous avons spécifiquement défini M = 2 ^ k pour simplifier la fonction de décodage. Cela a fini comme ceci:
uint32_t RansDecode(RansState& x, RansInBuf& in) { assert(x >= RANS_L);
Le décodage commence par le même
x que celui obtenu à la fin du codage. Pour ce faire, il doit être enregistré avec les données encodées.
A la fin du décodage, l'état du décodeur
x doit être exactement le même que le codage. En général, à chaque étape,
x doit être exactement le même qu'à l'étape de codage correspondante. Ce fait aide beaucoup lors du débogage.
Comme vous pouvez le voir, le décodage fonctionne plus rapidement que l'encodage, car il n'y a pas d'opérations de division.
Le moment le plus difficile dans la fonction de décodage est la méthode pour déterminer dans quel intervalle la valeur a chuté (x% M).
La méthode la plus simple et la plus rapide consiste à utiliser la table
sym [] , taille
M. Dans ce cas, nous obtenons une table de la même taille que dans l'algorithme FSE, à la différence que dans rANS, la table n'est pas «mélangée», les caractères sont en ordre et une telle table est beaucoup plus facile à construire.
Le principal inconvénient de cette approche est la taille de la table
sym , qui croît de façon exponentielle avec l'augmentation de
k .
Méthode d'alias
Une
méthode d'alias a été inventée pour déterminer plus efficacement le hit dans un intervalle. Cette méthode vous permet de déterminer rapidement l'intervalle souhaité à l'aide de petites tables - par le nombre de caractères de l'alphabet.
Une explication longue et longue peut être trouvée ici:
Fléchettes, Dés et Pièces . Je vais décrire l'essentiel de la méthode en bref: nous prenons un morceau de l'intervalle le plus long et l'attachons à l'intervalle le plus court afin que la taille totale soit exactement
M /
N (où
N est le nombre de caractères de l'alphabet). Il s'avère que si vous le faites séquentiellement, vous vous retrouverez toujours avec
N paires de taille
M /
N.Naturellement,
M doit être divisible par
N. Et si nous rappelons que nous avons
M = 2 ^
k , alors la taille de l'alphabet s'avère également être une puissance de deux. Ce n'est pas un problème, car vous pouvez toujours compléter l'alphabet à la taille souhaitée avec des caractères inutilisés avec une fréquence nulle.
Le fait que l'intervalle de caractères soit divisé en plusieurs parties complique un peu, mais pas beaucoup la procédure de codage. Si vous vous souvenez du FSE, les intervalles étaient donc généralement répartis sur toute la gamme, comme si un mélangeur fou avait travaillé dessus, et rien ne fonctionnait =)
Il n'est pas difficile de déterminer l'intervalle souhaité: divisez
x par
N et tombez dans l'une des paires. Ensuite, nous comparons le reste de la division de
x% N avec la frontière entre les segments d'une paire et tombons soit dans un intervalle soit dans un autre.
Nous essayons en pratique
Nous utiliserons le code de l'
exemple fini .
Nous prenons les données pour la compression du fichier:
size_t in_size; uint8_t* in_bytes = read_file("book1", &in_size);
1. Vous devez d'abord décider de
la structure des données .
Nous utilisons l'option la plus simple: nous allons coder un octet en utilisant l'alphabet [0 ... 255].
2. L'étape suivante consiste à déterminer la
fréquence des caractères de l' alphabet:
(fonction
stats.count_freqs )
for (size_t i = 0; i < in_size; i++) { freqs[in_bytes[i]]++; }
3. Donc, nous avons des fréquences de symboles, mais maintenant nous devons les
normaliser , c'est-à-dire réduire (ou augmenter) proportionnellement de sorte qu'au total nous obtenons M = 2 ^ k. Ce n'est pas une tâche aussi simple que cela puisse paraître, nous utilisons donc une fonction prête à l'emploi:
stats.normalize_freqs(...);
Soit dit en passant, vous devez déterminer la valeur de
k . Puisque notre alphabet est composé de 256 caractères,
k moins de 8 ne doit pas être pris. Tout d'abord, prenez le maximum - 16, puis essayez d'autres valeurs.
4. Créez une
table d'alias :
stats.make_alias_table();
5. On encode
depuis la fin , puis on décode dans l'ordre normal.
RansState rans;
En outre, l'exemple par référence décode les données compressées à l'aide de statistiques prédéfinies. Dans la vraie vie, pour le décodage, vous devez enregistrer un tableau de fréquences (statistiques) avec des données compressées. Dans le cas le plus simple, vous devrez y dépenser N * k bits.
Comme promis ci-dessus, regardons les résultats de compression pour différentes valeurs de k (dans le code, c'est
prob_bits ), en tenant compte de l'augmentation de taille due à l'enregistrement de la table des fréquences:
(
Taille originale du fichier book1: 768771)
k = 16: 435059 + 512 = 435571 octets
k =
15 : 435078 + 480 =
435558 octets
k = 14: 435113 + 448 = 435561 octets
k = 13: 435239 + 416 = 435655 octets
k = 12: 435603 + 384 = 435987 octets
k = 11: 436530 + 352 = 436882 octets
k = 10: 440895 + 320 = 441215 octets
k = 9: 453418 + 288 = 453706 octets
k = 8: 473126 + 256 = 473382 octets
Vous pouvez voir que plus k est élevé, meilleure est la compression. Mais à un certain point (à k = 16), les frais généraux de la table de fréquences commencent à l'emporter sur les avantages d'une précision accrue. Si vous compressez un fichier plus petit, cet effet apparaîtra sur un k plus petit.
Vous devez également dire quelques mots sur l'astuce appelée "rANS entrelacés", qui est également implémentée
dans cet exemple . L'idée est qu'en utilisant alternativement deux variables d'état indépendantes, on utilise mieux le parallélisme du processeur. En conséquence, le décodage est encore plus rapide.
En conclusion, je tiens à noter que la méthode de compression de fichier sélectionnée est trop simple. Il ne prend pas en compte les caractéristiques des données, c'est pourquoi la compression est loin d'être optimale. Si vous regardez attentivement l'entrée, vous pouvez constater que certaines
combinaisons de lettres sont plus courantes que d'autres et que certaines ne se produisent pas du tout. En utilisant ce fait, la compression peut être considérablement améliorée. Mais c'est un sujet pour un article séparé.
Postface
Pourquoi écrire votre propre archiveur alors qu'il existe de nombreux utilitaires éprouvés? La réponse est assez simple: les archiveurs adaptés à un format spécifique se compressent beaucoup mieux.
Lors du développement de jeux sur
Playrix , nous nous appuyons souvent sur la nécessité de réduire la taille de la build. Les jeux évoluent constamment, la quantité de contenu augmente et l'espace est limité.
Une fois de plus
, en regardant avec
envie les ressources, nous avons réalisé que certains fichiers peuvent être compressés beaucoup mieux que zip, compte tenu de leur structure. Au cours des expériences, nous avons réussi à réduire considérablement la taille de notre propre format d'animation, il y a aussi quelques changements dans la compression des fichiers graphiques.
Lors du développement d'algorithmes de compression, un codeur entropique universel, tel que rANS ou FSE, est un outil indispensable. Il prend complètement la tâche d'écrire des caractères avec le moins de bits, permettant au développeur de se concentrer sur les principaux détails de l'algorithme. Et cela fonctionne aussi très rapidement à la fois en encodage et en décodage.
J'espère que cet article vous aidera à vous familiariser avec rANS et à l'utiliser dans vos projets.
Les références
Vous pouvez voir ici des exemples de mise en œuvre de rANS (avec différentes options d'optimisation):
Fabian Giesen:
github.com/rygorous/ryg_ransVous pouvez lire des détails intéressants et des détails sur le blog de Fabian (en anglais):
→
notes RANS→
rANS avec des distributions de probabilités statiques→
RANS en pratique