Algoritma LZW

12:45:00 PM konixbam

winrar_kompresorAlgoritma LZW (Lempel-Ziv-Welch) dikembangkan oleh Terry A.Welch dari metode kompresi sebelumnya yang ditemukan oleh Abraham Lempel dan Jacob Ziv pada tahun 1977. Algortima ini menggunakan teknik dictionary dalam kompresinya. Dimana string karakter digantikan oleh kode table yang dibuat setiap ada string yang masuk. Tabel dibuat untuk referensi masukan string selanjutnya. Ukuran tabel dictionary pada algoritma LZW asli adalah 4096 sampel atau 12 bit, dimana 256 sampel pertama digunakan untuk table karakter single (Extended ASCII), dan sisanya digunakan untuk pasangan karakter atau string dalam data input.

Algoritma LZW melakukan kompresi dengan mengunakan kode table 256 hingga 4095 untuk mengkodekan pasangan byte atau string. Dengan metode ini banyak string yang dapat dikodekan dengan mengacu pada string yang telah muncul sebelumnya dalam teks.

Algoritma kompresi LZW secara lengkap :

1. Dictionary (kamus) diinisialisasi dengan semua karakter dasar yang ada : {‘A’..’Z’,’a’..’z’,’0’..’9’}.
2. W <- karakter pertama dalam stream karakter.
3. K <- karakter berikutnya dalam stream karakter.
4. Lakukan pengecekan apakah (W+K) terdapat dalam Dictionary
a. Jika ya, maka W <- W + K (gabungkan W dan K menjadi string baru).
b. Jika tidak, maka :
- Output sebuah kode untuk menggantikan string W.
- Tambahkan string (W+ K) ke dalam dictionary dan berikan nomor/kode berikutnya yang belum digunakan dalam dictionary untuk string tersebut.
- W <- K.
5. Lakukan pengecekan apakah masih ada karakter berikutnya dalam stream karakter.
a. Jika ya, maka kembali ke langkah 2.
b. Jika tidak, maka output kode yang menggantikan string W, lalu terminasi proses (stop).


LZW1
Flowchart Algoritma LZW


Sebagai contoh, string “ABBABABAC” akan dikompresi dengan LZW. Isi pada dictionary diset dengan tiga karakter dasar yang ada yaitu: “A”, “B”, dan “C”.

LZW2
Tahapan Kompresi LZW


Kolom posisi menyatakan posisi sekarang dari stream karakter dan kolom karakter menyatakan karakter yang terdapat pada posisi tersebut. Kolom dictionary menyatakan string baru yang sudah ditambahkan ke dalam dictionary dan nomor indeks untuk string tersebut ditulis dalam kurung siku. Kolom output menyatakan kode output yang dihasilkan oleh langkah kompresi.

LZW3
Hasil Proses Kompresi


Proses dekompresi data pada algoritma LZW tidak jauh berbeda dengan proses kompresinya. Pada dekompresi LZW, juga dibuat tabel dictionary dari data input kompresi, sehingga tidak diperlukan penyertaan tabel dictionary ke dalam data kompresi.

Berikut algoritma dekompresi LZW :

1. Dictionary diinisialisasi dengan semua karakter dasar yang ada : {‘A’..’Z’,’a’..’z’,’0’..’9’}.
2. CW kode pertama dari stream salah satu karakter dasar).
3. Lihat dictionary dan output string dari kode tersebut (string.CW) ke stream karakter.
4. PW <- CW; CW <- kode berikutnya dari stream kode.
5. Apakah string.CW terdapat dalam dictionary ?
a. Jika ada, maka :
- Output string.CW ke stream karakter
- P <- string.PW
- C <- karakter pertama dari string.CW
-Tambahkan string (P+C) ke dalam dictionary
b. Jika tidak, maka :
- P <- string.PW
- C <- karakter pertama dari string.PW
-Output string (P+C) ke stream tambahkan string tersebut ke dalam (sekarang berkorespondensi dengan CW)
6. Apakah terdapat kode lagi di stream code?
a. Jika ya, maka kembali ke langkah 4.
b. Jika tidak, maka terminasi proses (stop).


blogger-emoticon.blogspot.com
read more >

Algoritma DMC

9:05:00 AM konixbam

DMC algoritmAlgoritma DMC (Dynamic Markov Compression) adalah algoritma kompresi data lossless yang dikembangkan oleh Gordon Cormack dan Nigel Horspool. Algoritma ini menggunakan pengkodean aritmatika mirip dengan prediksi pencocokan sebagian (PPM), kecuali bahwa input diperkirakan satu bit pada satu waktu (bukan dari satu byte pada satu waktu). DMC memiliki rasio kompresi yang baik dan kecepatan moderat, mirip dengan PPM, tapi memerlukan sedikit lebih banyak memori dan juga tidak diterapkan secara luas. Beberapa implementasinya baru-baru ini mencakup program kompresi eksperimental pengait oleh Nania Francesco Antonio, ocamyd oleh Frank Schwellinger, dan sebagai submodel di paq8l oleh Matt Mahoney. Ini didasarkan pada pelaksanaannya pada tahun 1993 di C oleh Gordon Cormack. Pada DMC, input simbol alfabet diproses per bit, bukan per byte. Setiap output transisi menandakan berapa banyak simbol tersebut muncul. Penghitungan tersebut dipakai untuk memperkirakan probabilitas dari transisi.
Contoh: Transisi yang keluar dari state 1 diberi label 0/5, artinya bit 0 di state 1 terjadi sebanyak 5 kali.

DMC

Secara umum, transisi ditandai dengan 0/p atau 1/q dimana p dan q menunjukkan jumlah transisi dari state dengan input 0 atau 1. Bahwa nilai probabilitas input selanjutnya bernilai 0 adalah p/(p+q) dan input selanjutnya bernilai 1 adalah q/(p+q). Lalu bila bit sesudahnya ternyata bernilai 0, jumlah bit 0 ditransisi dan ditambah satu menjadi p+1. Begitu pula bila bit sesudahnya ternyata bernilai 1, jumlah bit 1 sekarang ditransisi dan ditambah satu menjadi q+1.
Algoritma kompresi DMC :

1. s <- 1 ( jumlah state sekarang) 2. t <- 1 (state sekarang) 3. T[1][0] = T[1][1] <- 1 (model inisialisasi) 4. C[1][0] = C[1][1] <- 1 (inisialisasi untuk menghindari masalah frekuensi nol) 5. Untuk setiap input bit e : a. u <- t b. t <- T[u][e] (ikuti transisi) c. Kodekan e dengan probabilitas : C[u][e] / (C[u][0] + C[u][1]) d. C[u][e] <- C[u][e]+1 e. Jika ambang batas cloning tercapai, maka : - s <- s + 1 (state baru t’) - T[u][e] <- s ; T[s][0] <- T[t][0] ; T[s][1] <- T[t][1] - Pindahkan beberapa dari C[t] ke C[s]




Masalah tidak terdapatnya kemunculan suatu bit pada state dapat diatasi dengan menginisialisasi model awal state dengan satu. Probabilitas dihitung menggunakan frekuensi relatif dari dua transisi yang keluar dari state yang baru.
Jika frekuensi transisi dari suatu state t ke state sebelumnya (state u), sangat tinggi, maka state t dapat di-cloning. Ambang batas nilai cloning harus disetujui oleh encoder dan decoder. State yang di-cloning diberi simbol t’.

Aturan cloning adalah sebagai berikut :
1. Semua transisi dari state u dikirim ke state t’. Semua transisi dari state lain ke state t tidak dirubah.
2. Jumlah transisi yang keluar dari t’ harus mempunyai rasio yang sama (antara 0 dan 1) dengan jumlah transisi yang keluar dari t.
3. Jumlah transisi yang keluar dari t dan t’ diatur supaya mempunyai nilai yang sama dengan jumlah transisi yang masuk.


Model Markov sebelum cloning


DMC3
Model Markov setelah cloning

blogger-emoticon.blogspot.com

read more >

Algoritma Huffman

10:03:00 AM konixbam

huffman_tree_tAlgoritma Huffman, yang dibuat oleh seorang mahasiswa MIT bernama David Huffman, merupakan salah satu metode paling lama dan paling terkenal dalam kompresi teks. Algoritma Huffman menggunakan prinsip pengkodean yang mirip dengan kode Morse, yaitu tiap karakter (simbol) dikodekan hanya dengan rangkaian beberapa bit, dimana karakter yang sering muncul dikodekan dengan rangkaian bit yang pendek dan karakter yang jarang muncul dikodekan dengan rangkaian bit yang lebih panjang.


1. Pass pertama, Baca (scan) file input dari awal hingga akhir untuk menghitung frekuensi kemunculan tiap karakter dalam file. n <- jumlah semua karakter dalam file input. T <- daftar semua karakter dan nilai peluang kemunculannya dalam file input. Tiap karakter menjadi node daun pada pohon Huffman.
2. Pass kedua, Ulangi sebanyak (n -1) kali :
a. Item m1 dan m2 <- dua subset dalam T dengan nilai peluang yang terkecil.
b. Gantikan m1 dan m2 dengan sebuah item {m1,m2} dalam T, dimana nilai peluang dari item yang baru ini adalah penjumlahan dari nilai peluang m1 dan m2.
c. Buat node baru {m1, m2} sebagai father node dari node m1 dan m2 dalam pohon Huffman.
3. T sekarang tinggal berisi satu item, dan item ini sekaligus menjadi node akar pohon Huffman. Panjang kode untuk suatu simbol adalah jumlah berapa kali simbol tersebut bergabung dengan item lain dalam T.


Sebagai contoh, dalam kode ASCII string 7 huruf “ABACCDA” membutuhkan representasi 7 × 8 bit = 56 bit (7 byte), dengan rincian sebagai berikut:
gambar_1_bit_Huffman
Untuk mengurangi jumlah bit yang dibutuhkan, panjang kode untuk tiap karakter dapat dipersingkat, terutama untuk karakter yang frekuensi kemunculannya besar. Pada string di atas, frekuensi kemunculan A = 3, B = 1, C = 2, dan D = 1, sehingga dengan menggunakan algoritma di atas diperoleh kode Huffman sebagai berikut:

gambar_2_bit_Huffman
Dengan menggunakan kode Huffman ini, string “ABACCDA” direpresentasikan menjadi rangkaian bit : 0 110 0 10 10 111 0. Jadi, jumlah bit yang dibutuhkan hanya 13 bit. Tampak bahwa kode untuk sebuah simbol/karakter tidak boleh menjadi awalan dari kode simbol yang lain guna menghindari keraguan (ambiguitas) dalam proses dekompresi atau decoding. Karena tiap kode Huffman yang dihasilkan unik, maka proses dekompresi dapat dilakukan dengan mudah.
Contoh: saat membaca kode bit pertama dalam rangkaian bit “[0]11001010110”, yaitu bit “0”, dapat langsung disimpulkan bahwa kode bit “0” merupakan pemetaan dari simbol “A”. Kemudian baca kode bit selanjutnya, yaitu bit “1”. Tidak ada kode Huffman “1”, lalu baca kode bit selanjutnya, sehingga menjadi “11”. Tidak ada juga kode Huffman “11”, lalu baca lagi kode bit berikutnya, sehingga menjadi “110”. Rangkaian kode bit “110” adalah pemetaan dari simbol “B”. Metode Huffman yang diterapkan dalam penelitian ini adalah tipe statik, dimana dilakukan dua kali pembacaan (two-pass) terhadap file yang akan dikompresi; pertama untuk menghitung frekuensi kemunculan karakter dalam pembentukan pohon Huffman, dan kedua untuk mengkodekan simbol dalam kode Huffman.blogger-emoticon.blogspot.com
huffman_tree
Untuk menguraikan kembali data yang sudah dikodekan sebelumnya dengan algoritma Huffman, dapat digunakan cara sebagai berikut :
1. Baca bit pertama dari string biner masukan
2. Lakukan traversal pada pohon Huffman mulai dari akar sesuai dengan bit yang dibaca. Jika bit yang dibaca adalah 0 maka baca anak kiri, tetapi jika bit yang dibaca adalah 1 maka baca anak kanan.
3. Jika anak dari pohon bukan daun (simpul tanpa anak) maka baca bit berikutnya dari string biner masukan.
4. Hal ini diulang (traversal) hingga ditemukan daun.
5. Pada daun tersebut simbol ditemukan dan proses penguraian kode selesai.
6. Proses penguraian kode ini dilakukan hingga keseluruhan string biner masukan diproses.
blogger-emoticon.blogspot.com
read more >