J'ai récemment découvert l'article intéressant suivant qui prétend compresser efficacement les ensembles de données aléatoires de toujours plus de 50%, quels que soient le type et le format des données.
Fondamentalement, il utilise des nombres premiers pour construire de manière unique une représentation de blocs de données de 4 octets qui sont faciles à décompresser étant donné que chaque nombre est un produit unique de nombres premiers. Pour associer ces séquences aux nombres premiers, il utilise un dictionnaire.
Ma question est:
- Est-ce vraiment réalisable comme le suggèrent les auteurs? Selon l'article, leurs résultats sont très efficaces et compressent toujours les données à une taille plus petite. La taille du dictionnaire ne sera-t-elle pas énorme?
- Ne pourrait-il pas être utilisé pour recompresser itérativement les données compressées en utilisant le même algorithme? Il est évident, et il a été démontré, que de telles techniques (où les données compressées sont recompressées autant de fois que possible, réduisant considérablement la taille du fichier) sont impossibles; en effet, il n'y aurait pas de bijection entre l'ensemble de toutes les données aléatoires et les données compressées. Alors, pourquoi cela semble-t-il possible?
- Même si la technique n'est pas encore parfaite, elle peut évidemment être optimisée et fortement améliorée. Pourquoi cela n'est-il pas plus largement connu / étudié? Si en effet ces affirmations et résultats expérimentaux sont vrais, cela ne pourrait-il pas révolutionner l'informatique?
Réponses:
C'est impossible. Vous ne pouvez pas compresser des données aléatoires , vous avez besoin d'une structure pour en profiter. La compression doit être réversible, vous ne pouvez donc pas tout compresser de 50% car il y a beaucoup moins de chaînes de longueur que de longueur n .n / 2 n
Il y a quelques problèmes majeurs avec le document:
Ils utilisent 10 fichiers de test sans aucune indication de leur contenu. Les données sont-elles vraiment aléatoires? Comment ont-ils été générés?
Ils affirment atteindre des taux de compression d' au moins 50%, tandis que leurs données de test montrent qu'ils atteignent au plus 50%.
Quelle? Les nombres premiers sont des nombres premiers quelle que soit la base.
Problème n ° 1 avec la décompression: la factorisation principale est un problème difficile, comment le font-ils efficacement?
Je ne pense pas que ce document soit très bon.
la source
Je vais m'en remettre à Tom van der Zanden qui semble avoir lu l'article et découvert une faiblesse dans la méthode. Bien que je n'ai pas lu le document en détail, en partant du résumé et du tableau des résultats, cela semble être une affirmation largement crédible.
Ce qu'ils prétendent est un taux de compression constant de 50% sur les fichiers texte (pas "tous les fichiers"), qu'ils notent est à peu près le même que LZW et environ 10% pire que le codage Huffman (probablement d'ordre zéro). La compression de fichiers texte de 50% n'est pas difficile à réaliser à l'aide de méthodes raisonnablement simples; c'est une tâche de premier cycle dans de nombreux cours d'informatique.
Je suis d'accord que le document n'est pas très bon en tant que recherche publiée, et je ne pense pas qu'il parle bien des critiques que cela a été accepté. Mis à part les détails manquants évidents qui rendent les résultats impossibles à reproduire (par exemple, quels étaient les fichiers texte), et aucune tentative de les relier au domaine de la compression, il n'y a aucun sens qu'ils comprennent vraiment ce que fait leur algorithme.
Le site Web de la conférence revendique un ratio d'acceptation de 1: 4, ce qui vous fait vous demander ce qu'ils ont rejeté.
la source
Tu demandes:
Oui bien sûr. Même pour leur exemple trié sur le volet ("LE RENARD RAPIDE EN ARGENT SAUTE LE CHIEN LAZY"), ils n'atteignent pas la compression, car le dictionnaire contient chaque sous-chaîne de 4 octets du texte (moins 4 octets pour la seule répétition de " LE ") ... et la version" compressée "du texte doit inclure tout le dictionnaire plus toute cette merde de nombre premier.
Encore une fois, vous semblez avoir une bonne compréhension intuitive de la situation. Vous vous êtes intuitivement rendu compte qu'aucun schéma de compression ne peut jamais être efficace sur toutes les entrées, car s'il l'était, nous pourrions simplement l'appliquer encore et encore pour compresser n'importe quelle entrée vers un seul bit - puis vers le néant!
En d'autres termes: une fois que vous avez compressé tous vos fichiers .wav en .mp3, vous n'obtiendrez aucune amélioration de la taille du fichier en les compressant. Si votre compresseur MP3 a fait son travail, il n'y aura plus de modèle à exploiter pour le compresseur ZIP.
(La même chose s'applique au cryptage: si je prends un fichier de zéros et le crypte selon mon algorithme cryptographique de choix, le fichier résultant a intérêt à ne pas être compressible , ou bien mon algorithme de cryptage fuit "pattern" dans sa sortie!)
Ces affirmations et résultats expérimentaux ne sont pas vrais.
Comme Tom van der Zanden l'a déjà noté, "l'algorithme de compression" de Chakraborty, Kar et Guchait est imparfait en ce que non seulement il n'atteint aucun taux de compression, il est également irréversible (en maths, "non bijectif"): il y a une multitude de textes qui "se compressent" tous dans la même image, car leur algorithme est essentiellement une multiplication et la multiplication est commutative.
Vous devriez vous sentir bien que votre compréhension intuitive de ces concepts vous a conduit à la bonne conclusion instantanément. Et, si vous pouvez gagner du temps, vous devriez avoir pitié des auteurs de l'article qui ont clairement passé beaucoup de temps à réfléchir sur le sujet sans le comprendre du tout.
Le répertoire de fichiers un niveau au-dessus de l'URL que vous avez publié contient 139 «articles» de même qualité, tous apparemment acceptés dans les «Actes de la Conférence internationale sur la recherche émergente en informatique, information, communication et applications». Cela semble être une conférence simulée du type habituel. Le but de ces conférences est de permettre aux universitaires frauduleux de prétendre à une "publication dans une revue", tout en permettant aux organisateurs sans scrupules de gagner une tonne d'argent. (Pour en savoir plus sur les fausses conférences, consultez ce fil reddit ou divers articles StackExchange sur le sujet .) Les conférences factices existent dans tous les domaines. Apprenez simplement à faire confiance à votre instinct et à ne pas croire tout ce que vous lisez dans une "procédure de conférence", et tout ira bien.
la source
L'entropie limite efficacement les performances de la compression sans perte la plus forte possible. Il n'existe donc aucun algorithme capable de compresser les ensembles de données aléatoires de plus de 50%.
la source
Les méthodes de compression, qui sont restaurables, trouvent en général un modèle et le ré-expriment de manière simpliste. Certains sont très intelligents, d'autres très simples. À un moment donné, il n'y a pas de modèle. Le (s) processus a (ont) fait bouillir les données vers le modèle unique le plus simple. Toutes les tentatives de compression à partir de ce point entraînent un ensemble de données plus volumineux ou diluent l'unicité. Dans les schémas de compression des nombres magiques, il y a toujours un défaut, une légère main ou une perte. méfiez-vous de tout processus qui prétend dépasser le dernier WinZip ou RAR.
la source