## Penerapan Algoritma Sequitur Pada Kompresi Record Database Pada Database

## Sarbudi Siahaan
Program Studi Teknik Informatika, STMIK Budi Darma, Medan, Indonesia Jalan Sisingamangaraja No. 338 Medan, Indonesia

## Abstrak
Perkembangan teknologi informasi yang pesat telah menjadi peran yang sangat penting untuk pertukaran informasi yang cepat. Salah satu solusi untuk masalah di atas adalah dengan melakukan pemampatan (compression) data baik itu berupa data teks, suara dan citra sebelum ditransmisikan  dan  kemudian  penerima  akan  merekonstruksikannya  kembali  menjadi  data  aslinya  (decompression).  Kompresi  atau pemampatan  merupakan  salah satu   ilmu  pengetahuan di bidang  komputer.  Pemampatan dilakukan  karena  adanya keterbatasan  dalam ruang memori, keterbatasan media penyimpanan data, dan kebutuhan waktu transfer data yang terbatas. Dalam perkembangan teknologi yang  semakin  pesat,  sebuah  media  penyimpanan  data  sudah  menjadi  kewajiban  yang  harus  dimiliki  oleh  setiap  manusia  yang  selalu berhubungan dengan komputer, baik itu penyimpanan data internal maupun penyimpanan data eksternal. Sama halnya seperti basis data (database) sudah menjadi sebuah kebutuhan pokok bagi setiap perorangan atau organisasi untuk menjalan suatu kegiatan yang ber sifat komputerisasi. Basis data (database) merupakan kumpulan dari data-data teks yang membentuk suatu file yang saling berhubungan dengan tatacara yang tertentu untuk membentuk data baru atau informasi baru. Namun suatu database dikatakan baik jika tidak terdapat redudansi data, kecepatan akses yang baik dan ukururan file pada memori tidak besar. kompresi data pada record database sangat membantu dalam mengatasi redudansi data, mempercepat akses data dan dapat mengurangi ukuran sebuah file. Kompresi record database pada database bertujuan mengurangi jumlah masukan ganda (sama) yang akan disimpan pada sebuah database. Hal ini tentunya akan mengurangi jumlah inputan karakter yang akan tersimpan dan secara otomatis akan mengurangi ukuran file di dalam ruang memori komputer.
Kata Kunci : Kompresi,Record,  Database, Sequitur.

## Abstract
The rapid development of information technology has become a very important role for rapid information exchange. One solution to the problem above is by compressing data both in the form of text, voice and image data before it is transmitted and then the recipient will reconstruct  it  back  into  the  original  data  (decompression).  Compression  or  compression  is  one  of  the  sciences  in  the  computer  field. Compression is done because of limitations in memory space, limitations of data storage media, and the need for limited data transfer time. In the rapid development of technology, a data storage media has become an obligation that must be owned by every human being who is always associated with computers, both internal data storage and external data storage. Just as a database (database) has become a basic requirement for every individual or organization to run a computerized activity. Database (database) is a collection of text data that forms a file that is interconnected with certain procedures to form new data or new information. However, a database is said to be good if there is no data redundancy, good access speed and file size in memory is not large. Data compression in database records is very helpful in overcoming data redundancy, speeding up data access and reducing the size of a file. Compression of database records in the d atabase aims to reduce the number of duplicate (equal) entries that will be stored in a database. This will certainly reduce the number of input characters that will be stored and will automatically reduce the size of files in the computer's memory space.
Keywords : Compression, Record, Database, Sequitur.

## 1. PENDAHULUAN
Perkembangan teknologi  informasi  yang pesat  telah menjadi  peran yang sangat  penting untuk  pertukaran informasi  yang cepat. Salah satu solusi  untuk masalah di  atas adalah dengan melakukan pemampatan (compression) data baik  itu berupa data teks, suara dan citra sebelum ditransmisikan dan kemudian penerima akan merekonstruksikannya kembali menjadi data aslinya  (decompression).  Kompresi  atau  pemampatan  merupakan  salah  satu    ilmu  pengetahuan  di  bidang  komputer. Pemampatan  dilakukan  karena  adanya  keterbatasan  dalam  ruang  memori,  keterbatasan  media  penyimpanan  data,  dan kebutuhan  waktu  transfer  data  yang  terbatas.    Dalam  perkembangan  teknologi  yang  semakin  pesat,  sebuah  media penyimpanan  data  sudah  menjadi  kewajiban  yang  harus  dimiliki  oleh  setiap  manusia  yang  selalu  berhubungan  dengan komputer, baik itu penyimpanan data internal maupun penyimpanan data eksternal. Sama halnya seperti basis data (database) sudah menjadi sebuah kebutuhan pokok bagi setiap perorangan atau organisasi untuk menjalan suatu kegiatan yang bersifat komputerisasi.  Basis  data  (database)  merupakan  kumpulan  dari  data-data  teks  yang  membentuk  suatu  file  yang  saling berhubungan dengan tatacara yang tertentu untuk membentuk data baru atau informasi baru. Namun suatu database dikatakan baik jika tidak terdapat redudansi data, kecepatan akses yang baik dan ukururan file pada memori  tidak besar.  Kompresi data pada record database sangat membantu dalam mengatasi redudansi data, mempercepat akses data dan dapat mengurangi ukuran sebuah file. Kompresi record database pada database bertujuan mengurangi jumlah masukan ganda (sama) yang akan disimpan pada sebuah database. Hal ini tentunya akan mengurangi jumlah inputan karakter yang akan tersimpan dan secara otomatis akan mengurangi ukuran file di dalam ruang memori komputer. Dalam penelitian ini, algoritma yang digunakan dalam  pengkompresian  record  database  pada  database  ini  adalah  menggunakan  algoritma  Sequitur.  Algoritma  sequitur merupakan sebuah algoritma waktu linear yang menyimpulkan tatabahasa bebas konteks (context free grammar) ke dalam suatu  pemampatan  untuk  mengurangi  masukan  yang  berulang  atau  dengan  kata  lain  melakukan  pengelompokan  karakter yang sama pada isi sebuah file [1].

## 2.1 Kompresi Data
Proses kompresi merupakan mereduksi ukuran suatu data untuk menghasilkan representase digital yang padat atau mampat (compact) namun tetap dapat mewakili kuantitas informasi yang terkandung pada data tersebut [2]. Dalam beberapa literatur, istilah  kompresi  sering  disebut  juga  source  coding,  data  compression,  bandwidth  compression,  dan  signyal  compression. Data dan informasi  adalah dua hal yang berbeda. Pada data terkandung suatu informasi. Namun tidak semua bagian data terkait dengan informasi tersebut atau pada suatu  data terdapat bagian-bagian data yang berulang tersebut disebut dengan data berlebihan (redundacy data). Tujuan kompresi data adalah untuk mengurangi data berlebihan tersebut sehingga ukuran data menjadi lebih kecil dan lebih ringan dalam proses transmisi [2]. Kompresi data dapat diartikan juga sebagai suatu proses mereduksi  ukuran  suatu  data  dengan  mengubah  sekumpulan  data  menjadi  sekumpulan  kode  yang  dapat  menghemat kebutuhan tempat penyimpanan dan waktu untuk transmisi data.
Jenis kompresi data berdasarkan mode penerimaan data oleh manusia dapat dibagi menjadi dua, yaitu :
1.  Dialoque Mode
Yaitu  proses  penerimaan  data  dimana  pengirim  dan  penerima  seakan berdialog (real time), seperti pada contoh video conference dimana kompresi data harus berada dalam batas penglihatan dan pendengaran manusia.
2.  Retrieval Mode
Yaitu  proses  penerimaan  data  tidak  dilakukan  secara  real  time,  dapat dilakukan random acces terhadap data dan dapat bersifat interaktif.
Jenis kompresi data berdasarkan outputnya dibagi menjadi dua bagian yaitu: a.   Lossy Compression
Yaitu  teknik  kompresi  dimana  data  hasil  dekompresi  tidak  sama  dengan  data  sebelum  kompresi.  Contoh  :  Mp3, streaming  media,  JPEG,  MPEG,  dan  WMA.  Kelebihan  dari  lossy  compression  yaitu  ukuran  file  lebih  kecil dibanding lossless namun masih tetap memenuhi syarat untuk digunakan. Biasanya teknik ini membuang bagian  – bagian data yang sebenarnya tidak berguna, tidak begitu dirasakan, tidak  begitu  dilihat  oleh  manusia  sehingga manusia    masih    beranggapan  bahwa  data  tersebut  masih  bisa  digunakan  walaupun  sudah  dikompresi.  Misainya terdapat image asli berukuran 12,249 bytes, kemudian dilakukan kompresi dengan JPEG kualitas 30 dan berukuran 1,869 bytes berarti image tersebut 85% lebih kecil dan ratio kompresi 15% [2].
b.   Lossless Compression
Yaitu  teknik  kompresi  dimana  data  hasil  kompresi  dapat  didekompres  lagi  dan  hasilnya  tepat  sama  seperti  data sebelum proses kompresi. Teknik ini digunakan jika dibutuhkan data setelah dikompresi harus diekstrak/dekompres lagi tepat sama. Teknik kompresi lossless ini banyak digunakan untuk berkas–berkas dokumen, dimana sama sekali tidak  diperkenankan  adanya  perbedaan  antara  informasi  awal  (sebelum  proses  kompresi)  dan  informasi  yang diperoleh setelah proses dekompresi. Teknik kompresi  ini  mempertahankan  kebutuhan  informasi  yang  dikandung oleh data, sehingga informasi  yang  terkandung pada file yang telah terkompresi  tetap terjaga meskipun  ukurannya telah berubah dari ukuran data aslinya [2].

## 2.2 Algoritma Sequitur
Algoritma  Sequitur  merupakan  algoritma  waktu  linear  yang  menyimpulkan  tata  bahasa  bebas  konteks  (context-free grammar) ke dalam suatu pemampatan untuk mengurangi masukan yang berulang [4] Operasi sequitur terdiri dari pemastian dua  sifat  yang  berlaku.  Ketika  menjelaskan  algoritma,  sifat-sifatnya  bertindak  sebagai  batasan.  Algoritma  beroperasi menjalankan batasan di  dalam sebuah tata bahasa yang ketika diagram  keunikan (diagram  uniqueness) dilanggar, sebuah aturan baru dibentuk, dan ketika batasan aturan kegunaan (rule utility) dilanggar, aturan yang sia-sia dihapus.  *ada algoritma ini  dikenal  simbol  nonterminal  dan  simbol  terminal.  Kedua  jenis  simbol  tersebut  merupakan  unsur  dari  production  rules (aturan-aturan  yang  digunakan  untuk  membangun  sebuah  kalimat).  Sebuah simbol nonterminal diletakkan di sebelah kiri dan sebuah string simbol terminal dan nonterminal di sebelah kanan. Simbol nonterminal di sebelah kiri menjadi nama dari string yang di sebelah kanan.
Algoritma   Sequitur  membangun   tata  bahasanya   dengan  menggunakan   2 prinsip, yaitu :
1.  Digram  Uniqueness,  tidak ada pasangan  simbol yang  berdekatan  yang muncul lebih dari satu.
2.  Semua  aturan  harus  digunakan  lebih  dari  satu  kali  dan  aturan  yang  hanya digunakan sekali harus diabaikan atau ditiadakan.
Kedua aturan ini dapat dilihat pada  gambar 2.2, di mana terdapat 3 contoh string yang dikompresi  menggunakan  metode Sequitur.  Input  S  sebelah  kiri  dari  gambar  2.2 bagian (a) sudah merupakan sebuah tata bahasa yang mengandung frase bc yang berulang  sehingga  frase  bc  dijadikan  sebagai   production  rule.  Frase  bc  kemudian diubah menjadi  simbol nonterminal  A.  Perubahan  tersebut  menghasilkan  dua  aturan  grammar,  di  mana  aturan  pertama  merupakan  input  yang redundancy-nya dihilangkan dan aturan kedua merupakan simbol A yang menggantikan digram bc.
Pada  gambar  1.  bagian  (b)  input  S  sebelah  kiri  mengandung  redundancy abcdbc yang kemudian diubah ke dalam simbol  nonterminal  A.  Simbol  nonterminal  A  mengandung    redundancy    bc    yang    juga    diubah    ke    dalam    simbol nonterminal    B.  Gambar  1.  bagian  (c)  menunjukkan  bagaimana  prinsip  kedua  dari  algoritma  Sequitur.  Karena  simbol nonterminal B yang mengandung simbol aA hanya muncul satu kali, maka simbol tersebuh diabaikan. Demikian pula dengan
simbol C yang mengandung BdA  yang  juga  hanya  muncul  sekali.  Sehingga  mengubah  simbol abcdbc  menjadi simbol nonterminal A adalah lebih optimal.
Gambar 1. Tiga urutan  contoh input dan grammar .

## 3. ANALISA DAN PEMBAHASAN
Permasalah yang didapatkan dari hasil penelitian ini adalah bagaimana sebuah database yang terdiri dari record data dimana record data tersebut berupa gabungan karakter huruf dan angka yang tersimpan di dalam sebuah basis data dapat dikompresi atau dikurangi ukuran file nya. Jika dibandingkan dengan aplikasi kompresi yang sering digunakan saat ini sebagai contoh adalah  aplikasi  Winrar.  Sebuah  file  database  yang  dikompresi  menggunakan  aplikasi  Winrar maka  file  database  tersebut tidak bisa digunakan lagi karena type file database yang dikompresi tersebut akan berubah format menjadi type WinRAR Archive. Dalam penelitian ini proses kompresi record database dilakukan pada saat proses penyimpanan data dari inputan  data  ke  dalam  database,  namun  database  yang  dikompresi  tersebut  tetap  bisa  digunakan    dan  dapat  melakukan kompresi  data  teks  secara  berulang  dalam  satu  database.  Kompresi  data  pada  record  database  sangat  membantu  dalam mengatasi redudansi data, mempercepat akses data dan dapat mengurangi ukuran sebuah file. Kompresi record database pada database bertujuan mengurangi  jumlah masukan  ganda yang akan disimpan pada sebuah database. Hal  ini tentunya akan mengurangi jumlah inputan karakter yang akan tersimpan dan secara otomatis akan mengurangi ukuran file di dalam ruang memori  komputer.  Penelitian  ini  diharapkan  mampu  mengatasi  permasalahan-permasalahan  yang  sudah  dipaparkan sebelumnya.  Tujuan  utama  dari  kompresi  data  adalah  untuk  mengurangi  atau  memapatkan  sebuah  ukuran  data.  Pada penelitian kali ini, yang menjadi objek penelitan adalah basis data(database).

## 3.1 Kompresi Record Database dengan Algoritma Sequitur
Proses  kompresi  record  database  menggunakan  algoritma  sequitur  tidak  jauh  berbeda  dengan  jenis  algoritma  kompresi lainnya. Kompresi record database dengan algoritma sequitur berfokus pada kemunculan karakter ganda lebih dari sekali. Konsep dalam kompresi record database dengan algoritma sequitur memeliki 2 aturan kepastian yang berbeda yaitu diaram keunikan  ( Digram  Uniquenes )  dan  aturan  kegunaan  ( Rule  Utility ).  Diagram  keunikan  mempunyai  arti  bahwa  tidak  ada pasangan dari karakter/simbol yang muncul lebih dari sekali dalam suatu tata bahasa. Jika hal ini terjadi maka akan melanggar aturan  batasan  pertama  ( Digram  Uniquenes )  sehingga  akan  membentuk  aturan  baru  (simbol  non-terminal)  yang  akan menggantikan  karakter/simbol  yang  muncul  lebih  dari  sekali  dalam  suatu  tata  bahasa.  Aturan  kegunaan  ( Rule  Utility ) mempunyai arti bahwa setiap aturan produksi digunakan lebih dari sekali. Jika ada aturan yang hanya digunakan sekali maka akan  terjadi  pelanggaran  pada  batasan  kedua  ( Rule  Utility )  sehingga  aturan  yang  hanya  dipakai  sekali  akan dihapus/dihilangkan.
Untuk  penerapan  algoritma  sequitur  dalam  kompresi  record  database,  penulis  memberikan  contoh  tata  bahasa  yang  akan dikompresi/dipapatkan adalah sebagai berikut:
“b b e b e e b e b e b b e b e e”
Jumlah  karakter  yang  akan  diproses  adalah  sebanyak  16  karakter.  Jumlah  tersebut  memang  terbilang  sangat  kecil  jika dilakukan  pamampatan  data.  Karena  pada  dasarnya  ukuran  dari  16  karakter  tidak  terlalu  besar  dalam  sebuah  media penyimpanan. Namun tujuan penulis membatasi ukuran karakter adalah memperjelas proses kompresi dari setiap karakter ke  karakter  lainnya  yang  terbilang  cukup  panjang.  Proses  kompresi  record  database  dengan  algoritma  sequitur  adalah sebagai berikut.
Setelah semua karakter diseleksi satu persatu, maka proses kompresi akan selesai. Hasil kompresi teks “ b b e b e e b e b e b b e b e e ”  menggunakan algoritma sequitur menjadi “DBD” dimana A=be, B=AA,  D=bBe. ““ b b e b e e b e b e b b e b e e ” S -> DBD A = be B = AA D=bBe
Dekompresi  merupakan  proses  pengembalian  data  ke  data  awal  atau  ke  informasi  awal.  Dekompresi  teks  menggunakan algoritma sequitur terbilang cukup sederhana. Proses dekompresi dilakukan berdasarkan nilai krakter yang diubah ke dalam simbol-simbol terminal.
Karakter “b b e b e e b e b e b b e b e e” S - >  DBD A - > be B- > AA
D - > bBe
Gambar 2. Dekompresi Sequitur
Tabel 1. Dekompresi
No Simbol Terminal Nilai Karakter 1 A be 2 A be 3 A Be 4 A be 5 B AA 6 B AA 7 A be 8 A be 9 B AA 11 D bBe
Hasil kompresi sebelumnya adalah sebanyak 3 karakter yaitu “DBD”, dimana setelah di dekompresi hasilnya akan kembali ke teks atau data awal.
S  -> DBD
A -> be B-> AA D->bBe D = bAAe, A=be   jadi       D=bbebee B=AA, A=be  jadi              B=bebe D = bAAe, A=be   jadi       D=bbebee Maka hasil dekompresi dari karakter DBD ->  bbebeebebebbebee.

## 4.  IMPLEMENTASI
Tampilan  program  merupakan  penampakan  antarmuka  akhir  dari  sistem  yang  dibuat,  pada  system  ini  terdapat  4 form at tampilan  halaman,  yaitu Form Halaman  Menu  Utama,  Halaman  Kompresi,  Dekompresi  dan  tentang  penulis.  Berikut  ini tampilan form atau halaman tersebut: 1. Form Menu Utama Form menu utama merupakan tampilan yang pertama kali muncul ketika menjalan program. Pada tahap ini akan muncul beberapa  pilihan  menu  yang  berfungsi  untuk  mengakses form-form yang  terdapat  di  dalam  sistemt  ersebut,  berikut tampilan dari form menu utama:
Gambar 3. Form Menu Utama 2.   Form Kompresi Data Form kompresi data merupakan form yang digunakan untuk melakukan kompresi terhadapat teks yang diinput. Setelah teks  tersebut  dikompresi  atau  dikurangi  jumlah  karakternya,  maka  karakter  yang  telah  dikompresi  akan  disimpan  ke dalam database.
Gambar 4. Form Kompresi Data
3. Form Dekompresi Form Dekompresi  merupakan form yang  digunakan  untuk  mengembalikan  teks  hasil  kompresi  ke  teks  awal  atau  ke informasi awal.
Gambar 5. Form Dekompresi Data.

## 5. KESIMPULAN
Berdasarkan hasil perancangan dan implementasi terhadap perangkat lunak dengan metode Network Security Agency (NSA) ini, penulis menarik kesimpulan sebagai berikut :
1. Penerapan algoritma Sequitur pada kompresi record database pada database dapat membantu para pengguna komputer terrmasuk dalam mengolah database untuk menghemat daya memory, dan transmisi pengiriman data yang cepat.
2. Perancangan kompresi record database pada database menggunakan bahasa pemograman Microsoft Visual Studio. Net 2008.
3. Algoritma Sequitur dapat diterapkan pada kompresi data teks untuk proses kompresi dan dekompresi teks dalam bentuk kata atau grammar..

## REFERENCES
[1] Erwin,Umi  Proboyekti  “Kompresi  Data  Teks  Menggunakan  Pendekatan  Grammar  Kompression  dengan  algoritma  Sequitur”,  Fakultas  Teknik Universitas Kristen Duta Wacana, vol. 3, pp.20-26, 2007
[2] Erwin,Umi  Proboyekti  “Kompresi  Data  Teks  Menggunakan  Pendekatan  Grammar  Kompression  dengan  algoritma  Sequitur”,  Fakultas  Teknik Universitas Kristen Duta Wacana, vol. 3, pp.20-26, 2007
[3] Prof. Dr. Jogiyanto H.M, M.B.A., Akt, Pengenalan Komputer,2006,291 – 299
[4] Fathansyah,  “Basis Data”, Sistem Basis Data, Bandung, INFORMATIKA, 2015, pp.2-10 [5]    C.J Date,  “Pengenalan Sistem Basis Data(Edisi Bahasa Indonesia)”, Defenisi Basis Data, Jakarta, Gramedia, 2006, pp.10-103