Théorie: algorithme de compression qui rend certains fichiers plus petits mais pas plus?

Question

Je suis tombé sur cette question;

"Un algorithme de compression sans perte prétend garantir de faire des fichiers plus petits et pas de fichiers plus grand.
Est-ce;

  

a) Impossible

     

b) possible, mais peut fonctionner pour une durée indéterminée,

     

c) Possibilité pour le facteur de compression de 2 ou moins,

     

d) possible pour tout facteur de compression? "

Je suis penchée vers (a), mais n'a pas pu donner une explication solide pourquoi. (Je vais énumérer les pensées d'un ami et je suis venu avec une réponse possible)

Answer 1

Par le principe pigeon trous, d'une chaîne de 10 bits vous avez 1024 entrées possibles et doivent mapper à 9 bits ou moins, donc il y a <1024 sorties.

garantit soit l'algorithme a des collisions (compression avec perte) ou à un moment donné choisit de retourner l'entrée non modifiée en tant que sortie.

Dans ce dernier cas, vous ne pouvez pas déterminer comment décompressez une chaîne arbitraire de bits. (Il pourrait être une entrée non modifié, ou une sortie compressée à partir d'une chaîne de bits plus grand).

-> Impossible.

Answer 2

Juste une petite précision du poste de RJFalconer ...

Vous suffit d'avoir certains les fichiers deviennent plus petits, de sorte que l'affirmation selon laquelle une chaîne de 10 bits doit mapper 9 bits ou moins ne sont pas tout à fait raison. En particulier, si quelqu'un a proposé un tel mécanisme de compression, il peut carte toutes les chaînes de 10 bits ou moins à la même sortie (à savoir une transformation d'identité).

Cependant, on nous dit qu'il ya au moins un fichier qui ne devient plus petit. Sans perte de généralité, considérer que commencer par x bits et finissent sous forme de bits y, où y est strictement inférieur à x.

Considérons maintenant le domaine des "fichiers avec des bits y ou moins", qui a 2 ^{y + 1} -1 chaînes de bits (y compris celui vide). Pour aucun de ceux pour résultat dans un fichier plus grand, chacun doit mapper une chaîne de bits dans le même domaine, à savoir 2 ^{y + 1} -1 fichiers compressés. Cependant, on sait déjà que la chaîne initiale de longueur x bits comprime l'une de ces valeurs. - ne laissant que 2 -2 valeurs possibles ^{de A + 1}

cette point le principe du trou de pigeon vient à - vous pouvez clairement pas la carte 2 ^{y + 1} -1 entrées à 2 ^{y + 1} -2 sorties sans répéter un signal de sortie, ce qui porte atteinte à la réversibilité de compression.

Answer 3

a) impossible

Si vous avez un fichier qui ne peut pas être compressé plus, vous devez encore ajouter les informations si elle a été compressé ou non, de sorte que dans ce cas, le fichier devrait croître.

Answer 4

Je sais que je suis un peu en retard, mais je trouve cela via Google et quelqu'un d'autre pourrait faire la même chose, donc je vais poster ma réponse: la solution évidente est a) impossible, ainsi fait par Jon Skeet (et btw il y a beaucoup de preuves partout sur l'internet). Je ne conteste pas l'impossibilité de compresser les données au hasard, juste pour être clair dès le début; Je compris la théorie qui pose derrière elle, et -si vous demandez moi- je fais confiance le calcul. : D

Mais, si nous sommes autorisés à penser latéralement , nous pourrions certainement tirer profit de la fait que la question ne soit pas bien définie, ce qui signifie qu'elle ne donne pas une définition stricte de « algorithme de compression » et des propriétés qu'il devrait avoir (mais de réduire certains fichiers sans extension quelqu'un d'autre) .

En outre, il ne met pas que ce soit la condition sur les fichiers à compresser, la seule chose qu'il est intéressé est « pour faire des fichiers plus petits et pas de fichiers plus » .

Cela dit, nous avons maintenant au moins deux façons de montrer que, en fait, il existe un tel algorithme:

1. Nous pouvons exploiter le nom du fichier pour stocker une partie des informations du fichier (ou même le fichier entier, si le système de fichiers permet, réduisant ainsi tous les fichiers à 0 bit). Trivialement, on pourrait tout simplement décider de laisser chaque fichier intact mais, ce qui réduit à 0 bit et le renommer avec un nom prédéfini. Je suis d'accord que cela pourrait être considéré comme la tricherie, mais là encore, il n'y a aucune restriction à la question initiale et cet algorithme permettrait d'atteindre efficacement l'objectif (tant que personne ne renomme le fichier, c'est pourquoi ce serait un choix de conception très pauvres en plus étant inutile).

2. Nous pouvons limiter le nombre de fichiers à compresser, par exemple, à ceux au moins bits X longue. Encore une fois, une solution triviale serait de laisser chaque fichier intact mais que nous pouvons réduire ce qui en fait correspondre à un fichier plus petit que les bits de X. Maintenant on ont un algorithme qui, citant mot pour mot, fait des fichiers plus petits et pas des fichiers de plus; cependant, il effectue une restriction à toutes ses entrées possibles (à savoir qu'il ne peut pas traiter tous les fichiers).

Pour ceux qui soutiennent que ce ne serait pas une utilité pratique, je dis que je suis d'accord avec vous ... mais bon, c'est la théorie, ce qui était juste une dissertation théorique. ;)

Il est évident que, si je devais faire un test et faire face à cette question, je mettrais un X gras sur le a), puis juste aller sans trop réfléchir à ce sujet.

Néanmoins, il est parfaitement possible de montrer que, puisque le langage naturel est intrinsèquement ambiguë et la question ne soit pas formellement exprimé, chacun des autres réponses possibles est pas nécessairement mauvais: placer les bonnes conditions et éventuellement préciser plus clairement ce que l'on entend par certains concepts, nous pouvons légalement être en mesure d'atteindre l'objectif de l'une des autres options présentées ci, en faisant une sorte de ruse et de forcer le programme pour obtenir le comportement souhaité.

Answer 5

  

e) possible

... avec certaines restrictions.

Je suis récemment tombé sur Shoco , une bibliothèque de compression de chaîne pour les petites chaînes. Je me suis souvenu de cette question lors de la lecture de cette affirmation:

  

... la propriété la plus remarquable de Shoco est que la taille compressée ne dépassera jamais la taille de votre chaîne d'entrée, à condition qu'il soit ASCII.

     

Si vous êtes sûr que les données d'entrée est ASCII, votre tampon pour ne doit être aussi grande que la chaîne d'entrée

http: //ed-von-schleck.github. io / Shoco / # how-it-worksfr

Answer 6

possible

to make some files smaller and no files larger

si ledit algorithme de compression rend le fichier plus volumineux, ont juste retourner le fichier d'origine.