BAB 2 LANDASAN TEORI

BAB 2 LANDASAN TEORI

2.1

Basis Data 2.1.1 Pengertian Data Data adalah sekumpulan fakta, konsep, atau instruksi dalam media penyimpanan untuk komunikasi, pengambilan kembali dan pemrosesan yang bertujuan untuk menyediakan informasi yang dapat dipahami oleh manusia (WH Inmon, 2002, p388). Data juga diartikan sebagai fakta murni tentang organisasi dan transaksi bisnisnya (Whitten, 2004, ).

2.1.2 Pengertian Basis Data Basis data adalah kumpulan data yang saling berhubungan secara logis dan memiliki penjelasan akan data tersebut, yang dirancang untuk memenuhi kebutuhan organisasi akan informasi. Basis data merupakan sebuah tempat penyimpanan data yang dapat digunakan secara bersamaan oleh banyak pengguna. Data tidak disimpan di dalam file-file yang terpisah namun diintegrasikan sehingga memiliki duplikasi data yang minimal (Connolly, 2002, p14). Ketika kebutuhan informasi sebuah organisasi diidentifikasi, maka akan dihasilkan entity, atribut, dan relasi. Entity adalah sebuah obyek tertentu (orang, tempat, benda, konsep, atau event) di dalam organisasi yang 8

9 akan disimpan dalam basis data. Atribut adalah ciri-ciri entity yang menggambarkan obyek yang akan disimpan di dalam basis data. Sedangkan relasi adalah hubungan antara entity.

2.1.3 Pengertian Basis Data Relasional Basis data relasional adalah basis data yang menggunakan model relasional. Model relasional didasarkan pada konsep relasi matematika, pertama kali diperkenalkan oleh Edgar Frank Codd pada tahun 1970. Pada model relasional, data disimpan dalam tabel-tabel atau yang disebut relasi. Setiap relasi memiliki nama dan disusun dari kolom-kolom data yang disebut atribut. Setiap baris atau tuple menyimpan sebuah nilai untuk setiap atribut (Connolly, 2002, p 69). Struktur data sebuah basis data relasional terdiri dari (Connolly, 2002, pp 72-74) : 1.

Relasi, adalah sebuah tabel dengan kolom dan baris.

2.

Atribut, adalah kolom yang memiliki nama dari sebuah relasi.

3.

Domain, adalah kumpulan nilai yang diperbolehkan untuk satu atau lebih atribut.

4.

Tuple, adalah sebuah baris dari relasi.

5.

Degree, adalah jumlah atribut dari relasi.

6.

Cardinality, adalah jumlah tuple dari relasi.

7.

Relational database, adalah kumpulan relasi yang telah dinormalisasi dengan nama-nama yang unik.

10 2.1.4 Pengertian Database Management System Database Management System (DBMS) adalah suatu sistem perangkat lunak yang memungkinkan pengguna untuk mendefinisikan, membuat, memelihara, dan mengontrol akses ke basis data (Connolly, 2002, p16). DBMS biasanya menyediakan fasilitas : a.

Data Definition Language (DDL) Bahasa ini memungkinkan pengguna mendefinisikan basis data, menentukan tipe data, struktur, dan batasan data yang akan disimpan dalam basis data.

b.

Data Manipulation Language (DML) Bahasa ini memungkinkan pengguna memasukkan, mengubah, menghapus, dan mengambil data dari basis data.

c.

Kontrol akses terhadap basis data Kontrol akses yang disediakan meliputi : ƒ

Sistem keamanan yang mencegah pengguna yang tidak berhak untuk mengakses basis data.

ƒ

Sistem integritas yang menjaga konsistensi data yang disimpan.

ƒ

Sistem pengendalian concurrency yang memungkinkan akses bersamaan ke basis data.

ƒ

Sistem recovery yang memungkinkan pengembalian keadaan basis data ke suatu kondisi tertentu ketika terjadi kegagalan perangkat keras atau piranti lunak.

ƒ

Katalog yang dapat diakses pengguna yang menyediakan deskripsi mengenai data di dalam basis data.

11 Sebuah DBMS mempunyai lima komponen utama (Connolly, 2002, p18), yaitu : 1.

Perangkat keras DBMS memerlukan perangkat keras agar dapat berjalan. Perangkat keras dapat berupa sebuah komputer personal, mainframe, atau jaringan komputer.

2.

Piranti lunak Piranti lunak terdiri dari DBMS itu sendiri, bersama dengan sistem operasi, dan termasuk piranti lunak jaringan jika DBMS berupa jaringan komputer.

3.

Data Dari pandangan pengguna, komponen DBMS yang paling penting adalah data. Data yang disimpan berupa data operasional dan metadata atau deskripsi mengenai data tersebut.

4.

Prosedur Prosedur mengacu pada instruksi dan peraturan yang mengatur desain dan penggunaan basis data. Pengguna memerlukan prosedur bagaimana

menggunakan

dan

menjalankan

sistem

yang

didokumentasikan. 5.

Pengguna Komponen terakhir adalah pengguna yang terlibat di dalam sistem.

12 Menurut Connolly (2002, pp 25-30), kelebihan yang dimiliki DBMS antara lain pengendalian duplikasi data, konsistensi data, informasi yang didapat lebih dari jumlah data yang sama, pembagian data, integritas data yang meningkat, keamanan yang lebih baik, lebih ekonomis, produktifitas yang meningkat, pemeliharaan yang lebih mudah, backup dan restore yang lebih mudah. Sedangkan kekurangan yang dimiliki DBMS antara lain menjadi lebih kompleks, ukuran yang agak besar, biaya yang lebih besar, kadang-kadang performa lebih buruk, dan dampak yang lebih besar bila terjadi kegagalan.

2.1.5 Pengertian Relational Database Management System Sebuah tipe DBMS di mana basis data diatur dan diakses menurut hubungan antara nilai data berdasarkan model data relasional. RDBMS diciptakan oleh tim yang dipimpin oleh Edgar Frank Codd dan didanai oleh IBM pada tahun 1970. Contoh RDBMS yang ada misalnya Oracle, SQL Server, DB2, Sybase, dan lain-lain. (http://www.orafaq.com/glossary/faqglosr.htm)

2.2

Backup dan Restore 2.2.1 Pengertian Backup dan Restore Secara umum, backup dan restore adalah salah satu macam strategi dan prosedur yang dilakukan untuk melindungi basis data dari kehilangan data dan merekonstruksi basis data apabila terjadi kehilangan data (Oracle Database Backup and Restore Basic, 2003, p1).

13 Backup sendiri berarti melakukan duplikasi data yang ada ke sebuah tempat penyimpanan lain yang lebih aman, biasanya disebut media backup. Sedangkan restore berarti mengolah data di dalam media backup untuk mengembalikan kondisi data seperti keadaan pada waktu tertentu.

2.2.2 Alasan Diperlukannya Backup Menurut Anil Desai (2001, pp 5-7), alasan yang membuat basis data perlu dibackup antara lain : a.

Informasi yang sangat berharga Informasi adalah hal yang sangat berharga pada era sekarang ini. Perkembangan suatu perusahaan sangat bergantung pada kecepatan informasi yang didapat dan bagaimana pengolahannya. Maka bila terjadi kerusakan pada basis data, dapat mengakibatkan lumpuhnya suatu perusahaan.

b.

Membuat ulang data sangat sulit dan membutuhkan biaya yang besar Seperti yang diketahui bahwa data suatu perusahaan tidak hanya penting, namun juga sangat sulit untuk digantikan bila data tersebut hilang. Sangat lebih mudah mengembalikan data dari backup daripada membuat ulang data.

c.

Downtime yang sangat mahal Bila terjadi sesuatu pada sistem penyimpanan data, kerugian yang terjadi selama sistem tersebut berhenti akan sangatlah besar.

14 d.

Persepsi publik dapat membuat dan menghancurkan bisnis Pelanggan suatu perusahaan selalu mengharapkan suatu jaminan keamanan berbisnis dengan perusahaan tersebut. Apabila tidak ada jaminan bahwa kerjasama tersebut aman maka akan mengakibatkan perusahaan kehilangan pelanggan. Sebaliknya apabila ada jaminan keamanan berbisnis dengan perusahaan tersebut, akan menaikkan citra dari perusahaan dan tentu saja akan menaikkan jumlah pelanggan bagi perusahaan.

2.2.3 Ancaman Terhadap Data Seperti yang telah diuraikan pada sub bab sebelumnya, betapa pentingnya suatu data, maka menurut Anil Desai (2001, pp 5-7) ada banyak ancaman terhadap data, antara lain : a.

Kerusakan piranti lunak dan perangkat keras Kerusakan pada perangkat keras seperti rusaknya media penyimpanan / storage dapat menyebabkan data dapat hilang secara total, karena hal tersebut mengakibatkan tempat penyimpanan data tidak dapat terbaca lagi. Salah satu pencegahannya adalah dengan menggunakan sistem redudancy, yaitu membuat duplikat sistem yang berfungsi sebagai backup secara berkala.

b.

Orang dengan intensi yang baik Seringkali orang yang berintensi baik juga melakukan kesalahankesalahan secara tidak sengaja sehingga menyebabkan kerusakan data / kerusakan piranti keras seperti kesalahpahaman, kurangnya pelatihan,

15 dan kesalahan fisik (seperti menjatuhkan kopi di atas komputer atau tidak sengaja melakukan reboot komputer). c.

Orang dengan intensi yang buruk Banyak sekali orang yang secara sengaja ingin mendapatkan dan menghancurkan data suatu sistem. Ancaman yang utama berasal dari jaringan internet di mana banyak sekali hacker yang mencoba merusak data suatu organisasi.

d.

Bencana alam Bencana alam dapat terjadi kapan saja dan di mana saja secara tiba-tiba sehingga diperlukan suatu backup data berkala untuk mengantisipasi adanya bencana ini.

e.

Masalah potensial lainnya Ada banyak sekali masalah potensial lainnya seperti yang terjadi pada tahun 2000 di mana masih banyak sistem yang masih menggunakan tahun sebanyak dua digit (masalah Y2K).

2.3

XML 2.3.1 Definisi eXtensible Markup Language (XML) adalah sebuah meta-language (bahasa yang menjelaskan bahasa yang lain) yang memungkinkan perancang untuk dapat membuat tag-tag mereka sendiri, untuk menyediakan fungsifungsi yang tidak terdapat di dalam HTML (Hypertext Markup Language) (Connolly, 2002, p1006).

16 XML adalah suatu format universal yang digunakan untuk mendeskripsikan dan mempertukarkan struktur dokumen dan data pada internet. XML merupakan salah satu bagian dari Standard Generalized Markup Language (SGML) dan disahkan oleh World Wide Web Consortium (W3C). XML mendefinisikan struktur data dalam format yang terbuka untuk semua platform. Selain itu XML juga menjadikan data mudah untuk ditransfer antar jaringan. XML dituliskan dalam sebuah file dengan format teks ASCII biasa. XML hanya mendeskripsikan bagaimana struktur dari sebuah data, bukan bagaimana seharusnya data tersebut ditampilkan seperti pada Hypertext Markup Language (HTML).

2.3.2 Keuntungan Beberapa keuntungan dari XML (Wikanta, 2001, pp 10-11) : 1.

Ekstensibilitas Ekstensibilitas

berarti

adanya

suatu

kebebasan

untuk

menentukan tag-tag sendiri sesuai kebutuhan. 2.

Memisahkan data dengan presentasi XML memungkinkan pemisahan data dengan presentasi. Artinya, sebuah data hanya berisi data saja tanpa informasi lain mengenai cara menampilkannya. Tag-tag pada XML menjelaskan mengenai isi datanya. Misal : Bandung

Tag menjelaskan Bandung merupakan sebuah nama bukan sebuah kota.

17 3.

Fungsi pencarian yang lebih tepat Jika menggunakan XML, orang akan mudah dalam menemukan dan mencari informasi. Misalnya, pencarian seseorang bernama “Bandung”, jika dalam HTML, maka semua kata “Bandung” baik merupakan nama kota atau nama orang atau nama lainnya akan ditampilkan. Akan tetapi, dalam XML pencarian dapat dilakukan dengan mencari tag yang isi atau nilainya adalah Bandung sehingga hasil pencarian akan lebih tepat.

2.3.3 Bagian Dokumen XML Berikut ini adalah salah satu contoh dokumen XML : Sarah Bellum Colonel Timeslip <subject>Robot-sitting instructions <message>Thanks for watching my robot pal Zonky while I'm away. He needs to be recharged <emphasis>twice a day and if he starts to get cranky, give him a quart of oil. I'll be back soon, after I've tracked down that evil mastermind Dr. Indigo Riceway.

18 Sebuah dokumen XML terdiri dari bagian-bagian yang disebut node (Junaedi, 2003, pp 6-7) yaitu : 1.

Root node, yaitu node yang melingkupi keseluruhan dokumen. Dalam satu dokumen XML hanya ada satu root node. Root node biasa disebut juga root element.

2.

Element node, yaitu bagian dari dokumen XML yang ditandai dengan tag pembuka dan tag penutup, atau bisa juga tag tunggal elemen kosong.

3.

Atribut node, di mana nama dan nilai atribut pada tag awal sebuah elemen atau pada tag tunggal.

4.

Text node, adalah teks yang merupakan isi dari sebuah elemen, ditulis di antara tag pembuka dan tag penutup.

5.

Comment node, adalah baris komentar yang tidak dieksekusi oleh parser.

6.

Processing Instruction Node, adalah perintah pengolahan dalam dokumen XML. Node ini diawali dengan “”. Akan tetapi header standar XML bukanlah processing instruction node.

7.

Name space node, adalah node yang mewakili deklarasi namespace. XML mempunyai beberapa aturan dasar untuk pembuatan dokumen XML yang rapi atau well-formed. Dokumen yang well-formed adalah dokumen yang tunduk pada seperangkat aturan minimal yang memungkinkan dokumen diproses oleh browser atau program lainnya.

19 Beberapa aturan dasar pembuatan dokumen XML well-formed (Young, 2000, p25) : 1.

Dokumen tersebut harus mempunyai persis satu elemen tingkat teratas (root element).

2.

Elemen-elemen harus disarangkan dengan tepat.

3.

Setiap elemen harus memiliki tag awal dan tag akhir.

4.

Nama tipe elemen dalam tag awal harus persis berhubungan dengan nama dalam tag akhir yang bersangkutan.

5.

Nama-nama

tipe

elemen

bersifat

case-sensitive

(membedakan

penulisan huruf besar dengan huruf kecil).

2.4

Kompresi Data Kompresi data adalah suatu ilmu pengetahuan untuk merepresentasikan informasi dalam ukuran yang lebih kecil. Proses pembuatan representasi ini dilakukan dengan cara mengidentifikasi dan menggunakan struktur yang ada di dalam data. Data dapat berupa karakter di dalam file teks atau angka di dalam file suara atau gambar (Sayood, 2006). Teknik kompresi terdiri dari dua bagian, yaitu algoritma kompresi yang memproses input X dan menghasilkan representasi Xc yang memiliki bit yang lebih sedikit, dan algoritma rekonstruksi yang memproses input representasi Xc dan menghasilkan rekonstruksi Y. Berdasarkan kebutuhan rekonstruksi, kompresi data dapat dibagi menjadi dua yaitu kompresi lossless (di mana Y identik dengan X) dan kompresi lossy di mana rekonstruksi Y berbeda dengan X).

20 2.4.1 Klasifikasi Algoritma Kompresi 1.

Kompresi Lossless dan Lossy Teknik pengompresan data dapat diklasifikasikan menjadi dua tipe kompresi yaitu pengompresan lossless dan lossy. Kompresi lossless dan lossy merupakan istilah yang mendeskripsikan apakah seluruh informasi data dari suatu file asli dapat dikembalikan ke seperti semula atau tidak pada proses dekompresi. Teknik kompresi lossles, seperti namanya, tidak menyebabkan hilangnya informasi. Jika data telah dikompresi dengan teknik lossless, data yang asli dapat direkonstruksi secara sempurna dari data yang telah dikompres tersebut. Teknik lossless biasanya digunakan oleh program yang tidak mempunyai toleransi terhadap perbedaan antara data yang asli dan yang telah direkonstruksi. Teknik ini paling banyak digunakan untuk kompresi teks. Sangat penting untuk mendapatkan hasil rekonstruksi yang identik dengan teks yang asli, karena perbedaan yang kecil saja dapat mengakibatkan perbedaan arti. Namun bukan hanya untuk teks saja, teknik ini juga digunakan untuk data-data yang penting. Sebagai contoh adalah gambar hasil radiologi dan gambar dari satelit. Jika gambar hasil radiologi yang telah dikompres tidak dapat direkonstruksi menjadi sama seperti yang asli, maka akan terdapat kesalahan diagnosa pada penyakit pasien. Sama hal nya dengan gambar satelit, jika data rekonstruksi tidak

21 identik dengan yang asli maka dapat mengakibatkan kesalahan yang fatal. Teknik kompresi lossy menyebabkan hilangnya informasi. Data yang telah dikompresi tidak direkonstruksi sama seperti data yang asli. Dengan adanya pengurangan informasi, maka rasio kompresi menjadi lebih tinggi daripada teknik kompresi lossless. Pada

beberapa

aplikasi,

pengurangan

informasi

tersebut

bukanlah suatu masalah. Sebagai contoh ketika menyimpan data suara manusia, menyimpan data yang asli tidak diperlukan. Berkurangnya kualitas suara dapat ditoleransi sejauh isi suara masih dapat dimengerti (Sayood, 2006).

2.

Kompresi Statistical dan Dictionary Berdasarkan teknik yang dipakai, algoritma kompresi dapat dibagi menjadi dua bagian besar, yaitu yang menggunakan model statistik dan dictionary. Pada model statistik, algoritma kompresi menggunakan kode yang berbeda-beda panjangnya, kode yang lebih pendek digunakan untuk simbol yang muncul lebih banyak di dalam data. Dalam menggunakan algoritma kompresi statistik, ada dua hal yang harus diperhatikan yaitu menentukan kode yang tidak dapat diartikan secara ambigu dan menentukan kode yang memiliki ukuran rata-rata minimum. Algoritma kompresi yang termasuk model statistik ini adalah algoritma Shannon-Fano, Huffman, Arithmetic, PPM, dan lain-lain.

22 Algoritma kompresi statistik menggunakan model statistik dari data input dan kualitas kompresi bergantung pada seberapa baik model tersebut.

Metode

kompresi

yang

berbasis

dictionary,

tidak

menggunakan model statistik ataupun kode yang berbeda-beda panjangnya. Metode ini menentukan rangkaian simbol-simbol dan melambangkannya

dengan

sebuah

tanda.

Dictionary

dapat

menampung simbol yang statis ataupun dinamis. Statis berarti isi dictionary tidak dapat dihapus hanya bisa ditambah. Sedangkan dinamis berarti memperbolehkan penambahan dan penghapusan isi dictionary ketika data input dibaca. Algoritma yang menggunakan metode dictionary antara lain algoritma Lempel-Ziv (LZ) dan berbagai macam variannya, deflate, kompresi pada file GIF dan PNG, dan lain-lain (Salomon, 2004).

2.4.2 Encoding dan Decoding Pada umumnya pengompresan data terdiri dari dua proses yang digunakan dalam program atau peralatan yaitu : (http://www.newmediarepublic.com/dvideo/compression/adv04.html) a. Encoding adalah suatu proses pada software atau hardware di mana program atau peralatan melakukan pengkodean dalam format tertentu. Program atau peralatan yang melakukan proses encoding disebut encoder atau coder. Dalam kompresi data, file-file data yang akan dikompres menggunakan program encoding. Bit-bit dalam file aslinya akan diencode

23 dengan

menggunakan

algoritma

pengompresan

yang

diinginkan,

sehingga ukuran hasil kompresi akan lebih kecil dari ukuran aslinya. b. Decoding adalah suatu proses pada software atau hardware di mana program atau peralatan melakukan penguraian kode dari file hasil encoding. Program atau peralatan yang melakukan proses decoding disebut decode. Peralatan yang dapat melakukan proses encoding dan decoding disebut codec. Dalam proses decoding, file hasil dari proses encoding akan dikembalikan ke bentuk aslinya dengan algoritma pengompresan.

2.4.3 Rasio Kompresi Rasio kompresi adalah istilah komputer yang digunakan untuk mengukur pengurangan ukuran data yang dihasilkan oleh suatu algoritma kompresi

(http://www.fact-index.com/d/da/data_compression_ratio.html).

Cara yang biasa digunakan untuk mengekspresikan suatu rasio kompresi adalah dengan menggunakan persentase, yaitu dengan rumus :

R=

S−P × 100% S

Di mana : R = Rasio kompresi (%) S = Ukuran file sebelum dikompres (bytes) P = Ukuran file setelah dikompres (bytes)

24 2.4.4 XMill

XMill adalah sebuah algoritma untuk melakukan kompresi terhadap data dalam bentuk XML yang biasanya mencapai rasio kompresi dua kali lipat daripada kompresi biasa. XMill tidak membutuhkan informasi skema file XML namun skema tersebut dapat digunakan untuk meningkatkan rasio kompresi. XMill yang dikembangkan menggunakan alat kompresi yang telah ada yaitu gzip. XMill dapat ditingkatkan dengan menggunakan kompresi khusus yang sesuai dengan tipe data yang disimpan, seperti DNA, gambar, dan lain-lain (Liefke, p1). XMill didesain untuk menggunakan keteraturan format dalam data XML untuk meningkatkan kompresi. Keteraturan tersebut dapat disediakan sebagai input untuk menjadi alat bantu XMill. Namun hal tersebut tidak wajib diperlukan, karena input tersebut tidak mempengaruhi data. XMill menggunakan tiga prinsip dasar dalam mengkompresi data XML (Liefke, p2) : 1.

Memisahkan struktur dari data Struktur berisi tag dan atribut XML dan berbentuk tree. Data terdiri dari urutan karakter yang merepresentasikan isi dan nilai atribut. Struktur dan data dikompres secara terpisah.

2.

Mengelompokkan data yang artinya sama Data dikelompokkan ke dalam sebuah container dan setiap container dikompres secara terpisah. Sebagai contoh semua data

25 dimasukkan ke dalam satu container, sedangkan semua data dimasukkan ke container yang kedua.

3.

Mengkompresi tiap kelompok data sesuai dengan tipe datanya Beberapa data berbentuk teks, ada juga yang angka, atau urutan DNA. XMill menggunakan kompresi yang berbeda untuk setiap tipe

data.

Secara garis besar, arsitektur XMill dapat digambarkan sebagai berikut (Liefke, p9) :

Gambar 2.1 Gambar Arsitektur XMill

Data XML dianalisis oleh SAX-Parser yang mengirim setiap token (tag, atribut, atau nilai data) ke path processor. Oleh path processor, tag dan atribut yang membentuk struktur XML dikirim ke structure container. Nilai

26 data dikirim ke bermacam data container sesuai dengan letak data (path) tersebut. Structure container dan setiap data container dikompresi secara terpisah menggunakan gzip kemudian disatukan menjadi satu kesatuan output. Teknik pemisahan struktur dari isi data dilakukan dengan cara tag awal disimpan dan diberi angka, sedangkan tag akhir diganti dengan simbol /. Nilai data digantikan dengan nomor container. Sebagai contoh diambil file XML sebagai berikut : <Title lang="English"> Transaction Processing Gray Reiter

Struktur file XML tersebut divisualisasikan sebagai berikut : <Title lang="C1"> C2 C3 C3

Kemudian jika dilakukan encoding terhadap struktur tersebut akan menjadi : Book = #1, Title = #2, @lang = #3, Author = #4 Structure = #1 #2 #3 C1 / C2 / #4 C3 / #4 C3 / /

27 Whitespace seperti spasi di antara tag-tag diabaikan, nantinya decompressor akan menggantinya dengan simbol standar. Sedangkan untuk

memasukkan setiap nilai data ke data container yang berbeda, setiap container diberi path untuk data yang disimpan. Path digunakan untuk

memberi tanda lokasi tag tersebut. Sebagai contoh, nilai data Transaction Processing akan mempunyai path /Book/Title, sedangkan nilai data Gray mempunyai path /Book/Author. Setiap nilai data yang ada di

dalam dokumen XML akan dimasukkan ke container sesuai dengan pathnya.

2.4.5 Algoritma LZ77

LZ77 termasuk algoritma kompresi yang menggunakan dictionary. Pada pendekatan ini, dictionary yang digunakan adalah bagian dari urutan sebelumnya yang diproses. Encoder memproses urutan input menggunakan sliding window. Window terdiri dari dua bagian, yaitu search buffer yang

mengandung bagian yang sedang diproses, dan look-ahead buffer yang mengandung bagian selanjutnya yang akan diproses. Pada gambar 2.2, search buffer terdiri dari delapan simbol, sedangkan look-ahead buffer

terdiri dari tujuh simbol. Dalam prakteknya, ukuran buffer tersebut jauh lebih besar (Sayood, 2006).

Gambar 2.2 Buffer pada LZ77

28 Untuk

memproses

urutan

pada

look-ahead

buffer,

encoder

memindahkan pointer pencari kembali ke search buffer sampai menemukan simbol yang sesuai dengan simbol pertama pada look-ahead buffer. Jarak antara pointer dengan look-ahead buffer disebut offset. Encoder kemudian memeriksa simbol yang mengikuti simbol di lokasi pointer apakah cocok dengan simbol berikutnya pada look-ahead buffer. Jumlah semua simbol yang cocok disebut match length. Encoder mencari match length yang paling maksimum. Ketika sudah ditemukan panjang maksimum tersebut, maka encoder menyimpan dalam triple (o, l, c), di mana o adalah offset, l adalah match length, dan c adalah simbol berikutnya setelah pasangan yang cocok

pada look-ahead buffer. Sebagai contoh pada gambar 2.2, offsetnya adalah 7, match length adalah 4 (untuk urutan karakter abra), dan simbol yang

mengikuti pasangan yang cocok adalah r. Jika tidak ditemukan data yang cocok, maka offset dan match length bernilai 0. Untuk menunjukkan bagaimana proses decoding bekerja, anggap urutan cabraca sudah di-decode dan berikutnya terdapat triple <0,0,C(d)>, <7,4,C(r)>, dan <3,5,C(d)>. Triple yang pertama

sangat mudah didecode, tidak ada pasangan dengan urutan sebelumnya, maka simbol berikutnya adalah d. String yang telah di-decode menjadi cabracad. Elemen pertama pada triple berikutnya berarti decoder harus

menggerakkan pointer tujuh karakter ke belakang dan menduplikasi empat karakter dari titik tersebut, kemudian menambahkan karakter r di paling belakang. Maka string yang didapat menjadi cabracadabrar. Triple

29 terakhir menandakan mundur sebanyak tiga karakter dan menduplikasi lima karakter sehingga string menjadi cabracadabrarrarrad.

2.4.6 Algoritma Huffman

Metode yang banyak digunakan untuk kompresi data adalah algoritma Huffman. Algoritma ini menjadi dasar kebanyakan program yang digunakan pada komputer personal. Beberapa program hanya menggunakan metode Huffman, sedangkan yang lain menggunakan algoritma ini sebagai satu bagian dari beberapa algoritma lain yang dipakai (multistep compression) (Salomon, 2004, p68). Algoritma ini diciptakan oleh David A. Huffman pada tahun 1952 sebagai bagian dari tugas kelas yang diajar oleh Robert Fano di MIT. Kode Huffman yang dihasilkan dari algoritma ini disebut prefix code. Prosedur Huffman didasarkan pada dua hal agar mendapatkan prefix code yang paling optimal : 1.

Simbol yang muncul lebih sering mempunyai kode yang lebih pendek daripada simbol yang jarang muncul

2.

Dua simbol yang paling jarang muncul mempunyai panjang yang sama Sangat mudah untuk memahami bagian pertama. Jika simbol yang

lebih sering muncul mempunyai kode yang lebih panjang daripada simbol yang jarang muncul, maka rata-rata bit per simbol menjadi lebih besar dibandingkan jika kondisi tersebut dibalik. Untuk memahami bagian kedua, perhatikan contoh berikut. Misalkan kode optimum C untuk dua simbol yang paling jarang muncul mempunyai

30 panjang yang berbeda. Misalkan kode yang lebih panjang mempunyai k bit lebih banyak daripada kode yang lebih pendek. Hal ini berarti jika k bit terakhir dihapus dari kode yang lebih panjang, maka kita masih memiliki kode yang berbeda. Karena kode tersebut mewakili simbol dengan frekuensi terkecil, maka tidak ada kesalahan ketika kode yang lebih pendek menjadi prefix dari kode yang lain. Dengan menghapus k bit tersebut, maka diperoleh rata-rata bit yang lebih kecil. Metode ini dimulai dengan membuat daftar semua simbol diurutkan menurun sesuai dengan frekuensinya. Kemudian dibuatlah sebuah tree dengan satu simbol pada setiap leafnya. Hal ini dilakukan dalam beberapa langkah, dengan setiap langkah mengambil dua simbol dengan frekuensi terkecil, menghapusnya dari daftar dan menggantinya dengan simbol pembantu yang merepresentasikan keduanya. Ketika daftar telah diproses menjadi hanya satu simbol pembantu (yang merepresentasikan simbol keseluruhan), tree sudah selesai dibentuk. Kemudian tree akan ditelusuri (traverse) untuk menentukan kode setiap simbol.

Sebagai contoh terdapat daftar frekuensi sebagai berikut : Tabel 2.1 Tabel Contoh Daftar Frekuensi Karakter Karakter a1 a2 a3 a4 a5 Frekuensi 40 20 20 10 10

31 Proses kompresi dilakukan dengan langkah-langkah sebagai berikut : 1.

a4 dikombinasikan dengan a5 dan digantikan dengan simbol gabungan a45, di mana frekuensinya adalah 20.

2.

Sekarang tinggal tersisa 4 simbol, a1 dengan frekuensi 40, dan a2, a3, dan a45 dengan frekuensi masing-masing 20. Simbol a3 dan a45 dipilih, gabungkan keduanya dan ganti dengan simbol pembantu a345 yang frekuensinya 40.

3.

Tiga simbol tersisa, a1, a2, dan a345, dengan frekuensi 40, 20, dan 40. Simbol a2 dan a345 dipilih, gabungkan dan ganti dengan simbol a2345 yang frekuensinya 60.

4.

Akhirnya, gabungkan dua simbol tersisa, a1 dan a2345 dan ganti dengan a12345 dengan frekuensi 100.

Setelah tree selesai dibuat, tambahkan kode 0 untuk rusuk atas dan kode 1 untuk rusuk bawah.

Gambar 2.3 Gambar Huffman Tree

32 Kode-kode yang didapat adalah 0, 10, 110, 1110, dan 1111. Jumlah bit yang digunakan untuk menyimpan keseluruhan kode adalah 40 * 1 + 20 * 2 + 20 * 3 + 10 * 4 + 10 * 4 = 220 bit. Hal ini berarti 2.2 bit per simbol yang menandakan adanya pengurangan karena satu simbol biasanya disimpan dengan 8 bit. Daftar simbol dan frekuensi harus disimpan agar proses dekompresi dapat berjalan. Hal ini berati menambah beberapa byte ke hasil kompresi. Algoritma dekompresi sangatlah sederhana. Mulai pada awal, baca bit pertama pada hasil kompresi. Jika bit tersebut adalah nol, maka bergeraklah ke rusuk atas dari tree, jika bernilai satu maka bergeraklah ke rusuk bawah dari tree. Baca bit berikutnya dan lakukan hal yang sama. Jika menemui sebuah leaf, maka sebuah simbol asli telah ditemukan dan simbol tersebut dimasukkan ke dalam hasil dekompresi. Kemudian dilanjutkan dengan bit berikutnya.

2.5

Unified Modelling Language (UML) Unified Modelling Language pertama kali dikembangkan pada pertengahan

tahun 1990 oleh perusahaan Rational Software. UML telah menjadi standar yang digunakan untuk membuat rancangan aplikasi berorientasi obyek. Menurut Booch, Grady, dkk. (1999, p13), Unified Modelling Language merupakan suatu bahasa yang menggunakan model dan diagram standar untuk merancang model bagi suatu proyek yang berbasis pemrograman berorientasi objek. UML adalah suatu bahasa standar untuk membuat cetak biru piranti lunak. Dengan membuat cetakan biru (blue print) akan membantu pengembang aplikasi untuk memvisualisasikan

33 permasalahan yang dihadapi dalam pengembangan suatu proyek. UML membantu pengembang aplikasi untuk mengetahui kebutuhan pengguna (user requirement), membantu rancangan proyek yang lebih baik dan untuk menghasilkan kode program yang lebih baik. UML hanya suatu bahasa dan juga satu bagian dari metode pengembangan perangkat lunak. Banyak program yang dapat digunakan untuk membuat diagram UML, misalnya Rational Rose, Visio 2000, Visual Modeler, Enterprise Architect, dan sebagainya. Use case diagram merupakan suatu diagram yang menunjukkan sekumpulan use case, actor, dan relationship. Diagram ini merupakan sesuatu yang penting

terutama dalam mengorganisasi dan memperagakan perilaku suatu sistem. Notasinotasi yang terdapat pada use case diagram : 1.

Use Case Use case merupakan suatu deskripsi dari sekumpulan urutan tindakan

yang dilaksanakan sistem untuk menghasilkan hasil yang diperlukan actor.

Gambar 2.4 Contoh Simbol Use Case 2.

Actor Actor merupakan sekumpulan peran yang dimainkan seorang user dari use case ketika saling berinteraksi dengan use case.

Gambar 2.5 Contoh Simbol Actor

34 3.

Include Include merupakan sebuah hubungan dalam use case diagram, yang

digunakan bila ada beberapa skenario yang berulang di beberapa use case lainnya. Agar tidak terjadi pengulangan, skenario ini dibuat menjadi sebuah use case yang akan diliputi oleh use case lainnya. CancelOrder «uses»

FindOrder Actor1

Gambar 2.6 Contoh Include

4.

Extend Extend merupakan sebuah hubungan dalam use case diagram yang

digunakan saat sebuah variasi atas sebuah behaviour normal digambarkan, di mana ingin digunakan bentuk yang lebih mudah untuk dikontrol dan extension points dalam use case dasar dideklarasikan.

5.

Generalization

Hubungan ini memungkinkan suatu child use case mewarisi behaviour yang dimiliki oleh parent use case.