Dynamic Markov Compressioin atau disingkat dengan DMC adalah salah satu metode kopresi lossless. Metode ini dikembangkan oleh Gordon Cormack dan Nigel Horspool yang menggunakan algoritma pengkodean aritmatika.
Algoritma
DMC memprediksi dan kode satu bit pada suatu waktu. Ini berbeda dari PPM dalam kode itu bit bukan byte, dan dari konteks pencampuran algoritma seperti PAQ bahwa hanya ada satu konteks per prediksi. Bit diprediksi kemudian dikodekan menggunakan pengkodean aritmatika.
Aritmatika coding
Sebuah aritmatika bitwise coder seperti DMC memiliki dua komponen, prediktor dan coder aritmatika. Prediktor yang menerima sebuah n-bit string masukan x = x 1 x 2 ... x n dan memberikan itu probabilitas p (x), dinyatakan sebagai produk dari serangkaian prediksi, p (x 1) p (x 2 | x 1) p (x 3 | x 1 x 2) ... p (x n | x 1 x 2 ... x n -1). Coder aritmatika mempertahankan dua angka biner presisi tinggi, p rendah dan p tinggi, yang mewakili berbagai kemungkinan untuk total probabilitas bahwa model akan menugaskan untuk semua string leksikografis kurang dari x, mengingat bit x lihat sejauh ini. Kode dikompresi untuk x adalah p x, terpendek bit string yang mewakili angka antara p rendah dan p tinggi. Itu selalu mungkin untuk menemukan nomor dalam kisaran ini tidak lebih dari satu bit lebih panjang dari Shannon limit, log 2 1 / p (x '). Satu nomor tersebut dapat diperoleh dari p tinggi dengan menjatuhkan semua bit tertinggal setelah bit pertama yang berbeda dari p rendah.
Kompresi hasil sebagai berikut. Kisaran awal diatur ke p rendah = 0, p tinggi = 1. Untuk setiap bit, prediktor memperkirakan p 0 = p (x i = 0 | x 1 x 2 ... x i -1) dan p 1 = 1 - p 0, probabilitas dari 0 atau 1, masing-masing. Coder aritmatika kemudian membagi rentang saat ini, (p rendah, p tinggi) menjadi dua bagian secara proporsional dengan p 0 dan p 1. Kemudian subrange sesuai dengan berikutnya bit x i menjadi rentang baru.
Untuk dekompresi, prediktor yang membuat seri identik prediksi, mengingat bit didekompresi sejauh ini. Coder aritmatika membuat seri identik berbagai perpecahan, kemudian memilih kisaran mengandung p x dan output bit x i sesuai dengan subrange itu.
Dalam prakteknya, tidak perlu untuk menjaga p rendah dan p tinggi di memori untuk presisi tinggi. Sebagai kisaran menyempit, bit terkemuka kedua nomor akan sama, dan dapat menjadi output langsung.
Di bawah ini adalah tampilan dari program kompresi dengan metode DMC :
Comments
Post a Comment