Petite évaluation du parsing parfait

Pour une raison inconnue, je me suis remis à coder dernièrement.
Un de mes objectifs, depuis longtemps, était d'investiguer ce qu'on appelle le parsing parfait, ou optimal. En quoi cela consiste-t-il ?

Dans certains compresseurs, et notamment la famille la plus nombreuse (LZ77), il est possible de représenter la même donnée de plusieurs façons différentes. Pour donner un exemple grossier, on pourrait représenter un fichier sous une succession de littéraux, donc sans compression. Le format le permet, mais ce ne serait pas très efficace.


La compression classique consiste simplement à utiliser un codage compresseur dès que c'est possible. Mais il pourrait être préférable de ne pas compresser tout de suite pour bénéficier d'une meilleure compression plus tard. Tout ceci se calcule, et c'est d'ailleurs ce que fait BZ2 pour obtenir une meilleure compression que son ancêtre.
Toutefois, même l'évaluation différée a une limite, et il y a toujours, du moins en théorie, la possibilité de trouver un meilleur codage.

D'où le parsing parfait. Sur le papier, cela permet de trouver le meilleur codage possible. En pratique, ce n'est jamais qu'une implémentation particulière de l'algorithme du plus court chemin. Ça marche donc plutôt bien tant que le codage est statique, mais il faut accepter un prix énorme sur l'occupation mémoire et les temps de calculs.

J'ai donc fait une première implémentation sur la base de LZD, car il a, et de loin, le codage le plus simple. Les premiers résultats sont donc tombés.
Et bien ce n'est pas fameux. Certes, la compression est toujours meilleure, mais de très peu. Sur mon scénario de test standard "petits fichiers" (téléchargeable), LZD normal donne un gain moyen de -31.8%. Avec le parsing optimal, c'est -32.0%. Pas de quoi casser 3 pâtes à un canard, surtout quand on mesure la lenteur et les restrictions mémoires associées.

Donc les résultats ne sont pas extraordinaires.
Pour voir les choses du bon côté, cela permet de souligner que LZD possède déjà un système de parsing évolué relativement efficace. Et peut-être que sur un code plus complexe (par exemple BZ2), les opportunités d'optimisation seraient supérieures.
Ça reste à tester, mais attention, tout ceci prends du temps, alors, si c'est pour peu de perspectives...