Dlaczego współczynnik kompresji przy użyciu bzip2 dla sekwencji „a” jest tak zwariowany?

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()

Stopień kompresji zaczyna się od 37 dla „a”, a osiąga próg rentowności przy 39 „a” s (stopień kompresji = 1). Wykres zaczyna się dość płynnie i nagle zaczyna się denerwować przez 98 sekund, a stamtąd w coraz mniejszych odstępach czasu.

Lokalne minima i gładkie odcinki wydają się również dość zmienne i losowe. Czy ktoś może mi wyjaśnić, dlaczego bzip2 pokazuje to zachowanie w tym przykładzie?

Załóżmy, że prosty algorytm kompresji reprezentuje ciąg aprzez przechowywanie , tj. Jakiś stały nagłówek, ciąg znaków i liczbę powtórzeń n . Jest to kodowanie długości przebiegu . Następnie długość sprężonego tekstu będzie blisko do + LG n bitów dla niektórych stałych a . Odpowiedni współczynnik kompresji wynosiłby a + lg ( n $(\text{header}, \mathtt{\text{"a"}}, n)$a$n$$a + \lg n$$a$ . Jest to z grubsza kształt krzywej widzianej z odległości, jeśli zaniedbujesz lokalne wzloty i upadki. Asymptotycznie współczynnik kompresji wynosiΘ(lg(n)p/n)przyp≥1(jeszcze tego nie opracowałem, ale podejrzewam, że istnieją inne czynniki, które sprawiają, że wielkość wyjściowa jest superliniowa na długości ciąg wejściowy).$\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}$

Ponieważ współczynnik kompresji jest zbyt bliski odwrotnemu współczynnikowi długości do obserwacji wizualnej, oto dane dla mojej małej długości w mojej implementacji (może to zależeć od wersji biblioteki bzip2, ponieważ istnieje wiele sposobów kompresji niektórych danych wejściowych ). Pierwsza kolumna wskazuje liczbę as, druga kolumna jest długością skompresowanego wyjścia.

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 jest znacznie bardziej skomplikowany niż proste kodowanie w czasie wykonywania. Działa w szeregu kroków, a pierwszy krok jest krokiem kodowania długości przebiegu , ale z ustalonym limitem rozmiaru. Pierwszy krok działa w następujący sposób: jeśli bajt jest powtarzany co najmniej 4 razy, następnie zastąp bajty po czwartym bajtem wskazującym liczbę powtórzeń usuniętych bajtów. Na przykład aaaaaaajest przekształcany na aaaa\d{3}(gdzie \d{003}jest znak o wartości bajtu 3); aaaaprzekształca się aaaa\d{0}w i tak dalej. Ponieważ istnieje tylko 256 różnych wartości bajtów, w ten sposób można zakodować tylko te sekwencje, w których bajt jest powtarzany do 259 razy; jeśli jest ich więcej, rozpoczyna się nowa sekwencja. Ponadto implementacja referencyjna zatrzymuje się przy liczbie powtórzeń 252, która koduje ciąg 256 bajtów.

$\mathtt{a}^n$$1 \le n \le 3$$4 \le n \le 258$aaaa\d{252}\d{252} to liczba powtórzeń, których nie zaznaczyłem) jest powtarzany i dlatego jest kompresowany w kolejnych krokach.

aaaa\374aa$n=258$a

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

Moja analiza tego przykładu nie jest wyczerpująca. Aby zrozumieć inne efekty, musiałbyś przestudiować inne etapy transformacji: przeważnie zatrzymałem się po kroku 1 z 9. Mam nadzieję, że daje to wyobrażenie o tym, dlaczego współczynniki kompresji stają się nieco nierówne i nie zmieniają się monotonicznie. Jeśli naprawdę chcesz dowiedzieć się każdego szczegółu, zalecamy wzięcie istniejącej implementacji i obserwowanie jej za pomocą debugera.

W większości przypadków takie drobne zmiany nie są głównym celem przy projektowaniu algorytmu kompresji: w wielu typowych scenariuszach, takich jak algorytmy kompresji ogólnego przeznaczenia lub mediów, różnica kilku bajtów jest nieistotna. Kompresja próbuje wycisnąć wszystko na poziomie lokalnym i próbuje połączyć transformacje w taki sposób, aby zyskiwać często, rzadko tracąc, a potem niewiele. Niemniej jednak zdarzają się sytuacje, takie jak protokoły komunikacyjne specjalnego przeznaczenia zaprojektowane do komunikacji o niskiej przepustowości, gdzie liczy się każdy element. Inna sytuacja, w której ważna jest dokładna długość wyjściowa, ma miejsce, gdy skompresowany tekst jest szyfrowany: gdy przeciwnik może przesłać część tekstu do skompresowania i zaszyfrowania, zmiany długości tekstu zaszyfrowanego mogą ujawnić część skompresowanego i zaszyfrowanego tekstu do przeciwnik; Exploit CRIME na HTTPS .