## Perancangan Aplikasi Kompresi File Teks dengan Menerapkan Algoritma Sequitur
Mhd Emil Frayoga
Program Studi Teknik Informatika, STMIK Budi Darma, Medan, Indonesia Jalan Sisingamangaraja No. 338 Medan, Indonesia

## Abstrak
File teks atau data teks merupakan salah satu komponen yang sangat penting bagi setiap orang maupun pada setiap instansi dalam  bentuk  tercetak  maupun  berbentuk  multemedia.  Dimana  file  atau  data  dapat  menyimpan  beberapa  hal  penting  di dalamnya, maka semakin besar ukuran dari suatu file atau data semakin besar pula media penyimpanan yang akan di butuhkan. Dengan melihat akan kebutuhan pemampatan sutau file atau data, maka di perlukan adanya kompresi atau pemampatan pada data, sehingga dapat  mengurangi pemakaian pada ruang  media  penyimpanan  eksternal,  memperkecil kebutuhan badwidth, mempercepat  proses  pengiriman  data,  dan  memampatkan  dengan  rasio  yang  lebih  tingi  dari  pada  data  hasil  sebelum pemampatan.  Proses  kompresi  di  lakukan  untuk  mengatasi  masalah  dalam  media  penyimpanan,  dimana  algoritma  untuk kompresi tersebut menggunakan algoritma sequitur.
Kata kunci : File Teks, Kompresi, Algoritma Sequitur.

## Abstract
Text files or text data is one component that is very important for each person as well as for each agency in the form of printed or multi-media. Where files or data can store some important things in it, the greater the size of a file or data the greater  the storage  media  that  will  be  needed.  By  looking  at  the  compression  requirements  of  the  file  or  data,  there  is  a  need  for compression or compression on the data, so that it can reduce usage in the external storage media space, minimize bandwidth requirements, speed up the data transmission process, and compress the ratio higher than the data results before compression. The compression process is done to solve problems in storage media, where the algorithm for compression uses the sequitur algorithm.
Keywords : Text File, Compression, Sequitur Algorithm.

## 1. PENDAHULUAN
Dengan adanya perkembangan teknologi yang sangat pesat, menjadikan komputerisasi bagian utama dalam dunia pekerjaan.  Data-data  yang  harus  di  simpan  dalam  setiap  harinya  akan  membuat  kapasitas  penyimpanan  pada komputerisasi  semakin rendah. Ukuran data yang di simpan semakin  besar  maka semakin kecil pula kapasitas penyimpanan di komputerisasi. Permasalahan ini sering di hadapi oleh pengguna komputer yang kurang cukupnya media penyimpanan data.
Secara umum telah diketahui bahwa file-file yang berbentuk teks tentunya banyak sekali akan di jumpai kata-kata pengulangan di dalamnya. Pengulangan inilah yang di manfaatkan agar dapat mengkompres file tersebut menjadi  lebih  kecil.  Kompresi  di  tujukan  pada  suatu file untuk  memperkecil  penyimpanan  data,  mempercepat pengiriman data, dan memperkecil kebutuhan bandwidth .
Permasalahan  di  atas,  sebenarnya  dapat  di  atasi  atau  di  tangani  dengan  adanya  pemampatan  atau pengkompresian  pada  data.  Pemampatan  atau  pengkompresian  data  adalah  salah  satu  cara  untuk  memperkecil data sehingga hanya memerlukan sedikit ruang penyimpanan untuk mempersingkat waktu pertukaran data yang lebih segnifikan atau lebih efisien. Jika tanpa adanya proses pengkompresian, mungkin kapasitas pada komputer membutuhkan  ratusan  bahkan  jutaan  kapasitas  hanya  untuk  menyimpan  sebuah file atau  data  yang  berukuran sangat besar. Maka dari  itu, dengan adanya proses pengkompresian ukuran kapasitas pada file atau data dapat menjadi jauh lebih kecil.
Dengan  adanya  kebutuhan  dalam  pemampatan  data  maka  di  perlukan  sebuah  aplikasi  yang  bisa  atau yang  mampu  memperkecil  suatu  ukuran  pada  data,  sehingga  menjadikan  keuntungan  untuk  mengurangi pemakaian ruang atau kapasitas pada penyimpanan komputerisasi, serta mempercepat proses pertukaran data antar penyimpanan.  Teknik  kompresi  yang  di  gunakan  adalah  menggunakan  algoritma  sequitur  dalam  kompresi file teks.

## 2. LANDASAN TEORI

## 2.1 Kompresi Data
Kompresi data berarti sebuah proses mengkodekan informasi menggunakan bit atau informasi bearing unit yang lain yang lebih rendah  dari pada representasi data yang tidak terkodekan dengan suatu sistem encoding tertentu. Kompresi data juga diartikan sebagai teknik untuk memampatkan data agar diperoleh data dengan ukuran yang lebih  kecil  dari  pada  ukuran  aslinyasehingga  lebih  efisien  dalam  penyimpanan  atau  mempersingkat  waktu pertukaran data tersebut. [1]
Teknik kompresi didasarkan menjadi dua bagian, yakni : 1. Kompresi Lossless
Kompresi  data  algoritma lossless digunakan  untuk  mengurangi  jumlah  informasi  sumber  yang  akan ditransmisikan  dalam  sedemikian  rupa  sehingga  ketika  informasi  didekompresi,  tidak  ada  kehilangan informasi.  Kompresi lossless ini  dimungkinkan  karena  sebagian  besar  data  dunia  nyata  memiliki  statistik perulangan dan algoritma ini mengeksploitasi pengulangan untuk merepresentasikan data lebih ringkas tanpa kehilangan informasi.
2. Kompresi Lossy Kompresi data lossy kontras dengan kompresi data lossless . Algoritma kompresi data lossy tidak menghasilkan tepat  salinan  informasi  setelah  dekompresi.  Dalam  skema  ini,  beberapa  informasi  mengalami  kehilangan. Kompresi lossy mengurangi  ukuran file dengan  menghilangkan  beberapa  data  berlebihan  yang  tidak  akan diakaui oleh manusia setelah decoding.[2]

## 2.2 Algoritma Sequitur
Sequitur merupakan sebuah algoritma waktu linier yang menyimpulkan tata bahasa bebas konteks ( contex-free grammar ) kedalam suatu pemampatan untuk mengurangi masukkan yang berulang. Operasi sequitur terdiri dari pemastian  dua  sifat  yang  berlaku.  Ketika  menjelaskan  algoritma,  sifat-sifatnya  bertindak  sebagai  batasan. Algoritma beroperasi menjalankan batasan didalam sebuah tata bahasa yang ketika diagram keunikkan (diagram uniqueness ) dilanggar, sebuah aturan baru dibentuk, dan ketika batasan aturan digunakan ( rule utility ) dilanggar, aturan yang sia-sia dihapus. [3]
Diagram keunikan mempunyai arti bahwa tidak ada pasangan dari simbol atau diagram muncul lebih dari sekali  dalam  sebuah  tata  bahasa.  Jika  hal  ini  terjadi  maka  akan  melanggar  aturan  batasan  pertama  (diagram uniqueness ) sehingga akan membentuk aturan baru (simbol non-terminal ) yang akan menggantikan simbol atau diagram yang muncul lebih dari sekali. [3]
Rule utility mempunyai arti bahwa setiap aturan produksi digunakan lebih dari sekali. Dan jika ada aturan yang  hanya  digunakan  sekali  maka  akan  terjadi  pelanggaran  pada  batasan  kedua  ( rule  utility )  sehingga  aturan yang hanya yang dipakai sekali akan dihapus atau dihilangkan. [3] Tiga urutan contoh input dan grammar
Setiap algoritma memiliki cara kerja tersendiri, dimana cara kerja ini menjelaskan bagaimana proses atau langkah-langkah  yang  dimiliki  dalam    algoritma  itu  tersendiri.  Adapun  langkah-langkah  cara  kerja  algoritma sequitur adalah sebagai berikut :
1. Mencari  nilai  awal string dengan  memunculkan  tabel  nilai  frekuensi  dan  setiap  karakter  atau string akan dikalikan dengan 8 bit.
2. Kemudian urutkan karakter berdasarkan frekuensi kemunculan dari yang terbesar hingga terkecil.
3. Menerapkan  algoritma  sequitur  dengan  menampilkan  tabel  agar  lebih  mudah  untuk  dilihat  pada  proses algoritma sequitur ini. Dan proses kerja algoritma ini menyimbolkan setiap pasangan karakter atau string yang muncul lebih dari sekali.
4. Melakukan perhitungan terhadap proses algoritma yang telah dikerjakan sebelumnya dengan memunculkan tabel frekuensi setiap kemunculan karakter atau string yang telah diproses.
5. Hasil yang telah diketahui kemudian diterapkan kedalam rumus yang berlaku pada proses kompresi tersebut.
.

## 3. ANALISA DAN PEMBAHASAN
Proses kompresi bertujuan untuk memperkecil ukuran pada suatu data agar menghasilkan data yang padat tetapi masih memiliki kuantitas yang terdapat pada data tersebut. Pada tahap ini akan menjelaskan proses kompresi file teks  dimana  kompresi  akan  dilakukan  dengan  algoritma sequitur . Sequitur sendiri  merupakan  algoritma  yang menyimpulkan tata bahasa  bebas konteks ( contex-free grammar) untuk mengkompresi agar tidak  mengulangi teks atau masukkan  yang  berulang. Model kompresi file teks dengan  menggunakan algoritma sequitur dengan mencari pasangan karakter yang sama kemudian karakter-karkter tersebut diberi simbol yang disebut juga simbol non-terminal, proses  kompresi  ini  tetap  dilanjutakan sampai  semua  karakter tidak  ada  lagi  memiliki  pasangan karakter yang sama atau pasangan karakter yang berulang. Saat melakukan proses kompresi dengan menggunakan algoritma sequitur ini,  algoritma sequitur beroperasi  dengan  menjalankan  batasan  diagram  keunikan  ( diagram uniquences ) dan aturan kegunaan ( rule utility ).

## 3.1 Kompresi Data
Sebelum melakukan proses kompresi menggunakan algoritma sequitur , penulis menentukan string yang akan di gunakan. Misalkan file teks berisi string “MAMA_MAKAN_MAKANAN_BERGIZI”. Harus di ketahui terlebih dahulu  bawah string  “ MAMA_MAKAN_MAKANAN_BERGIZI” terdiri dari 26 karakter, dimana 1 karakter tersebut sama dengan ( = ) 1 byte dan 1 byte  sama dengan ( = ) 8 bit, maka total string sebelum dikompresi adalah 26 byte atau sama dengan ( = ) 208 bit.
Untuk  mengetahui ukuran dari string “MAMA_MAKAN_MAKANAN_ BERGIZI”, dapat dilihat pada tabel sebagai berikut:
Tabel 1. Ukuran String Sebelum Dikompresi Karakter Frekuensi ASCII Desimal ASCII Binary Bit Bit x Frekuensi A 7 65 01000001 8 56 M 4 77 01001101 8 32 Sp (spasi) 3 32 00100000 8 24 N 3 78 01001110 8 24 K 2 75 01001011 8 16 I 2 73 01001001 8 16 E 1 69 01000101 8 8 R 1 82 01010010 8 8 G 1 71 01000111 8 8 B 1 66 01000010 8 8 Z 1 90 01011010 8 8 Jumlah bit x frekuensi 208 bit
File teks  yang  telah  di  ketahui string dan  hasil  jumlah  dari  setiap  frekuensi  kemunculannya,  maka  proses selanjutnya adalah proses kompresi menggunakan algoritma sequitur. Pada algoritma sequitur, string yang telah ada kemudian di proses untuk mendapatkan string yang berduplikat atau dengan kata lain 2 karakter atau 2 huruf yang muncul lebih dari sekali . Kemudian karakter tersebut akan di periksa, jika ada pasangan yang muncul lebih dari satu kali maka pasangan tersebut diubah menjadi simbol non-terminal . String awal
: MAMA_MAKAN_MAKANAN_BERGIZI String ke huruf kecil : mama_makan_makanan_bergizi Seperti penjelasan diatas, string yang sudah diubah kedalam huruf kecil, kemudian akan di periksa apakah ada pasangan  yang  muncul  lebih dari  sekali. Dari string “mama_makan_makanan_bergizi”, pasangan karakter “ma” muncul sebanyak empat kali. Maka seperti prinsip kinerja algoritma sequitur ini, pasangan karater “ma” akan  di  ubah  menjadi  simbol non-terminal yaitu  menjadi  “A”.  Maka  terbentuklah  sebuah string baru  menjadi “AA_Akan_Akanan_bergizi”.
Kemudian dari string yang baru, akan di periksa kembali apakah ada pasangan karakter yang muncul lebih dari sekali. Setelah di periksa kembali ternyata pasangan karakter “Ak” muncul lebih dari sekali yaitu muncul sebanyak dua kali. Maka dari itu, pasangan karater “Ak” akan di ubah menjadi simbol non-terminal yaitu simbol “B”.  Sehingga  membentuk string “AA_Ban_Bana_bergizi”.    Proses  keseluruhan  algoritma sequitur ini,  dapat dimuat dalam bentuk tabel yang disajikan sebagai berikut :
Tabel 2.  Proses Algoritma Sequitur Proses String Aturan
Diagaram Duplikat Pada String Pembentukkan Simbol ( Non-Terminal ) ( Rule ) String Yang Dihasilkan Hapus Aturan 1 mama makan makanan bergizi ma A A = ma AA Akan Akanan bergizi - 2 AA Akan Akanan bergizi Ak A A = ma B = Ak AA Ban Banan bergizi - 3 AA Ban Banan bergizi Ba A B A = ma B = Ak C = Ba AA Cn Cnan bergizi C Proses String Diagaram Duplikat Pada String Pembentukkan Simbol ( Non-Terminal ) Aturan ( Rule ) String Yang Dihasilkan Hapus Aturan 4 AA Bn Bnan bergizi Bn A B A = ma B = Aka C = Bn AA C Can bergizi - 5 AA C Can bergizi Null A B C A = ma B = Aka C = Bn - -
Pada tabel di atas, proses ketiga menunjukkan bawah terdapat simbol non-terminal yaitu simbol “C” yang di  mana  simbol  tersebut  di  hapus  pada  proses  yang  ketiga.  Sesuai  dengan  aturan  kegunaan  ( rule  utility )  yang terdapat pada algoritma sequitur ini, menerangkan bahwa setiap aturan ( rule ) di gunakan lebih dari sekali dan jika ada aturan yang hanya di gunakan sekali maka akan terjadi pelanggaran pada batasan kedua ( rule utility ) sehingga aturan yang hanya di pakai sekali akan di abaikan atau di tiadakan. Maka  simbol “B” yang memiliki pasangan karakter “Ak” yang kebetulan simbol ini hanya di gunakan sekali harus di abaikan atau di tiadakan. Maka dari itu simbol “B” ini akan di munculkan kembali dan di beri hasil dari simbol “C” tersebut, sehingga hasil dari simbol “B” adalah “Aka”. Jadi, string “mama makan makanan hama” setelah diproses menggunakan algoritma sequitur menjadi string “AA_C_Can_bergizi”. Setelah melakukan proses kompresi dengan algoritma sequitur, proses selanjutnya adalah menghitung total string bit yang telah diproses menggunakan algoritma sequitur . Pada string “ MAMA_MAKAN_MAKANAN_BEGIZI” ukuran string sebelum dikompresi adalah 208 bit, sedangkan proses setelah dikompresi dengan string “AA_C_Can_bergizi” dengan jumlah 16 karakter yaitu 128 bit. Perhitungan string bit yang sudah diperoleh dari hasil kompresi algoritma sequitur dapat di lihat sebagai berikut :
Tabel 3.  Ukuran String Setelah Di kompresi Karakter Frekuensi ASCII Desimal ASCII Binary Bit Bit * Frekuensi Sp (spasi) 3 32 00100000 8 24 A 2 65 01000001 8 16 C 2 67 01000011 8 16 Karakter Frekuensi ASCII Desimal ASCII Binary Bit Bit * Frekuensi i 2 105 01101001 8 16 n 1 110 01101110 8 8 b 1 98 01100010 8 8 e 1 101 01100101 8 8 r 1 114 01110010 8 8 g 1 103 01100111 8 8 a 1 97 01100001 8 8
z 1 122 01111010 8 8 Jumlah Bit x Frekuensi 128 bit
Setelah mengetahui hasil kompresi tersebut, hasil kompresi dapat di ukur atau di hitung sebagi berikut :
𝐶𝑟 = 100% − 𝑢𝑘𝑢𝑟𝑎𝑛 𝑏𝑖𝑡 𝑑𝑎𝑡𝑎 𝑠𝑒𝑡𝑒𝑙𝑎ℎ 𝑑𝑖𝑘𝑜𝑚𝑝𝑟𝑒𝑠𝑖 𝑢𝑘𝑢𝑟𝑎𝑛 𝑏𝑖𝑡 𝑑𝑎𝑡𝑎 𝑠𝑒𝑏𝑒𝑙𝑢𝑚 𝑑𝑖𝑘𝑜𝑚𝑝𝑟𝑒𝑠𝑖 × 100%
𝐶𝑟 = 100% − 128 𝑏𝑖𝑡 208 𝑏𝑖𝑡 × 100%
𝐶𝑟 = 100% −  61%
𝐶𝑟 = 39%
Dari  hasil  perhitungan compression  ratio ,  ternyata  proses  kompresi  dengan  menggunakan  algoritma sequitur lebih hemat 39% pada kapasitas yang di miliki.

## 3.2 Dekompresi Algoritma Sequitur
Proses  dekompresi  ini  bertujuan  agar string yang  telah  terkompresi  kembali  seperti  semula  saat  sebelum  di kompresi.  Maka  dari  itu,  setiap  proses  kompresi  pasti  selalu  di  dampingi  dengan  adanya  dekompresi.  Dari pernyatan ini, penulis akan mengurai bagaimana cara dekompresi algoritma sequitur dengan string yang telah di proses sebelumnya.
Telah  di  ketahui string yang  sudah  di  kompresi  yaitu string “AA_C_Can_  bergizi”.  Pada  algoritma sequitur , proses algoritma  ini  memiliki aturan ( rule ) dimana di dalam  aturan ini  memiliki simbol  A, B, dan C. Setiap simbol memiliki pasangan karakter yang berulang.
Untuk lebih jelas terhadap dekompresi algoritma sequitur dapat dilihat pada tabel berikut :
Tabel 4. Proses Dekompresi Algoritma Sequitur Proses String Kompresi Aturan Rule Keterangan Rule String Setelah Dekompresi 1 AA C Can bergizi A= ma Simbol “A” diganti dengan pasangan karakter “ma” mama C Can bergizi 2 mama C Can bergizi C = Bn Simbol “C” diganti dengan rule “Bn” mama Bn Bnan bergizi 3 mama Bn Bnan bergizi B = Aka Simbol “B” memiliki rule “Aka”. Telah diketahui simbol “A” memiliki pasangan karakter “ma”. Jadi simbol “B = ma + ka” ditambah  dengan karatek “n” dan “an”.
mama makan makanan bergizi

## 4.  IMPLEMENTASI
Program aplikasi tersebut terdiri dari dari 3 form yaitu form menu utama, form proses dan form about me. Berikut adalah tampilan menu utama pada aplikasi yang di rancang sebagai berikut : 1. Tampilan Menu Utama
Tampilan  menu  utama  adalah  tampilan  saat  aplikasi  pertama  kali  dijalankan  dan  belum  melakukan  proses apapun, seperti pada gambar berikut,
Gambar 1.Tampilan Menu Utama
2. Tampilan Proses Kompresi
Tampilan  input  proses  kompresi  merupakan  halaman  yang  di  gunakan  untuk  melakukan  proses  kompresi dengan menggunakan algoritma sequitur . Pada halaman form proses kompresi ada beberapa bagian menu di dalamnya yang meliputi sebagai berikut :
Gambar 2. Tampilan Hasil Proses Kompresi
3. Tampilan Input Proses Dekompresi
Tampilan input proses dekompresi merupakan halaman yang di gunakan untuk melakukan proses dekompresi dengan menggunakan algoritma sequitur . Pada halaman form proses dekompresi ada beberapa bagian menu di dalamnya yang meliputi sebagai berikut :
Gambar 3. Tampilan Hasil Dekompresi.

## 5. KESIMPULAN
Kesimpulan yang dapat diambil setelah melakukan perancangan aplikasi kompresi file teks dengan menerapkan algoritma Sequitur adalah :
1. Algoritma Sequitur untuk mengkompresi file teks yaitu dengan cara menyimbolkan setiap pasangan karakter yang muncul lebih dari sekali dan  pasangan karakter tersebut diberi simbol yang disebut juga simbol non- terminal.
2. Penerapan algoritma sequitur untuk kompresi file teks dengan menggunakan aplikasi Visual Studio Net.2008.
3. Perancangan  aplikasi  kompresi  file  teks  dengan  menggunakan  Microsoft  Visual  Basic  2008  untuk memudahkan proses kompresi hanya menginput file teks yang akan diproses kompresi sehingga menghasilkan file hasil kompresi dan beserta headernya..

## REFERENCES
[1]  Cut Try Utari,  "Implementasi Algoritma Run Length Encoding Untuk Perancangan Aplikasi Kompresi Dan Dekompresi File C itra," Jurnal Time , vol. V, no. 233-3601, p. 2, 2016.
[2]  Surya  Darma  Nasution  et  al,  "Goldbach  Codes  Algorithm  For  Text  Compression," International  Jornal  of  Software  &  Hardware Research in Engineering , vol. 4, no. 2347-4890, p. 11, November 2016.
[3]  MLIS et al, Umi Proboyekti S.kom., "kompresi data teks menggunakan pendekatan grammar compression dengan algoritma sequitur," jurnal informatika , vol. vol.03, no. 1693-7279, april 2007.
[4]  David Salomon et al, "introduction," in Handbook of Data Compression . New York, Inggris: British Library, 2010, ch. 978-1-84882- 903-9, p. 12.