Kompresi: Algoritma: Coders statistik

Pengantar

Coders statistik adalah tulang punggung dari kompresi. Kami pertama kali memerlukan model sederhana untuk kompresor: 

(RAW) INPUT -> COMPRESSOR -> OUTPUT (TRANSMISI) 

(TRANSMISI) INPUT -> decompressor -> OUTPUT (RAW) 

Ide dasarnya adalah: kompresor menebak apa masukan akan, dan menulis bit yang lebih sedikit untuk output jika menebak dengan benar. Perhatikan bahwa decompressor HARUS mampu membuat menebak sama seperti kompresor, untuk benar decode transmisi, karena transmisi yang berbeda tergantung pada prediksi.

Saat ini, bagaimanapun, kita hanya peduli dengan "coder statistik". Ini adalah sebuah algoritma yang mengkodekan atau decode karakter, dengan jumlah bit sebanding dengan -log2 (probabilitas diprediksi).Perhatikan bahwa mungkin putaran jumlah bit atau menyandikan dengan ekstra - asalkan mereka berusaha untuk mencapai tujuan ini, itu adalah coder statistik.

Misalnya, jika data RAW bisa menjadi salah satu dari empat karakter: a, b, c, atau d, dan coder statistik diceritakan (dengan sisa kompresor) untuk mengharapkan bahwa terjadi 50% dari waktu, b terjadi 25% dari waktu, c terjadi 25% dari waktu, dan d terjadi hampir tidak pernah, maka kita akan ingin kode sebagai berikut:

1 bit untuk (-log2 (0,5) = 1) 
2 bit untuk b & c (-log2 (0,25) = 2)

misalnya: 

a: 0 
b: 10 
c: 11 

catatan bahwa ada banyak kemungkinan lain (yaitu {1,01,00}, {1,00,01}, {0,11,10}) - semua yang penting adalah bahwa panjang kode sebaik mungkin

Anda mungkin berpikir "RAW" IO sebagai coder statistik yang memprediksi setiap simbol dengan probabilitas yang sama. Dengan demikian, ada nilai-nilai 256 untuk byte, dan masing-masing diberikan probabilitas yang sama, p = 1/256, sehingga -log2 (1/256) = 8 bit.

Dalam teks khas (seperti ini) karakter SPACE dan 'e' sangat sering terjadi, sehingga mereka harus ditulis dalam beberapa bit (3) sementara 'q' sering terjadi, sehingga harus ditulis dalam lebih bit (12).

Cara lain untuk melihat tujuan dari coder statistik adalah ini: membayangkan bahwa input hanya memiliki dua simbol A dan B (ini adalah sempurna umum, karena setiap byte dapat diuraikan ke dalam bit-nya). Biarkan p (A) adalah probabilitas aktual A. Karena hanya ada dua simbol, p (A) + p (B) = 1, sehingga p (B) = 1 - p (A). Biarkan L (a) = # bit yang digunakan untuk menulis, dan L (b) = # bit yang digunakan untuk menulis b (dicatat bahwa ini adalah TIDAK bilangan bulat). Dengan demikian, tujuan kami adalah untuk meminimalkan fungsi 

L = L (A) * p (A) + L (B) * p (B) 

p (A) & p (B) diberikan, dan L (A) & L ( B) dibatasi oleh fakta bahwa kode harus decodable (yaitu L (A) = L (B) = 0 adalah tidak valid, tidak adalah L (A) = L (B) = 0,5) 

Hal ini dapat ditunjukkan bahwa nilai-nilai yang meminimalkan L adalah: 

L (A) = -log2 (p (A)) 
L (B) = -log2 (p (B)) = -log2 (1 - p (A)) 

L = -log2 (p ( A)) * p (A) -log2 (1 - p (A)) * (1 - p (A)) 

Jadi L hanya tergantung pada p (A) (atau p (B) jika Anda lebih suka).

Anda mungkin bertanya-tanya: bagaimana L dapat menjadi non-integer? Nah, salah satu jawabannya adalah: "aritmatika encoding", yang akan kita bicarakan nanti. , Jawaban lain yang lebih mudah adalah: "memblokir".

Pemblokiran adalah ketika Anda menggabungkan dua simbol yang berdekatan bersama-sama untuk memungkinkan panjang kode pecahan. Sebagai contoh, mari A dan B menjadi satu-satunya simbol masukan (input biner). Jika coding set adalah: 

AA: 0 
AB: 10 
BA: 110 
BB: 111 

Kemudian, A ditulis dalam (sekitar) 0,7 bit, dan B ditulis dalam sekitar 1,4 bit.

Telah terbukti, bahwa jika N simbol diblokir bersama-sama, inefficieny coding karena ke integer panjang kode dibatasi oleh:

(Ekstra panjang per simbol) <= 1 / N bit

Baik. Ini adalah akhir dari intro untuk coding statistik. Berikut ini kami pergi melalui Shannon-Fano coding, Huffman coding, dan coding kemudian aritmatika.

LAMPIRAN: 
Tujuan dari coding statistik adalah untuk simbol kode dengan mereka Shannon-order0-entropi. Silakan lihat berita saya posting di entropi.

 


 

Coding Algoritma

Ingat contoh saya:

a: 0 
b: 10 
c: 11

Anda mungkin bertanya bagaimana kode tersebut telah tiba di. Sangat mudah untuk melakukan konseptual untuk alfabet kecil, namun bagaimana kita dapat melakukannya untuk alfabet besar? Jelas, kami ingin tujuan umum berulang atau rekursif algoritma.

Proses ini diperlukan untuk semua bilangan bulat-panjang prefix-kode.

Sebuah kode prefix adalah salah satu sehingga tidak ada bagian dari satu kode adalah awalan yang lain. Ini diperlukan untuk decoding sederhana. Sebagai contoh:

a: 0 
b: 01 
c: 10

TIDAK kode awalan bebas. Jika decoder melihat string "0010" tidak akan tahu apakah ini adalah "a, b, a" atau "a, a, c".

Contoh lain dari awalan-kode NON:

a: 0 
b: 01 
c: 11

string "00111" HARUS "a, b, c" Namun, decoder tidak bisa langsung tahu jika dimulai sebagai ", sebuah" atau "a, b" - yaitu satu kode tidak dapat diterjemahkan sampai setelah nanti yang diperiksa. semacam ini decoding harus dihindari.

a: 0 
b: 10 
c: 11

IS awalan-kode. Tidak ada string ambigu. "0010" berarti ", a, b" dan "00111" berarti "a, b, c" dan decoder dapat mengatakan ini segera.

 

Sekarang kita ingin membuat satu awalan-kode ini. Bagaimana kita melakukannya? Kami istirahat proses menjadi dua langkah:

1. Tentukan panjang dari kode. jika Li adalah panjang kode engan Mari Ei = Li - (- log2 (Pi)) di mana Pi adalah probabilitas kode i Ei adalah panjang ekstra ditulis untuk setiap simbol, yaitu panjang yang ditulis yang tidak diperlukan . Kami ingin memilih panjang sehingga dapat meminimalkan jumlah Pi * Ei. Ini harus masuk akal karena Pi adalah angka kejadian i, dan Ei adalah kelebihan panjang, sehingga jumlah Pi * Ei adalah panjang total keluaran yang lebih lama dari yang diperlukan.

2. Buat awalan-kode bagi mereka panjang kode.

 

Langkah 1 dicapai dengan Shannon-Fano coding, atau Huffman coding. Ini dibahas kemudian. Sejauh Langkah 2 yang bersangkutan, panjang ini dapat dihasilkan dengan cara apapun.

 

Kraft Ketimpangan

Ternyata awalan-kode hanya ada untuk kode IF:

K = Sum (i = 0 N) dari 2 ^ (- Li) <= 1

Ini adalah ketimpangan Kraft. Bukti dari pernyataan ini adalah di luar lingkup tulisan ini. Catatan, meskipun, bahwa Li = -log2 (Pi) + Ei

sehingga 2 ^ (- Li) = 2 ^ (- log2 (Pi) - Ei) = 2 ^ (log2 (Pi)) * 2 ^ (- Ei) = Pi / 2 ^ (Ei)

Jadi K = Sum (i = 0 N) dari Pi / 2 ^ (Ei)

Gambar kasus sederhana di mana Ei = E untuk semua i

Jadi K = Sum (i = 0 N) dari Pi / 2 ^ (E) = [Sum (i = 0 N) dari Pi] / 2 ^ E

tapi [Sum (i = 0 N) dari Pi] = 1

Jadi K = 1/2 ^ E

Jadi ketimpangan Kraft mengatakan 02/01 ^ E <= 1 1 = 2 ^ 0

2 ^ (- E) <= 2 ^ (0)

-E <= 0

E> = 0

Hasilnya adalah: The Kraft ketidaksetaraan mengatakan bahwa kode adalah decodeable JIKA DAN HANYA JIKA panjang kode yang lebih besar dari atau sama dengan yang ditentukan oleh entropi.

Ini harus masuk akal baik.

 

Menghasilkan Kode Prefix-Gratis

 

Dua metode akan disajikan di sini. Salah satunya adalah sederhana dan intuitif, satu ujung praktis dan pemotongan.

Yang pertama adalah sangat sederhana. Hanya membuat pohon biner simbol, sehingga kedalaman di pohon adalah panjang kode.

Sebagai contoh: 
L (a) = 1 
L (b) = 2 
L (c) = 2

Lalu kita membuat pohon:

  
      a 
    / 
akar b 
    \ / 
      X 
        \ 
          c

Sekarang melintasi pohon. Setiap up-cabang sedikit satu. Setiap cabang bawah adalah sedikit nol. Penciptaan pohon ini adalah algoritma yang relatif sederhana.

 

Metode kedua adalah cepat dan menciptakan kode abjad-memerintahkan. Saya shant membahasnya di sini, tapi Anda mungkin melihat kode Huffman Sumber saya untuk check it out.

 


 

Shannon-Fano Coding

 

Shannon-Fano coding adalah metode untuk menciptakan panjang kode awalan-kode.

Ide dasar antara Huffman & SF coding adalah: 
karena setiap BIT output cadangan jumlah yang sama ruang, setiap bit harus memiliki probabilitas yang sama.

Mari kita berpikir tentang kode sebagai pohon biner seperti dijelaskan di atas. Pernyataan di atas adalah sama dengan mengatakan bahwa pada setiap node dari pohon, cabang atas dan bawah cabang harus memiliki probabilitas yang sama occuring.

Misalnya, secara normal 8-bit byte, kita memiliki pohon benar-benar simetris. Beberapa cabang yang diambil sering, dan beberapa diambil hampir tidak pernah. Misalnya, dalam teks, cabang atas dari akar hampir tidak pernah diambil (yaitu karakter ASCII tidak pergi lebih dari 127).

Dengan demikian, semua algoritma menghasilkan kode-panjang adalah cara menyebarkan karakter lebih pohon biner sehingga probabilitas adalah sama di masing-masing cabang.

Bayangkan bahwa kita tahu hitungan kejadian untuk setiap simbol: yaitu jika input string (aabbaac) maka jumlah kejadian adalah: 
C (a) = 4 
C (b) = 2 
C (c) = 1

Kemudian kita ingin pohon:

  
      a 
     / 
    4 
   / 
akar b 
   \ / 
    3 2 
     \ / 
      X 
       \ 
        1 
         \ 
          c

Jumlah pada setiap cabang menunjukkan jumlah jumlah frekuensi dalam "subtree": yaitu pohon dengan node yang sebagai akarnya.

Kita bisa melihat bahwa di setiap cabang, jumlah TIDAK sama, meskipun mereka ADALAH sebagai dekat dengan sama seperti yang mungkin. Ini berarti bahwa kode bilangan bulat panjang string ini adalah sub-optimal. Setiap kali jumlah yang tidak sama, maka kode ini tidak sebagus entropi.

Bagaimana kita membuat pohon seperti ini? Mudah.

Mengambil semua karakter, masing-masing memiliki jumlah yang terkait dengan itu, dan menempatkan mereka di node yang terkait dengan apa-apa. Sebut set ini S0. Mari C (S0) = jumlah semua penting di S0.

Ambil node dengan jumlah tertinggi, dan memasukkannya ke dalam set S1. Sekarang C (S0) lebih rendah.

Terus melakukan ini sampai C (S1)> = C (S0). Sekarang kita telah membagi data sebagai berikut: untuk

 

	
      [S1] 
     / 
    C (S1) 
   / 
akar 
   \ 
    C (S0) 
     \ 
      [S0]

Sekarang, ambil [S1] sebagai titik awal, dan membaginya menjadi [S2] dan [S1]. Lakukan hal yang sama untuk [S0], membuat [S3] dan [S0]. Terus melakukan ini sampai Satu set hanya memiliki satu anggota, di mana titik itu adalah simpul daun.

Saya akan melakukan contoh di set:

C (a) = 4 
C (b) = 2 
C (c) = 1 
C (d) = 1

S0 = {a, b, c, d}, C (S0) = 8

menarik keluar

S1 = {a} C (S1) = 4; S0 = {b, c, d} C (S0) = 4

jumlah yang sama, berhenti membangun S1

S1 hanya memiliki satu anggota, berhenti bekerja di S1

S0 = {b, c, d} C (S0) = 4

menarik keluar b untuk membuat S2

S2 = {b} C (S2) = 2; S0 = {c, d} C (S0) = 2

jumlah yang sama, berhenti membangun S2

S2 hanya memiliki satu anggota, berhenti bekerja pada S2

S0 = {c, d} C (S0) = 2

biarkan S2 = {c}, dan S0 = {d} dan kita sudah selesai.

 

  
      a 
     / 
    4 
   / 
akar b 
   \ / 
    4 2 
     \ / 
      X c 
       \ / 
        2 1 
         \ / 
          X 
           \ 
            1 
             \ 
              d

Yang merupakan kode ideal untuk set ini.

 

Ini disebut Shannon-Fano coding.

 


 

Huffman Coding

Ditemukan bahwa Shannon-Fano coding sedikit sub-optimal dalam beberapa kasus.

Jadi kode Huffman adalah yang terbaik yang dapat memiliki dengan kode bilangan bulat panjang.

> OOPS !!! Aku punya deskripsi yang salah dari Huffman coding! <

Ini dia, kira-kira: bukannya lulus maju seperti Shannon-Fano, lulus mundur dibuat. Dalam Shannon-Fano kami menciptakan sebuah pohon dengan memulai dengan semua karakter pada akar, kemudian melanggar mereka menjadi dua kelompok dan recursing bawah. Dalam Huffman, kita mulai dengan semua karakter "Off dari pohon", di sisi "kanan" tangan - yaitu masa lalu daun. Kami kemudian mengambil beberapa karakter untuk menjadi yang paling kanan daun. Kemudian kita ambil lagi dan membuat node induk, dan menemukan jalan kembali ke akar. Namun, dalam praktiknya hal itu dilakukan sedikit berbeda:

Mengambil daftar semua karakter Anda, menempatkan mereka di node daun, dan memberikan setiap node hitungan sama dengan hitungan karakter di dalamnya. Node ini saat ini tidak memiliki orang tua atau anak-anak (mereka tidak akan pernah memiliki anak). Sekarang lupa bahwa ini adalah karakter, dan hanya menyebut mereka node dengan jumlah. Mengurutkan mereka sehingga orang-orang dengan jumlah terendah adalah pertama. Sekarang, ambil dua node count paling rendah, membuat node baru sebagai induk dari dua, dan mengatur hitungan node baru sama dengan jumlah dari jumlah anak-anak nya.(Anda melihat bagaimana kami recursing mundur dalam membangun pohon). Sekarang, tambahkan node baru ini ke daftar diurutkan dari node, dalam posisi diurutkan yang benar. Dua node yang dibuat menjadi anak-anak tidak lagi dalam daftar (yaitu daftar mendapat lebih pendek dengan satu node). Ulangi sampai daftar hanya memiliki satu anggota - ini adalah akar!

Sekarang contoh, salah satu yang kita sudah lakukan dengan Shannon-Fano:

[a]: 4 
[b]: 2 
[c]: 1 
[d]: 1

Saya akan menggunakan [] untuk menunjukkan node, sehingga [[x], [[y], [z]]] adalah node dengan dua anak, satu adalah daun [x], dan satu memiliki dua anak sendiri , [y] dan [z]. [X]: N berarti jumlah node yang N.

Menginisialisasi pengkodean: mengubah karakter menjadi daun node & semacam:

[c]: 1 
[d]: 1 
[b]: 2 
[a]: 4

Ambil dua terendah: [c] & [d], dan membuat node baru: [[c], [d]]: 2 
dimasukkan kembali dalam rangka diurutkan [b]: 2 
[[c], [d]]: 2 
[a]: 4

ambil dua terendah: [b] & [[c], [d]], dan membuat node baru: [[b], [[c], [d]]]: 4 
[a]: 4 
[[b ], [[c], [d]]]: 4

Sekarang kita jelas dilakukan: hanya ambil yang terendah dua dan membuat node baru:

[[A], [[b], [[c], [d]]]]: 8

Hanya ada satu node yang tersisa, itu akar.

Sekarang saya akan menarik pohon sehingga Anda dapat melihat apa yang berarti notasi ini:

 

  
      a 
     / 
    4 
   / 
akar b 
   \ / 
    4 2 
     \ / 
      X c 
       \ / 
        2 1 
         \ / 
          X 
           \ 
            1 
             \ 
              d

Sama dengan Shannon-Fano coding dibuat. (Ini adalah mudah cuz probabilitas yang kekuatan kebalikan dari dua)

 


 

Aritmatika teoritis Coding (Pendahuluan)

Ok, di sini kita pergi. Masukan boots rendam Anda.

Aritmatika Coding (arithcoding) adalah metode penulisan kode dalam panjang non-integer. Hal ini memungkinkan kita untuk kode sangat dekat dengan entropi ideal.

Ingat bahwa memblokir karakter bersama-sama dapat menghasilkan coding dari panjang non-integer. Sebagai contoh :


p (A) = 2/3


p (B) = 1,3



maka kode:


0 = AA


10 = AB


11 = B


Menulis A & B dengan panjang kode yang ideal.

Dalam prakteknya, pemblokiran diperlukan untuk mendapatkan perilaku yang optimal mungkin sewenang-wenang besar. Juga, ideal-blocking (seperti di atas) adalah masalah yang sulit untuk memecahkan secara real-time. Jadi kita perlu arithcoding.

Arithcoding didasarkan pada prinsip ini: Bilangan Real sangat mirip dengan Data File. Mari kita berpikir tentang hal ini dan memahaminya. Jika Anda memiliki nomor nyata, ditentukan hingga N digit, maka masih ada jumlah tak terbatas cara untuk memperpanjang dari itu. Demikian pula untuk file. Juga, untuk sejumlah nyata N digit, ada exp (N) nomor dengan nomor ini dari digit. Demikian pula untuk file.Dengan analogi, kita bisa memikirkan sebuah file sebagai bilangan real.

Sebagai contoh, jika kita mengetahui panjang input, L (dalam bit), ada 2 kemungkinan input ^ L. Kami bisa memikirkan setiap file input sebagai angka biner (itu apa itu). Sebagai contoh: masukan 0101100 setara dengan bilangan biner 0101100 (duh!). Tapi, kami ingin encoder menjadi panjang-independen, jadi kami ingin menggunakan properti diperpanjang bilangan real, seperti yang disebutkan di atas. Jadi, bukannya berpikir bilangan biner sebagai integer, kita akan menganggapnya sebagai fraksi biner 0.0101100 - yaitu titik desimal ditambahkan ke kiri. Sekarang kita dapat memperpanjang file: untuk 0.01011001 atau 0.01011000 tanpa menimpa bilangan real lainnya: yaitu setiap nomor harus menentukan satu file unik.

Tidak seperti bilangan real matematika, kita bisa tahu berapa banyak digit presisi berada di nomor tersebut, yaitu 0.00 adalah tidak sama dengan 0.000 karena jumlah digit yang berbeda; mereka menentukan file yang berbeda.

Waktu untuk diagram:

 

-------------------------------------------------- ------ 8/8 

                    1 111 
                    + ----------------------------------- 7/8 
                    0 110 
            1 
            + ------------------------------------------- 6/8 
            0 
                    1 101 
                    + ----------------------------------- 5/8 
                    0 100 
   1 
   + ---- ------------------------------------------------ 4 / 8 
   0 
                    1 011 
                    + ----------------------------------- 3/8 
                    0 010 
            1 
            + --- ---------------------------------------- 2/8 
            0 
                    1 001 
                    + --- -------------------------------- 1/8 
                    0 000 

------------- ------------------------------------------- 0/8

Mari kita lihat ini dari kiri ke kanan. Kita mulai dengan interval di bagian paling kiri, antara dua garis putus-putus terjauh. Kami melanjutkan ke pertama tanda '+'. Pada titik kita masukan ini sedikit dari file.Ini memberitahu kita apakah akan naik atau turun. Sekarang, kita memotong interval setengah, dan pergi ke salah satu sisi. Kami terus melakukan hal ini di masing-masing ditambah. Setelah melakukan ini 3 kali, pergi semua jalan ke kanan. Kita sekarang dalam selang waktu yang sesuai dengan 3 bit diinput. Fraksi di kanan setara dengan data diinput. Setiap triplet Data sesuai dengan fraksi di bawahnya.

Sangat mudah untuk mengkonfirmasi bahwa fraksi ini sama dengan biner-fraksi data diinput:

 

----- 8/8 
0.111 
----- 7/8 
0.110 
----- 6/8 
0,101 
----- 5/8 
0.100 
----- 4/8 
0,011 
----- 3/8 
0.010 
----- 2/8 
0,001 
----- 1/8 
0.000 
----- 0/8

Hal ini jelas bahwa ini setara dengan kanan dari diagram di atas. Sekali lagi, masing-masing fraksi biner sesuai dengan fraksi di bawahnya. Kami menulis seperti ini, karena masing-masing fraksi biner sesuai dengan interval antara fraksi atas dan di bawahnya.

Misalnya, 010 sesuai dengan interval (2/8, 3/8).

Hal ini nyaman, karena setiap perpanjangan 010 juga akan di interval (2/8, 3/8): misalnya, 0100 dalam interval (4/16, 5/16) dan 0101 di interval (5 / 16, 16/06): keduanya berada di (2/8, 3/8).

 

Ok, sekarang kita telah mempertimbangkan masukan sebagai fraksi biner, mari kita berpikir tentang bagaimana kita akan memampatkan itu.

Ini benar-benar cukup sederhana:

1. pertama, kita harus memikirkan bagaimana kita akan menulis sebuah interval. Hal ini dilakukan dengan menuliskan SETIAP nilai dalam interval tersebut. Kami sewenang-wenang memutuskan bahwa tepi bawah interval akan berada di dalam interval tersebut, dan tepi atas akan di depan. Dengan demikian, untuk menunjukkan 0.000 kita bisa menulis 0/8 atau 16/01 atau 0,000000001. Kami selalu memilih jalan terpendek, dan menuliskannya sebagai fraksi biner, karena data komputer dalam bilangan biner, tidak rasional.

2. Kedua, kita harus menyadari bahwa interval yang lebih besar ditulis dalam bit yang lebih sedikit. Sebagai contoh, jika A memberikan interval (0, 1/2) dan B memberikan interval (1/2, 3/4) dan C memberikan interval (3/4, 1) maka kita dapat menentukan interval ini sebagai:

A: 0,0-0,1 
B: 0,10-0,11 
C: 0,11-1,00

dan kita dapat menulis mereka sebagai nilai terpendek dalam interval:

A: 0.0: 0 
B: 0.10: 10 
C: 0.11: 11

Jangan khawatir bahwa 1,00 tidak valid (ingat bahwa kita selalu menggunakan 0.X untuk menunjukkan file X) karena bagian atas interval tidak terpakai.

Bahkan, Anda secara intuitif dapat melihat bahwa jika interval adalah ukuran R, ia bisa ditetapkan di sekitar log2 ((1 / R)) bit. Catatan bahwa ini bisa menjadi non-integer, dan itu baik-baik saja.

Hanya untuk latihan, mari kita lihat pada interval untuk kode set, (A, B, C) di atas:

 

------------------------------------------------- 1 
               CC C 
               ---------------------------------- 15/16 
               B CB 
               --------- ------------------------- 7/8 
    
    
    CA CA 
    -------------------- ------------------------- 3/4 
               C BC 
               -------------------- -------------- 11/16 
               B BB 
               ------------------------------- --- 5/8 
    
    
    BA BA 
    ------------------------------------------ --- 1/2 
    
               C AC 
               ---------------------------------- 1/8 
    
               B AB 
               --- ------------------------------- 1/4 
    
    
    
    
    AA AA 
-------------- ----------------------------------- 0
Proses ini sama seperti sebelumnya: mulai dengan penuh  interval kiri (0,1): ketika Anda sampai ke cabang,  membaca dari input, dan mengambil cabang yang sesuai  dengan data yang Anda baca. Lakukan hal yang sama pada cabang kedua.  Setelah Anda membaca dua, Anda sekarang memiliki interval untuk  menentukan dua input. Pikirkan ini sebagai berturut-turut  membagi / menyempurnakan kerja-interval. 

Untuk input lagi, Anda akan terus membagi lebih dan lebih.

Misalnya, untuk menulis BA Anda akan memiliki interval (1/2, 5/8) yang dapat ditulis sebagai biner fraksi 0.100: TIDAK 0.1: 0.1 Menentukan (B atau C) di pilihan pertama: 0,10 menentukan B di pertama pilihan: Anda perlu menulis 0.100 untuk menentukan BA. Similary 0,1010 adalah BB dan 0,1011 adalah SM.

 


Karena kita tahu bahwa selang ukuran R ditulis dalam l = -log2 (R) bit, itu adalah sederhana untuk melihat bahwa jika R = p (probabilitas karakter yang) maka l = -log2 (p) bit, yang merupakan ideal. Dengan demikian, yang harus kita lakukan untuk kode data adalah untuk mencari tahu p, maka kita dapat membuat proses membagi interval yang akan kode data Idealnya!

Dengan demikian, kita melihat bahwa contoh di atas (dengan A, B, C) akan memberikan coding ideal jika dan hanya jika P (A) = 1/2, P (B) = 1/4 dan P (C) = 1/4 dan A, B & C tidak memiliki korelasi (yaitu setelah A, probabilitas dari karakter berikutnya adalah sama seperti setelah B, sama seperti setelah C; yaitu tidak ada karakter menyiratkan apa-apa tentang yang lain).

 


 

Praktis Coding aritmatika dengan renormalization

Pembahasan di atas semua sangat bagus: tapi bagaimana Anda melakukannya? Metode Interval-divisi atas akan bekerja besar, kecuali untuk satu masalah: pada file data yang besar, interval akan mendapatkan sangat kecil. Terlalu kecil untuk menjaga dalam kata mesin.

Bahkan, jika Anda tidak peduli tentang kecepatan, Anda dapat menggunakan di atas metode. Namun, kebanyakan dari kita suka kecepatan. Dengan demikian, kita perlu menjaga interval dalam kata mesin integer.

Ini berarti bahwa untuk sebuah kata 32-bit, Anda tidak dapat menentukan lebih precicision bahwa 2 ^ (- 32).

Namun, pertimbangkan kode datar untuk byte: yaitu byte memiliki nilai 0 -> 255 dan Anda menulis masing-masing dengan probabilitas yang sama 1/256. Kemudian setelah satu acara coding, interval adalah 1/256, setelah byte lain, interval adalah 1/65536, setelah 3 byte interval adalah 1/2 ^ (24) dan setelah selang waktu 4 bytes adalah 2 ^ (- 32). YIKES! Dalam 4 byte masukan kita habis kata mesin kami! Kami ingin kompres file lama dari 4 byte !!

Dengan demikian, kita perlu cara untuk menjaga selang kami menjadi terlalu kecil.

Rahasianya adalah: renormalization.

Mari kita berpikir seperti ini:

kita mulai dengan rendah terikat, L, dan batas atas, H, untuk jangkauan kami. Pictorially, L adalah bagian bawah grafik dan H adalah bagian atas. Sekarang, seperti yang kita pergi melalui rekursi coding (yaitu membagi rentang) L dan H lebih dekat dan lebih dekat bersama-sama. Ketika kita selesai, kita menulis angka antara dua (katakanlah (L + H) / 2) dan kami sudah selesai. Tapi, jika kita mewakili L dan H sebagai fraksi biner, seperti di atas, maka kita dapat menulis keluar bit seperti yang kita pergi: setelah beberapa paling kiri bit L dan H adalah sama, maka mereka tidak pernah bisa berubah.

misalnya: jika kita ingin kode dari "model" dari:

 

------------------------------------------------- 1 
               B                                
               ---------------------------------- 1/2 
               A                                
----------- -------------------------------------- 0

dan input "ABAA" maka kode lanjutkan seperti:

 

LH Chars melihat 
------------------------------------ 
0,0000 0,1111 none 
0,0000 0,0111 A 
0,0011 0,0111 AB 
0,0011 0,0101 ABA 
0,0011 0,0100 ABAA

Berjalan cepat-melalui tabel ini, untuk kejelasan ekstra:

kita mulai dengan L = 0,0000 dan H = 0,1111, ini adalah inisialisasi kondisi yang sesuai dengan berbagai. Kemudian kita melihat A, dan memotong rentang setengah, menjaga bagian bawah. Jelas, L tidak berubah. H harus / 2, yang sama dengan >> 1, sehingga H baru adalah 0,0111 Cara lain untuk melihat ini: H benar-benar mulai di 1,0000, dengan 0,0000 ... 0001 kurangi off. Dengan demikian, 1/2 = 0,1000, tapi kita harus mengurangi off 0.0000 .... 00001, yang memberikan 0,0111 Sekarang kita melihat B, jadi kami harus membagi rentang ke atas. H tetap sama, dan L meningkat dengan setengah dari (HL), yang merupakan 0,0011 ... Sisanya berikut karena ini lakukan.

sekarang kita bisa menuliskan 0,0011 dan dilakukan. Namun, kita bisa memiliki output 0 tepat pertama setelah A pertama: setelah L adalah 0.0000 dan H adalah 0,0111 maka kita dapat output 0 bit dan bergeser kedua hingga 0.000 dan 0.111;

Kami selalu bergeser nol menjadi L dan satu ke H, sehingga L akan 0.0000 dan H akan 0,1111 setelah pergeseran ini.

Alasan kita menggeser 1 ke H adalah bahwa H tidak benar-benar 0,1111, itu benar-benar 1,00000, tapi karena kita tidak bisa menangani hal ini, kita memperlakukan sebagai 0,11111111111111 .... yang setara dengan 0,9999999999 ... yang kita tahu dari Matematika sama dengan 1 (dalam basis-sepuluh). (ini harus setara dengan Satu, karena jika tidak sama, maka akan menjadi nomor yang berbeda yang bisa muat antara kedua).

 

Dengan demikian, sederhana algoritmik arith-coder di 16-bit register akan menjadi:

 

membatalkan A_Simple_Arithcoder (void) 
{ 
uword L, H; 

L = 0 
H = (1 << 16) - 1; / * Ada tempat desimal implisit di bit 16, 
                   hanya di sebelah kiri dari kata mesin * / 

while (MoreInput) 
  { 
  mendapatkan masukan 

  menyusut L 
  mengecilkan H 
  / * L dan H menyusut berdasarkan simbol probabilitas kumulatif. 
       ini disebut "langkah coding" * / 

  if (L & (1 << 15) == H & (1 << 15)) 
    { 
    outputbit (L & (1 << 15)); 

    / * Jika bit atas adalah sama, pergeseran mereka keluar * / 

    L << = 1; 
    H << = 1; 
  
    H ++; 

    / * Bergeser satu ke tempat yang paling signifikan dari H * / 
    } 
  } 

}

By the way, langkah coding adalah:

 

biarkan Sp = probabilitas simbol 
membiarkan Sl = jumlah semua probabilitas simbol, yang indeks 
           lebih rendah dari yang ada sekarang

 

R = H - L 
L + = R * Sl 
H - = R * (1 - (Sl + Sp))

Ini harus cukup jelas. Mengalikannya dengan R hanya sisik yang probabilitas ke dalam berbagai L dan H sehingga Sl = 0 -> L dan Sl + Sp = L -> H

 

Sekarang kami semua siap untuk menulis arithcoder kecuali untuk satu hal: underflow. Underflow adalah "kasus terburuk" untuk arithcoder dari gaya ini (atau gaya apapun). Ini terjadi sekitar sekali setiap 1000 byte, tapi kita harus mampu menanganinya, atau arithcoder kami akan mati.

Underflow terjadi ketika L = 0,01 ... dan H = 0,10 ...: yaitu mereka stradle titik tengah: L = 0,011111111 dan H = 0,100000001 adalah kasus terburuk. Masalahnya di sini adalah bahwa tidak peduli berapa banyak rentang yang dibagi, atas angka dari L dan H tidak akan sama sampai L dan H adalah sama !!!! (Ini tidak benar jika Anda memiliki besar tak berhingga mesin register).

Dengan demikian, kita harus mengakui bahwa L dan H dalam kasus underflow, dan melakukan sesuatu tentang hal itu.

 

Cara terbaik untuk memahami ini adalah untuk kembali ke arithcoder kami sebelumnya dan mengubah dasar konseptual. Setiap kali digit pertama L dan H keduanya 0, ini berarti L <1/2 dan H <1/2: ketika kita skala mereka, apa yang kita benar-benar melakukan adalah "menyusut jangkauan kami" dari (0,1) ke (0,1 / 2):

sebagai contoh:

 

biarkan Rl = rendah terikat rentang 
biarkan Rh = tinggi terikat rentang 
membiarkan Al = arithcoder rendah, mutlak 
biarkan Ah = arithcoder tinggi, mutlak 

Rl = 0, Rh = 1, Al = 0, Ah = 1 

Lanjutkan dengan arithcoding , mengecilkan Al dan Ah, jangan khawatir 
abour renormalization. 

Kami teman-teman L lama dan H dapat ditemukan dari: 

L = (Al - Rl) / (Rh - Rl) 
H = (Ah - Rl) / (Rh - Rl) 

yang hanya skala Al dan Ah di Rl-Rh bingkai. yaitu Al dan Ah 
diambil berada di interval (Rl, Rh) sedangkan L dan H dalam interval 
(0,1) 

sekarang, jika L <1/2 dan H <1/2 kemudian membiarkan Rh = (Rh - rl) / 2 + Rl 

dengan kata lain, jika Al dan Ah keduanya di bagian bawah dari 
interval Rl-Rh, kemudian dipotong interval Rl-Rh dalam setengah, memilih 
bagian bawah 

sama, jika L> 1/2 dan H> 1/2 membiarkan Rl = (Rh - Rl) / 2 + Rl 

memilih bagian atas.

Ini identik dengan kami "sederhana encoder aritmatika".

Sudut pandang ini akan membuat lebih mudah untuk memahami solusi untuk masalah underflow (yang lolos dari penulis ini untuk beberapa waktu) yang disebut metode "bit-plus-follow".

Ini benar-benar cukup sederhana sekali Anda tahu bagaimana melakukannya. Ketika L & H yang kurang dari 1/2, kita memotong rentang dua dan mengambil bagian bawah. Ketika L & H berada di atas 1/2, kita memotong rentang dua dan mengambil bagian atas. Jadi, ketika L & H berada di tengah, kami hanya memotong rentang dua dan mengambil tengah! Sebagai berikut:

jika (1/4 <= L <3/4 && 1/4 <= H <3/4) { L - = 1/4; H - = 1/4; L * = 2; H * = 2; }

Ini harus jelas bahwa segmen kode ini skala tengah 1/2 kisaran hingga ke kisaran penuh.

Sekarang satu-satunya masalah adalah: bagaimana cara memberitahu decoder yang kita lakukan ini? Mari kita lagi mengubah secara konseptual kita.

Sebuah file data seperti serangkaian perintah. Decoder membaca ini perintah dan tahu bagaimana menafsirkannya & melakukan sesuatu yang berguna dengan mereka. Dalam aritmatika encoding, kita memiliki dua perintah kami dapat mengirim ke decoder: 0 = membagi lebih rendah 1 = membagi atas Karena kita dalam biner, ini adalah satu-satunya perintah yang kita dapatkan. Anda harus berhenti dan berpikir sejenak untuk memastikan bahwa sudut pandangnya adalah setara dengan Simple_ArithCoder kami yang dikeluarkan sedikit paling kiri dari biner pecahan dari L & H setiap kali mereka menjadi sama.

 

Jadi, bagaimana kita mengirim "membagi tengah" perintah? Nah, akan terlihat bahwa kita tidak bisa - dan memang, kita tidak bisa !!! - Tapi kami BISA mengirim "membagi tengah" perintah jika diikuti oleh salah satu perintah lain. Mari kita lihat beberapa contoh:

Bagaimana jika kita melakukan "membagi tengah" diikuti dengan "membagi rendah": yang hasilnya adalah:

 

1 ---------- 

                             3/4 -------- 

awal -> membagi dua menengah -> -> "membagi rendah" -> 1/2 ------ 
kisaran 
                             1/4 -------- 1/4 ------ 

0 ----------

Hasil akhirnya adalah berbagai (1/4, 1/2) - tapi itu sama dengan melakukan "setengah lebih rendah" diikuti dengan "bagian atas" !!

Sekarang apa yang terjadi jika kita sebuah "membagi tengah" diikuti dengan "membagi atas":

1 ---------- 

                             3/4 -------- 3/4 ------ 

awal -> membagi dua menengah -> -> "membagi atas" -> 1/2 - ----- 
kisaran 
                             1/4 --------                       

0 ----------

Hasil akhirnya adalah berbagai (1/2, 3/4) - tapi itu sama dengan melakukan sebuah "bagian atas" diikuti dengan "setengah lebih rendah" !!

Sekarang ingat 0 = membagi lebih rendah 1 = membagi atas Jadi kita bisa menulis algoritma:

 

( "Halve Tengah") kemudian (operasi B) = (operasi B) kemudian (operasi TIDAK B)

Sekarang bagaimana jika kita harus melakukan "Halve Tengah" beberapa kali sebelum operasi normal? Nah, yang hanya memerlukan beberapa aplikasi dari operasi! B. (ini mudah untuk mengkonfirmasi, hanya berpikir tentang rentang yang dibelah dua, seperti di atas). Dengan demikian kita memiliki gambar ini:

Aplikasi N dari ( "Halve Tengah") kemudian (operasi B) = (operasi B) maka aplikasi N dari (operasi! B)

Jadi, setiap saat kita ingin melakukan "Belah Tengah", kami hanya selisih counter, yang saya akan menelepon BPF, yang memberitahu kita berapa banyak bit berlawanan dengan output.

Sekarang, mari kita kembali Simple_Arithcoder kami, dan kami akan menambahkan BitPlusFollow.

 

membatalkan A_Simple_Arithcoder_Number1 (void) 
{ 
uword L, H; 
int b, BPF; 

BPF = 0; 

L = 0 
H = (1 << 16) - 1; / * Ada tempat desimal implisit di bit 16, 
                   hanya di sebelah kiri dari kata mesin * / 

while (MoreInput) 
  { 
  mendapatkan masukan 

  menyusut L 
  mengecilkan H 
  / * L dan H menyusut berdasarkan simbol probabilitas kumulatif. 
       ini disebut "langkah coding" * / 

  if (L & (1 << 15) == H & (1 << 15)) 
    { 
    b = L & (1 << 15); 
    outputbit (b); 
    jika (BPF) 
      { 
      while (bpf--) 
        { 
        outputbit (b!); 
        } 
      } 
      

    / * Jika bit atas adalah sama, pergeseran mereka keluar * / 

    L << = 1; 
    H << = 1; 
  
    H ++; 

    / * Bergeser satu ke tempat yang paling signifikan dari H * / 
    } 
  else if ((L >> 13) == 0x1 && (H >> 13) == 0x2) 
    { 
    / * jika atas dua bit L yang 01 dan atas dua bit dari H adalah 10 
       maka mereka mengangkang tengah dan kita perlu melakukan "membagi tengah" * / 

    BPF ++; 

    / * Ini melakukan - = 1/4 * / 
    L & = (1 << 14) -1; 
    H | = (1 << 14); 

    L << = 1; 
    H << = 1; 
    H ++; 
    } 
  } 

}

 

Itu salah satu cara untuk melakukannya, menggunakan pendekatan yang sangat sedikit-oriented. Mari kita melihat cara lain:

 

membatalkan A_Simple_Arithcoder_Number2 (void) 
{ 
Ulong Satu, Half, Quarter, ThreeQuarters; 
ulong L, H; 
int b, BPF; 

BPF = 0; 

Satu = (1 << 16); 
Setengah = Satu / 2; 
Quarter = Half / 2; 
ThreeQuarters = Half + Quarter; 

L = 0 
H = Satu - 1; 

sementara (MoreInput) 
  { 
  mendapatkan masukan & menyusut L, H 

  if (L> = Half) 
    { 
    b = 1 
    outputbit (b); 
    jika (BPF) 
      { 
      while (bpf--) 
        { 
        outputbit (b!); 
        } 
      } 

    L - = Half; 
    H - = Half; 
      
    L * = 2; 
    H * = 2; 
  
    H ++; 
    } 
  Else if (H  = Quarter && H 

 

Nah, itu saja. Ada beberapa hal yang perlu diperhatikan:

1. catatan yang kita gunakan <= dan> = untuk bagian bawah kisaran, tetapi untuk bagian atas jangkauan. Sangat penting bahwa Anda memilih salah satu batas untuk menjadi "dalam" dan satu untuk "keluar" - mereka tidak bisa keduanya "di" jangkauan.

2. catatan bahwa X + = X setara dengan X * = 2 dan X << = 1 dan bahwa metode X + = X adalah tercepat pada kebanyakan arsitektur.

3. Perhatikan bahwa H adalah benar-benar (H + 1), dan juga bahwa H