Teknik Kompresi - Lossless

Kompresi Data adalah teknik mengecilkan data sehingga di peroleh file dengan ukuran yang lebih kecil dari pada ukuran aslinya. Pihak pengirim kompresi data harus menggunakan teknik yang sudah baku (encoding) dan pihak penerima juga menggunakan teknik dekompresi (decoding) yang sama dengan si pengirim.

Lossless data kompresi adalah kelas dari algoritma data kompresi yang memungkinkan data yang asli dapat disusun kembali dari data kompresi. Ciri-cirinya adalah:

•       Metode lossless menghasilkan data yang identik dengan data aslinya. Hasilnya sama seperti data sebelum proses kompresi.

                Contoh : ZIP, RAR, GZIP

¢  Data tidak berubah atau hilang pada proses kompresi atau dekompresi. Teknik ini digunakan jika kita membutuhkan data yang setelah dikompresi harus dapat diekstrak/dekompres lagi tepat sama. Biasanya digunakan jika akurasi data sangat penting

¢  Ratio kompresi (Rasio kompresi yaitu, ukuran file yang dikompresi dibanding yang tak terkompresi dari file) dengan metode ini sangat rendah

¢  Menghilangkan perulangan karakter

¢  Kadang ada data-data yang setelah dikompresi dengan teknikini ukurannya sama atau lebih besar

Lossless vs Lossy

Metode Kompresi Lossless

Kompresi Audio

•       Loseless

                format : FLAC digunakan oleh audio engineer

•       Lossless 

•       Lossless audio codec tidak mempunyai masalah Dalam kualitas suara, penggunaannya dapat difokuskan pada:

–      Kecepatan kompresi dan dekompresi

–      Derajat kompresi

–      Dukungan hardware dan software

•       Lossless  : proses dekompresi yang menghasilkan data yang sama dengan yang Semula

•       Kompresi lossless audio menghasilkan representasi data digital yang dapat diperluas ke tepat digital duplikat dari stream audio asli.Hal ini kontras dengan perubahan ireversibel pada playback dari teknik kompresi lossy seperti Vorbis dan MP3 . rasio kompresi adalah sama dengan yang untuk data kompresi lossless generik (sekitar 50-60% dari ukuran asli  ), dan secara substansial kurang dari untuk kompresi lossy, yang biasanya menghasilkan 5-20% dari ukuran aslinya

Standart compressing lossless yaitu :

¢  Packbits encoding (Run-length encoding)

¢  CCIT Group 3 1D

¢  CCIT GRoup 3 2D

¢  CCIT Group 4

¢  Lempel-Ziv and Welch aalgoruthm LZW

Huffman Coding

·         Berbasis pada perhitungan statistik

·         Mengunakan bantuan pohon biner

·         Data yang frekuensi munculnya paling banyak dikode dengan jumlah bit terkecil

·         Data yang frekuensi munculnya paling sedikit dikode dengan jumlah bit terbesar

Contoh Kompresi Lossless Pada Teks

¢  Static Huffman Coding

¢  Misal : MAMA SAYA

                                                A = 4 ®  4/8 = 0.5

                                                M = 2 ®   2/8 = 0.25

                                                S = 1        ®   1/8 = 0.125

                                                Y = 1        ®   1/8 = 0.125

                                Total = 8 karakter

¢  Sehingga w(A) = 1, w(M) = 00, w(S) = 010, dan w(Y) = 011

Lempel-Ziv-Welch coding

-          Asumsi setiap karakter dikode dengan 8 bit (nilai code 256)

-           Membentuk table gabungan karakter (kata dalam kamus)

-           Tabel ini menyimpan kode kata dengan jumlah bit tetap  (umumnya maksimum 12 bit)

Contoh Lempel-Ziv-Welsh Coding

Ecoding:

¢  Input : 1 2 4 5 2 3 4 6 1

¢  Decoding :

Lossless pada kompresi citra

¢  Teknik kompresi citra dimana tidak ada satupun informasi citra yang dihilangkan.

¢  Biasa digunakan pada citra medis.

Contoh Kompresi Lossless Pada Gambar

¢  Original Image (lossless PNG, 60.1 KB size) - uncompressed is 108.5 KB

n  Low Compression (84% less information than uncompressed PNG, 9.37 KB)

n  Medium Compression (92% less information than uncompressed PNG, 4.82 KB)

n  High Compression (98% less information than uncompressed PNG, 1.14 KB)

¢  Metode loseless:

—  Run Length Encoding,

—  Entropy Encoding(Huffman, Aritmatik), dan

—  Adaptive Dictionary Based (LZW)

Lossless pada video

·         Konsepnya sama dengan pada gambar

·         Contoh aplikasinya adalah frekuensi temporary

Lossless pada audio

¢  Format kompresi lossless untuk audio

¢  Shorten (paling tua), Free Lossless Audio Codec (FLAC), Apple Lossless, MPEG-4 ALS, Monkey's Audio, WavPack, True Audio.

¢  Ada dua tahap utama dalam kompresi lossless pada data audio, yaitu

¢  prediction dan

¢  residual coding

¢  Contoh aplikasinya: frekuensi masking, temporary masking

Sebagian besar program kompresi lossless melakukan dua hal secara berurutan:

—  langkah pertama menghasilkan model statistik untuk data input, dan

—  langkah kedua menggunakan model ini untuk memasukkan data peta ke urutan bit sedemikian rupa sehingga"kemungkinan" (misalnya sering dijumpai) data akan menghasilkan output lebih pendek dari "mustahil" data.

Huffman Coding

•       Digunakan untuk pengkodean teks, citra dan video

•       Kompresi dengan algoritma Huffman Coding dilakukan dengan cara :

–      Hitung frekuensi kemunculan setiap simbol.

–      Pilih dua buah simbol dengan frekuensi terkecil, lalu gabungkan dalam satu tangkai.

–      Ulangi langkah kedua hingga tidak ada lagi tangkai yang dapat digabungkan.

RLE Coding

•       Prinsip dasarnya adalah menghitung jumlah/panjang data yang sama dalam serangkain data yang akan dikompres

•       Contoh pada dokumen hitam H (tulisan) dan putih P (latar belakang dokumen), berikut misalnya data pada satu baris dokumen yang direpresntasikan dalam pixel :

                PPPPPPPPPPPPHPPPPPPPPPPPPPPHHHPPPPPPPPPPPPPPPPPPPPPPPHPPPPPPPPPPP

                Bentuk kompresinya adalah : 12P1H14P3H23P1H11P

•       Contoh Aplikasi:

–      Kompresi citra format bmp pada Windows dan OS/2 untuk citra 1, 4 dan 8 bit/pixel

–      Citra format PCX 8 dan 24 bit/pixel

–      Fax dan scanner hitam putih

Lempel- Ziv – Welch Coding ( LZW )

•       Kamus adaptif yang dapat digunakan dalam GIF dan TIFF

•       Menggunakan Teknik Dictionary dimana string karakter digantikan oleh kode tabel yang dibuat setiap ada string yang masuk

Arithmetic Coding

•       Menggantikan satu deretan simbol input dengan sebuah bilangan floating point.

•       Semakin panjang dan semakin kompleks pesan yang dikodekan , semakin banyak bit yang diperlukan untuk pengkodean tersebut.

Kelebihan dan Kekurangan

•       kompresi lossless menggunakan algoritma RLE dan Huffman Coding akan tergantung pada data yang akan dikompresi.

–      Dalam algoritma RLE (Run Length Encoding), jika karakter yang muncul berbeda-beda maka ukuran file akan lebih besar.

–      Dalam penerapan Huffman Coding dibutuhkan tempat pada awal (header) file untuk menyimpan informasi yang diperlukan untuk proses dekompresi (decoding).

–      Kompresi pada data audio, image, dan video juga sebenarnya dapat menggunakan metode general purpose seperti Huffman Coding, RLE, dan algoritma kompresi lossless lainnya.

–