Comment calculer les paramètres optimaux dans un schéma de codage start-step-stop?

Question

Un code start-step-stop est une technique de compression de données utilisée pour compresser des nombres relativement petits.

Le code fonctionne comme suit: Il a trois paramètres, start, step et stop. Démarrer détermine la quantité de bits utilisée pour calculer les premiers nombres. Step détermine le nombre de bits à ajouter au codage lorsque nous manquons d’arbitres et que nous arrêtons le nombre maximal de bits utilisés pour coder un nombre.

La longueur d'un codage est donc donnée par l = début + étape * i.

Le " i " La valeur d’un code particulier est codée à l’aide de unary. C'est-à-dire un nombre de 1 bits suivi d'un 0 final. Si nous avons atteint stop, nous pouvons supprimer le bit 0 final. Si i est égal à zéro, nous n'écrivons que le bit 0.

Ainsi, un code de démarrage (1, 2, 5) fonctionnerait comme suit:

Valeur 0, codée comme: 0 0
Valeur 1, codée comme: 0 1
Valeur 2, codée comme suit: 10 000
Valeur 9, codée comme: 10 111
Valeur 10, codée sous la forme: 11 00000
Valeur 41, codée comme: 11 11111

Alors, dans le cas d’un fichier contenant plusieurs numéros, comment calculer les codes de démarrage optimaux pour ce fichier? Les paramètres optimaux sont définis comme ceux qui donneront le taux de compression le plus élevé.

Answer 1

Ces " start-step-stop " codes ressemble à une manière différente d’appeler les codes de Huffman . Voir la technique de base pour obtenir un aperçu du pseudo-code permettant de les calculer.

En gros, voici ce que fait l'algorithme:

Avant de commencer le codage de Huffman, vous devez rassembler les statistiques de chaque symbole que vous allez compresser (leur fréquence totale dans le fichier à compresser).

Une fois que vous avez créé un arbre binaire en utilisant ces informations de sorte que les symboles utilisés se trouvent en haut de l’arborescence (et utilisent donc moins de bits), de sorte qu’aucun encodage ne possède un préfixe code . Puisque si un codage a un préfixe commun, il pourrait y avoir une ambiguïté dans la décompression.

À la fin du codage de Huffman, votre valeur de départ sera la profondeur du nœud feuille le moins profond, votre étape sera toujours égale à 1 (logiquement, cela semble logique, pourquoi forcer plus de bits que nécessaire, ajoutez-en un à la fois ,) et votre valeur d’arrêt sera la profondeur du nœud feuille le plus profond.

Si les statistiques de fréquence ne sont pas triées, il faudra O (nlog n), si elles sont triées par fréquence, vous pouvez le faire en O (n).

Les codes Huffman garantissent la meilleure compression moyenne pour ce type d’encodage:

  

Huffman a été capable de concevoir le plus   méthode de compression efficace de cette   type: pas d'autre mapping d'individu   symboles de source à des chaînes uniques de   les bits produiront une moyenne plus petite   taille de sortie lorsque le symbole réel   fréquences d'accord avec ceux utilisés pour   créer le code.

Cela devrait vous aider à mettre en œuvre la solution idéale à votre problème.

Modifier: bien que similaire, ce n'est pas ce que recherchait le PO.

Cet document académique rédigé par le créateur de ces codes décrit une généralisation de codes start-step-stop, codes start-stop. Cependant, l’auteur explique brièvement comment obtenir une étape de démarrage optimale vers la fin de la section 2. Cela implique l’utilisation d’une variable statistique aléatoire ou du financement par force brute comme la meilleure combinaison. Sans aucune connaissance préalable du fichier, l’algorithme est O ((log n) ^ 3).

J'espère que cela vous aidera.

Answer 2

L’approche que j’ai utilisée était une simple solution de force brute. L'algorithme a suivi ces étapes de base:

1. Comptez la fréquence de chaque nombre dans le fichier. Dans la même passe, calculez la quantité totale de nombres dans le fichier et déterminez le plus grand nombre sous la forme maxNumber.

2. Calcule la probabilité de chaque nombre en divisant sa fréquence par le nombre total de nombres dans le fichier.

3. Déterminez "optimalStop". égal à log2 (maxNumber). C’est le nombre idéal de bits à utiliser pour représenter maxNumber comme dans la théorie de l’information de Shannon et donc une estimation raisonnable de la quantité maximale optimale de bits utilisée dans le codage d’un nombre particulier.

4. Pour chaque " début " valeur de 1 à "optimalStop" répétez les étapes 5 à 7:

5. Pour chaque " étape " valeur comprise entre 1 et ("optimalStop" - "début") / 2, répétez l'étape 6 & amp; 7:

6. Calculez le " arrêt " valeur la plus proche de " optimalStop " qui satisfait stop = start + step * i pour un entier i.

7. Calcule le nombre moyen de bits qui seraient utilisés par ce codage. Ceci peut être calculé en multipliant la probabilité de chaque nombre par sa longueur en bits dans le codage donné.

8. Choisissez le codage avec le nombre moyen de bits le plus bas.