Lossless Coding [PDF]

Citation preview

Lossless Coding Alvian Bastian, S.ST., M.Sc.



Data Compression • Tujuan Kompresi Data: Merepresentasi file dalam jumlah bit paling sedikit dan seakurat mungkin. Source File (DF)



15 KB



Compress



Compress File (CF)



5 KB



decompress



Decompress File (DF)



15 KB + error



Data Compression • Lossless Compression 1. DF = SF; jika file DF=15 KB, maka SF=15 KB 2. Slow 3. Biasa digunakan untuk teks 4. Contoh kompresi: Run Length, Huffman, LZ (Lempel-Ziv) • Lossy 1. DF ≠ SF; bisa saja DF = 14.8 KB dan SF = 15 KB 2. Fast 3. Biasa digunakan untuk audio, video 4. Contoh kompresi: MPEG, MP3, dsb



Modeling and Coding Sejumlah file: 111222233



compress



model



132432



(Dimana angka 1 ada 3, angka 2 ada 4, angka 3 ada 2), sehingga menjadi model dalam kompresi data



unary code



101110 11011110 1110110



codes



Performance Measure • Compression Ratio: 𝑏𝑏𝑏 𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟 𝑏𝑏𝑏𝑏𝑏𝑏 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 (𝑆𝑆) 𝐶𝐶 = 𝑏𝑏𝑏 𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟 𝑎𝑎𝑎𝑎𝑎 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 (𝐶𝐶) • SF = 4 bits -> CF = 1 bit 𝑆𝑆(𝑏𝑏𝑏𝑏) 4 ∴ 𝐶𝐶 = = =4 𝐶𝐶(𝑏𝑏𝑏𝑏) 1 Jika CF tinggi, maka algoritma yang digunakan baik.



Lossless Coding • •



• •



•



Input untuk lossless coder adalah simbol dan outputnya adalah codeword, biasanya binary codeword. Kita terbiasa dengan ASCII untul alfabet bahasa inggris. Dalam sistem kompresi gambar, simbol bisa berupa piksel terkuantisasi atau koefisien transformasi terkuantisasi. Kemudian, codeword yang ditetapkan untuk simbol oleh lossless coder ditransmisikan atau disimpan. Jika panjang semua codeword yang ditetapkan untuk simbol yang berbeda adalah tetap atau konstan, maka lossless coder disebut fixed rate coder. Disisi lain, jika panjang kode dari codewords adalah variabel, maka coder adalah coder dengan panjang variabel. Pulse Code Modulator memberikan codewords dengan panjang yang sama ke simbol inputnya. Pada pembahasan pada bagian ini, kita akan melihat bahwa seorang Pengkode Huffman menetapkan panjang variabel codewords untuk menetapkan codewords untuk simbol inputnya, pertama-tama codewords harus dikomputasi dan disimpan.



Lossless Coding • Decoder lossless melakukan operasi invers, yaitu mengeluarkan simbol yang sesuai dengan inputnya – codeword. Oleh karena itu, sangat penting bahwa decoder lossless memiliki codebook yang sama dengan encoder. • Kepraktisan lossless coder tergantung pada ukuran codebook yang dibutuhkannya untuk meng-encode simbol-simbol inputnya serta kompleksitas penyandiannya. • Seorang Pengkode Huffman memerlukan codebook yang besar, sedangkan Arithmetic Coder tidak memerlukan codebook sama sekali, meskipun mungkin lebih kompleks daripada Pengkode Huffman. • Pilihan pembuat lossless coder tertentu tidak hanya bergantung pada dua faktor di atas, tetapi juga pada kompresi yang dapat dicapai.



Information Theory • • • • • •



Mari kita pertimbangkan sumber informasi, seperti transformer coder. Sumber informasi menghasilkan simbol pada suatu waktu dari satu set simbol yang disebut sumber alfabet. Misalnya, gambar intensitas mungkin memiliki 256 kemungkinan nilai skala abu-abu dan setiap nilai piksel dapat dianggap sebagai simbol. Jadi, alfabet sumber dalam hal ini memiliki 256 simbol. Karena kita tidak tahu sebelumnya simbol mana yang akan dihasilkan oleh sumber, kita hanya dapat menggambarkan kemunculan simbol-simbol sumber dengan cara probabilistik. Dengan demikian, kita memiliki sumber informasi yang menghasilkan simbol pada suatu waktu dari alfabet simbolnya dengan masing-masing simbol memiliki kemungkinan kejadian tertentu. Jumlah informasi yang disampaikan oleh simbol kepada penerima harus tidak negatif, harus besar jika probabilitasnya kecil, dan kecil jika probabilitasnya besar. Ini sesuai dengan gagasan intuitif tentang informasi yang disampaikan oleh pesan. Ukuran kuantitatif diperlukan untuk keperluan desain teknik.



Information Theory • Teori informasi merupakan disiplin ilmu dalam bidang matematika terapan yang berkaitan dengan kuantisasi data sehingga data atau informasi dapat disimpan dan dikirimkan tanpa kesalahan (error) melalui kanal komunikasi. • Aplikasi dari teori informasi meliputi kompresi data tanpa cacat (lossless data compression, pada ZIP), kompresi data (lossy data compression, pada MP3), dan pengkodean kanal (channel coding, pada DSL, ADSL, dll). • Teori informasi merupakan cabang dari matematika peluang dan statistik, yang berkaitan dengan konsep informasi dan entropi informasi. • Digunakan untuk mengembangkan lossless Compression Technique (CT).



Information Theory 1. Experiment Beberapa prosedur atau percobaan yang dapat kita lakukan dengan jumlah yang tak terbatas dan memiliki beberapa set hasil. Contoh: Melempar dadu Hasil: {1,2,3,4,5,6} = sampel Mengatur semua hasil = ruang sampel -> n(S)=6



Information Theory 2. Random Experiment - Beberapa percobaan yang memiliki lebih dari satu hasil Contoh: 1. Melempar Dadu 2. Melempar Koin Hasilnya dapat random



Information Theory 3. Event  Mengatur hasil Probabilitas untuk mendapatkan dadu bertitik lebih dari 3 dalam melempar dadu -> {4,5,6} n(B) = 3, sehingga 𝑃 𝐵 =



𝑛(𝐵) 𝑛(𝑆)



3 6



= =



1 2



Information Theory • Self Information Today is Saturday Info Sender



Msg: There will be rain tomorrow Msg: Tomorrow is Sunday



Info=0



Receiver Self Information



Information Theory E1 = Probability to rain heavily tomorrow E2 = Probability of having next day (tomorrow) as Sunday (Saturday) P(E2)=1 Self Information (E2) = 0 (min) Probability (E2) = 1 (max) Probability (E1) = 0.4 Self Information (E1) = …?



Information Theory • Event A, set of outcomes of some random Exp. E. • Self Information contained in event (A): 1 𝑖 𝐴 = 𝑙𝑙𝑙𝑏 𝑃(𝐴) Jika P(E2) = 1; S.I (E2) Kapan kondisinya P(↑), S.I (↓), atau P(↓), S.I(↑)



Information Theory • Entropy Self Information untuk Event, Entropy untuk Experiment. Rata-rata self information dari setiap percobaan (experiment) A1, A2, A3,….., An 𝑃 ∪ 𝐴𝑖 = 1



Information Theory • Entropy 𝐻 = � 𝑃 𝐴𝑖 𝑖(𝐴𝑖 )



Contoh: Banyaknya percobaan = 5 Sehingga: 𝐻 = 𝑃 𝐴1 𝑖 𝐴1 + 𝑃 𝐴2 𝑖 𝐴2 + ⋯ + 𝑃 𝐴5 𝑖(𝐴5 ) 1 1 Jika 𝑖 𝐴 = 𝑙𝑙𝑙𝑏 , maka 𝐻 = ∑ 𝑃(𝐴𝑖 ) log 𝑏 𝑃(𝐴)



Sehingga 𝐻 = − ∑ 𝑃(𝐴𝑖 ) log 𝑏 𝑃(𝐴𝑖 )



𝑃(𝐴𝑖 )



Information Theory • Entropy Contoh: Sequence = 12345665 Maka 𝑃 1 = 𝑃 2 = 𝑃 3 = 𝑃 4 = 2 1 𝑃 5 =𝑃 6 = = 8 4 Hitung Entropy-nya..?



1 8



Information Theory • Entropy 𝐻 = − � 𝑃(𝐴𝑖 ) log 2 𝑃(𝐴𝑖 )



1 1 1 1 = − log 2 × 4 + − log 2 × 2 8 4 8 4 1 1 = log 2 8 × 4 + log 2 4 × 2 8 4 1 1 3 = × 3 + × 2 = + 1 = 2.5 2 2 2



Prefix Codes and Uniquely Decodable Codes • • • •



Coding = Penetapan urutan binari ke alfabet Code = Menetapkan urutan binary Codeword = Anggota individual dari Code Alphabet = Kumpulan huruf atau simbol Contoh: Alphabet



{



Letter



Codeword



a1 a2 a3 a4



0 1 10 11



}



Code



Prefix Codes and Uniquely Decodable Codes Uniquely Decodable Codes (UDC) • Urutan kode yang dapat di-decode hanya dengan satu cara. Contoh 1:



a1 a2 a3 a4



0 1 10 11



}



a1 a2 a3 a4



0 10 110 111



}



Contoh 2:



1st 10 2nd



100



a2a1 a3



Karena ada dua cara untuk melakukan peng-kodean maka sequence code (urutan kode) ini not-UDC



a2a1 Karena hanya satu cara untuk melakukan peng-kodean maka sequence code ini merupakan UDC



Prefix Codes and Uniquely Decodable Codes 1. Prefix 2. Dangling Suffix a - 010 b - 01011 Code: 01011



a (010) merupakan prefix dari b jika (010) merupakan prefix dari b maka 11 merupakan dangling suffix prefix



(0,01,010,0101,01011)



Prefix Codes and Uniquely Decodable Codes • Algoritma untuk menguji Uniquely Decodable Codes: 1. Kelompokkan codewords 2. Jika tidak ada prefix yang ditemukan maka itu merupakan UDC. Tetapi Jika ada prefix yang ditemukan kemudian tambahkan dangling suffix (DS). 3. Jika DS = beberapa codeword, maka ini bukan merupakan UDC Tetapi jika semua DS berakhir, maka ini merupakan UDC.



Prefix Codes and Uniquely Decodable Codes Contoh 1:



a1 a2 a3 a4



0 1 01 11



Langkah pengujian: 1. Kelompokkan codewords : {0,1,01,11}, karena ada prefix yang ditemukan selanjutnya ke langkah berikutnya. 2. Tambahkan DS, {0,1,01,11,1}, 1 merupakan DS untuk codewords 3 dan 4 3. Karena DS sama dengan codewords {0,1,01,11,1}, maka ini bukan merupakan UDC



Prefix Codes and Uniquely Decodable Codes Contoh 2:



a1 a2 a3 a4



0 10 110 111



Langkah pengujian: 1. Kelompokkan codewords : {0,10,110,111} 2. Karena tidak ada prefix yang ditemukan berarti ini merupakan UDC



Prefix Codes and Uniquely Decodable Codes Prefix Code • Jika ada codeword yang bukan prefix untuk setiap codeword apapun, maka itu merupakan prefix code. Contoh 1: 0 10 110 111



}



Prefix Code



Contoh 2: 0 1 10 11



}



Not Prefix Code



Prefix Codes and Uniquely Decodable Codes Prefix Code 1:



a1 a2 a3 a4



0 1 10 11



0 a1



2:



0



1 0 a3



a2



a1 a2 a3 a4



a1



1 a4



0 10 110 111



3: a1 a2 a3 a4



1



a2



0



0 a3



1 a4



0



1



a1



0



1



0



0 01 001 0001



a2



1 1



a3 a3



Prefix Codes and Uniquely Decodable Codes Jika semua huruf ada pada External node maka itu merupakan prefix code 3:



2:



1: 0



1



a1



0







a2



a3



 not prefix code



0



X



 1 a4







X 0



1



a1







1



0 a2







0 a3



prefix code



0



1 a4







0



1



a1



a2



1 1



a3 a3



 



not prefix code







Huffman Coding • Kode Huffman merupakan variable-length codes dan optimal untuk sumber dengan model probabilitas yang diberikan. Disini, optimalitas menyiratkan bahwa panjang kode rata-rata dari Kode Huffman paling dekat dengan source entropy. • Dalam Pengkodean Huffman, lebih banyak simbol yang mungkin diberikan codeword yang lebih pendek dan simbol yang lebih kecil kemungkinannya diberikan codeword yang lebih panjang. • Digunakan untuk Data Compression • Digunakan jika Probabiliti dari elemen sumber file diketahui Sedangkan jika probabiliti dari elemen sumber file tidak diketahui maka menggunakan Adaptive Huffman Coding.



Huffman Coding Jika ada sebuah file a1



a2



a5



a3



…. …. ….



…



…. …. ….



a1



a5



a3



a4



a2



{a1, a2, a3, a4, a5}



Code (without using)



letter



probability



000 001 010 011 100



a1 a2 a3 a4 a5



0.2 0.4 0.2 0.1 0.1



codeword



l1 = 3x0.2 + 3x0.4 + 3x0.2 + 3x0.1 + 3x0.1 = 3x(0.2+0.4+0.2+0.1+0.1) = 3x(1) = 3 bits/symbol



Huffman Coding Metode 1 mencari codeword Diurutkan dari yang terbesar: a2(0.4) a1(0.2) a3(0.2) a4(0.1) a5(0.1)



a2(0.4) a1(0.2) a3(0.2)



0



a2(0.4) 0



a4’(0.2)



1



1



letter



probability



codeword



a1 a2 a3 a4 a5



0.2 0.4 0.2 0.1 0.1



01 1 000 0010 0011



a3’(0.4) a1(0.2)



a1’(0.6) 0



a2(0.4)



1



1 Diurutkan dari kanan ke kiri



l2= 2x0.2+1x0.4+3x0.2+4x0.1+4x0.1 = 0.4+0.4+0.6+0.4+0.4 = 2.2 bits/symbol Sehingga dengan menggunakan Pengkodean Huffman kita dapat merepresentasikan file menjadi 2.2 bits/symbol



Huffman Coding



Metode 2 (Tree Method) a2 0.4



a1 0.2



a3 0.2



a4 0.1



a5 0.1 1



0 0 0.4



0 0.2 a3



0



0.6



1 0.2



1



a1



0.2



1



0.1



0.1



a4



a5



1 0.4 a2



sehingga



letter



probability



codeword



a1 a2 a3 a4 a5



0.2 0.4 0.2 0.1 0.1



01 1 000 0010 0011



Huffman Coding • Letter having higher probability will have smaller codewords. Probability decrease (↓), length of code increase (↑) • Length of codeword of two least probability are same.



Minimum Variance Huffman Codes a2(0.4)



a2(0.4)



a1(0.2)



a4'(0.2)



a3(0.2)



a1(0.2)



a4(0.1) a5(0.1)



0



a3(0.2)



a1'(0.4) a2(0.4) 0



1



1



Average length= 0.2x2+0.4x2+0.2x2+0.1x3+0.1x3 = 2.2 bits/symbol



a4'(0.2)



a2'(0.6) 0



a1'(0.4)



0 1 1



1 Letter



Prob.



Codeword



a1



0.2



10



a2



0.4



00



a3



0.2



11



a4



0.1



010



a5



0.1



011



Contoh Soal • Sebuah sumber mengeluarkan huruf dari alfabet A={a1,a2,a3,a4,a5} dengan probabilitas P(a1)=0.15, P(a2)=0.04, P(a3)=0.26, P(a4)=0.05, dan P(a5)=0.50. a. Hitung entropi dari sumber ini. b. Temukan Kode Huffman dari sumber ini. c. Temukan panjang kode rata-rata.



Jawaban Soal a. Entropi



𝐻 = − � 𝑃 𝐴𝑖 log 2 𝑃 𝐴𝑖



= −0.15 log 2 0.15 − 0.04 log 2 0.04 − 0.26 log 2 0.26 − 0.05 log 2 0.05 − 0.50 log 2 0.50 = 0.15 × 2.736 + 0.04 × 4.643 + 0.26 × 1.94 + 0.05 × 4.32 + 0.50 ×1 = 1.81652



Jawaban Soal b. Huffman Code a5(0.50)



a5(0.50)



a3(0.26)



a3(0.26)



a1(0.15)



a1(0.15)



a4(0.05) a2(0.04)



a5(0.50) a3(0.26)



1



a3‘(0.50) a1‘(0.24)



1



1



0



0



0



a4‘(0.09)



a5(0.50)



0



1



letter a1 a2 a3 a4 a5



1



huffman code 110 1111 10 1110 0



Jawaban Soal a. Rata-rata panjang dari code ini l=0.15x3+0.04x4+0.26x2+0.05x4+0.50x1 = 0.45 + 0.16 + 0.52 + 0.20 + 0.50 = 1.83 bits/symbol



Contoh 3.1 • Sebuah sumber dengan alfabet diskrit dari delapan huruf dengan probabilitas P = [0.2 0.15 0.13 0.13 0.12 0.10 0.09 0.08]T, Konstruksilah Kode Huffman dan hitung panjang kode ratarata.



Contoh 3.1 Jawaban: • Probabilitas simbol dalam urutan menurun, dan oleh karena itu, berikan simbol dalam urutan yang sama dengan probabilitas simbol yang diberikan. Dimulai paling dua pesan yang mungkin sesuai dengan pesan m7 dan m8, buat node dengan probabilitas yang sama dengan jumlah 0.09 dan 0.08. • Tetapkan “0” pada cabang atas dan “1” pada cabang bawah. Karena dua probabilitas terkecil berikutnya adalah 0.1 dan 0.12, bentuk node yang cabangnya memiliki dua probabilitas ini dan yang jumlahnya sama dengan 0.22. • Tetapkan “0” pada cabang atas dan “1” ke cabang bawah. Dua probabilitas selanjutnya yang akan digabungkan adalah 0.13 dan 0.13. Selanjutnya, kita mendapatkan pohon Huffman yang ditunjukkan pada Gambar berikut.



Contoh 3.1



Konstruksi Pohon Huffman untuk vektor probabilitas



Contoh 3.1 •



Selanjutnya, kode untuk pesan diperoleh dengan membaca digit dari node akar ke node terminal secara berurutan. Dengan demikian, kita mendapatkan Kode Huffman untuk letter yang ditunjukkan pada Tabel berikut. Kita dapat menemukan rata-rata panjang kode L dari Kode Huffman pada Tabel dari persamaan yaitu:



Kode Huffman dari Contoh 3.1



Contoh 3.1 • Entropi dari sumber ini didapatkan dari Persamaan sebagai 2.9436 bits/simbol. Efisiensi Huffman Coding didefenisikan sebagai rasio entropi terhadap rata-rata panjang kode, yaitu 99.11%. Jadi kita menemukan bahwa Kode Huffman hampir sama dengan entropi sumber untuk sumber khusus ini. • Kode MATLAB untuk pembuatan Kode Huffman tercantum dibawah ini. Prosedur yang ditetapkan oleh kode MATLAB sedikit berbeda dari prosedur di atas. Namun, panjang kode sama dengan efisiensi kode.



Contoh 3.1 % Example5 4.m % Program to generate Huffman codes for the % given probability vector p % The Huffman codes and the corresponding code lengths are % stored in the arrays HC and L, respectively. %p = [1/8 1/4 1/10 1/10 1/16 1/16 1/12 13/60]; %p = [.2.15.13.12.1.09.08.13]; %p = [.25.25.125.125.0625.0625.0625.0625]; %p = [.5.1.1.1.1.1]; %p = [.2.18.1.1.1.06.06.04.04.04.04.03.01]; p = [.2 .15 .13 .12 .1 .09 .08 .13]; % Check for negative value for any probability and % if the sum of the probabilities do not add up to 1. if any(find(p1.0e-10 error('Not a valid probability set\n') Lanjutan code di slide berikutnya…!!! end



Contoh 3.1 % Compute the source entropy. H = sum(-p.* log2(p+1e-08)); sprintf('Source Entropy = %5.2f\n',H) % Call the function Huffman to generate the Huffman codes. [HC,L] = Huffman(p); % Compute the average code length of the Huffman codes. AvgLength = sum(p.*double(L)); % compute the Huffman code efficiency as the ratio of entropy to % the average code length. E = 100*H/AvgLength; sprintf('Average Code Length = %5.2f\n',AvgLength) sprintf('Efficiency = %5.2f%%\n',E)



Contoh 3.1 Huffman.m function [HC,L] = Huffman(p) % [HC,L] = HUFFMAN(p) % Generates Huffman codes for input symbols % with a given probability distribution p % The Huffman Codes are stored in the array HC % The code lengths are stored in the array L M = length(p); N = M; A = zeros(1,N-2); p1 = sort(p,'descend'); % Part I of the code generation



Lanjutan code di slide berikutnya…!!!



Contoh 3.1



Huffman.m



for i = 1:N-2 p1(M-1) = p1(M-1) + p1(M); s = find(p1(M-1) >= p1(1:M-2)); if ~isempty(s) loc = s(1); else loc = M-1; end T = p1(M-1); for k = M-2:-1:loc p1(k+1) = p1(k); end p1(loc) = T; A(N-2-i+1) = loc; M = M - 1; end Lanjutan code di slide berikutnya…!!!



Contoh 3.1 % Part II of the code generation HC = uint16(zeros(1,N)); L = uint16(ones(1,N)); HC(2) = 1; M = 2; j = 1; while j