Compression efficace de données binaires simples

27

J'ai un fichier contenant des nombres binaires ordonnés de à 2 n - 1 :02n1

0000000000
0000000001
0000000010
0000000011
0000000100
...
1111111111

7z n'a pas compressé ce fichier très efficacement (pour n = 20, 22 Mo ont été compressés à 300 Ko).

Existe-t-il des algorithmes capables de reconnaître une structure de données très simple et de compresser le fichier sur plusieurs octets? Je veux aussi savoir quel domaine de la CS ou de la théorie de l'information étudie de tels algorithmes intelligents. "AI" serait trop large, veuillez suggérer des mots clés plus concrets.
La notion de symétrie devrait jouer un rôle fondamental dans la compression des données, mais les requêtes de recherche «symétrie dans la compression des données» et «théorie des groupes dans la compression des données» ne retournent étonnamment presque rien de pertinent.

DSblizzard
la source
11
Découvrez la complexité de Kolmogorov, qui est en quelque sorte la compression optimale (jusqu'à une constante additive). Malheureusement, la complexité de Kolmogorov n'est pas calculable ...
Yuval Filmus
12
Pourquoi avez-vous besoin de compresser ces données? Ne pouvez-vous pas simplement le régénérer chaque fois que vous en avez besoin? (Ce qui est étroitement lié à l'approche de la complexité de Kolmogorov mentionnée par @YuvalFilmus: la complexité de Kolmogorov est essentiellement la longueur du programme le plus court qui génère la sortie).
David Richerby
7
J'ai écrit un tel algorithme au lycée, il y a 20 ans. Compte tenu de votre entrée, il aurait compressé à "quelques octets" (environ 3 500 000: 1 dans un scénario optimal). Cependant, les données ressemblent rarement à ceci, il n'est donc pas pratique d'avoir un algorithme comme celui-ci. Les algorithmes de compression généraux doivent traiter des modèles complexes, pas simples. Tout le monde peut écrire un algorithme pour stocker des données linéaires, mais le stockage de données intéressantes est le défi.
phyrfox
3
Comment n = 20 vous donne 22 Mo?
J'obtiens
3
@JiK oh, ok. eh bien ce serait une première notion de compression, ne pas utiliser 8 bits pour représenter un seul bit.
njzk2

Réponses:

27

Cela semble être un cas d'utilisation clair pour la compression delta . Si est connu a priori, cela est trivial: stockez le premier nombre mot pour mot, et pour chaque numéro suivant stockez uniquement la différence avec le précédent. Dans votre cas, cela vous donneran

0
1
1
1
1
...

O(n)O(1)

nNn

Contrairement à la proposition «tout ou rien» de DW, la compression delta avec un encodage de longueur peut en fait donner des taux de compression raisonnables pour certains types de contenu simples du monde réel, comme l'audio basse résolution. (Il convient donc à la compression audio de faible qualité, à très faible latence et à faible puissance.)

à gauche
la source
44

Bien sûr, il existe bien sûr des algorithmes. Voici mon algorithme:

  1. 02n1nn

  2. Sinon, écrivez 1 bit, puis écrivez la compression 7z du fichier.

Ceci est extrêmement efficace pour les fichiers de cette structure particulière.

Le fait est qu'il n'y a pas de repas gratuit dans la compression de données. Vous pourrez peut-être créer un algorithme de compression qui comprime bien un type de fichier, au détriment de la compression d'autres. Mais, si vous savez a priori quelque chose sur la nature des fichiers que vous allez compresser, vous pouvez optimiser votre algorithme pour ce type particulier de fichier.

Le domaine est la "compression des données". Consultez notre balise de et lisez des manuels sur la compression de données.

DW
la source
5
Le travail d'un compresseur est de reconnaître des modèles communs et de les exploiter. Ce n'est pas comme si ce schéma était rare ou obscur. Il est donc naturel de se demander pourquoi il n'est pas exploité. Lui dire qu'il y a un compromis ou lui donner un algorithme qui échoue sur tout sauf que ce modèle est une dérobade totale.
Mehrdad
17
Bien sûr, cela me semble inhabituel. Cela apparaît très rarement dans les données réelles, par rapport aux types de modèles que recherchent les bons compresseurs.
amalloy
17
@Mehrdad Ce n'est pas une échappatoire sournoise: c'est tout le problème . Pour tout modèle X qui est simplement généré et simplement vérifié, il existe un algorithme de compression qui recherche ce modèle et le traite. C'est donc la réponse à toute question du type "Existe-t-il un algorithme de compression qui traite un tel X?" Bien sûr, il y a toujours un algorithme qui recherche des motifs légèrement plus complexes. Et il y en a un qui recherche des motifs légèrement plus complexes que celui-là aussi, à l' infini . Votre objection est mal fondée.
David Richerby
Les commentaires ne sont pas pour une discussion approfondie; cette conversation a été déplacée vers le chat .
Gilles 'SO- arrête d'être méchant'
Une application extrême de ce principe est les liens magnétiques bittorrent où tout fichier ou collection de fichiers de toute taille est simplement représenté (compressé) en 160 bits de données fixes. Il existe bien sûr un risque de collision de hachage.
slebetman
17

Tout ce qui utilise un BWT (transformée de Burrows – Wheeler) devrait être capable de compresser cela assez bien.

Mon test Python rapide:

>>> import gzip
>>> import lzma
>>> import zlib
>>> import bz2
>>> import time
>>> dLen = 16
>>> inputData = '\n'.join('{:0{}b}'.format(x, dLen) for x in range(2**dLen))
>>> inputData[:100]
'0000000000000000\n0000000000000001\n0000000000000010\n0000000000000011\n0000000000000100\n000000000000010'
>>> inputData[-100:]
'111111111111010\n1111111111111011\n1111111111111100\n1111111111111101\n1111111111111110\n1111111111111111'
>>> def bwt(text):
    N = len(text)
    text2 = text * 2
    class K:
        def __init__(self, i):
            self.i = i
        def __lt__(a, b):
            i, j = a.i, b.i
            for k in range(N): # use `range()` in Python 3
                if text2[i+k] < text2[j+k]:
                    return True
                elif text2[i+k] > text2[j+k]:
                    return False
            return False # they're equal

    inorder = sorted(range(N), key=K)
    return "".join(text2[i+N-1] for i in inorder)

>>> class nothing:
    def compress(x):
        return x

>>> class bwt_c:
    def compress(x):
        return bwt(x.decode('latin_1')).encode('latin_1')

>>> for first in ('bwt_c', 'nothing', 'lzma', 'zlib', 'gzip', 'bz2'):
    fTime = -time.process_time()
    fOut = eval(first).compress(inputData)
    fTime += time.process_time()
    print(first, fTime)
    for second in ('nothing', 'lzma', 'zlib', 'gzip', 'bz2'):
        print(first, second, end=' ')
        sTime = -time.process_time()
        sOut = eval(second).compress(fOut)
        sTime += time.process_time()
        print(fTime + sTime, len(sOut))

bwt_c 53.76768319200005
bwt_c nothing 53.767727423000224 1114111
bwt_c lzma 53.83853460699993 2344
bwt_c zlib 53.7767307470001 5930
bwt_c gzip 53.782549449000044 4024
bwt_c bz2 54.15730512699997 237
nothing 6.357100005516259e-05
nothing nothing 0.0001084830000763759 1114111
nothing lzma 0.6671195740000258 27264
nothing zlib 0.05987233699988792 118206
nothing gzip 2.307255977000068 147743
nothing bz2 0.07741139000017938 187906
lzma 0.6767229399999906
lzma nothing 0.6767684639999061 27264
lzma lzma 0.6843232409999018 27324
lzma zlib 0.6774435929999072 27280
lzma gzip 0.6774431810001715 27292
lzma bz2 0.6821310499999527 27741
zlib 0.05984937799985346
zlib nothing 0.05989508399989063 118206
zlib lzma 0.09543156799986718 22800
zlib zlib 0.06264000899977873 24854
zlib gzip 0.0639041649999399 24611
zlib bz2 0.07275534999985211 21283
gzip 2.303239570000187
gzip nothing 2.303286251000145 147743
gzip lzma 2.309592880000082 1312
gzip zlib 2.3042639900002087 2088
gzip gzip 2.304663197000309 1996
gzip bz2 2.344431411000187 1670
bz2 0.07537686600016968
bz2 nothing 0.07542737000017041 187906
bz2 lzma 0.11371452700018381 22940
bz2 zlib 0.0785322910001014 24719
bz2 gzip 0.07945505000020603 24605
bz2 bz2 0.09332576600013454 27138

(Les nombres ici sont 'first_compressor second_compressor time_taken bytes_out')

(BWT tiré d' ici )

Ce n'est pas seulement «quelques octets», mais c'est bien mieux que juste gzip seul. BWT + bz2 descend à 237 octets de 1114111 pour une entrée 16 bits, par exemple.

Hélas, les BWT sont beaucoup trop lents et gourmands en mémoire pour de nombreuses applications. Surtout étant donné qu'il s'agit d'une implémentation naïve en Python - sur ma machine, je manque de RAM avant 2 ** 20.

Avec Pypy, j'ai pu exécuter l'intégralité de l'entrée 2 ** 20, et il la comprime à 2611 octets avec un BWT suivi de bz2. Mais prendre plus de 3 minutes et culminer à plus de 4 Go de RAM utilisés ...

Malheureusement, cette approche est toujours un espace de sortie O (2 ^ n), semble-t-il - au moins à partir de l'ajustement de courbe 1..20.

TLW
la source
Vous pourriez vous en débarrasser evalen faisant: for first in (bwt_c, nothing, lzma, zlib, gzip, bz2):et fOut = first.compress(inputData).
kasperd
@kasperd - comment imprimer les noms dans ce cas? Personnellement, il est plus simple (et moins sujet aux erreurs) de faire une évaluation que d'essayer de garder les noms + références synchronisés.
TLW
5
D'abord bwt puis bz2 compresse cela extrêmement bien. C'est un comportement extrêmement étrange et probablement dû à ce schéma exact. Notez que vous effectuez deux fois le bwt (bz2 est basé sur le BWT), ce qui entraîne généralement une pire compression. Notez également que bwt fonctionne généralement actuellement en 4 times block sizemémoire (par exemple ~ 4 Mo pour cela) et à des vitesses de >10 MB/s(je suis l'auteur d'un tel algorithme de bibliothèque / compression bwt), ce qui est tout à fait utilisable pour de nombreuses applications. Notez que même gzip produit de très bons résultats compressibles. Merci d'avoir partagé je ne suis au courant d'aucune recherche sur l'utilisation de bwt deux fois.
Christoph
3
@Christoph - Je sais que bz2 est basé sur BWT ... J'avais en fait commencé à écrire une réponse à l'effet de `` juste utiliser bz2 '', mais j'ai constaté qu'il ne compressait pas aussi bien que prévu, est allé '' ', et j'ai décidé de voir si mon propre BWT ferait mieux. Seulement, j'avais besoin d'un compresseur pour la sortie, et je suis allé «peut aussi bien essayer différents compresseurs pour voir ce qui se passe».
TLW
1
@Christoph - J'ai jeté un autre regard. 2 bwts de ces données génèrent quelque chose qui se prête très bien au codage RLE. Comme dans, si vous comptez le nombre de paires RLE requises pour les BWT imbriqués 0, 1, 2, ... sur une entrée 16 bits, vous obtenez 622591 1081343 83 ...
TLW
10

L'encodage PNG fait exactement ce que vous voulez. Il fonctionne également sur des données réelles, pas seulement sur des données extrêmement organisées.

En PNG, chaque ligne est codée avec un filtre, dont 4 sont spécifiés. L'un d'eux est "coder ce pixel comme la différence entre sa valeur et la valeur du pixel au-dessus." Après filtrage, les données sont ensuite compressées à l'aide de DEFLATE.

Ce filtrage est un exemple spécifique du Delta Encoding mentionné par leftaroundabout dans sa réponse, sauf qu'au lieu de le suivre avec Run Length Encoding, vous le suivez avec l'algorithme DEFLATE plus puissant. Il atteint le même objectif, seul DEFLATE gérera une plus grande variété d'entrées tout en fournissant les taux de compression souhaitables.

Un autre outil qui est souvent utilisé dans les données scientifiques où le simple filtre + DEFLATE n'est pas aussi efficace que l'encodage RICE. Dans RICE, vous prenez un bloc de valeurs et sortez tous les bits les plus significatifs d'abord, puis tous les seconds bits les plus significatifs, jusqu'aux bits les moins significatifs. Vous compressez ensuite le résultat. Pour vos données qui ne seront pas aussi efficaces que le filtrage de style PNG (car vos données sont parfaites pour le filtrage PNG), mais pour beaucoup de données scientifiques, elles ont tendance à donner de bons résultats. Dans de nombreuses données scientifiques, nous voyons que le bit le plus significatif a tendance à changer lentement, tandis que le moins significatif est presque aléatoire. Cela taquine les données hautement prévisibles des données hautement entropiques.

0000000000       00000  most significant bits
0000000001       00000
0000000010  =>   00000
0000000011       00000
0000000100       00000
                 00000
                 00000
                 00001
                 00110
                 01010 least significant bits
Cort Ammon - Rétablir Monica
la source
5

Tout algorithme pratique recherchant des structures spécifiques serait limité uniquement aux structures codées en dur. Vous pouvez patcher 7z pour reconnaître cette séquence spécifique, mais à quelle fréquence cette structure spécifique va-t-elle se produire dans la vie réelle? Pas assez souvent pour justifier le temps nécessaire pour vérifier les entrées pour cette entrée.

Mis à part les aspects pratiques, on peut concevoir le compresseur parfait comme un algorithme qui tente de construire le programme le plus court qui produit une sortie donnée. Il va sans dire qu’il n’existe aucun moyen pratique de procéder. Même si vous avez essayé une énumération par force brute de tous les programmes possibles et vérifié s'ils produisaient la sortie souhaitée ( pas une idée complètement folle ), vous rencontrerez le problème Halting , ce qui signifie que vous devrez abandonner les essais après un certain nombre des étapes d'exécution, avant de savoir si ce programme ne peut certainement pas produire la sortie souhaitée.

L'arbre de recherche d'une telle approche par force brute croît de façon exponentielle avec la longueur du programme et n'est pas pratique pour tous, sauf pour les programmes les plus simples (quelque chose comme 5-7 instructions).

Roman Starkov
la source
n
1
nnn+1n1
Eh bien, des outils comme Mathematica trouvent des fonctions pour de nombreuses séquences ...
Raphael
3

Les taux de compression dépendent entièrement du décompresseur ciblé. Si le décompresseur ne peut pas décoder les numéros séquentiels de 4 octets de manière plus compacte que 4 octets par numéro, alors vous êtes SOL.

Il y a différentes choses qui permettraient le codage de nombres séquentiels. Par exemple un codage différentiel. Vous prenez n octets à la fois, puis prenez la différence ou le xor des bits, puis compressez le résultat. Cela ajoute 4 options ici pour essayer pour chaque nombre d'octets: identité a'[i] = a[i]; différence a'[i] = a[i-1]-a[i]; différence inverse a'[i] = a[i]-a[i-1]; et le xor a'[i] = a[i]^a[i-1]. Cela signifie ajouter 2 bits pour sélectionner les méthodes et un nombre d'octets pour 3 des 4 options.

Cependant, toutes les données ne sont pas une séquence d'enregistrements de longueur fixe. Le codage différentiel n'a pas de sens pour cela (sauf si le compresseur peut prouver empiriquement qu'il fonctionne pour un peu de données).

monstre à cliquet
la source