Algorithme Compression

[LLB]

flngr, ça ne marche pas, tu auras des collisions.
Compte combien de valeurs différentes tu peux représenter avec tes deux, trois, quatre... hashs. Compte combien de valeurs différentes on peut former avec 100 Mo (ou 1 Go ou ce que tu veux). Il y a forcément des millions de fichiers qui mènent aux mêmes hashs. Un hash n'est pas bijectif, ce n'est pas de la compression.

[Graindolium]

un système pour trouver le calcule qui donne le résultat équivalant

un délire du style décimal de PI , ensembles de combinaison ...  comme les image procédural , la compression deviens très complexe quant il s'agit d'optimisation intelligente de l'information ,

si j'ai "ddddd" ça s'explique par une suite de 5 "d" , mais là ont veux aller + loin que de la vectorisation et faire de la procéduralisation intelligente , je sais pas si ont peut démontré que pour n'importe quelle ensemble à n'importe quelle entropie une compression peut être inférieur à la quantité d'information , mais c'est possible ,compliquer j'avoue
faudrait qu'un robot face des expériences sur des suite d'octet, pour trouver des possibilité d'interprétation de l'information

comme ton truc flngr, c'est limite absolut quoi

donc y aurais un petit espoirs pour les rêveurs , genre dvd sur disquette , mais j'ai écrit "un put1 de petit espoirs " hein
et pas pour tout les DVD seulement de rare DVD pourais s'interprété par une réduction très intéligente de l'information comme les DVD avec des démo mais pas ceux avec des films

aller vous faire foutre avec vos compression moi j'dis !! !

[flngr]

http://en.wikipedia.org/wiki/Pigeonhole_principle

[flngr]

Je ne suis pas certain quil y ait tant de probabilités que cela en utilisant plus de 2 hashs.. Mais même en admettant qu'il y ait énormément de collisions (?), il y a une contre mesure simple :

au moment de la compression (qui va du coup nécessiter un super-calculateur qui n'existe pas encore..), à compter le nombre collisions que l'algorithme de décompression brute force rencontrerait avant de tomber sur la bonne séquence de bits. Ensuite on enregistre ce nombre (ex "10000000") a côté du hash (on a plus besoin que d'un seul du coup). Et lors du décodage on a juste à "skipper" pour éviter les faux positifs.

Comme le fichier à compresser à une taille fixe, le nombre de collisions produites entre le début du brute force et la chaîne exacte doit être assez limité. Surtout si on se limite à des fichiers de taille raisonnable (128 bytes ? :p)

Après, peut-on encore appeler cela de la décompression.. Vu le temps et énergie nécessaire à récupérer les données.. S'il faut un cluster de 1000 cartes Tesla (au moins l'algo se parallélise facilement)  pour décompresser un petit texte..

[ponce]

flngr: j'ai entendu dire qu'avec SHA-1 par example, il n'y a pas de collisions connues. On sait qu'elles existent mais on a pas la puissance de calcul pour les trouver. Donc si tu partage un fichier par le réseau et qu'ils ont le même SHA-1, tu peux avoir une certaine confiance dans le fait que ce sont les mêmes données.

Par contre, inverser le hash comme tu dis n'est effectivement pas possible réaliste: c'est une méthode équivalente a trouver des collisions, et vu qu'avec certains hash modernes on y arrive pas...

[ponce]

flngr: admettons que si on veut compresser une séquence de N bits alors tu stockes le hash et, ayant un calculateur quantique très rapide, tu calcule le numéro de cette occurence de hash dans un dénombrement de toutes les séquences de N bits.

Alors tu va stocker H bits + C bits, où H est le nombre de bits du hash et C le nombre de bits de ce numéro d'occurence du hash.
Sauf que quand N tend vers l'infini, C fera (N - H) bits.

Un exemple: ton hash fait 2 bits et tu compresse une séquence de 5 bits. Il y a 2^5 séquences possible, 2^2 hash possibles, donc au mieux chaque hash a en tout 2^(5-2) = 8 séquences associées. Tu stockes 2 bits pour le hash et 3 pour ce numéro de séquence => pas de compression.

[xoofx]

Rien. En fait, je ne suis pas tout à fait d'accord avec les remarques sur Shannon ou sur l'histoire du fichier d'@lx. Le théorème de Shannon parle de la longueur moyenne. On peut donc avoir un algo qui compresse bien certaines choses (et les rend plus petites que l'entropie) et moins bien d'autres choses.
Pour le fichier d'@lx, c'est facile de faire un programme qui compresse bien les fichiers n'ayant pas d'octet en double, et d'avoir donc une taille inférieure à 256 octets pour le fichier. Ou alors, on pourrait chercher à tirer des redondances du fichier (si on ne lit pas les bits 8 par 8, il y a peut-être des motifs à exploiter ?).

Lorsque la variable est random (et même si l'algo de randomness n'est pas ultra-sophistique), tu ne peux pas deviné quel sera le prochain bit ou octet avec précision. A moins comme je l'ai dit de connaitre l'algo de random que j'ai utilise pour construire ce fichier, il n'est pas possible d'avoir un compresseur qui descende en dessous des 256 octets pour ce fichier.

Si on pousse le raisonnement a l'absurde, c'est comme si tu me disais: j'ai une pièce qui fait pile ou face, qui produit donc 2 valeurs, je peux te compresser ces 2 valeurs en 1. Tu vois bien que ce n'est pas possible. C'est le principe du "Pigeonhole".

Au mieux, un compresseur sur ce fichier de 256 octets peut faire 256 octets + 1 bits (je vous laisse deviner comment), c'est la compression maximale que tu peux achever.

In-fine, la compression est affaire de prédiction. Si ce qui arrive n'est absolument pas prédictible, il n'est pas possible de compresser la donnée (et même, en voulant la compresser, on augmente forcement sa taille, d'au minimum 1 bit).

[Ap0]

Qq pourrait mexpliquer basiquement le pigeon hole ? je suis entrain de taffer donc c'est un peu chaud..

[Ap0]

g regarder vite fait.. ^^..

[xoofx]

Qq pourrait mexpliquer basiquement le pigeon hole ? je suis entrain de taffer donc c'est un peu chaud..

Je l'ai expliqué avec l'histoire du 1 bit, mais je vais recommencer:

• Prenons l'alphabet binaire, composé de 2 caractères (0 et 1)
• On se propose d'encoder une chaîne binaire composée de 2 caractères, il y a donc 2^2 possibilités, 4 chaînes possibles => 00, 01, 10, 11
• Supposons que l'on veuille encoder ces 2 bits en 1 bits (la réduction maximum que l'on aimerait atteindre avec le compresseur ultime n'est-ce pas?)
• Maintenant, expliques moi comment encoder 4 chaînes possibles, avec un état qui ne te donne que 2 possibilités (0 ou 1).

tic tac tic tac...

C'est exactement le même principe avec cette histoire de hash proposés plus tôt: Dis moi comment avec une clé de 128 bits (type MD5) l'on pourrait encoder toutes les possibilités offertes par une chaîne de 256 bits? Si tu ne saisis pas la limite théorique de cela, tu ne peux pas comprendre les enjeux et les limites posées par la compression et la théorie de l'information (et donc l'aberration de ton discours originel).

g regarder vite fait.. ^^..

Ap0, tu débarques sur ce forum en proclamant avoir un algo de compression magique pour que 14 messages de ta part plus loin (je rappelle, dans la mesure du possible, ne pas prendre aussi un forum comme un tchat), nous n'en sachions pas plus et que tu découvres par la même occasion quelques fondamentaux de la compression.

Si ce thread ne prend pas plus de consistance, je serais contraint de le déplacer dans la section HS.

[Ap0]

Bin perso je ne vois pas ce que cette histoire de pigeon maurait fait decouvrir, je ne savait pas que qq aurait prit le temps decrire une page entiere pour cela mais bon ^^.. a la base je recherchais des personne qui travaille sur la compression, donc ya eu lhistoire de la chaine de 256 octects, LLB a ensuite remis les choses a leur place (pas mal le message) : comme il le dit un compresseur pourrait marcher sur cette chaine et moin bien sur dautre chaine,..

@lx -> Si tu le souhaite je pourrais poser qq questions ? je ne pense pas etre responsable a part entiere de la tournure des choses etant donné qu'une majorité des personne ici présente croye que je parle de n'importe (c'est bien sa ?).Actuellement je devrais aller faire a manger cela dit.. a tout a lheure avec une question constructive jespere ^^  !

Dailleur avec votre aide on pourrait peut etre developpez de nouvelle formules mathematiques..

[MsK`]

Je sais pas si ça vous fait le même effet à vous, mais moi j'ai l'impression d'avoir retrouvé luc2

Je pensais au fils caché de bartoshe et graindo.

[ponce]

Bon Ap0, déjà bienvenue sur ce forum
L'accueil que tu as eu est chahuté mais c'est normal, c'est un peu le même que tu aurait eu en venant avec des idées sur l'énergie perpétuelle.
@lx a pris le temps de te donner de bons conseils, j'espère que tu les recevra comme un cadeau et pas comme une attaque visant à te décrédibiliser, ce qui n'est pas du tout l'objet du thread.

[flure]

J'ai failli dire un truc sur la crédibilité mais j'ai décidé de compresser ce message pour rester dans le sujet

[flngr]

Ce message est compressé