Pourquoi le taux de compression utilisant bzip2 pour une séquence de «a» est-il si nerveux?

library(ggplot2)

compress <- function(str) {
  length(memCompress(paste(rep("a", str), collapse=""), type="bzip2"))
  / nchar(paste(rep("a", str), collapse=""))
}

cr <- data.frame(i = 1:10000, r = sapply(1:10000, compress))

ggplot(cr[cr$i>=5000 & cr$i<=10000,], aes(x=i, y=r)) + geom_line()

Le taux de compression commence à 37 pour "a" et atteint le seuil de rentabilité à 39 "a" s (taux de compression = 1). Le graphique commence assez lisse et devient brusquement nerveux pendant 98 "a" et à partir de là à des intervalles de plus en plus petits.

Les dépressions locales et les sections lisses semblent également assez erratiques et aléatoires. Quelqu'un peut-il m'expliquer pourquoi bzip2 montre ce comportement dans cet exemple?

a$(\text{header}, \mathtt{\text{"a"}}, n)$a$n$$a + \lg n$$a$$\dfrac{a + \lg(n)}{n}$$\Theta(\lg(n)^p/n)$$p \ge 1$

$\lg n$$n$$a$$n$$a+1$$a+2$$\dfrac{a}{n}$$\dfrac{a+1}{n}$$\dfrac{a+2}{n}$

Étant donné que le taux de compression est trop proche du taux inverse de la longueur pour l'observation visuelle, voici les données pour une petite longueur dans mon implémentation (cela peut dépendre de la version de la bibliothèque bzip2, car il existe plusieurs façons de compresser certaines entrées ). La première colonne indique le nombre de a, la deuxième colonne est la longueur de la sortie compressée.

1–3       37
4–99      39
100–115   37
116–258   39
259–354   45
355       43
356       40
357–370   41
371–498   43
499–513   41
514–609   45
610       43
611       41
613–625   42
626–753   44
754–764   42
765       40
766–767   41
768       42
769–864   45
…

Bzip2 est beaucoup plus complexe qu'un simple encodage de longueur. Il fonctionne en une série d'étapes, et la première étape est une étape d'encodage de longueur d'exécution , mais avec une limite de taille fixe. La première étape fonctionne comme suit: si un octet est répété au moins 4 fois, remplacez les octets après le 4ème par un octet indiquant le nombre de répétitions des octets effacés. Par exemple, aaaaaaaest transformé en aaaa\d{3}(où \d{003}est le caractère avec la valeur d'octet 3); aaaaest transformé en aaaa\d{0}, et ainsi de suite. Puisqu'il n'y a que 256 valeurs d'octets distinctes, seules les séquences où l'octet est répété jusqu'à 259 fois peuvent être codées de cette façon; s'il y en a plus, une nouvelle séquence démarre. En outre, l'implémentation de référence s'arrête à un nombre de répétitions de 252, qui code une chaîne de 256 octets.

$\mathtt{a}^n$$1 \le n \le 3$$4 \le n \le 258$aaaa\d{252}\d{252} est le nombre de répétitions, je n'ai pas vérifié) est lui-même répété et donc compressé par les étapes suivantes.

aaaa\374aa$n=258$a

$n=100$$\mathtt{a}^{101}$aaaa\d{97}aaaaaa$n=101$aA$68 \le n \le 83$

Mon analyse de cet exemple est loin d'être exhaustive. Pour comprendre d'autres effets, il faudrait étudier les autres étapes de la transformation: je me suis surtout arrêté après l'étape 1 de 9. J'espère que cela vous donne une idée des raisons pour lesquelles les taux de compression deviennent un peu saccadés et ne varient pas de façon monotone. Si vous voulez vraiment comprendre chaque détail, je vous recommande de prendre une implémentation existante et de l'observer avec un débogueur.

Pour la plupart, de telles variations infimes ne sont pas l'objectif principal lors de la conception d'un algorithme de compression: dans de nombreux scénarios courants, tels que les algorithmes de compression à usage général ou multimédia, une différence de quelques octets n'est pas pertinente. La compression essaie d'extraire chaque bit au niveau local, et essaie d'enchaîner les transformations de manière à gagner souvent tout en perdant rarement, puis pas beaucoup. Il existe néanmoins des situations telles que des protocoles de communication spéciaux conçus pour une communication à faible bande passante où chaque bit compte. Une autre situation où la longueur de sortie exacte est importante est lorsque le texte compressé est chiffré: lorsqu'un adversaire peut soumettre une partie du texte à compresser et chiffrer, les variations de la longueur du texte chiffré peuvent révéler la partie du texte compressé et chiffré à l'adversaire; Exploit CRIME sur HTTPS .