Kompresi Teks

  • 0

Kompresi Teks

Category : Uncategorized

 

Pada teori informasi, jika probabilitas kemunculan suatu simbol dinyatakan dengan Pi(x), maka menurut Shannon, jumlah informasi dirumuskan sebagai:  bit dan

Entropi menyatakan jumlah informasi yang dikandung dalam suatu pesan, yang didasarkan pada data statistiknya. Sehingga  Entropi dihitung dengan : bit.

Dalam kompresi, terdapat beberapa kelas algoritma, yaitu :

 

Dictionary :

Teknik buku kode

Mengkopi data yang sama, atau sering berulang

Mengirimkan alamat dictionary bukan data.

 

Statistical :

Menghitung frekuensi dan probabilitas kondisional dari data

Kode yang muncul dengan probabilitas yang paling tinggi dikodekan dengan panjang kode yang paling pendek.

Dalam hal ini kompresi teks, termasuk dalam kompresi Lossless. Losing bit dalam rekonstruksi tidak dapat diterima untuk beberapa format data :

  • program code
  • network data
  • format not known
  • legal/military reason.

Huffman Coder

Merupakan metode untuk membangkitkan kode dengan panjang rata-rata bit yang minimum. Prosedur Huffman Coder :

  1. Huffman code dikonstruksi dari urutan probabilitas input menurut nilai peluang yahng dimiliki.
  2. Dua peluang yang paling kecil dijumlahkan untuk membentuk set yang baru dari peluang.
  3. Set yang baru dari peluang, yang memiliki satu peluang yang lebih kecil dari set asal, disusun kembali menurut magnitudanya. Untuk peluang yang sama dapat disusun dalam beberapa cara.
  4. Ketika didapati 2 nilai probabilitas, maka proses dihentikan.

 

Arithmetic Coding

Merupakan teknik untuk coding yang mengijinkan informasi dari pesan dalam deretan pesan dikombinasikan untuk sharing bit yang sama. Teknik ini membolehkan jumlah total dari bit yang dikirimkan mendekati jumlah dari informasi sendiri dari pesan individual.

Ide utama dari Arithmetic coding adalah untuk menyatakan setiap deretan yang mungkin dari n pesan dengan interval yang terpisah antara 0 dan 1, seperti interval dari 0.2 sampai 0.5.

 

Ilustrasi :

Teknik lain yang digunakan dalam mengkonstruksi sebuah enkoder sumber adalah menyusun pesan-pesan dalam urutan peluang yang mengecil dan membagi pesan tersebut menjadi dua bagian yang memiliki peluang mendekati sama. Pesan2 pada bagian pertama diberi bit 0 dan bagian kedua diberi bit 1. Prosedur tersebut kini diterapkan lagi untuk setiap bagian secara terpisah, dan diteruskan hingga tak lagi dapat dilakukan pembagian lagi. Dengan Menggunakan algoritma tersebut, maka kode word dari 6 pesan yang terjadi dengan urutan peluang 1/3,1/3,1/6,1/12,1/24,1/24, adalah :

A 1/3 0 0    
B 1/3 0 1    
C 1/6 1 0    
D 1/12 1 1 0  
E 1/24 1 1 1 0
F 1/24 1 1 1 1

Dengan demikian code words yang diperoleh dengan algoritma diatas adalah :

00 01 10 110 1110 1111 (lihat tabel dibaca dari atas kebawah )

Referensi ; [pdf]

 

 

 

 

 

 

 

 

 

 

Facebook Comments

-- Download Kompresi Teks as PDF --



Leave a Reply

Archives