Journal Hashzip

Posté par  (site Web personnel) .
Étiquettes : aucune
0
14
juil.
2003
Bon voilà, hier en surfant sur freshmeat, je tombe sur ça : http://FreeDaemonConsulting.com/tech/hzip.php

Et donc je m'empresse d'envoyé le mail suivant au concepteur :

>For every 256 bytes of input, 30 bytes of output result, guaranteed. The big
>challenge that lies ahead is to 'verify' this works for all possibilities of
>bits (2^256 verifications).  

Yes that 's what an hashing algorithm is supposed to do... I don't understand
well what you are doing..? It's 100% sure that for every 256 bytes string
you'll get a shrinked result... but that only means that there exists some
collisions... more than one 256 bytes length string shrink into the same 30
bytes length string... because a hashing function is injective unlike a
compression algorithm which is bijective... that also means that a given
compression algorithm can't compress all input... this is the countable
argument.. you associate elements from a bigger set to a smaller set... not
all elements from the bigger set can have a counterpart in the smaller set...
if all elements have a counterpart, that means either there exists
collisions, or the two set are equals (that also means not all input are
shrinked but some of them are bigger).

Regards

Quentin Anciaux


Dont voici la réponse :


Thanks for the input.  You and others have given me an introduction to number
theory and the reasons why my algorithm doesn't work, in theory.  While I
concede that it is a true statement
, I'm wanting to determine where my
algorithm fails, so I can make it work for the general case, and perhaps
expand a data structure or two in the specific cases where it does break
down.
--
Todd Fries .. /////


Free Daemon Consulting, LLC                    Land: 405-748-4596
http://FreeDaemonConsulting.com              Mobile: 405-203-6124
"..in support of free software solutions."

Key fingerprint: 37E7 D3EB 74D0 8D66 A68D  B866 0326 204E 3F42 004A
            Key: http://todd.fries.net/pgp.txt

(last updated 2003/03/13 07:14:10)


J'en ris encore...
  • # Re: Hashzip

    Posté par  . Évalué à 4.

    Tres drole en effet la compression basee sur des tables de hashage. Perso dans le genre truc delirant il y avait le mec qui stockait plus d'info par bit qui m'a aussi fait mourir de rire :
    Son idee c'etait de prendre en compte l'ordre d'aparition des bits :
    00 -> 0
    01 -> 1
    10 -> 2
    11 -> 3
    01 puis 11 -> 4
    10 puis 11 -> 5
    Il etait persuade d'avor revolutionne l'informatique jusqu'a ce que je lui demande comment il comptait stocker l'ordre d'apparition. Ca lui a pris une semaine pour se rendre compte qu'il perdait autant d'info qu'il en gagnait.

    Encore une bonne idee de compression pourtant...

    Kha
    • [^] # Re: Hashzip

      Posté par  (site Web personnel) . Évalué à 1.

      Une bonne idée serait de trouver des fonctions relativement simple qui réordonne de façon réversible les bits d'une string pour que celle-ci passe mieux avec un algorithme classique...

      Mais bon le problème c'est que ces fonctions si elles existent, doivent prendre peut de place par rapport au données compressée...

      Sinon bardaf c'est l'embardée...
      • [^] # meilleur algo de compression

        Posté par  . Évalué à 1.

        je crois que le mieux est d'avoir un algorithme pour chaque type de fichier (texte en francais, texte en anglais, source C, source java, langage machine, musique, voix, video, etc.)
        ainsi chaque algo a son "dictionnaire" et sa "grammaire" spécifique aux fichiers qu'il traite

        sur freshmeat y'a deja des programmes qui testent plein d'algos sur un meme fichier et finalement compressent avec le meilleur

        enfin rappelons qu'il vaut mieux compresser au MAXIMUM avant de crypter, toute grammaire particulière et toute redondance risquent de faciliter la tache du décrypteur indiscret
        • [^] # Re: meilleur algo de compression

          Posté par  . Évalué à 3.

          les codes de huffman permettent de calculer le meilleur code statistique pour une entrée donnée. Autrement dit la longueur moyenne en bit d'un symbole dans le message compressé est égale à l'entier suppérieur à l'entropie de l'entrée (sachant que c'est le minimum de la compression sans perte).

          Les codes de Huffman si on contraint leur longueur perde peut de performance et ont une representation qui reste faible en taille (quelques dizaine de bit par octet different à coder).

          Par contre il sont incapable de faire du codage de flux, il faut lire tout le fichier, faire un peu de stat, un arbre, 2 ou 3 rafinements et enfin la compression.
    • [^] # Re: Hashzip

      Posté par  . Évalué à 3.

      Y'a aussi la methode infaillible de compression infinie, qui permet de reduire la taille des fichiers a zero octet sans perdre d'information, quel que soit le fichier: il suffit de stocker l'information dans le nom du fichier!

      Pour les esprits chagrins qui diront que la taille des noms de fichiers est limitee, il suffit evidemment de decouper en plusieurs parties.

      Faudra penser a breveter ca.
      • [^] # Re: Hashzip

        Posté par  . Évalué à 1.

        Excellente ton idée. Pousse les députés européens pour qu'ils acceptent le brevet logiciel.

        Après à toi la fortune... mais aussi la tête mise-à-prix par IBM, Maxtor et autre Seagate. :-)
      • [^] # Re: Hashzip

        Posté par  . Évalué à 3.

        Sans oublier le compresseur fourni en standard sur tous les Unix: /dev/null. Le jour où on aura réussi à coder le décompresseur adéquat, ca va déchirer :)
  • # Re: Hashzip

    Posté par  (site Web personnel) . Évalué à 4.

    >For every 256 bytes of input, 30 bytes of output result, guaranteed. The big
    >challenge that lies ahead is to 'verify' this works for all possibilities of
    >bits (2^256 verifications).

    Bah c'est simple, cette boite vient d'inventer la compression "à l'infini". Voici la recette:
    - Découper un fichier en blocs de 256 octets.
    - Passer le tout à la moulinette magique de compression i2bp^WFree Daemon Consulting.
    - Egouter ensemble tous les résultats de 30 octets. Réserver au frais.
    - Recommencer à la première étape jusqu'à obtention d'un bouillon compressé de 30 octets au total.

    Pourvu que s'dure !
    • [^] # Re: Hashzip

      Posté par  (site Web personnel) . Évalué à 3.

      Mais le plus fort c'est la façon qu'il propose de tester sha1... essayer toutes les possibilités pour voir si il y a des collisions...

      arf elle est terrible...
      • [^] # Re: Hashzip

        Posté par  . Évalué à 2.

        Ben 256 bits ca fait jamais que 1.158x10^77 et 30 bits ca fait que 1 milliard et des brouettes de possibilites, Donc a raisons d'un milliard d'operation par secondes il ne faut que 3.617x10^67 annees pour verifier. rien de bien alarmant.

        J'espere quand meme pour lui qu'il a commence hier, sinon il risque d'etre un peu juste...

        Kha
        • [^] # Re: Hashzip

          Posté par  (site Web personnel) . Évalué à 1.

          euh...

          c'est des bytes (octets)...

          Mais bon c'est surprenant que ce type nous sorte ça en voyant le background qu'il affiche sur cette page...

          http://todd.fries.net/resume.html(...)
          • [^] # Re: Hashzip

            Posté par  . Évalué à 1.

            comme quoi on peut pas être calé dans tous les domaines...
            merde, si ça trouve ca s'applique à moi aussi :)

            mais bon il aurait pu se documenter avant de mettre ses idées de débutant en première page sur freshmeat
          • [^] # Re: Hashzip

            Posté par  . Évalué à 1.

            Ah oui tres juste, ou avais-je la tete....

            Kha
        • [^] # Re: Hashzip

          Posté par  (site Web personnel) . Évalué à 1.

          Vous êtes mauvaise langue, dès aujourd'hui, avec la sortie de MultiDeskOS, tout cela va devenir possible, un nouveau monde s'offre à nous, où l'espace disque est une illusion et où les OS tournent sous dos...

          Vous êtes des sceptiques, il va falloir désinfecter...
          • [^] # Re: Hashzip

            Posté par  . Évalué à 1.

            Ciel j'avais pas vu qu'on était le 15. Que pensez vous de faire décaler la fête national le 15 juillet ? comme ca, cela coinciderai avec le début de l'ère d'une nouvelle révolution !
            ... Au debut il y eu le néant puis du néant naquis le propriétaire célérat et vil, puis une petite révolution bouta les grands propriétaires hors du pouvoir. Le règne de la liberté et du libre arriva ! Et tout ceci fut irrémédiablement changé pour toujours par le MultiDeskOS.
  • # Re: Hashzip

    Posté par  . Évalué à 4.

    C'est vrai que dans le genre "Eureka, j'ai trouvé le truc révolutionnaire", il est fort... Malheureusement, si cela avait été aussi simple, d'autres l'auraient déjà exploité avant lui.

    Quand à ton explication, elle semble claire. Maintenant, le mec, il a soit aucune notion de mathématiques pour ne pas comprendre les fonctions injectives et bijectives, soit aucune notion de télécoms pour ne pas comprendre les bases du codage de source (et des maths qui vont dessous) et que l'on ne peut pas compresser une source à l'infini... ("Hep les mecs, j'ai compressé toute l'encyclopédie Universalis sur un (1) bit. Ce bit vaut "0". Pour lire l'encyclopédie, il faut mon décompresseur sur 10 CD-ROM. La license pour exploiter mon décompresseur vaut 15'000 €")

    Juste pour finir de rire de cette frite, euh de ce Mr. Fries, cliquez sur le petit logo "HTML 4.01 valid"... Et oh... le W3C dit que le document n'est pas valide... Bon... euh qu'est-ce qui me dit que le validateur du W3C fait son boulot correctement ? Finallement Mr. Fries semble être un cerveau du domaine des TI, il doit certainement avoir un site valide et c'est le moteur du W3C qui est buggué. :-)

    PS: J'adore cliquer sur ces fameuses icones (X)HTML / CSS / ... valide... Que de belles surprises on retrouve toujours. Les auteurs de site web ne doivent pas se rendre compte qu'il ne faut pas rendre une page valide une fois pour qu'elle le soit tout le temps. Il s'agit d'une démarche permanente pour rendre et conserver son contenu valide.

Suivre le flux des commentaires

Note : les commentaires appartiennent à ceux qui les ont postés. Nous n’en sommes pas responsables.