Pertemuan 7 Compression

 Pertemuan 7 Compression 

1. Menjelaskan Monsep Kompresi Data

    Kompresi data adalah sebuah proses yang mengubah data input menjadi data output dengan ukuran yang lebih kecil. data dapat berupa karakter dalam file teks, angka yang merupakan contoh bentuk gelombang ucapan atau gambar, atau urutan angka yang dihasilkan oleh proses lain. alasan kita membutuhkan kompresi data adalah karena semakin banyak informasi yang kita hasilkan dan gunakan dalam bentuk digital terdiri dari angka yang di reprensentasikan oleh byte data. 

a). Teknik Kompresi Data 

      1). Lossless Compression, Teknik kompresi lossless, tidak melibatkan kehilangan informasi. jika data telah dikompresi tanpa kehilangan, maka data asli dapat dipulihkan dengan tepat dari data yang dikompresi. kompresi lossless umunnya digunakan untuk aplikasi yang tidak dapat mentolerir perbedaan apa pun antara data asli dan data rekonstruksi.

          Jika data dalam bentuk apa pun akan diproses atau "ditingkatkan" nanti untuk menghasilkan lebih banyak informasi, integritasnya harus dijaga. Misalnya, kita mengompresi gambar radiologis menjadi lossy mode dan perbedaan antara rekonstruksi Y dan X asli tidak dapat dideteksi secara visual.

        Data yang diperoleh dari satelit seringkali diolah kemudian untuk mendapatkan indikator numerik yang berbeda dari vegetasi, deforestasi, dan lain sebagainya. Jika data yang direkonstruksi tidak identik dengan data asli, pemrosesan dapat menghasilkan “peningkatan” atau perbedaan.

      2). Lossy Compression,   Teknik kompresi lossy melibatkan beberapa kehilangan informasi,dan data yang telah dikompresi menggunakan teknik lossy. Pada umumnya tidak dapat dipulihkan atau direkonstruksi dengan tepat. Sebagai imbalan untuk menerima distorsi ini dalam rekonstruksi, kita dapat memperoleh rasio kompresi yang jauh lebih tinggi daripada yang dimungkinkan dengan kompresi lossless.

b). Ukuran Kinerja 

      Algoritma kompresi dapat dievaluasi dengan beberapa cara yang berbeda. Kita dapat mengukur kompleksitas relatif dari algoritma memori yang diperlukan untuk mengimplementasikan algoritma, seberapa cepat kinerja algoritma pada mesin tertentu. Jumlah kompresi dan seberapa dekat algoritma tersebut menyerupai rekontruksi aslinya.

      Cara yang sangat logis untuk mengukur seberapa baik algoritme kompresi kumpulan data tertentu. Dengan melihat rasio jumlah bit yang diperlukan untuk mewakili data sebelum kompresi dengan jumlah bit yang diperlukan untuk merepresentasikan data setelah kompresi. Rasio ini disebut rasio kompresi.  Misalkan menyimpan gambar yang terdiri dari larik persegi 256 × 256 piksel membutuhkan 65.536 byte. Gambar dikompresi dan versi terkompresi membutuhkan 16.384 byte. Kami akan mengatakan bahwa rasio kompresinya adalah 4:1. Kita juga dapat merepresentasikan rasio kompresi dengan mengungkapkan pengurangan jumlah data yang diperlukan sebagai persentase dari ukuran data asli.

2). Memahami Pemodelan dan Pengkodean dalam Kompresi Data

     Meskipun persyaratan rekonstruksi dapat memaksa keputusan apakah skema kompresi menjadi lossy atau lossless. Skema kompresi yang tepat yang kami gunakan akan bergantung pada sejumlah faktor yang berbeda. Beberapa faktor terpenting adalah karakteristik data yang perlu dikompresi. Teknik kompresi yang akan bekerja dengan baik untuk kompresi teks mungkin tidak berfungsi dengan baik untuk mengompresi gambar. Setiap aplikasi menyajikan serangkaian tantangan yang berbeda.

      Pengembangan algoritma kompresi data untuk berbagai data dapat dibagi menjadi dua tahap. Fase pertama biasanya disebut sebagai pemodelan. Dalam fase ini, kami mencoba mengekstrak informasi tentang redundansi yang ada dalam data dan mendeskripsikan redundansi tersebut dalam bentuk model. Tahap kedua disebut pengkodean. Deskripsi model dan "deskripsi" tentang perbedaan data dari model dienkode, biasanya menggunakan alfabet biner. Perbedaan antara data dan model sering disebut sebagai residual.

Tabel 7. Consider the following sequence of numbers {x1, x2 .x3,...};

      Jika kita mengirim atau menyimpan representasi biner dari angka-angka

ini, kita perlu menggunakan 5 bit per sampel. Namun, dengan mengeksploitasi

struktur dalam data, kita dapat merepresentasikan urutan tersebut menggunakan

bit yang lebih sedikit. 

Xn = n+8 n= 1,2.. 

      Struktur deret angka khusus ini dapat dikarakterisasi dengan persamaan.

Jadi,ˆx1=9,x1=9,ˆx2=10, x2 = 11, dan seterusnya. Untuk memanfaatkan

struktur ini, mari kita periksa Perbedaan antara data dan model. Perbedaan (atau

sisa) diberikan oleh urutan.

en = xn - ^xn : 0 1 0  - 1 1 -1 0 1 -1 -1 1 1 1 

      Urutan sisa hanya terdiri dari tiga angka {−1, 0, 1}. Jika kita menetapkan

kode  00  hingga −1, kode 01 hingga 0, dan kode 10  hingga 1, kita  perlu

menggunakan 2 bit untuk mewakili setiap elemen dari urutan residual. Oleh

karena itu, kita dapat memperoleh kompresi dengan mengirimkan atau

menyimpan parameter model dan urutan sisa. Pengkodean dapat dilakukan

secara tepat jika kompresi yang diperlukan adalah lossless, atau perkiraan jika

kompresi dapat menjadi lossy.

Gambar 13. Urutan Nilai Data

Gambar 14. Urutan Nilai Data

a. THE HUFFMAN CODING ALGORITHM

Prosedur Huffman didasarkan pada dua pengamatan mengenai kode prefiks yang optimal:

1).  Dalam kode yang optimal, simbol yang muncul lebih sering (memiliki kemungkinan kemunculan yang lebih tinggi) akan memiliki codeword yang lebih pendek daripada simbol yang lebih jarang muncul.

2).  Dalam kode yang optimal, dua simbol yang paling jarang muncul akan memiliki panjang yang sama

b. NONBINARY HUFFMAN CODE

Prosedur pengkodean biner Huffman dapat dengan mudah diperluas ke kasus non-biner di mana elemen kode berasal dari alfabet m-binary, dan m tidak sama dengan dua. Ingatlah bahwa kami memperoleh algoritma Huffman berdasarkan pengamatan bahwa dalam kode awalan biner yang optimal:

1).  Simbol yang muncul lebih sering (memiliki probabilitas kemunculan yang lebih tinggi) akan memiliki codeword yang lebih pendek daripada simbol yang lebih jarang muncul.

2).  Kedua simbol yang paling jarang muncul akan memiliki panjang yang

sama.

c. ADAPTIVE HUFFMAN CODING

Pengkodean Huffman membutuhkan pengetahuan tentang kemungkinan urutan sumber. Jika pengetahuan ini tidak tersedia, pengkodean Huffman menjadi prosedur dua jalur: statistik dikumpulkan pada lintasan pertama, dan sumber dikodekan pada lintasan kedua. Untuk mengubah algoritma ini menjadi one-pass prosedur, Faller dan Gallagher secara

independen mengembangkan algoritma adaptif untuk membangun kode Huffman berdasarkan statistik dari simbol yang sudah ditemukan. Ini kemudian diperbaiki oleh Knuth dan Vitter

d. GOLOMBS CODE

Kode Golomb-Rice milik keluarga kode yang dirancang untuk menyandikan bilangan bulat dengan asumsi bahwa semakin besar bilangan bulat, semakin rendah kemungkinan terjadinya. Kode paling sederhana untuk situasi ini adalah kode unary.

3). Memahami Jenis Kompresi Data

a. MEDIA-SPECIFIC COMPRESSION

Media specific compression dirancang khusus untuk data media seperti gambar, audio, video, dan sejenisnya. Kemungkinan besar, jenis file dan kompresor ini membentuk sebagian besar konten yang dikirim, diterima, dimanipulasi, disimpan, dan ditampilkan oleh aplikasi Anda kepada pengguna. Pepatah lama, "Sebuah gambar bernilai ribuan kata," benar-benar benar dalam hal kompresi data: gambar 1024 x 1024 RGB adalah 3 MB data. Jika Anda menganggap huruf berenkode ASCII, Anda dapat menampilkan 3.145.728 huruf untuk ukuran yang sama.

b. GENERAL-PURPOSE COMPRESSION

Kompresi umumnya adalah algoritme seperti DEFLATE, GZIP, BZIP2, LZMA, dan PAQ, yang menggabungkan berbagai transformasi lossless untuk menghasilkan penghematan untuk file nonmedia seperti teks, kode sumber, data serial, dan konten biner lainnya yang tidak akan mentolerir kompresi data lossy. Ada banyak penelitian yang sehat di bidang ini Berhenti dengan Tolak Ukur Kompresi dalam Teks Besar menunjukkan kumpulan kompresi tujuan umum yang semuanya telah ditugaskan untuk mengompresi file teks besar,

untuk mengukur bagaimana mereka menumpuk satu sama lain. Dan algoritma baru terus dikembangkan.

4). Memahami teknik kompresi data

Sebelum beralih ke gangguan kompresi ke setiap bagian aplikasi mewah kita, penting untuk mencatat semua trade-off dan kasus penggunaan yang terlibat. Tidak setiap algoritme cocok untuk setiap kasus penggunaan, dan dalam beberapa kasus, implementasi yang berbeda dari format kompresi yang sama mungkin lebih sesuai dengan kebutuhan kita.

a. Skenario Penggunaan Kompresi, Mari kita mulai diskusi ini dengan menyetel tahapan di mana data dikompresi, disimpan, dan didekompresi. Ini sangat penting untuk memahami dari mana data berasal dan ke mana perginya, karena interaksi penting antara pembuat enkode dan dekoder, yang akan kita bicarakan lebih lanjut nanti. Pertama, mari kita lihat empat skenario umum. 

b. Compressed Offline, Decompressed On-Client, Dalam skenario pertama ini,

data dikompresi di suatu tempat yang tidak terkait dengan klien, lalu

didistribusikan ke klien, tempat data tersebut didekompresi untuk digunakan.

c. Compressed On-Client, Decompressed  In-Cloud, Sebagian besar aplikasi

media sosial modern menghasilkan banyak konten di klien dan kemudian

mendorongnya ke cloud untuk diproses dan didistribusikan ke sesama

pengguna sosial lainnya. Dalam situasi ini, beberapa kompresi ringan

biasanya dilakukan pada klien, untuk mengurangi jumlah overhead dalam

komunikasi keluar. Misalnya, mengambil paket data sosial, dan membuat

serialisasi dengan format serialisasi biner, lalu mengompresi gzip sebelum

mengirimnya ke server.

d. Compressed  In-Cloud, Decompressed  On-Client, Data yang dikompresi di

cloud dibagi menjadi dua bucket utama, yang memiliki karakteristik yang

sangat berbeda, yaitu:

    1).  Dynamic data  that  is  generated  by  the  cloud  resource, ketika klien

meminta hasil dari beberapa operasi database, atau file server

mengirimkan data tata letak dinamis, klien menunggu konten dibuat.

Waktu yang dibutuhkan server untuk membuat dan mengompresi data itu

sangat penting; jika tidak, klien akan mengalami latensi jaringan.

    2).  Large  data  that’s  passed off  to  the  cloud  for  efficient  computing,

Pentingnya skenario ini sering kali didorong untuk memastikan

minimalisasi bit untuk media yang ada. Misalnya, bayangkan memiliki dua

gigabyte file PNG yang perlu dikonversi ke gambar WebP dengan 10

resolusi berbeda, atau 1.200 jam video yang harus dikonversi ke H.264

sebelum ditampilkan. 

e. Compressed  On-Client, Decompressed On-Client, Dalam kasus ini, klien

menghasilkan data, mengompresnya, dan kemudian mengirimkannya ke klien

lain untuk mendekompresi