Mengapa rasio kompresi menggunakan bzip2 untuk urutan "a" begitu gelisah?

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

Rasio kompresi dimulai pada 37 untuk "a" dan mencapai titik impas pada 39 "a" (rasio kompresi = 1). Grafik dimulai dengan cukup mulus dan tiba-tiba menjadi tegang untuk 98 "a" dan dari sana dengan interval yang semakin kecil.

Terendah lokal dan bagian yang halus tampaknya juga tidak menentu dan acak. Dapatkah seseorang menjelaskan kepada saya mengapa bzip2 menunjukkan perilaku ini dalam contoh ini?

Misalkan algoritma kompresi sederhana yang mewakili proses adengan menyimpan , yaitu beberapa header tetap, string , dan jumlah repetisi n . Ini adalah pengodean run-length . Maka panjang teks dikompresi akan menjadi dekat dengan sebuah + lg n bit untuk beberapa konstanta a . Rasio kompresi yang sesuai adalah + lg ( n $(\text{header}, \mathtt{\text{"a"}}, n)$a$n$$a + \lg n$$a$ . Ini kira-kira bentuk kurva yang terlihat dari kejauhan, jika Anda mengabaikan pasang surut lokal. Secara asimtotik, rasio kompresi adalahΘ(lg(n)p/n)denganp≥1(saya belum berhasil tetapi saya menduga ada faktor lain yang berperan yang membuat ukuran output superlinear pada panjang masukan string).$\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}$

Karena rasio kompresi terlalu dekat dengan rasio terbalik dari panjang untuk pengamatan visual, berikut adalah data untuk panjang kecil dalam implementasi saya (ini mungkin tergantung pada versi perpustakaan bzip2, karena ada beberapa cara untuk mengompres beberapa input ). Kolom pertama menunjukkan jumlah a's, kolom kedua adalah panjang dari output terkompresi.

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 jauh lebih kompleks daripada pengkodean run-length sederhana. Ini bekerja dalam serangkaian langkah, dan langkah pertama adalah langkah penyandian run-length , tetapi dengan batas ukuran tetap. Langkah pertama bekerja sebagai berikut: jika byte diulang setidaknya 4 kali, kemudian ganti byte setelah 4 dengan byte yang menunjukkan jumlah pengulangan byte yang terhapus. Misalnya, aaaaaaaditransformasikan ke aaaa\d{3}(di mana \d{003}karakter dengan nilai byte 3); aaaaditransformasikan ke aaaa\d{0}, dan seterusnya. Karena hanya ada 256 nilai byte yang berbeda, hanya urutan di mana byte diulang hingga 259 kali dapat dikodekan dengan cara ini; jika ada lebih banyak, urutan baru dimulai. Selanjutnya, implementasi referensi berhenti pada hitungan ulangi 252, yang mengkodekan string 256 byte.

$\mathtt{a}^n$$1 \le n \le 3$$4 \le n \le 258$aaaa\d{252}\d{252} adalah jumlah pengulangan, saya belum memeriksa) itu sendiri diulang dan karena itu dikompresi oleh langkah selanjutnya.

aaaa\374aa$n=258$a

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

Analisis saya tentang contoh ini masih jauh dari lengkap. Untuk memahami efek lain, Anda harus mempelajari langkah-langkah lain dari transformasi: Saya kebanyakan berhenti setelah langkah 1 dari 9. Saya harap ini memberi Anda gambaran mengapa rasio kompresi menjadi sedikit berombak dan tidak berubah secara monoton. Jika Anda benar-benar ingin mengetahui setiap detail, saya sarankan mengambil implementasi yang ada dan mengamatinya dengan debugger.

Untuk sebagian besar, variasi menit seperti itu bukan fokus utama ketika merancang algoritma kompresi: dalam banyak skenario umum, seperti algoritma tujuan-umum atau kompresi media, perbedaan beberapa byte tidak relevan. Kompresi mencoba untuk menekan setiap bit di tingkat lokal, dan mencoba untuk rantai transformasi sedemikian rupa untuk mendapatkan yang sering sementara jarang kalah dan kemudian tidak banyak. Meskipun demikian ada beberapa situasi seperti protokol komunikasi tujuan khusus yang dirancang untuk komunikasi bandwidth rendah di mana setiap bit penting. Situasi lain di mana panjang keluaran yang tepat penting adalah ketika teks terkompresi dienkripsi: ketika musuh dapat mengirimkan bagian dari teks untuk dikompresi dan dienkripsi, variasi pada panjang teks sandi dapat mengungkapkan bagian teks terkompresi dan dienkripsi untuk musuh;CRIME mengeksploitasi pada HTTPS .