Score de Weissmann
Le score de Weissman est une métrique utilisée pour évaluer les performances des applications de compression sans perte. Il a été développé par Tsachy Weissman, professeur à l'Université de Stanford, en collaboration avec Vinith Misra, étudiant diplômé, à la demande des producteurs de la série télévisée Silicon Valley de HBO. Cette série télévisée met en scène une start-up technologique fictive travaillant sur un algorithme de compression de données[1],[2],[3],[4]. Le score de Weissman permet de comparer le temps nécessaire et le taux de compression des applications mesurées, avec ceux d'une norme de facto en fonction du type de données traitées.
La formule se présente comme suit, où :
- r représente le taux de compression ;
- T est le temps requis pour la compression ;
- Les paramètres surlignés sont les mêmes métriques que ceux d'un compresseur standard et alpha est une constante d'échelle[1].
Le score de Weissman a été utilisé par Daniel Reiter Horn et Mehant Baid de Dropbox pour analyser le véritable travail en matière de compression sans perte. Selon les auteurs, ce score « met l'accent sur la vitesse de compression par rapport au taux de compression dans la plupart des cas »[5].
Exemple
modifierCet exemple illustre l'application du score de Weissman aux données du Prix Hutter[6], en utilisant le paq8f comme norme standard et en fixant la constante d'échelle à 1.
Application | Ratio de compression | Temps de compression [min] | Score de Weissmann |
---|---|---|---|
paq8f | 5.467600 | 300 | 1.000000 |
raq8g | 5.514990 | 420 | 0,720477 |
paq8hkcc | 5.682593 | 300 | 1.039321 |
paq8hp1 | 5.692566 | 300 | 1.041145 |
paq8hp2 | 5.750279 | 300 | 1.051701 |
paq8hp3 | 5.800033 | 300 | 1.060801 |
paq8hp4 | 5.868829 | 300 | 1.073826 |
paq8hp5 | 5.917719 | 300 | 1.082325 |
paq8hp6 | 5.976643 | 300 | 1.093102 |
paq8hp12 | 6.104276 | 540 | 0,620247 |
décomp8 | 6.261574 | 540 | 0,63623 |
décomp8 | 6.276295 | 540 | 0,637726 |
Limites
modifierBien que la valeur du score soit relative aux normes de comparaison, l'unité de mesure des temps a un impact sur le score, (voir exemples 1 et 2). Cette situation découle de la nécessité que l'argument de la fonction logarithmique soit sans dimension. De plus, le multiplicateur ne peut pas avoir une valeur numérique inférieure ou égale à 1, car le logarithme de 1 est égal à 0 (comme illustré dans les exemples 3 et 4) et le logarithme de toute valeur inférieure à 1 est négatif (exemples 5 et 6) ; il en résulterait des scores de 0 (même avec des changements), indéfinis ou négatifs (même s'ils sont meilleurs que positif).
Exemples
modifier# | Compresseur standard | Compresseur noté | Score de Weissmann | Observations | ||||
---|---|---|---|---|---|---|---|---|
Ratio de compression | Temps de compression | Logarithme (temps de compression) | Ratio de compression | Temps de compression | Logarithme (temps de compression) | |||
1 | 2.1 | 2 minutes | 0,30103 | 3.4 | 3 minutes | 0,477121 | 1×(3,4/2,1)×( 0,30103 / 0,477121 )= 1,021506 | Le changement d'unité ou d'échelle modifie le résultat. |
2 | 2.1 | 2 minutes | 2.079181 | 3.4 | 3 minutes | 2.255273 | 1×(3,4/2,1)×( 2,079181 / 2,255273 )= 1,492632 | |
3 | 2.2 | 1 minute | 0 | 3.3 | 1,5 minutes | 0,176091 | 1×(3,3/2,2)×( 0 /0,176091) = 0 | Si le temps est égal à 1, son logarithme est égal 0 ; le score peut donc être égal à 0 ou à l'infini. |
4 | 2.2 | 0,667 minutes | −0,176091 | 3.3 | 1 minute | 0 | 1×(3,3/2,2)×(−0,176091/ 0 )= infini | |
5 | 1.6 | 0,5 heure | −0,30103 | 2.9 | 1,1 heure | 0,041393 | 1×(2,9/1,6)×( −0,30103 /0,041393)= −13,18138 | Si le temps est inférieur à 1, son log est négatif ; alors le score peut être négatif. |
6 | 1.6 | 1,1 heure | 0,041393 | 1.6 | 0,9 heure | −0,045757 | 1×(1,6/1,6)×(0,041393/ −0,045757 )= −0,904627 |
Voir également
modifierRéférences
modifier- (en) « A Fictional Compression Metric Moves Into the Real World - IEEE Spectrum », sur spectrum.ieee.org (consulté le )
- Perry, « A Made-For-TV Compression Algorithm », (consulté le )
- Sandberg, « HBO's 'Silicon Valley' Tech Advisor on Realism, Possible Elon Musk Cameo », The Hollywood Reporter, (consulté le )
- Jurgensen et Rusli, « There's a New Geek in Town: HBO's 'Silicon Valley' », The Wall Street Journal, (consulté le )
- (en) « Lossless compression with Brotli in Rust for a bit of Pied Piper on the backend », Dropbox Tech Blog (consulté le )
- Hutter, « Contestants », (consulté le )