Algoritma DMC

Algoritma 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.



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

Model Markov setelah cloning