Journal Hashzip

Posté par allcolor (site web personnel) le 14 juillet 2003 à 21:28.

Étiquettes : aucune

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 Jerome Herman le 14 juillet 2003 à 22:02. É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 allcolor (site web personnel) le 14 juillet 2003 à 22:12. É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 free2.org le 14 juillet 2003 à 22:54. É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 jiceb le 15 juillet 2003 à 00:20. É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: meilleur algo de compression
        
        Posté par allcolor (site web personnel) le 15 juillet 2003 à 00:34. Évalué à 1.
        
        Y a ça qui semble faire ce que je parlais plus haut...
        
        http://citeseer.nj.nec.com/arnavut97block.html(...)
- [^] # Re: Hashzip
  
  Posté par patate le 15 juillet 2003 à 08:56. É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 Lee Nux le 15 juillet 2003 à 09:09. É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 Larry Cow le 15 juillet 2003 à 15:44. É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 Edouard Gomez (site web personnel) le 14 juillet 2003 à 22:42. É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 allcolor (site web personnel) le 14 juillet 2003 à 22:46. É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 Jerome Herman le 14 juillet 2003 à 22:53. É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 allcolor (site web personnel) le 14 juillet 2003 à 23:00. É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 free2.org le 14 juillet 2003 à 23:08. É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 Jerome Herman le 14 juillet 2003 à 23:10. Évalué à 1.
        
        Ah oui tres juste, ou avais-je la tete....
        
        Kha
    - [^] # Re: Hashzip
      
      Posté par nojhan (site web personnel, Mastodon) le 15 juillet 2003 à 00:29. É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 Laurent Mouillart le 15 juillet 2003 à 00:37. É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.
        
        [^] # À propos de révolution ...
        
        Posté par Dugland Bob le 15 juillet 2003 à 01:02. Évalué à 1.
        
        ... le Stephen Wolfram il est passé à la trappe je crois
# Re: Hashzip

Posté par Lee Nux le 15 juillet 2003 à 08:43. É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 à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.