Author Topic: Algorithme Compression  (Read 36553 times)

0 Members and 1 Guest are viewing this topic.

Offline Ap0

  • Base
    • View Profile
  • Ville: Perpignan
Algorithme Compression
« on: 27 August 2012 à 03:15:20 »
Bonjour, Bonsoir..
Voici quelque temps que je travail sur un algorithme de compression : il serait possible de compresser le contenu d'un DVD sur une disquette cela sans perte de qualité mais prendrais plusieurs années. Je souhaiterais donc savoir si qq a deja travailler sur la compression par ici ?? ^^
Merci
Ap0

Offline xoofx

  • Base
    • Pouet.net
    • View Profile
    • xoofx
  • Ancienneté: 1989
  • Groupe: FRequency
  • Rôle: code (+musique), web
  • Ville: Grenoble
Re : Algorithme Compression
« Reply #1 on: 27 August 2012 à 03:54:26 »
Voici quelque temps que je travail sur un algorithme de compression : il serait possible de compresser le contenu d'un DVD sur une disquette cela sans perte de qualité mais prendrais plusieurs années. Je souhaiterais donc savoir si qq a deja travailler sur la compression par ici ?? ^^
ahah, c'est une blague, hein, dis? Tu sais que tu es entrain de bosser sur un truc qui ne mène nulle part hm? Fais attention hein, une vie entière ne te suffira pas pour trouver un tel algorithme hein, tu es vraiment prêt a faire un tel sacrifice?  ::)

Offline Graindolium

  • Base
    • View Profile
    • Graindo_page
  • Ancienneté: 2009
  • Groupe: Adinpsz
  • Rôle: code, musique, gfx, ...
  • Ville: in Guyane
Re : Algorithme Compression
« Reply #2 on: 27 August 2012 à 05:21:26 »
ah justement j'avais eu l'inspiration d'un algorithme purement mathématique quant j'étais ado , qui aurais compresser des donnés pour les réduire énormément, mais j'ai dû me rendre compte que numériquement la quantité d'information qui défffinise les données ont une limite ,

ont ne peut pas compresser un fichier de 700Mo en 1Mo , enfin ça dépend du fichier bien sûr , mais pour un film qui est déjà compresser en vérité dans sont format image vidéo et son, donc qu'il y a déjà eu un travail de réduction de l'information ,

ton truc ça serait comme dire que le génome humain pourrais être réduit à une 10ène de petit brin d'ADN , se qui est théoriquement inconcevable , ou comme si un bits pourrais défffinir 1000 bits, alors que les possibilités de combinaison de 1000 bits dépasse largement les possibilité de 1 bits :D

même si tu développer une function très sophistiquer qui analyse les bits pour trouver des mécanismes géométrique ou autres , tu aura forcément une limite , quelques soit ton algorithme , qu'il soit itératif ou je sais pas quoi, tu peut pas défffinir un random de donné énorme avec 10 valeur de rien du tout

j'avais conclu que mon idée d'algorithme itératif au bou d'un certain temps tendrais en l'infini à obtenir la réduction d'information minimal théoriquement possible, ce qui est cool mais si c'est pour que compresser et décompresser prenne trop de temps , et que en + j'avais pas réfléchit à comment le coder ,

mais ça reste intéressant , de toute façon tu t'en rendra bien compte par toi même !
et si tu fait ça pour relancer le commerce des disquettes ça sert à rien bientôt les serveurs serons archiver en ADN synthétiser se qui prend rien comme place, :) pourquoi se cassé les noix à compresser , alors que + ça vas + ont à de la place  , à moins que ta trouver un algorithme métaphysique fabuleux, tu passe des donnés dans les mondes parallèle ? attention à force de foutre de la merde cher eux ça vas leur donné des idées et ont vas se retrouver dans la matrice avec des caractères de partout :$

ou alors tu utilise de la transcendance, tu arrive à faire une détection des possibilités dans les décimales de PI et ta plus cas défffinir ton fichier par la position et la longueur de chaine dans Pi qui sont égale à ton fichier :P lol tout les conneries d'algo fractaliste sont trop fantastique en théorie
et même si c'était le cas le nombre obtenu serais probablement énorme et incalculable, c'est simple si tu prend par exemple un morceau tout les 10 bits et que tu interprète chaque suite de 10 bits comme un index dans un tableau de permutation de combinaison générable procéduralement avec un algo qui retrouve la chaine juste à partir d'un nombre , enfaite ça vas encore foiré par ce que les nombres indexeur obtenu serons aussi gros que les chaines , ont est baisez quoi que l'on face !! !

par contre un truc intéressant et sympa ça serai de bosser sur un algo d'encryptage de donné verrouiller par un key passe de cryptage O_O , bien sûr ça existe déjà mais se faire sont propre cryptage secret ça ça serait le kiff , j'ai long temps fantasmé sur ça mais jamais eu le time dis coder , un jour peut-être ::) et y a pleins d'idée que je laisse séché dans mon grenier
« Last Edit: 27 August 2012 à 06:42:43 by Graindolium »

Offline xoofx

  • Base
    • Pouet.net
    • View Profile
    • xoofx
  • Ancienneté: 1989
  • Groupe: FRequency
  • Rôle: code (+musique), web
  • Ville: Grenoble
Re : Algorithme Compression
« Reply #3 on: 27 August 2012 à 07:21:06 »
Voici quelque temps que je travail sur un algorithme de compression
Tiens, puisque on ne peut pas attendre des millions d’années que tu compresses un DVD, voici juste 256 octets a compresser. Tu vas pouvoir tout de suite réaliser l'aberration de ton objectif.

Offline flngr

  • Base
    • View Profile
  • Ancienneté: -1
  • Groupe: adinpsz
  • Rôle: unfinished intros champion
  • Ville: Paris
Re : Algorithme Compression
« Reply #4 on: 27 August 2012 à 09:47:30 »
j'ai du mal à imaginer un film tenant sur un disquette :)

par contre oui tu peux faire de la compression destructive :D

Offline wullon

  • Base
    • Pouet.net
    • Coup de coeur
    • Slengpung
    • View Profile
    • wullon homepage
  • Ancienneté: 2006
  • Groupe: Adinpsz
  • Rôle: orga/zik/design
  • Ville: Paris
Re : Algorithme Compression
« Reply #5 on: 27 August 2012 à 13:11:30 »
C'est vrai que c'est assez fascinant cette idée que Pi contienne toutes les chaînes possibles.

Somehow related, à l'ère du cloud, les sociétés comme Dropbox utilisent la déduplication.

Offline TarMil

  • Base
    • Pouet.net
    • View Profile
    • Greek Sugar Cake
  • Ancienneté: 2006
  • Groupe: Ctrl-Alt-Test
  • Rôle: Code
  • Ville: Villejuif
Re : Algorithme Compression
« Reply #6 on: 27 August 2012 à 13:18:04 »
Ca me rappelle le mec qui avait publié un logiciel qui compressait n'importe quel fichier en 1 octet. Evidemment, le décompresseur n'était pas fourni. :)
- De l'eau ?
- J'ai la gorge sèche, pas les pieds sales.

ponce

  • Guest
Re : Algorithme Compression
« Reply #7 on: 27 August 2012 à 13:34:59 »
Si c'est de la compression destructice de vidéo, alors oui on peut peut-être encoder un DVD sur une disquette (et ça sera très moche).
Si c'est de la compression sans perte, il y a une limite dure et prouvée théoriquement qu'on ne peux pas dépasser.

Offline MsK`

  • Base
    • Pouet.net
    • View Profile
  • Rôle: Code
  • Ville: Paris/RP

Offline Ap0

  • Base
    • View Profile
  • Ville: Perpignan
Re : Algorithme Compression
« Reply #9 on: 27 August 2012 à 16:19:54 »
Bonjour,
Personne n'a donc travailler sur la compression donc ?

Graindolium-> Merci pour la reponse construction.La méthode n'est pas destructrice, mais il ne sagit pas de compresser 1000 bits sous 1 bit n'exegerons rien ;).
Pour ce qui est de la methode de crypto que tu recherche j'ai une methode qui pourrait s'apparenter peut etre a de la cryptographie quantic : la methode de cryptographie dependrais donc des données qui la compose, en outre chaque fichier genererais donc une sorte d'algorithme propre a lui meme.

MsK`-> En effect tu peux rester sur du shannon si tu le souhaite ^^, je t'avouerais ne pas m'attarder sur cela..

ponce -> Si la limité est prouver a travers des mathématique dites logique, il pourrait etre interessant de se pencher sur le faite que les mathematique ne sont pas logique (dapres un certain theoreme donc je pourrais essayer de retrouver le nom); dans le cas echeant, et bien..

@lx -> en compression, si je ne fait erreur, + la chaine est grande, meilleur peut etre la compression, BWT permet aussi d'ameliorer la compression dans certains cas ^^

Bon décidement personne ne pourrait m'aider par ici, au moin j'aurais essayer, cela dit diviser la taille d'un DVD par 2 sa serait deja pas mal; mais ne serais ce que de compresser un fichier deja compresser sa pourrait etre le TOP meme si sa ne divise pas par 2 lespace ^^ : jespere donc trouver qq chose dassez rapide..

Offline flngr

  • Base
    • View Profile
  • Ancienneté: -1
  • Groupe: adinpsz
  • Rôle: unfinished intros champion
  • Ville: Paris
Re : Algorithme Compression
« Reply #10 on: 27 August 2012 à 18:21:26 »
la seule vraie méthode efficace pour compresser, c'est d'avoir un algorithme qui re-crée les données.


c'est un peu comme ça qu'une sortie vidéo de démo HD de 700 Mo sur youtube, ne fait que 64k à la base.

donc il faudrait un algo qui refabrique toutes les scènes de ton DIVX avec juste quelques algos et fonctions mathématiques, générateurs de textures, synthés... mais comme tu ne maitrise pas la façon dont ton film a été réalisé (il n'a pas été prévu pour ça, il y a beaucoup trop d'informations, détails, bruit..) autant dire que c'est impossible.


désolé de casser un rêve :p
« Last Edit: 27 August 2012 à 18:25:50 by flngr »

Offline flngr

  • Base
    • View Profile
  • Ancienneté: -1
  • Groupe: adinpsz
  • Rôle: unfinished intros champion
  • Ville: Paris
Re : Algorithme Compression
« Reply #11 on: 27 August 2012 à 18:29:15 »
sinon oui tu peux compresser ton divx, sur une feuille de papier même si tu veux.

si le mec qui veut le lire a Dropbox, tu lui envoi le hash, qui résume l'information de ton divx de manière quasi-unique, et qui est tout petit :D

</troll>

Offline flngr

  • Base
    • View Profile
  • Ancienneté: -1
  • Groupe: adinpsz
  • Rôle: unfinished intros champion
  • Ville: Paris
Re : Algorithme Compression
« Reply #12 on: 27 August 2012 à 18:34:12 »
(j'avais essayé de compresser (j'ai du code C pour ça) en faisant du brute force, c'est-à-dire en cherchant dans des séries de nombres aléatoires les séquences qui correspondent à une chaine, et en sauvegardant juste la seed de la série, l'index du début et de la fin de la séquence "matchant".  ça peut marcher avec des petites chaines de caractère simple, mais bon à part ça c'est juste impraticable en terme de temps de calcul, ça ne "termine" jamais (on peut chercher à l'infini des combinaisons de nombres qui correspondraient..). et faire par paquets, ça compresse pas tellement du coup)

Offline Zavie

Re : Algorithme Compression
« Reply #13 on: 27 August 2012 à 19:10:17 »
@lx -> en compression, si je ne fait erreur, + la chaine est grande, meilleur peut etre la compression, BWT permet aussi d'ameliorer la compression dans certains cas ^^

Pas forcément. Le taux de compression que tu peux espérer atteindre est fonction de l'entropie, et c'est ce qu'énonce Shanon.

Pour ta question de départ, par DVD tu entends film je suppose ? Sachant qu'un film enregistré sur support DVD est déjà lourdement compressé. Compressé par réduction (la résolution pauvre d'un DVD n'a rien à voir avec le grain d'une pellicule 35mm), par perte (on jette à la poubelle les éléments du signal qui sont considérés comme négligeables étant donnés le fonctionnement de la vue (on jette une partie de l'information chromatique, on approxime le signal avec des courbes simples...) et de l'ouïe (on jette les fréquences qui sont moins bien distinguées), et par compression sans perte.

Bref un DVD représente déjà beaucoup moins de données qu'un film brut. Je ne connais pas les ordres de grandeurs, mais après une estimation à la très grosse louche (disons 25 images par seconde avec 4 millions de points et 40 bits de profondeur de couleur, au bout de 2 heures ça va chercher dans les 3To quand même... à faire tenir en 4Go) je pense qu'on parle d'un taux quelque part entre 1/100 et 1/1000. C'est déjà pas mal.

Et tu voudrais faire tenir ça sur 1,44Mo ? Ce n'est juste pas possible, sauf à avoir une icône animée éventuellement.

Tu peux certes faire tenir un DVD sur un espace plus petit, par exemple avec le MPEG4, mais au delà c'est un sujet de recherche active à l'heure actuelle (typiquement par l'industrie de l'image qui voit déjà dans dix ans monsieur tout le monde avoir des TV 4K en stéréo, et que ça pose de gros défis de transmettre des images pareilles avec les moyens de transmission actuels). Si tu pars sur de la donnée brute (autre chose que du film), selon le type de données tu peux avoir des résultats meilleurs (données très redondantes) ou moins bons (données avec une entropie très forte).

Faire tenir un DVD sur une disquette, oui c'est possible : si la quantité d'information que contient le DVD est extrêmement pauvre. On peut certes générer des quantités importantes de données à partir de peu d'information (intro 4k ou 64k, jeu de la vie, ADN...), mais c'est de la génération et non de la compression : ça ne marche que dans un sens.

Il faut que tu te rendes compte que c'est un problème qui a des limites théoriques, qui ont été prouvées, et ce n'est pas en balayant les mathématiques d'un revers de main que tu passeras outre ces limites.

Offline Ap0

  • Base
    • View Profile
  • Ville: Perpignan
Re : Algorithme Compression
« Reply #14 on: 27 August 2012 à 23:14:35 »
N'hesitez pas a continuer a exprimer vos travaux sur la compression.

Zavie -> Je ne souhaite pas partager ton idée qu'il faut que quelqu'un se rende compte de quoi que se soit ^^, je recherche "et puis c'est tout".. Apres si tu souhaite t'arreter a quelque theoreme cela ne regarde que toi et je respect cette position, mais je ne peux accepter le faite que tu souhaite m'imposer ta vision des choses sans connaitre la compression dans sa profondeur, ni meme avoir vu/compris l'algorithme que j'ai developpe.J'espere que tu me comprendrais, meme si j'en doute quand meme un peu.. A bon entendeur, je ne cherche pas a entrer dans un quelquonque conflit..