Utilisation de la base 80 pour compresser des fichiers

Je veux compresser la taille du fichier en créant mon propre système de numérotation qui est un nombre basé sur 80, je veux vraiment savoir si cela est possible? J'ai appris que l'hexadécimal utilise des symboles comme A, B, C, D, E, F pour représenter 10,11,12,13,14,15 - et c'est ce que je veux faire avec mon propre système de numérotation mais à plus grande échelle . Veuillez me corriger si je manque quelque chose.

C'est possible ?

Bien que vous ayez besoin de moins de nombres à 80 que de nombres à 2 (bits) pour encoder le même fichier, la seule façon de stocker ces nombres à 80 sur un ordinateur est de les encoder en bits. Vous ne gagnez donc rien.

En fait, vous perdez de l'espace, car 80 n'est pas une puissance de 2: vous aurez besoin de 7 bits pour chaque nombre basé sur 80, mais dans ces 7 bits, vous pourriez à la place encoder 128 états différents, si vous les utilisiez directement.

Il existe plusieurs façons d'interpréter la question. Je pense que vous demandez peut-être que vous avez une séquence de$n$ lettres dans un alphabet $\Sigma$ où $\left| \Sigma \right| = 80$. Vous souhaitez stocker cela dans le moins de bits possible. Nous supposerons que les lettres de l'alphabet sont uniformément réparties.

La quantité d'espace théorique nécessaire pour stocker ceci est $n \log_2 \left| \Sigma \right|$morceaux. En utilisant le codage arithmétique, vous pouvez le faire en temps linéaire, en utilisant$O(\log n)$bits d'espace intermédiaire. (N'oubliez pas, c'est le logarithme du nombre de symboles, en bits! Si la taille de la séquence tient dans un mot machine, le stockage intermédiaire requis est au maximum un nombre constant de mots machine.)

C'est donc plutôt bien. Mais qu'en est-il si nous voulons un accès aléatoire?

Il s'avère que cela peut être fait. La première technique à le faire n'a été découverte qu'il y a environ quatre ans. Nous pouvons stocker la séquence dans$n \log_2 \left| \Sigma \right|$bits, de sorte que la lecture ou l'écriture d' une entrée$O(1)$temps. Si vous y réfléchissez, c'est un résultat remarquable, car cela signifie qu'un ordinateur qui fonctionne avec n'importe quel radix est, dans un sens, équivalent à un binaire.

Voici l'article: Yevgeniy Dodis, Mihai Pătraşcu et Mikkel Thorup, An Alternative to Arithmetic Coding with Local Decodability , STOC 2010.

Soit dit en passant, rappelez-vous le nom de Mihai Pătraşcu. Il était et est la chose la plus proche que nous ayons d'un Évariste Galois moderne. Il est décédé très jeune, d'une tumeur au cerveau à l'âge de 29 ans. Mais au cours de sa courte carrière d'informaticien, son travail a révolutionné le domaine de l'analyse des algorithmes d'une manière qui prendra des décennies à comprendre pleinement.

Si vous avez un certain nombre (par exemple. 123456789⏨) sous forme de texte , vous pouvez l' écrire dans une autre base (comme 21i3v9 dans la base 36), de sorte que vous compressez il écrit sous forme de texte (de 9 caractères à 6).

Si vous allez plus loin, vous finissez par le stocker en binaire (4 octets¹).

Maintenant, cela fonctionne parce que vous avez commencé avec un ensemble réduit [0-9] et que vous êtes passé à un plus grand [0-9a-z] et que de nombreux bits de données n'étaient pas utilisés dans la représentation initiale.

De même, si nous savons qu'un fichier ne contient que des lettres, nous pouvons facilement le compresser en changeant la base. Cependant, si vous compressez à partir d'un contenu arbitraire, cela ne fonctionnera pas (toujours). Vous pouvez compresser (obtenir des sorties plus petites) pour certains fichiers, mais d'autres deviendront plus grands comme toute méthode de compression sans perte , cela est inévitable.

Cela peut néanmoins être utile, par exemple une méthode qui comprime bien les textes anglais mais qui agrandit les textes chinois peut être assez bonne si vous écrivez beaucoup plus d'anglais que de chinois.

¹ En fait, vous n'avez besoin que de 2²⁷ bits, bien que de nos jours le stockage informatique utilise des multiples de 8 bits (mais peut-être que vous vouliez stocker une série de nombres de 2²⁷ bits? ☺).

Base 80 ?? Pourquoi 80? Cela n'a pas de sens, contrairement à la base 85. C'est assez pratique car vous pouvez représenter 4 octets en utilisant 5 caractères (car 85 ^ 5 = 4 437 053 125, ce qui est légèrement supérieur à 2 ^ 32 = 4 294 967 296)

Voici mon code pour écrire un seul 32 bits word:

for (i=0; i<5; i++)
{
    c = (word % 85) + 37;
    word /= 85;
    fwrite(&c, sizeof(uint8_t), 1, file);
}

et voici pour le relire:

    word = 0;
    for (i=4; i>=0; i--)
        fread(&c[i], sizeof(uint8_t), 1, file);

    for (i=0; i<5; i++)
        word = word*85 + c[i]-37;

Si vous voulez vraiment utiliser la base 80, vous pouvez utiliser la même approche et remplacer les instances de 85 par 80 et vous aurez besoin de 6 caractères pour 4 octets au lieu de 5.

Comment va-t-il compresser quoi que ce soit? Vous vous rendez compte que les fichiers sont écrits en base 256, non? Cela étant dit, si vous zippez un fichier écrit en base 85, il aura à peu près la même taille que le fichier d'origine zippé en base 256, ce qui fait de la base 85 (ou de la base 64) un bon choix si vous souhaitez représenter des données binaires à l'aide de caractères imprimables.

Différentes bases sont utilisées à des fins différentes, bien que comme les autres réponses l'expliquent, vous ne gagnerez rien en termes de compression.

Voir wikipedia pour une explication du codage base64 . La base 64 est souvent utilisée, non pour la compression, mais pour coder des données binaires qui entraîneraient normalement des caractères non imprimables et des codes de contrôle dans un espace de caractères ASCII imprimable. Cela se traduira par une taille de fichier plus grande, mais est utile pour transférer des données binaires qui peuvent être incorporées dans d'autres fichiers ASCII, par exemple à l'intérieur de XML, d'e-mails, de CSS, de pages Web, etc.