Tenir compte US Patent #5533051:algorithme de compression
Pour ma meilleure compréhension, ce que l'algorithme breveté dit est qu'il peut garantir une sans perte compression d'un bit sur une entrée. Il est clair que c'est totalement impossible (appliquer récursivement l'algorithme pour obtenir une représentation à un bit de n'importe quelle entrée). Est-ce que je comprends mal cet algorithme?
Votre compréhension est correcte. L'algorithme tel que décrit sera bouclé pour toujours pour certaines entrées (puisque la réponse à "est le fichier de sortie à ou au-dessous de la taille requise?" Sera toujours "non"). Voir le comp.compression FAQ pour une discussion approfondie des revendications d'être en mesure de compresser toute entrée et la compression de l'entrée aléatoire.
Le brevet présente trois méthodes de codage, ainsi qu'un algorithme pour sélectionner une compression de taille minimale à partir d'un ensemble de routines de compression. Je suppose que vous parlez de l'algorithme de la feuille 2, qui est destiné à sélectionner le meilleur résultat d'un ensemble de routines.
L'algorithme parcourt trois routines à condition que la "taille requise" soit inférieure à la taille à laquelle il est capable de compresser le texte. S'il ne peut pas compresser en dessous de la taille requise en utilisant l'une des routines, il utilise une "routine pour les données hautement randomisées".
Et il y a le défaut; il vérifie à nouveau l'exigence de taille, puis se réinitialise si la taille est supérieure à la taille requise. Par conséquent, il boucle pour toujours pour certaines entrées. Je suis sûr que la décision finale sur la taille n'est pas censée être là, et que la dernière routine est censée servir de solution de rechange.
Je ne trouve aucune revendication dans le brevet comme celle que vous énoncez, bien qu'il y ait un bogue là-dedans qui fera tourner l'algorithme.
L'auteur de GZip a une courte dissection de ce brevet qui peut vous intéresser: http://gailly.net/05533051.html – Xiaofu