## PERBANDINGAN METODE PUNCTURED ELIAS CODE DAN HUFFMAN PADA KOMPRESI FILE TEXT

## Dedek Andri Yansyah
Mahasiswa Teknik Informatika STMIK Budi Darma Jl. Sisingamangaraja No.338 Simpang Limun Medan

## ABSTRAK
Kompresi  data  bertujuan  untuk  mengurangi  ukuran  file  sebelum  menyimpan  atau  memindahkan  data  ke  dalam  media penyimpanan. Huffman dan Punctured Elias Codes adalah dua algoritma yang digunakan untuk proses kompresi  pada skripsi ini. Kompresi  data dengan ke dua algoritma tersebut digunakan pada kompresi  file teks. Pada dasarnya ke dua algoritma ini mempunyai cara kerja yang sama. Dimulai dengan pengurutan karakter berdasarkan frekuensinya, pembentukan pohon biner dan  diakhiri  dengan pembentukan  kode. Pada algoritma Huffman, pohon biner  dibentuk  dari  daun  hingga akar dan  disebut dengan pembentukan pohon dari bawah ke atas. Sebaliknya, Metode Punctured Elias Codes terdapat dua kode yaitu P1 dan P2.  Kompresi  file  teks  dilakukan  dengan  membaca  input  String  pada  file  teks  (*.txt  dan  *.doc)  dan  mengkodekan  String menggunakan Punctured Elias Code P1 atau P2, kemudian melakukan proses kompresi.  Hasil akhir dari kompresi adalah file berekstensi  *.header  sebagai  informasi  kode  dan  karakter  dari  string  dan  *.pec  yang  merupakan  String  bit  hasil  kompresi yang dapat didekompresi.Pada skripsi ini dibuat perangkat lunak yang menggunakan bahasa pemrograman  Visual Basic.Net 2008  untuk  membandingkan  ke  dua  algoritma  kompresi    tersebut.  Perbandingan  dilakukan  dalam  hal  rasio  kompresi    dan kecepatan proses file teks hasil kompresi.
Kata Kunci : Huffman, Punctured Elias Codes, Kompresi

## I. PENDAHULUAN
Pemampatan
data (data compression)
merupakan salah satu kajian di dalam  ilmu komputer yang bertujuan untuk mengurangi ukuran file sebelum menyimpan  atau  memindahkan  data  tersebut  ke dalam  media  penyimpanan  ( storage  device ).  Media penyimpanan  seperti floppy  disk ,  hard disk dan  CD ( Compact  Disc )  mempunyai  kapasitas  yang  terbatas. Jika  data  yang  akan  disimpan  pada  media penyimpanan  semakin  bertambahdan  berukuran besar,  maka  media  penyimpanan  tidak  dapat menyimpan  data  tersebut  karena  melebihi  kapasitas. Oleh  karena  itu,  untuk  mengatasi  masalah  ini digunakan lah pemampatan data.
Kompresi data adalah proses yang mengkonversi sebuah masukan berupa aliran data ( the source atau  data  asli  mentah)  menjadi  suatu  aliran data  lain  ( the  Output ,  aliran  bit  atau  aliran  sudah dikompres)  yang  memiliki  ukuran  lebih  kecil. Berdasarkan  adanya  kemungkinan  data  setelah dikompres dapat direkonstruksi kembali ke data yang asli, teknik kompresi data dibagi  menjadi dua  bagian yaitu  kompresi lossless dan  kompresi Lossy . Kompresi lossless memungkinkan data dapat dikembalikan ke data yang asli secara utuh atau tanpa ada  informasi  yang  hilang  dalam  data  tersebut. Sedangkan kompresi Lossy tidak dapat mengembalikan  data  yang  telah  dikompres  secara utuh dari data yang asli pada saat proses dekompresi.
Punctured  Elias  Codes adalah  suatu  metode yang  dirancang  oleh  Peter  Fenwick  dalam  sebuah percobaan untuk meningkatkan performa the Burrows–Wheeler transform . Istilah Punctured datang  dari  tempat  pengawasan eror kode-kode (ECC).  ECC  terdiri  dari  data  yang  asli  ditambah sejumlah  bilangan  dari check bits.  Jika  beberapa check bits dihilangkan, untuk mempersingkat
serangkaian  kode  itu,  hasil  kode  ditujukan  sebagai Punctured
Algoritma  Huffman  diperkenalkan  oleh  David A. Huffman seorang mahasiswa MIT dalam papernya yang  berjudul  " A  Method  for  the  Construction  of Minimum-  Redundancy  Codes "  dan  diterbitkan  pada tahun  1952.  Prinsip  kode Huffman adalah  karakter yang    paling    sering    muncul    di    dalam    data dikodekan    dengan    kode    yang  jumlah  bitnya  lebih sedikit,  sedangkan  karakter  yang  jarang  muncul dikodekan  dengan  kode  yang  jumlah  bitnya  lebih panjang.  Algoritma Huffman menggunakan  tabel frekuensi kemunculan karakter untuk
menggambarkan  setiap  karakter  menjadi  kode  atau string  biner.  Kode  atau  string  biner  yang  digunakan untuk  mengkodekan  setiap  karakter  dinamakan  kode Huffman .

## II. TEORITIS A. Kompresi Data
Kompresi data di dalam konteks ilmu komputer  adalah  merupakan  ilmu  atau  seni  dalam merepresentasikan  informasi  yang  terdapat  pada data ke  dalam  suatu  bentuk  yang  lebih  padat  (kecil)  (Pu, 2006).  Perkembangan  komputer  dan  multimedia mengakibatkan  kompresi  data  menjadi  hal  yang sangat penting dan berguna dalam teknologi pada saat sekarang ini. Solomon (2007) mengemukakan definisi kompresi  data  adalah  proses  yang  mengkonversi sebuah  masukan  berupa  aliran  data  ( the  source atau data asli mentah) menjadi  suatu  aliran  data  lain  ( the Output ,  aliran  bit,  atau  aliran  sudah  dikompres) yang  memiliki  ukuran  lebih  kecil.  Aliran  data (stream)  dapat  berupa  sebuah file atau buffer pada memori.  Data  dalam  konteks  kompresi  data melingkupi  segala  bentuk  digital  dari  informasi, yang dapat diproses oleh sebuah program komputer.  Bentuk dari  informasi tersebut secara luas
dapat diklasifikasikan sebagai teks, suara, gambar dan video.
B. Punctured Elias Codes
Punctured  Elias  Codes untuk  bilangan  integer dirancang  oleh  Peter  Fenwick  dalam  sebuah percobaan untuk meningkatkan performa the Burrows–Wheeler transform . Istilah Punctured datang  dari  tempat  pengawasan eror kode-kode (ECC).  ECC  terdiri  dari  data  yang  asli  ditambah sejumlah  bilangan  dari check bits.  Jika  beberapa check bits dihilangkan, untuk mempersingkat serangkaian  kode  itu,  hasil  kode  ditujukan  sebagai Punctured (Salomon,  2007).Cara  untuk  membangun kode Punctured  Elias  Codes ini  adalah  sebagai berikut:
1. Ambil bilangan biner dari n,
2. Reversed (balikkan  bit-bitnya),  dan  siapkan flag untuk  menunjukkan  jumlah  bit  yang bernilai 1 di dalam n.
3. Untuk  setiap  bit  1  di  dalam  n  kita  siapkan flag dari 1 dan akhiri flag dengan 0.
4. Gabungkan flag dengan  bilangan  biner  yang sudah dibalikkan ( reversed ).

## C. Algoritma Huffman
Algoritma  Huffman  diperkenalkan  oleh  David A.  Huffman  seorang  mahasiswa  MIT  dalam papernya  yang  berjudul  " A  Method  for  the Construction  of  Minimum-  Redundancy  Codes "  dan diterbitkan  pada  tahun  1952.  Prinsip  kode  Huffman adalah  karakter    yang    paling    sering    muncul    di dalam   data  dikodekan  dengan  kode   yang jumlah bitnya  lebih  sedikit,  sedangkan karakter  yang  jarang muncul  dikodekan  dengan  kode  yang  jumlah  bitnya lebih  panjang.  Algoritma  Huffman  menggunakan tabel frekuensi kemunculan karakter untuk menggambarkan  setiap  karakter  menjadi  kode  atau string  biner.  Kode  atau  string  biner  yang  digunakan untuk  mengkodekan setiap karakter dinamakan kode Huffman.
D. File teks File teks  merupakan file yang  berisi  informasi- informasi  dalam  bentuk  teks.  Data  yang  berasal  dari dokumen  pengolah  kata,  angka  yang  digunakan dalam perhitungan, nama dan alamat dalam basis data merupakan  contoh  masukan  data  teks  yang  terdiri dari  karakter,  angka  dan  tanda  baca  (Sitorus,  2012). Masukan  dan  keluaran  data  teks  direpresentasikan
sebagai  set  karakter  atau  sistem  kode  yang  dikenal oleh  sistem  komputer.  Ada  tiga  macam  set  karakter yang  umum  digunakan  untuk  masukan  dan  keluaran pada komputer, yaitu ASCII, EBCDIC, dan Unicode . ASCII  ( American  Standard  Code  for  Information Interchange )  merupakan  suatu  standar  internasional dalam  kode  huruf  dan  simbol  seperti  Hex  dan Unicode tetapi  ASCII  lebih  bersifat  universal. ASCII digunakan oleh komputer dan alat komunikasi  lain  untuk  menunjukkan  teks.  Kode ASCII memiliki komposisi bilangan biner sebanyak 8 bit,  dimulai  dari  00000000  hingga  11111111.  Total kombinasi  yang  dihasilkan  sebanyak  256,  dimulai dari  kode  0  hingga  255  dalam  sistem    bilangan desimal.    EBCDIC    ( Extended    Binary    Code Decimal    Interchange  Code )  merupakan  set  karakter yang  diciptakan  oleh  komputer  merk  IBM.  EBCDIC terdiri  dari  256  karakter  yang  masing-masing berukuran  8  bit.  Adanya  keterbatasan  pada  kode ASCII dan EBCDIC, dibuat standar kode internasional baru yang merupakan kode 16 bit   yang disebut Unicode . Unicode adalah  suatu  standar industri  yang  dirancang  untuk  dimanipulasi  secara konsisten oleh komputer

## III. ANALISA dan PERANCANGAN
A. Analisa Masalah Pemampatan data (data compression) merupakan salah satu kajian di dalam  ilmu komputer yang bertujuan untuk mengurangi ukuran file sebelum menyimpan  atau  memindahkan  data  tersebut  ke dalam  media  penyimpanan  ( storage  device ).  Media penyimpanan  seperti floppy  disk ,  hard disk dan  CD ( Compact  Disc )  mempunyai  kapasitas  yang  terbatas. Jika  data  yang  akan  disimpan  pada  media penyimpanan  semakin  bertambahdan  berukuran besar,  maka  media  penyimpanan  tidak  dapat menyimpan  data  tersebut  karena  melebihi  kapasitas. Oleh  karena  itu,  untuk  mengatasi  masalah  ini digunakan lah pemampatan data.
B. Kompresi Dengan Punctured Elias Codes
Analisis  proses  kompresi file teks  dengan metode Punctured  Elias  Codes Berikut  ini  adalah contoh  proses  kompresi file teks  dengan  metode Punctured Elias Codes . Misalkan  pada  sebuah file teks  berisi String “KURA-KURA KAKEKKU LARI KAYAK KUDA”. Untuk mengukur ukuran String itu di dalam komputer dapat dilihat pada Tabel 1. Tabel 1. String Yang Belum Dikompresi. Char Ascii Code Ascii Code (Binary) Bit Frek Bit x Frek K 75 01001011 8 9 72 U 85 01010101 8 4 32 R 82 01010010 8 3 24 A 65 01000001 8 7 56 - 4 00101101 8 1 8 Sp 32 00100000 8 4 32 E 69 01000101 8 1 8
Char Ascii Code Ascii Code (Binary) Bit Frek Bit x Frek L 76 01001100 8 1 8 I 73 01001001 8 1 8 Y 89 01011001 8 1 8 D 68 01000100 8 1 8 a. Ratio of compression (Rc) Rc = ukuran data sebelum dikompresi ukuran data setelah dikompresi Rc = 264 bit 136 bit Rc = 1.94
b. Compression ration (C r )
Cr = ukuran data setelah dikompresi
x 100% ukuran data sebelum dikompresi Cr = 36 bit x 100% 64 bit Cr = 51.51 %
c. Redundancy (Rd)
Rd = 100% - Cr Rd = 100% - 51.51% Rd = 48.49%

## C. Proses Kompresi Huffman
Sebagai  contoh  sederhana  sebuah  kompresi, dalam  kode  ASCII string 7  huruf  “AB  ACC  DA” membutuhkan representasi 7 x 7 bit  = 49 bit , dengan rincian seperti pada Tabel 3.4.
Tabel 2. Frekuensi Kemunculan Karakter pada Data.
Maka  dari  Tabel  2  pembentukan  pohon  Huffman untuk proses kompresi yang dapat terjadi deperlihatkan  pada  Gambar  2.  Seluruh  karakter beserta  frekuensi  kemunculannya  dapat  dilihat  pada gambar  3.1(a),  lalu  dua  buah  karakter  dengan frekuensi  terkecil  yaitu  “B  ”  dan  “D  ”  digabungkan serta tambahk an kode  “0” untuk node pertama  “B” dan kod e “1 ” untuk node kedua  “D ”. Hal in i dapat dilihat  pada  Gambar  3.1(b).  Kemudian  gabungan karakter  tersebut  digabungkan  dengan  karakter dengan  frekuensi  yang  paling  mendekati  yaitu  “C  ”, karakter gabungan tersebut yang terlihat pada Gambar 3.1(c).  Kemudian  karakter  gabungan  tersebut  di gabungkan    lagi  dengan  karakter  “A”    seperti  pada Gambar 3.1(d).
Tabel 3. Hasil Kompresi Menggunakan Algoritma Huffman Karakter Frekuensi Kemunculan Kode Huffman A 3 0 B 1 110 C 2 10 D 1 111
Dari  Tabel  3  dapat  diketahui  bahwa dibutuhkan representasi (3x1) + (1x3) + (2x2) + (1x3) = 13  bit.  Maka dapat diperoleh persentase kompresi dengan menggunakan  persamaan 4.1 sebesar:
49 - 13 x 100% = 73,46%
9

## IV. IMPLEMENTASI
Tahap  implementasi  sistem  merupakan  tahap pembuatan  perangkat  lunak,  tahap  lanjut  dari  tahap perancangan sistem pengujian. Tahap yang dilakukan untuk menterjemahkan perancangan berdasarkan hasil analisis pengujian dalam bahasa yang dimengerti oleh komputer  serta  penerapan  perangkat  lunak  pada keadaan yang sebenarnya.
Form  ini  adalah  form  yang  digunakan  untuk melakukan  proses  kompresi  dan  dekompresi  Dalam form  ini  pertama  sekali  kita  melakukan  penginputan terhadap file text yang akan diproses. File  yang akan diproses  ini adalah  form dengan  format text. Adapun prosesnya  dengan  mengklik  tombol  buka  file  untuk mencari  file  yang  akan  diproses.  Selanjutnya  klik tombol kompresi untuk melakukan kompres terhadap file  text  tersebut.  Adapun  tampilanya  dapat  dilihat pada  form  dibawah  ini  Tampilannya  dapat  dilihat pada gambar 1 dan 2 dibawah ini Gambar 1. Proses Input File Karakter Frekuensi Kemunculan Kode Ascii A 3 1000001 B 1 1000010 C 2 1000011 D 1 1000100
Gambar 2. Proses Kompres File
Form  ini  adalah  form  yang  digunakan  untuk melakukan  proses  dekompresi  dan  Dalam  form  ini pertama  sekali  kita  melakukan  penginputan  terhadap file  yang  telah  terkompres    yang  akan  diproses.  File yang  akan  diproses  ini  adalah  form  dengan  format huf. Adapun prosesnya dengan mengklik tombol buka file  untuk  mencari  file  yang  akan  diproses. Tampilannya dapar dilihat pada gambar 3 dibawah ini
Gambar 3. Proses Dekompresi
Form  ini  adalah  form  yang  digunakan  untuk melakukan  proses  kompresi  dan  dekompresi  Dalam form  ini  pertama  sekali  kita  melakukan  penginputan terhadap file text yang akan diproses. File  yang akan diproses  ini adalah  form dengan  format text. Adapun prosesnya  dengan  mengklik  tombol  buka  file  untuk mencari  file  yang  akan  diproses.  Selanjutnya  klik tombol kompresi untuk melakukan kompres terhadap file  text  tersebut.  Adapun  tampilanya  dapat  dilihat pada  form  dibawah  ini  Tampilannya  dapat  dilihat pada gambar 4. dan 5 dibawah ini
Gambar 4. Proses Kompresi Punctured Elias Code
Form  ini  adalah  form  yang  digunakan  untuk melakukan  proses  dekompresi  dan  Dalam  form  ini pertama  sekali  kita  melakukan  penginputan  terhadap file  yang  telah  terkompres    yang  akan  diproses. Adapun prosesnya dengan mengklik tombol buka file untuk mencari file yang akan diproses, kemudian klik tombol  dekompres.  Tampilannya  dapar  dilihat  pada gambar 5 dibawah ini
Gambar 5. Proses Dekompresi Punctured Elias Code

## V. KESIMPULAN
Secara  keseluruhan  mulai  dari  perancangan,  realisasi dan  pengujian,  dapat  ditarik  beberapa  kesimpulan, antara lain:
1. Pada  Kompresi  dengan  menggunakan  kode Huffman akan lebih optimal jika variasi karakter dari  informasi  tersebut  tidak  terlalu  banyak walaupun  frekuensi  kemunculannya  tinggi karena  pohon  Huffman  yang  akan  terbentuk tidak  terlalu  panjang  sehingga  kode  Huffman yang  mewakili  karakter  tersebut  menjadi  lebih singkat.
2. Berdasarkan  pengujian  kompresi  terhadap file teks  dengan  karakter  tidak  berulang,  dapat disimpulkan  bahwa    kompresi  dengan  metode Huffman  jauh  lebih  efektif  dibanding  dengan metode Punctured Elias Code
3. Pada  metode Punctured  Elias  Code khusus untuk File teks  yang  berekstensi  *.doc  hasil Output dekompresi  telah  diatur  dengan Form at perataan  teks  justify  dan  jenis font  Times  New Roman dengan ukuran font 12.

## VI. DAFTAR PUSTAKA
1. Adi Nugroho.2010 . Rekayasa Perangkat Lunak Berbasis Objek dengan Metode. USDP. Andi. Yogyakarta
2. Booch,G.Rumbaugh,J.Jacobsoon, I. (2005). Unified Modelling Language User Guide. Addison-Wesley Professional.
3. Darma, Putra, 2006. Pengolahan Citra Digital, AndiOffset,Yogyakarta
4. Indrajani, S.Kom , MM. 2011. Perancangan Basis Data Dalam Allin1. Elex Media. Komputindo. Jakarta
5. Pu,I.M.2006.Fundamental Data Compression . London: Butterworth Heinemann
6. Riyanto, Rahmat, 2009, Langsung Bisa Visual Basic.Net 2008, Andi, Yogyakarta.
7. Salomon,  D.  2007.  Data  Compression  :  The  Complete Reference. Third Edition.
8. Sitorus ,EunikeJohana. 2012 .  Studi  Perbandingan  Kompresi Menggunakan  Metode .  Shannon  Fano Dan Unary  Coding Pada File Teks.