Faut dire que je m'étais déjà pris la tête avec quand il nous avait certifié que la compression sans-perte n'existait pas.
Peut-être qu'il voulait dire qu'il n'existe pas d'algorithme de compression sans perte qui fasse effectivement une réduction de taille stricte quel que soit l'input?
Parce que ça ça se démontre : considère tous les inputs possibles de taille n ou moins. Si un tel algo existait, ça impliquerait une bijection d'un ensemble de cardinal 2n dans un ensemble de cardinal 2n-1, ce qui n'est pas possible.
Donc tu ne peux pas avoir un algorithme lossless qui arrive à effectivement compresser tous les inputs.
Après on peut par contre faire des algos lossless qui pour tout input de longueur au plus n, te fournissent un input de longeur au plus n+k pour k>0 donné à l'avance, et donc cet algo compressera effectivement quasiment tous les input.
[^] # Re: «Une fois, j'en ai même attrapé un gros comme ça !»
Posté par Shuba . En réponse au journal Comment les gens perçoivent la gratuité dans l'informatique ?. Évalué à 5.
Peut-être qu'il voulait dire qu'il n'existe pas d'algorithme de compression sans perte qui fasse effectivement une réduction de taille stricte quel que soit l'input?
Parce que ça ça se démontre : considère tous les inputs possibles de taille n ou moins. Si un tel algo existait, ça impliquerait une bijection d'un ensemble de cardinal 2n dans un ensemble de cardinal 2n-1, ce qui n'est pas possible.
Donc tu ne peux pas avoir un algorithme lossless qui arrive à effectivement compresser tous les inputs.
Après on peut par contre faire des algos lossless qui pour tout input de longueur au plus n, te fournissent un input de longeur au plus n+k pour k>0 donné à l'avance, et donc cet algo compressera effectivement quasiment tous les input.