BAB III : PERANCANGAN DAN IMPLEMENTASI SISTEM

6

1.8 Sistematika Penulisan

Sistematika penulisan dari skripsi ini terdiri dari beberapa bagian utama sebagai berikut:

BAB I : PENDAHULUAN Bab ini menjelaskan mengenai latar belakang masalah pemilihan judul, rumusan masalah, batasan masalah, tujuan penelitian, manfaat penelitian, metodologi penelitian, dan sistematika penulisan skripsi.

BAB II : LANDASAN TEORI Bab ini membahas mengenai dasar teori tentang algoritma kompresi LZW, Arithmetic Coding, RLE, transformasi BWT, dan teori Big-O yang digunakan untuk membandingkan kompleksitas setiap algoritma.

BAB III : PERANCANGAN DAN IMPLEMENTASI SISTEM Bab ini menguraikan tentang perancangan sistem yang meliputi perancangan setiap algoritma serta analisis untuk menentukan kompleksitasnya, dan interface sistem. Kemudian hasil rancangan tersebut akan diimplementasikan dengan bahasa pemrograman Borland Delphi.

BAB IV : ANALISIS DAN PENGUJIAN SISTEM Bab ini berisi tentang pengujian sistem yang telah diimplementasikan sekaligus melakukan analisis perbandingan kinerja setiap algoritma.

BAB V. KESIMPULAN DAN SARAN Bab ini berisi kesimpulan dari uraian bab-bab sebelumnya dan hasil penelitian yang diperoleh, serta saran-saran yang diharapkan dapat bermanfaat untuk pengembangan selanjutnya.

Universitas Sumatera Utara

BAB 2

LANDASAN TEORI

Pada bab ini akan dibahas dasar teori tentang kompresi data dan algoritma kompresi Lempel Ziv Welch (LZW), Arithemtic Coding, Run-Length Encoding (RLE), dan Burrows-Wheeler Transform (BWT). Kemudian akan dijelaskan pula tentang file uji yang akan digunakan dalam penelitian ini disertai dengan teori penghitungan kompleksitas algoritma dengan Big-O.

2.1 Kompresi Data

Kompresi data merupakan cabang ilmu komputer yang bersumber dari teori informasi. Teori informasi sendiri dipelopori oleh Claude Shannon sekitar tahun 1940-an. Teori ini mendefenisikan jumlah informasi di dalam pesan sebagai jumlah minimum bit yang dibutuhkan yang dikenal sebagai entropy. Teori ini juga memfokuskan

pada

berbagai metode

tentang

informasi

termasuk tentang

redundancy (informasi tak berguna) pada suatu pesan dimana semakin

banyak

redundancy maka semakin besar pula ukuran pesan, upaya mengurangi redundancy inilah yang akhirnya melahirkan subjek ilmu tentang kompresi data.

Menurut David Salomon [1, 2, 3] data kompresi adalah proses pengkonversian input data stream (sumber stream, atau data mentah asli) ke bentuk stream lain (output stream, atau stream yang sudah terkompresi) yang memiliki ukuran yang lebih kecil. Stream adalah sebuah file ataupun buffer dalam memory. Sedangkan menurut Ida Mengyi Pu [4] kompresi data adalah konteks dari ilmu komputer, ilmu (dan seni) yang menyajikan informasi ke dalam bentuk yang compact. Pada umumnya data kompresi terdiri dari pengambilan stream simbol dan mengubahnya ke dalam bentuk kode. Jika kompresi efektif, hasil kode stream akan lebih kecil daripada simbol asli [5].


8

Namun pada dasarnya data kompresi bertujuan untuk mengubah ukuran data menjadi lebih kecil dari ukuran semula sehingga dapat menghemat media penyimpanan dan waktu untuk transmisi data, beberapa penggunaan kompresi data dapat dilihat seperti pada gambar-gambar yang diperoleh dari internet yang biasanya dalam format JPEG (Joint Photographic Experts Group

atau GIF (Graphical

Interchange Format), modem yang sebagian besar menggunakan kompresi, HDTV (High Defenition Television) akan dikompresi menggunakan MPEG-2 (Moving Picture Experts Group 2), dan beberapa file sistem yang secara otomatis dikompresi ketika file tersebut disimpan [6]. Untuk melakukan kompresi data telah banyak algoritma yang telah dikembangkan. Namun, secara umum algoritma kompresi data dapat di bagi menjadi dua kelompok besar berdasarkan dapat tidaknya rekontuksi ke data asli dilakukan yaitu:

1. Kompresi Lossless Kompresi lossless adalah kompresi yang menjaga keakuratan data dimana perubahan atau hilangnya informasi bahkan beberapa bit saja pada data selama proses kompresi tidak bisa ditoleransi. Sehingga teknik kompresi ini bersifat reversible yaitu hasil kompresi bisa dikembalikan ke bentuk semula. Teknik ini lebih cocok diaplikasikan pada file database, teks, gambar medis, atau photo hasil satelit dimana hilangnya beberapa detail pada data dapat berakibat fatal. Contoh algoritma lossless adalah Arithmetic Coding, Huffman Coding, dan lain-lain.

2. Kompresi Lossy Pada kompresi lossy perubahan atau hilangnya beberapa informasi atau bit pada data bisa ditoleransi, sehingga hasil kompresi tidak bisa lagi dikembalikan ke bentuk semula (irreversible). Namun, hasil kompresi masih bisa mempertahankan informasi utama pada data. Kompresi ini cocok diaplikasikan pada file suara, gambar atau video. Umumnya teknik ini menghasilkan kualitas hasil kompresi yang rendah, namun rasio kompresinya cenderung tinggi. Contoh algoritma kompresi lossy adalah Fractal Compression, Wavelet Compression, Wyner-Ziv Coding (WZC), dan lain-lain.


9

2.2 Algoritma Lempel Ziv Welch (LZW)

Algoritma LZW merupakan algoritma kompresi data lossless yang ditemukan oleh Terry Welch, dimana algoritma ini merupakan peningkatan dari versi sebelumnya yaitu algoritma Lempel Ziv 77 (LZ77) dan Lempel Ziv 78 (LZ78) yang dikembangkan oleh Abraham Lempel dan Jacob Ziv pada tahun 1977 dan 1978. Kemudian algoritma LZW dipublikasikan oleh Terry Welch pada tahun 1984 [12].

Algoritma LZW adalah algoritma yang bersifat adaptif dan berbasis dictionary, dimana selama proses kompresi atau dekompresi berlangsung algoritma ini menggunakan sebuah dictionary yang dibentuk selama pembacaan input stream. Dictionary dibentuk dengan tujuan untuk menyimpan karakter atau pola string tertentu yang berguna untuk mengkodekan simbol atau string pada input stream yang merujuk pada index dalam dictionary. Sebelum proses kompresi atau dekompresi dimulai, sebuah dictionary akan diinisialisasi dengan simbol atau karakter-karakter dasar penyusun input stream, sehingga nilai default sebuah dictionary akan berisi 256 karakter ASCII dengan index 0-255. Sehingga pada awal pembacaan proses encoding maupun decoding, karakter atau kode pertama akan selalu ditemukan pada dictionary. Tabel 2.1 Algoritma Dasar LZW Encoding Step 1: Step Step Step Step Step Step Step Step Step Step Step Step Step Step Step Step

2: 3: 4: 4a: 4b: 4c: 4d: 4e: 4f: 4g: 4h: 4i: 4j: 4k: 5: 6:

Dictionary terlebih dahulu diinisialisasi dengan karakter ASCII CurrentChars ← Karakter pertama dari input stream DictIndex ← 255 while not EOF character do begin NextChar ← Karakter selanjutnya dari CurrentChars ConcatStr ← CurrentChars + NextChar if ConcatStr ada pada Dictionary then begin CurrentChars ← ConcatStr end else begin Output ← Index dari CurrentChars pada dictionary Isi ke dalam Dictionary (DictIndex, ConcatStr) DictIndex ← DictIndex + 1 CurrentChars ← NextChar end end EncodedStream ← Output

Sebagai contoh, jika input stream: “BABAABAAAA” dikompresi dengan algoritma LZW, maka prosesnya dapat dilihat pada tabel 2.2 berikut:


10

Tabel 2.2 Contoh Proses Encoding String “BABAABAAAA”

Prefix P

Char C

String P+C di dalam dictionary?

Output (Codeword)

“B”

“A”

Tidak

66

“A”

“B”

Tidak

65

“B”

“A”

Ya

-

“BA”

“A”

Tidak

256

“A”

“B”

Ya

-

“AB”

“A”

Tidak

257

“A”

“A”

Tidak

65

“A”

“A”

Ya

-

“AA”

“A”

Tidak

260

“A”

EOF

-

65

[Index] Entry Baru [256] “BA” [257] “AB” [258] “BAA” [259] “ABA” [260] “AA” [261] “AAA” -

Maka hasil kompresi input stream “BABAABAAAA” adalah kumpulan angka pada kolom output pada Tabel 2.2, yaitu 66, 65, 256, 257, 65, 260, 65. Input stream sebelum kompresi adalah 10 x 8 = 80 bit, apabila kumpulan angka tersebut diubah ke dalam bentuk codeword dengan panjang 9 bit maka hasil kompresi menjadi 7 x 9 = 63 bit, sehingga terjadi penghematan sebesar 80 - 63 = 17 bit.

Proses decoding algoritma LZW hampir sama dengan proses encoding, yaitu dengan menginisialisasi terlebih dahulu dictionary dengan 0-255 index pertama dari karakter ASCII. Namun, pada decoding yang dibaca adalah kumpulan kode (angka) hasil kompresi. Selama proses pembacaan kode berlangsung, pada saat itu pula dilakukan pembentukan isi dictionary yang menjadi refrensi untuk pembentukan string asli.

Tidak seperti encoding, pada decoding isi dictionary selalu ditambahkan setiap pembacaan codeword, hal inilah yang memnungkinkan string asli dapat dikembalikan.


11

Tabel 2.3 Algoritma Dasar LZW Decoding Step 1: Step Step Step Step

2: 3: 4: 5:

Step 6: Step 6a: Step Step Step Step Step

6b: 6c: 6d: 6e: 6f:

Dictionary terlebih dahulu diinisialisasi dengan karakter ASCII PreviousCodeWord ← Codeword pertama dari encoded stream String ← toString(PreviousCodeWord); Char ← toChar(first input codeword); DictIndex ← 256; while NOT EOF encoded stream CurrentCodeWord ← codeword selanjutnya pada encoded stream if CurrentCodeWord ada pada Dictionary then begin String ← toString(CurrentCodeWord) end else begin String ← toString(PreviousCodeWord) + Char end;

Step 6g: Step 6h: Step 6i: Step Step Step Step

6j: 6k: 7: 8:

Output ← Output + String; Char ← Karakter pertama dari string sekarang insertToDictionary(DictIndex, toString(PreviousCodeWord) + Char; PreviousCodeWord ← CurrentCodeWord; DictIndex++; end DecodedStream ← Output

Sebagai contoh, jika kode: “66, 65, 256, 257, 65, 260, 65” didekompresi dengan algoritma LZW, maka prosesnya dapat dilihat seperti tabel di bawah ini: Tabel 2.4 Contoh Proses Decoding dari Encoded String “BABAABAAAA” Current Codeword di dalam dictionary?

Previous Codeword

Current Codeword

Output (string)

First Char of String

1

66

-

“B”

-

-

-

2

66

65

“A”

“A”

Ya

[256] BA

3

65

256

“BA”

“B”

Ya

[257] AB

4

256

257

“AB”

“A”

Ya

[258] BAA

5

257

65

“A”

“A”

Ya

[259] ABA

6

65

260

“AA”

“A”

Tidak

[260] AA

7

260

65

“A”

“A”

Ya

[261] AAA

No

[Index] Entry Baru


12

Hasil dekompresi dari tabel 2.4 adalah kumpulan karakter atau string pada kolom output yaitu “BABAABAAAA”. Pada baris pertama dari table 2.4 terlihat bahwa tidak ada penambahan apa-apa pada dictionary, karena inisialisiasi awal dari decoding adalah menerjemahkan langsung kode pertama dari stream kode, hal ini dilakukan karena kode tersebut selalu dapat dipastikan ada dalam dictionary, karena sebelumnya dictionary telah diisi dengan 0-255 index pertama yang berisi karakter ASCII.

2.3 Algoritma Arithmetic Coding

Pada umumnya algoritma kompresi data melakukan teknik pengkodean dengan penggantian satu atau beberapa simbol yang sama dengan kode tertentu, berbeda dengan Arithmetic Coding, algoritma ini mengkodekan seluruh input stream dalam suatu file dengan sebuah angka floating point dengan interval [0,1) atau angka yang lebih besar atau sama dengan 0 dan lebih kecil dari 1 ( 0 ≤ x < 1).

Arithmetic Coding memiliki sejarah yang penting karena pada saat itu algoritma ini berhasil menggantikan algoritma Huffman selama 25 tahun, Arithmetic Coding memiliki perfomansi yang lebih unggul daripada Huffman Coding khususnya apabila diaplikasikan pada kumpulan alphabet yang ukurannya relatif kecil, awalnya Arithmetic Coding diperkenalkan oleh Shannon Fano dan Elias, kemudian dikembangkan secara luas oleh Pasco (1976), Rissanene (1976, 1984), dan Langdon (1984), yaitu sebagai ide alternatif yang menggantikan setiap input simbol dengan sebuah codeword, yaitu dengan mengkodekan seluruh input stream dengan sebuah single floating point sebagai output proses kompresi [4].

Untuk melakukan proses kompresi maupun dekompresi, Arithmetic Coding membutuhkan dua fase, yaitu dengan terlebih dahulu menentukan probalitas dan range setiap simbol lalu melakukan proses encoding maupuan decoding berdasarkan informasi probalitas tersebut.


13

Jika sekumpulan simbol S pada pesan M = (S1, S2, S3,…SN) dengan probalitas P = (P1, P2, P3,…PN) dimana ∑p = 1, akan dapat diperoleh subinterval yang unik untuk setiap simbol S yang berada pada interval [0, 1), yaitu [14]: S1 = [0, P1) S2 = [P1, P1 + P2 ) S3 = [P1 + P2, P1 + P2 + P3) … SN = [P1 + P2 + P3 + ...+ PN – 1, P1 + P2 + P3 + … + PN) Misalnya, untuk string “LOSSLESS”, maka akan dapat diperoleh probalitas dan range setiap s imbol seperti pada tabel 2.5 berikut:

Tabel 2.5 Contoh Range String “LOSSLESS” Simbol

Probalitas

Range

E

1/8

0.000 – 0.125

L

2/8

0.125 – 0.375

O

1/8

0.375 – 0.500

S

4/8

0.500 – 1.000

Untuk proses encoding maupun decoding informasi pada tabel 2.5 mutlak diperlukan untuk meperoleh codeword maupun pada saat pembentukan pesan asli. Dalam pembuatan probalitas, tidak ada ketentuan urutan-urutan penentuan segmen/karakter, asalkan antara encoder dan decoder melakukan hal yang sama.

Proses encoding dari algoritma Arithmetic Coding dimulai dengan membaca satu byte dalam satu waktu, lalu memberinya sebuah angka floating point batas bawah low dan batas atas high secara unik, nilai low dan high selalu dipertahankan untuk menentukan nilai low dan high simbol berikutnya. Proses pembacaan simbol dilakukan secara terus-menerus sampai tidak ada lagi simbol yang tersisa. Hasil kompresi adalah sebarang nilai antara interval low dan high dari simbol yang terakhir


14

diproses, namun yang lebih sering digunakan adalah nilai low. Algoritma dasar Arithmetic Coding Encoding dapat dilihat pada tabel 2.6 berikut: Tabel 2.6 Algoritma Dasar Arithmetic Coding Encoding Step Step Step Step Step Step Step Step Step

1: 2: 3: 3a: 3b: 3c: 3d: 4: 5:

Low ← 0.0 High ← 1.0 while karakter masih ada dalam input stream do begin CurrentSymbol ← Symbol CodeRange ← High – Low High ← Low + CodeRange * HighRange(CurrentSymbol) Low ← Low + CodeRange * LowRange(CurrentSymbol) end while EncodedStream ← [Low, High)

Sebagai contoh, apabila string “BILL_GATES” di-encoding dengan menggunakan algoritma encoding pada tabel 2.6, maka proses pertama yang harus dilakukan adalah menentukan terlebih dahulu probalitas dan range masing-masing simbol. Probalitas dan range simbol untuk string “BILL_GATES” dapat dilihat tabel 2.7 berikut. Tabel 2.7 Probalitas dan Range String “BILL_GATES” Simbol

Probalitas

Range

_

1/10

0.00 – 0.10

A

1/10

0.10 – 0.20

B

1/10

0.20 – 0.30

E

1/10

0.30 – 0.40

G

1/10

0.40 – 0.50

I L

1/10 2/10

0.50 – 0.60 0.60 – 0.80

S

1/10

0.80 – 0.90

T

1/10

0.90 – 1.00

Pada tabel 2.7, yang perlu diketahui adalah bahwa tiap karakter melingkupi range yang telah disebutkan kecuali bilangan yang tertinggi. Jadi karakter ’T’ sesungguhnya mempunyai range mulai dari 0.90 – 0.99...


15

Setelah probalitas dan range setiap simbol diketahui, maka proses selanjutnya adalah melakukan encoding. Proses pertama yang dilakukan adalah membaca karakter pertama dari string ‘BILL_GATES’ yaitu karakter ‘B’, CodeRange = 1.00 – 0.00 = 1.00, HighRange(B) = 0.30, LowRange(B) = 0.20. Sehingga diperoleh:

High = Low + CodeRange * HighRange(B) = 0.00 + 1.00 * 0.30 = 0.30 Low = Low + CodeRange * LowRange(B) = 0.00 + 1.00 * 0.20 = 0.20

Proses selanjutnya membaca karakter kedua yaitu karakter ‘I’, CodeRange = 0.30 0.20 = 0.10, HighRange(I) =0.60, LowRange(I)=0.50. Sehingga diperoleh:

High = Low + CodeRange* HighRange(I) = 0.20 + 0.10 * 0.60 = 0.260 Low = Low + CodeRange * LowRange(I) = 0.20 + 0.10 * 0.50 = 0.250

Dan seterusnya sehingga diperoleh hasil seperti pada tabel 2.8 berikut:

Tabel 2.8 Proses Encoding String “BILL_GATES” Simbol

Low

High

Code_Range

0.00

1.00

1.00

B

0.20

0.30

0.10

I

0.250

0.260

0.010

L

0.2560

0.2580

0.0020

L

0.25720

0.25760

0.00040

_

0.257200

0.257240

0.000040

G

0.2572160

0.2572200

0.0000040

A

0.25721640

0.25721680

0.00000040

T

0.257216760

0.25721680

0.000000040

E

0.2572167720

S

0.2572167760 0.0000000040 0.25721677520 0.25721677560 0.00000000040


16

1.0

0.30

0.260

0.2580

0.25760

0.257240

0.2572200

0.257211680

0.257211680 0.2572167760 0.25721677560

0.257211680 0.260

0.25721677560

0.2580 A

B 0.30

0.25760

0.257216760

I 0.250

0.257240

0.257200 0.20

0.0

0.250

_ L

0.2560

0.2560

T E

0.2572200

L 0.20

0.2572167760

0.257211680 0.2572167720 G

0.2572160

0.257200 0.257200

S

0.25721677520

0.25721640 0.257200

0.2572160

0.25721640

0.257216760

0.2572167720 0.25721677520

Gambar 2.1 Nilai Interval String ”BILL_GATES”

Nilai akhir proses encoding adalah low = 0.25721677520 dan high = 0.25721677560. Jadi, nilai yang akan mengkodekan string ”BILL_GATES” adalah sebarang nilai yang berada pada interval [low, high).

Pada decoding, yang dilakukan adalah mencari simbol yang melingkupi kode yang sedang dicari. Sebagai contoh, apabila angka (kode simbol) adalah 0.41938, maka simbol yang melingkupi range tersebut adalah karakter “G”, sedangkan kode simbol 0.938 adalah karakter “T" dan seterusnya. Sesaat setelah simbol ditemukan maka range dari simbol sekarang kemudian di-update untuk menghilangkan efek dari range simbol sebelumnya. Algoritma Arithmetic Coding decoding selengkapnya diperlihatkan pada tabel 2.9 berikut.

Tabel 2.9 Algoritma Dasar Arithmetic Coding Decoding Step Step Step Step Step Step Step Step Step

1: 2: 3: 4: 4a: 4b: 4c: 4d: 5:

Low ← 0.0 High ← 1.0 Ambil Code Do Cari simbol yang yang berkorespodensi dengan Code CodeRange ← High – Low Code Code – Low Code Code/CodeRange until Simbol = EOF


17

Dengan menggunakan algoritma pada tabel 2.9 maka kode 0.25721677520 dapat di-decoding menjadi string “BILL_GATES” seperti diperlihatkan pada tabel 2.10 berikut. Tabel 2.10 Proses Decoding String “BILL_GATES” Code

Symbol

Low Range Symbol

High Range Code Symbol Range

0.2572167752

B

0.2

0.3

0.1

0.572167752

I

0.5

0.6

0.1

0.72167752

L

0.6

0.8

0.2

0.6083876

L

0.6

0.8

0.2

0.041938

_

0.0

0.1

0.1

0.41938

G

0.4

0.5

0.1

0.1938

A

0.2

0.3

0.1

0.938

T

0.9

1.0

0.1

0.38

E

0.3

0.4

0.1

0.8

S

0.8

0.9

0.1

0.0

Pada prakteknya, algoritma Arithmetic Coding seperti yang dijelaskan sebelumnya adalah kurang efektif karena sebenarnya encoder mapuan decoder memiliki keterbatasan pengolahan bilangan floating point dengan presisi yang sangat tinggi (tanpa pembulatan). Sehingga, hal ini dapat menyebabkan error pada saat encoding maupun decoding. Jadi, untuk mengatasinya algoritma Arithmetic Coding harus diimplementasikan dengan menggunakan bilangan integer 16 atau 32 bit, karena proses perhitungan bilangan integer jauh lebih cepat dan akurat daripada bilangan floating point.

2.4 Algoritma Arithmetic Coding Dengan Bilangan Integer Algoritma Arithmetic Coding dengan bilangan integer sebenarnya memiliki prinsip yang sama dengan menggunakan bilangan floating point. Namun, pada implementasi integer dilakukan modifikasi range 0-1 menjadi 0000h - FFFFh (16 bit hexadesimal)


18

[13]. Proses encoding pada tabel 2.8 memperlihatkan bahwa setiap angka MSB (Most Significant Byte) antara low dan high sama, maka nilai tersebut tidak akan pernah berubah untuk iterasi selanjutnya. Sehingga, apabila proses encoding terus dilanjutkan maka tidak akan ada output yang dihasilkan. Jadi, untuk mengatasi masalah tersebut, encoder harus mendeteksi apakah MSB (Most Significant Bit) low dan high sama, jika ternyata sama maka nilai tersebut harus di-shift out ke output, dan menambahkan bit 0 dan 1 pada LSB (Least Significant Bit) low dan high. Hal inilah yang memungkinkan proses encoding bisa menghasilkan kode yang infinite antara 0000h-FFFFh.

Contoh: Low = 0110 1100 0001 0001

MSB Sama

High = 0111 0101 1010 0011

MSB Low = MSB High = 011. Shift-out bit-bit tersebut, sehingga Output = 011

Kemudian shift-in bit 0 dan 1 pada LSB low dan high. Low = 0110 0000 1000 1000 High = 1010 1101 0001 1111

Namun, adakalanya pada saat encoding nilai low dan high saling mendekati (hampir sama). Contoh: low = 49995 dan high = 50003. Apabila proses encoding dilanjutkan maka nilai tersebut akan semakin dekat hingga akhirnya sama, jika hal ini terjadi maka tidak akan ada MSB yang akan di-output-kan sampai proses encoding selesai. Kondisi ini disebut underflow, yaitu MSB ke-dua dari low = 1, dan high = 0. Jadi, untuk mengatasinya encoder harus menyingkirkan bit tersebut, lalu menambahkan bit 0 dan 1 pada LSB low dan high.

Berikut contoh yang mendiskripsikan kondisi underflow dan setelah diatasi:

Low = 0110 0000 1000 1000

Low = 0000 0010 0010 0000

High = 1001 1101 0001 1111

High = 1111 0100 0111 1111

Underflow

Fresh


19

Tabel 2.11 Algoritma Dasar Arithmetic Encoding Dengan Bilangan Integer Step Step Step Step

1: 2: 3: 4:

Step 5: Step 5a: Step 5b: Step 5c: Step Step Step Step Step Step Step Step Step Step Step Step Step Step Step Step Step Step Step Step

5d: 5da: 5db: 5dc: 5dd: 5de: 5df: 5dg: 5dh: 5di: 5dj: 5dk: 5dl: 5dm: 5dn: 5do: 5dp: 5e: 5f: 6:

Probalitas ditentukan dan penskalaan dilakukan bila perlu Low ← 0000h High ← FFFFh Underflow ← 0 while karakter masih ada dalam input stream do begin CodeRange ← High – Low + 1 High ← Low + (CodeRange * HighRange(CurrentSymbol) / ∑Si) - 1 Low ←Low + (CodeRange * LowRange(CurrentSymbol)/∑Si) loop sampai 2nd MSB tidak sama If 2nd MSB Low = 2nd MSB High then begin Hapus 2nd MSB Low dan 2nd High Output ← Output + 2nd MSB Low While Underflow > 0 do begin Output ← Output + OppositeBit(2nd MSB Low) End Shift in bit 0 dan 1 pada Low dan High else if Low dan High sedang underflow then begin Underflow ← Underflow + 1 Hapus bit penyebab underflow Shift-in bit 0 dan 1 pada Low dan High end else begin Lanjut mengkodekan simbol berikutnya end end end end EncodedStream ← Output

Contoh, untuk mengkodekan string “ABCCEDAC” dengan menggunakan 7 bit, maka prosesnya dapat dilihat seperti berikut [7]: Tabel 2.12 Probalitas string “ABCCEDAC” Simbol A B C D E

Frekuensi 2 1 3 1 1

Low 0 2 3 6 7

High 2 3 6 7 8

Low = 0; High = 7Fh; CurrentSymbol = “A”; ∑ i = 8; { ∑ i adalah total frekuensi } CodeRange = High – Low + 1 = 7Fh – 0 + 1 = 128d High = Low + (CodeRange * HighRange(A) / ∑ i ) – 1 = 0 + (128 * 2 / 8) – 1 = 31d (0011111b)


20

Low = Low + (CodeRange * LowRange(A) / ∑ i) = 0 + (128 * 0 / 8) = 0d (000000b)

Setelah MSB low dan high diperiksa maka, Output = 00b Low = 0000000b (0d) High = 1111111b (127d)

Proses tersebut diteruskan sampai karakter yang akan dikodekan tidak ada lagi. Proses keseluruhan diringkas pada tabel 2.13 berikut ini. Tabel 2.13 Proses encoding string “ABCCEDAC” Chr

Low

High

Output

Setelah MSB di shift-out Low

Und

High

A

0000000 [0]

0011111 [31]

00

0000000 [0]

1111111 [127]

0

B

0100000 [32]

0101111 [47]

010

0000000 [0]

1111111 [127]

0

C

0110000 [48]

1011111 [95]

C

1000100 [68]

1100111 [103]

10

E

1001111 [71]

1001111 [79]

100

0111000 [56]

1111111 [127]

D

1101110 [110]

1110110 [118]

11

0111000 [56]

1011011 [91]

A

0110000 [48]

1000001 [65]

C

0011011 [27]

0110101 [53]

Sisa

1

0111

Setelah Underflow Low

High

0100000[32]

1111111[127]

0

0110110 [54]

1101011 [107]

0 1

0110000[48]

1110111[119]

3

0000000[0]

1000111[71]

0

1

Maka output dari encoding string “ABCCEDAC” adalah 00010101001101111. Sehingga terjadi pengompresian dari 8 x 8 = 64 bit menjadi 17 bit.

Proses decoding pada Arithmetic Coding memiliki prinsip yang hampir sama dengan proses encoding. Pada saat decoding, codeword dari encoded stream diinisialisasi dengan N bit pertama, maksudnya jika pada saat encoding encoder menggunakan 16 bit, maka pada saat decoding codeword harus diinisialisasi juga dengan 16 bit pertama.

Satu hal yang perlu diperhatikan pada saat decoding adalah, sesaat setelah simbol yang mencakup nilai codeword ditemukan. Maka range simbol tersebut harus di-update untuk menghilangkan efek dari range simbol sebelumnya, kemudian


21

menentukan nilai high dan low berdasarkan simbol yang aktif, karena hal serupa juga telah dilakukan pada saat encoding. Algoritma dasar Arithmetic Coding decoding dengan bilangan integer ditunjukkan pada tabel 2.14 berikut ini. Tabel 2.14 Algoritma Dasar Arithmetic Decoding Dengan Bilangan Integer Step Step Step Step

1: 2: 3: 4:

Step 5: Step 5a: Step 5b: Step 5c:

Step 5d: Step 5e: Step Step Step Step Step Step Step Step Step Step Step Step Step Step Step Step Step

5f: 5fa: 5fb: 5fc: 5fd: 5fe: 5ff: 5fg: 5fh: 5fi: 5fj: 5fk: 5fl: 5fm: 5g: 6: 7:

Codeword ← ambil N bit pertama dari encoded stream Ambil probalitas yang telah dibentuk pada saat encoding Low ← 0000h High ← FFFFh while karakter <> EOF do begin { update CodeRange } CodeRange ← High – Low + 1 Temp ← (Codeword - Low) + 1 * ∑Si / CodeRange EncodedSymbols ← Cari karakter yang berkorespondensi dengan Temp { update high dan low } High ← Low + (CodeRange * HighRange(CurrentSymbol) / ∑Si) - 1 Low ← Low + (CodeRange * LowRange(CurrentSymbol)/∑Si) loop sampai 2nd MSB Low dan High tidak sama If 2nd MSB Low = 2nd MSB High then begin Shift out MSB tersebut Shift in bit 0 dan 1 pada Low dan High Shift in bit selanjutnya untuk codeword else if Low dan High sedang underflow then begin Shift in bit selanjutnya untuk codeword Shift out bit penyebab underflow tersebut Shift-in bit 0 dan 1 pada Low dan High end else begin Lanjut mendekoding codeword berikutnya end end end end DecodedStream ← EncodedSymbols

2.5 Algoritma Run-Length Encoding (RLE)

Algoritma RLE adalah algoritma yang memanfaatkan karakter-karakter yang berulang secara berurutan pada data yaitu dengan mengkodekannya dengan sebuah string yang terdiri dari jumlah perulangan karakter yang terjadi, diikuti dengan sebuah karakter yang berulang tersebut [15]. Sehingga banyak tidaknya deretan karakter yang berulang pada data merupakan penentu keberhasilan kompresi algoritma RLE.


22

Namun, pada prakteknya setiap kode perlu ditambahkan sebuah penanda (marker byte) yang berfungsi untuk menghindari keambiguan pada saat decoding. Jadi, secara umum format kode yang dihasilkan oleh algoritma RLE dapat dituliskan sebagai berikut

Tabel 2.15 Format Kode Deret Karakter Berulang m

n

s

dimana m adalah penanda (marker byte), n adalah jumlah deret karakter yang berulang, dan s sebuah karakter yang berulang tersebut.

Sebagai contoh apabila string: “AAAAABBACCCDDDDABCCCCCCC” dikompresi dengan algoritma RLE maka hasilnya adalah: “#5A#2B#1A#3C#4D#7C”. Karena panjang kode yang dihasilkan oleh RLE untuk setiap deret karakter minimal 3 byte, maka jumlah perulangan karakter harus lebih dari 3 (tiga) kali agar pengkodean bisa dilakukan. Satu hal yang perlu diperhatikan untuk penanda m adalah, sebaiknya yang dipilih adalah karakter yang jarang digunakan pada data (seperti tanda #, ^, |, atau ~). Namun, apabila penanda m terdapat pada data, cukup mengkodekannya sebanyak dua kali, sehingga apabila penanda tersebut muncul dua kali secara berturutturut saat decoding, maka penanda tersebut dianggap sebagai karakter asli.

Algoritma decoding pada RLE cukup sederhana yaitu mengembalikan karakter asli berdasarkan jumlah perulangan setiap karakter pada hasil kompresi. Misalnya, apabila

hasil

kompresi

adalah

“#5A#4CAA#5D”

maka

hasil

dekompresi

“AAAAACCCCAADDDDD”.

Pada umumnya algoritma RLE lebih efektif digunakan pada file-file grafis atau faxmail daripada file teks, karena pada umumnya karakter-karakter pada file teks bersifat heterogen dan sangat jarang memliki deretan karakter yang sama di atas 3 (tiga) kali. Namun, agar algoritma RLE efektif pada file teks, maka file tersebut perlu diubah kebentuk yang lebih compressable oleh RLE yaitu memiliki banyak karakter


23

yang sama secara berurutan, Jadi, untuk mengubah file teks tersebut digunakan algoritma Burrows Wheeler Transform (BWT).

2.6 Algoritma Burrows-Wheeler Transform (BWT)

Pada tahun 1994 David Wheeler dan Michael Burrows mengeluarkan makalah mereka yang berjudul “A Block-Sorting Lossless Data Compression Algorithm” yang menyajikan sebuah algoritma kompresi data berdasarkan suatu transformasi dimana transformasi ini sebelumnya telah ditemukan oleh David Wheeler pada tahun 1983 namun tidak dipublikasikan. Transformasi ini kemudian disebut sebagai BurrowsWheeler Transform (BWT) [11, 16].

Sebenarnya algoritma BWT bukan merupakan suatu algoritma kompresi yang berdiri sendiri seperti algoritma kompresi lainnya, melainkan suatu proses yang melakukan transformasi terhadap blok data teks menjadi suatu bentuk baru yang tetap mengandung karakter yang sama, hanya saja urutannya yang berbeda. Transformasi ini cenderung mengelompokan karakter secara berurut sehingga peluang untuk menemukan karakter yang sama secara berurutan akan meningkat sehingga akan lebih mudah dikompresi oleh algoritma kompresi seperti Run-Length Encoding, Move To Front, atau Huffman Coding. Karena algoritma BWT hanya melakuan perubahan urutan karakter dari data sebelumnya, maka algoritma ini bersifat reversible.

Proses encoding dari algoritma BWT adalah mentransformasikan sebuah string S yang memiliki sebanyak N karakter dengan cara melakukan rotasi (cyclic shift) atau permutasi sebanyak N-1 kali, sehingga terbentuk matriks M yang memiliki ordo NxN yang elemenya adalah karakter-karakter string S, sedangkan kolom dan barisnya adalah string hasil rotasi. Setelah proses rotasi selesai, maka baris matriks M diurutkan secara abjad (lexicographical). Salah satu dari baris matriks M adalah string asli S yang berada pada index I. Hasil encoding adalah string L yang dibentuk dari karakter terakhir dari setiap baris matriks M, dan index I [8]. Decoder pada BWT bisa


24

mengembalikan string asli S dengan hanya mengetahui pasangan L dan I tanpa membentuk kembali matriks M.

Sebagai contoh untuk melakukan transformasi pada string “BANANA” dapat dilihat pada langkah-langkah berikut:

1. Membentuk Matriks M yang berordo NxN Melakukan rotasi (cyclic shift) pada string “BANANA” sebanyak N-1 kali, sehingga diperoleh matrik M yang berordo NxN.

Gambar 2.2 Matriks M Dari String “BANANA” 2. Mengurutkan Hasil Rotasi Setelah matriks M terbentuk maka dilakukan pengurutan secara lexicographic pada baris-baris matriks.

0 1 2 3 4 5

0 A A A B N N

1 B N N A A A

2 A A A N B N

3 N B N A A A

4 A A A N N B

5 N N B A A A

I=3

L Gambar 2.3 Matriks M Dari String “BANANA” Setelah Diurutkan Secara Lexicographic


25

Pada gambar matriks 2.3 akan diperoleh string L yang dibentuk dari karakter terakhir setiap baris matriks M, dan index I yang menyatakan posisi string S asli, sehingga hasil encoding adalah (L, I) yang dalam hal ini adalah (NNBAAA, 3).

Proses decoding pada algoritma BWT sedikit berbeda dengan encoding. Jika pada encoding sebuah matriks M harus dibuat secara utuh, maka pada decoding, matriks yang dibuat hanya terdiri dari kolom pertama F dan kolom terakhir L. Dimana F diperoleh dengan cara mengurutkan L secara lexicographic. Hal ini berlaku karena kolom pertama matriks M pada saat encoding adalah terurut secara lexicographic dan setiap elemen L juga sama dengan elemen string S, hanya saja urutannya yang berbeda. Dengan kata lain, matriks yang dibentuk pada saat encoding dan decoding akan memiliki kolom pertama yang sama.

Untuk memperoleh string S berdasarkan L dan I, maka dibentuk suatu vektor transformasi T yang merupakan suatu array yang setiap elemennya menunjukkan korelasi atau pemetaan dari elemen F ke L. Hal ini diilustrasikan pada gambar 2.4 dengan F, T, dan L dari encoded string (NNBAAA, 3).

Gambar 2.4 Vektor Transformasi T Dari Encoded String (NNBAAA, 3)

Karena index I dari string S telah diketahui pada saat encoding (index yang diberi tanda asterik), maka akan diketahui pula karakter pertama dan terakhir dari string S pada F dan L, yaitu karakter “B” dan “A”. Sehingga dengan adanya informasi ini, maka string asli akan dapat diperoleh.


26

2.7 Optimasi Algoritma RLE dengan Algoritma BWT

Mengingat sifat algoritma BWT yang cenderung menghasilkan string yang memiliki banyak deretan karakter yang sama, maka akan sangat cocok bila dikompresi dengan algoritma RLE.

Sebagai

contoh,

apabila

string

“pelan-pelan_jalan_asalkan_selamat”

dikompresi dengan algoritma RLE tanpa terlebih dahulu ditransformasi dengan algoritma BWT, maka yang dihasilkan adalah string itu sendiri, karena tidak ada deretan karakter yang sama di atas 3 (tiga) kali. Namun, hasilnya akan berbeda bila string tersebut terlebih dahulu ditransformasi menggunakan algoritma BWT, sehingga hasil transformasinya akan seperti gambar 2.5 berikut:

nnnnjsllllk_mspp_leeaeaaaaaa-a_at 4n

4l

6a

Gambar 2.5 Contoh Hasil Transformasi Algoritma BWT

Apabila string pada gambar 10 dikompresi dengan algoritma RLE maka hasilnya adalah “*4njs*4lk_mspp_leeae*6a-a_at”. Sehingga terjadi pemampatan yaitu dari 33 byte menjadi 28 byte. Dari contoh ini terlihat bahwa algoritma RLE cukup efektif bila digabungkan dengan algoritma BWT. Untuk proses pengembalian ke string asli maka encoded string terlebih dahulu di-decoding dengan algoritma RLE kemudian algoritma BWT.

2.8 File Teks

File teks adalah file yang terdiri dari karakter-karakter terformat maupun tidak. Contoh terkernal adalah karakter ASCII (American Standard Code For Information Interchange). ASCII merupakan suatu standar pengkodean karakter pada mesin komputer, dimana setiap karakter direpresentasikan dengan 8 bit, sehingga jumlah


27

karakter ASCII yang dapat dibentuk adalah 28 = 256 karakter yang terdiri dari kombinasi 00000000 sampai 11111111, (dalam bentuk desimal 0 - 255).

Teks terformat (formatted style) adalah jenis teks yang sudah diberi style sehingga untuk merepresentasikan satu karakter saja membutuhkan space beberapa byte (1 byte = 8 bit). Contoh terkenal dari jenis file ini adalah format dokumen Microsoft Word (*.doc, *docx) dan Rich Text Format (*.rtf).

Teks tidak terformat (unformatted style) sering juga disebut teks sederhana (plain teks) merupakan jenis teks yang setiap karakternya berukuran 8 bit karena tidak ada fitur tambahan untuk memformat teks tersebut. Sehingga, plain text ukurannya lebih kecil dan lebih mudah diolah daripada teks yang terformat. Contoh perangkat lunak untuk pengolahan plain text adalah Notepad yang menghasilkan ekstensi (*.txt), dan beberapa perangkat lunak untuk pengetikan source code (kode program).

2.9 Kompleksitas Algoritma

Secara informal algoritma adalah suatu prosedur komputasi yang terdefenisi dengan baik yang mengambil beberapa nilai atau sekumpulan nilai sebagai input dan menghasilkan beberapa nilai atau sekumpulan nilai sebagai output. Dengan demikian algoritma adalah suatu urutan langkah-langkah komputasi yang mentransformasikan input menjadi output [9]. Secara singkat, algoritma merupakan langkah-langkah logis untuk pemecahan suatu masalah.

Dalam Ilmu Komputer suatu algoritma tidak hanya dilihat apakah algoritma tersebut benar atau dapat memecahkan masalah, tetapi juga harus efektif. Keefektifan suatu algoritma biasanya diukur dari seberapa besar jumlah waktu dan ruang (space) memori yang dibutuhkan untuk menjalankannya. Algoritma yang efesien adalah algoritma yang meminimumkan kebutuhan waktu dan ruang dimana semakin minim waktu dan ruang yang dibutuhkan, maka semakin efektif pula algoritma tersebut. Untuk menerangkan model abstrak pengukuran waktu dan ruang maka digunakan


28

suatu fungsi yang menjelaskan bagaimana ukuran masukan data (n) mempengaruhi perfomansi algoritma yang disebut sebagai kompleksitas algoritma Secara umum, kompleksitas algoritma terdiri dari dua macam yaitu kompleksitas waktu (time complexity) dan kompleksitas ruang (space complexity). Sehingga, dengan diketahuinya fungsi kompleksitas suatu algoritma, maka dapat ditentukan laju pertumbuhan waktu (ruang) yang diperlukan seiring dengan meningkatnya ukuran masukan (n) data. Dengan demikian, informasi pertumbungan fungsi kompleksitas (growth rates) dapat digunakan untuk membandingkan dua atau lebih algoritma dengan mengambil pangkat tertinggi (highest order) fungsi kompleksitas yang diekspresikan dengan notasi Big-O. Hal ini disebabkan karena nilai konstant pada fungsi kompleksitas tidak akan terlalu dominan bila dibandingkan dengan order tertinggi yang mungkin meledak untuk input yang semakin besar. Pada saat penentuan kompleksitas algoritma, ada beberapa istilah yang sering digunakan untuk menunjukkan kinerja suatu algoritma untuk ukuran input n, yaitu best-case,

average-case,

dan

worst-case

yang

masing-masing

menyatakan

kompleksitas keadaan terbaik, keadaan rata-rata, dan keadaan terburuk dari suatu algoritma. Namun, pada prakteknya penentuan nilai pasti untuk setiap case tersebut sulit dilakukan. Jadi, yang dilakukan hanyalah analisis asimtotik dari suatu algoritma, yaitu bagaimana pertumbuhan fungsi (growth of function) suatu algoritma dipengaruhi oleh input n yang semakin membesar menuju ke tak terhingga (infinity). Dalam analisis asimtotik, ada beberapa notasi yang sering digunakan untuk menunjukkan batas-batas fungsi asimtot, yaitu notasi Big-O, Big-Omega, dan BigTheta yang masing-masing menunjukkan batas atas (upper bound), batas bawah (lower bound), dan batas atas dan batas bawah (tight bound) dari fungsi asimtot.

2.10 Big-O Notasi Big-O adalah notasi matematika yang digunakan untuk menggambarkan suatu fungsi asimtotik. Notasi Big-O sering juga digunakan untuk menjelaskan seberapa besar ukuran dari suatu data mempengaruhi penggunaan sebuah algoritma dari sumber komputasi. Notasi ini pertama kali diperkenalkan pada tahun 1894 oleh Paul


29

Bachman, yaitu pada volume kedua dari bukunya Analytische Zahlentheorie (analisis teori bilangan) sehingga notasi Big-O biasa juga disebut sebagai notasi Landau (Landau notation), Bachman-Landau notation, atau notasi asimtotik (asymptotic notation).

Dalam bidang Matematika, notasi Big-O mendekripsikan sifat batasan (limiting behaviour) dari suatu fungsi ketika argument cenderung mengarah ke suatu nilai tertentu atau nilai tak hingga, biasanya berkaitan dengan fungsi yang lebih sederhana. Big-O mengkarakteristikkan fungsi-fungsi menurut pertumbuhan fungsi kompleksitasnya. Fungsi yang berbeda dengan pertumbungan fungsi kompleksitas yang sama bisa direpresentasikan dengan notasi Big-O yang sama. Sedangkan, dalam Ilmu Komputer notasi Big-O sangat berguna dalam analisis kompleksitas suatu algoritma.

Untuk menjelaskan konsep Big-O, diasumsikan terdapat dua fungsi f dan g, dengan kecepatan tingkat pertumbungan yang berbeda. Misalnya, f(n) = 100n2, dan g(n) = n4 [18].

Tabel 2.16 Perbandingan Pertumbuhan fungsi f dan g n

f(n)

g(n)

10

10.000

10.000

50

250.000

6.250.000

100

1.000.000

100.000.000

150

2.250.000

506.250.000

Gambar 2.6 Grafik Fungsi f dan g (Sumber: www.cs.odu.edu) Dari tabel 2.16 terlihat bahwa fungsi g(n) memiliki tingkat pertumbuhan yang lebih cepat dari pada f(n) saat n > 10, dan dapat dikatakan bahwa f(n) adalah Big-O dari g(n).


30

Defenisi (Big-O): Misalkan f(n) dan g(n) adalah dua fungsi asimtot nonnegatif. Dapat dikatakan bahwa f(n) = O(g(n)), jika dan hanya jika terdapat dua konstanta positif C dan n0 sehingga demikian f(n) ≤ C g(n) atau |f(n)| ≤ |C g(n)|, saat n ≥ n0 . Secara geometri f(n) = O(g(n)) dapat digambarkan sebagai berikut.

C g(n)

f(n)

n0

Gambar 2.7 Grafik Fungsi f(n) = O(g(n)) Contoh: diberikan fungsi f(n) = 3n 2 + 2n + 4. Maka dapat dikatakan bahwa f(n) = 3n2 + 2n + 4 = O(n2), karena: Untuk n ≥ 1 : 3n2 + 2n + 4 ≤ 3n2 + 2n2 + 4n2 3n2 + 2n + 4 ≤ 9n2 Karena itu, diperoleh C = 9, dan n0 = 1, sehingga memenuhi f(n) ≤ C g(n) saat n ≥ no dengan demikian f(n) = O(g(n)) = O(n2). Dengan cara yang sama, dapat juga dikatakan bahwa 5n + 10 adalah O(n2), karena: Untuk n ≥ 1 : 5n + 10 ≤ 5n2 + 10n2 5n + 10 ≤ 15n2 Karena itu, C = 15, dan n0 = 1, sehingga masih memenuhi f(n) ≤ C g(n) saat n ≥ n0.

2.11 Big-Ω

Big-Ω (Big Omega) merupakan kebalikan dari Big-O. Jika, Big-O menyatakan batas atas (upper bound) dari suatu fungsi asimtot, maka Big-Ω berarti menyatakan batas


31

bawah (lower bound) dari suatu fungsi asimtot. Dalam analisi algoritma, notasi ini sering digunakan untuk mendeskripsikan kompleksitas algoritma pada kasus terbaik (best-case), yang berarti algoritma tersebut tidak akan lebih baik dari fungsi kompleksitas yang dideskripsikan oleh notasi Big Omega tersebut.

Defenisi (Big-Ω): Misalkan f(n) dan g(n) adalah dua fungsi asimtot nonnegatif. Dapat dikatakan bahwa f(n) = Ω(g(n)), jika dan hanya jika terdapat dua konstanta positif C dan n0 sehingga demikian C g(n) ≤ f(n) atau |C g(n)| ≤ |f(n)|, saat n ≥ n0 . Secara geometri f(n) = Ω(g(n)) dapat digambarkan sebagai berikut.

f(n)

C g(n)

n0

Gambar 2.8 Grafik Fungsi f(n) = Ω(g(n))

Contoh: diberikan fungsi f(n) = 5n - 20. Maka dapat dikatakan bahwa f(n) = Ω(n), karena: Untuk n ≥ 1 : 5n – 20n ≤ 5n - 20 -15n ≤ 5n – 20 Karena f(n) dan g(n) merupakan fungsi asimtot non-negatif, maka dapat dituliskan: |-15n| ≤ |5n – 20| = 15n ≤ 5n – 20 Sehingga diperoleh C = 15, dan n0 = 1. Jadi, untuk setiap n ≥ no memenuhi C g(n) ≤ f(n) saat n ≥ no dengan demikian f(n) = 5n – 20 = Ω(n). Dengan cara yang sama, dapat juga dikatakan bahwa untuk fungsi f(n) = 3n2 + 10n + 6, memenuhi f(n) = Ω(n) atau f(n) = Ω(n2), namun f(n) ≠ Ω(n3).


32

2.12 Big-Θ

Ketika suatu algoritma memiliki fungsi kompleksitas lower bound yang sama dengan upper bound nya, misalnya algoritma Merge-Sort memiliki kompleksitas O(n log n) dan Ω(n log n) maka dapata dikatakan bahwa algoritma tersebut sebenarnya memiliki kompleksitas Θ(n log n), yang artinya best-case maupun worst-case running-time algoritma tersebut akan selalu berada pada n log n untuk input n tertentu.

Defenisi (Big-Θ): Misalkan f(n) dan g(n) adalah dua fungsi asimtot nonnegatif. Dapat dikatakan bahwa f(n) = Θ(g(n)), jika dan hanya jika terdapat konstanta positif C1, C2, dan n0 dimana f(n) = O(g(n)) dan f(n) = Ω(g(n)), sehingga memenuhi: C1 g(n) ≤ f(n) ≤ C2 g(n) Secara geometri f(n) = Θ(g(n)) dapat digambarkan sebagai berikut. C2 g(n)

f (n) C1 g(n)

n0

Gambar 2.9 Grafik Fungsi f(n) = Θ(g(n)) Contoh: diberikan fungsi f(n) = 3n2 + 10n + 6. Maka dapat dikatakan bahwa f(n) = Ω(n2). Berdasarkan defenisi Big-O dan Big-Ω maka dari fungsi f(n) dapat diperoleh: f(n) = O(n2)

f(n) = Ω(n2)

f(n) = O(n3)

f(n) = Ω(n)

f(n) ≠ O(n)

f(n) ≠ Ω(n3)

Karena menurut defenisi Big-Θ fungsi f(n) = O(g(n)) = Ω(g(n)), maka yang memenuhi adalah hanya pada saat f(n) = O(n2) dan f(n) = Ω(n2), sehingga dapat ditulis f(n) = Θ(n2).


33

2.13 Penentuan Big-O Algoritma

Dari ketiga notasi fungsi asimtot yang telah dibahas, sebenarnya masih adalagi notasinotasi yang berhubungan fungsi tersebut seperti Little-Oh, dan Littleh-Omega. Namun, dalam analisis algoritma, notasi Big-O yang paling sering digunakan karena notasi ini mendeskripsikan perfomansi kasus terburuk (worst-case) dari suatu algoritma. Sehingga, Big-O dapat menjamin bahwa suatu algoritma tidak akan lebih buruk dari worst-case. Oleh karena itu, Big-O dapat ditulis sebagai pangkat tertinggi (highest order) dari suatu fungsi polinomial dengan mengabaikan konstanta yang mungkin tidak akan terlalu berpengaruh untuk input (n) yang semakin membesar. Jadi, f(n) = 28n + 12 dapat ditulis dengan O(n), sedangkan untuk f(n) = 5n3 + 3n2 + 3 + 10 ditulis O(n3).

Tujuan penentuan kompleksitas suatu algoritma, sebenarnya bukanlah untuk mengetahui jumlah pasti operasi (langkah/intruksi) yang dikerjakan, melainkan bagaimana jumlah operasi dipengaruhi oleh berbagai ukuran masukan [10]. Kompleksitas algoritma dihitung berdasarkan jumlah langkah/instruksi yang dikerjakan. Penentuaan kompleksitas algoritma biasanya tergantung pada perintah (statement) yang digunakan. Berikut ketetapan waktu untuk beberapa statement.

1. Operasi pengugasan (assignment), operasi aritmatika, perbandingan, read, write, dan pengaksesan elemen array membutuhkan waktu konstant O(1).

Contoh: algoritma penukaran dua bilangan integer.

Tabel 2.17 Contoh Algoritma Penukaran Dua Bilangan Integer 1 2 3 4 5 6 7 8

Pseudo code procedure tukar(var integer x, y); var integer temp; begin temp ← x; x ← y; y ← temp; end; Total Waktu Eksekusi

Waktu Eksekusi

1 1 1 1+1+1=3


34

Pseudo code tabel 2.17 terdapat operasi penugasan (assignment) sebanyak tiga buah dan tiap operasi dilakukan satu kali. Maka kompleksitas algoritma tersebut adalah 1+1+1 = 3, atau Big-O = O(1).

2. If-then-else satatement adalah perintah yang memilih satu dari dua kondisi yang mungkin, karena prinsip Big-O menentukan worst-case dari suatu algoritma, maka waktu yang diambil dari pernyataan if-then-else adalah waktu terlambat (jumlah operasi terbanyak).

Contoh: algoritma pengecekan umur.

Tabel 2.18 Contoh Algoritma Pengecekan Umur 1 2 3 4 5 6 7

Pseudo code umur ← read(x); if umur < 17 then begin status ← “belum cukup umur!”; end else begin status ← “silahkan masuk!”; visitor ← visitor + 1; end; Total Waktu Eksekusi

Waktu Eksekusi 1 1 1 1 1+1=2 1+1+max(1,3)=5

Maka, kompleksitas algoritma pada tabel 2.18 adalah 1+1+max(1,3) = 5, maka Big-O adalah O(1).

3. Looping (for, while, repeat) adalah perintah untuk melakukan perulangan dengan panjang tertentu. Jadi, waktu untuk statement ini adalah banyaknya perulangan dikalikan dengan jumlah operasi di dalam perulangan tersebut.

Contoh: algoritma untuk penjumlahan sederetan angka. Tabel 2.19 Algoritma Untuk Penjumlahan Sederetan Angka 1 2 3 4 5

Pseudo code jumlah ← 0; for i ← 1 to n do begin jumlah ← jumlah + i; end; writeln(jumlah);

Waktu Eksekusi 1 (1+1)*n = 2n (1+1)*n = 2n

Total Waktu Eksekusi

1+2n+2n+1=2+4n

1


35

Maka, kompleksitas algoritma pada tabel 2.19 di atas adalah 4n+2 sehingga Big-O adalah O(n).

4. Perulangan bersarang (nested loop). Penghitungan waktu nested loop memiliki prinsip sama dengan looping biasa, hanya saja pada statement ini terdapat lagi statement perulangan, sehingga kasus ini sering memiliki kompleksitas O(n2) atau O(n3) tergantung jumlah statement perulangan di dalamnya.

Contoh: algoritma Bubble-Sort.

Tabel 2.20 Contoh Algoritma Bubble-Sort 1 2 3 4 5 6 7 8

Pseudo code for i ← 1 to n-1 do begin for j ← n downto i+1 do begin if A[j] < A[j-1] do begin temp ← A[j]; A[j] ← A[j-1]; A[j-1] ← temp; end; end; Total Waktu Eksekusi

Waktu Eksekusi (1+1+1)*n=3n (1+1+1)*n*n=3n2 (1+1+1+1)*n*n=4n2 (1+1)*n*n=2n2 (1+1+1+1)*n*n=4n2 (1+1+1)*n*n=3n2

16n2+3n

Maka, kompleksitas algoritma Bubble-Sort adalah 16n2+3n dengan notasi Big-O = O(n2).

Pada saat analisis algoritma, terdapat beberapa notasi Big-O yang sering diperoleh yaitu:

1. O(1) atau constant time Kompleksitas O(1) berarti waktu pelaksanaan algoritma adalah tetap, tidak bergantung pada ukuran masukan.

Contoh: Operasi penugasan (assignment),

operasi aritmatika, dan lain-lain. 2. O(2log n) atau logarithmic time Kompleksitas waktu O(log n) berarti laju pertumbuhan waktunya berjalan lebih lambat daripada pertumbuhan n. Algoritma yang termasuk kelompok ini adalah algoritma yang memecahkan persoalan besar dengan mentransformasikannya


36

menjadi beberapa persoalan yang lebih kecil yang berukuran sama. Contoh algoritma binary search, algoritma pengonversion bilangan integer ke biner.

3. O(n) atau linear time Algoritma dengan yang waktu pelaksanaannya linear umumnya terdapat pada kasus yang setiap elemen masukannya dikenai proses yang sama, misalnya algoritma sequential search. Bila n dijadikan dua kali semula, maka waktu pelaksanaan algoritma juga dua kali semula. 4. O(n 2log n) atau linearithmic time Waktu pelaksanaan O(n 2log n) terdapat pada algoritma yang memecahkan masalah menjadi beberapa masalah yang lebih kecil,

menyelesaikan setiap

masalah secara independen, dan menggabung solusi masing-masing masalah. Metode ini sering disebut dengan teknik devide and conquer. Contoh algoritma Merge Sort, dan Quick Sort. 5. O(n2) atau quadratic time Umumnya algoritma yang termasuk kelompok ini memproses setiap masukan dalam dua buah kalang bersarang, misalnya pada algoritma Bubble Sort. Bila n = 1000, maka waktu pelaksanaan algoritma adalah 1.000.000. Bila n dinaikkan menjadi dua kali semula, maka waktu pelaksanaan algoritma meningkat menjadi empat kali semula. 6. O(n3) atau cubic time Seperti halnya algoritma kuadratik, algoritma kubik memproses setiap masukan dalam tiga buah kalang bersarang, misalnya algoritma perkalian matriks. Bila n = 100, maka waktu pelaksanaan algoritma adalah 1.000.000. Bila n dinaikkan menjadi dua kali semula, waktu pelaksanan algoritma meningkat menjadi delapan kali semula.


37

7. O(2n) atau exponential time Algoritma yang tergolong kelompok ini mencari solusi persoalan secara "brute force", Bila n = 20, waktu pelaksanaan algoritma adalah 1.000.000. Bila n dijadikan dua kali semula, waktu pelaksanaan menjadi kuadrat kali semula.

8. O(n!) atau factorial time Seperti halnya pada algoritma eksponensial, algoritma jenis ini memproses setiap masukan dan menghubungkannya dengan n - 1 masukan lainnya, misalnya pada kasus TSP (Travelling Salesman Problem). Bila n = 5, maka waktu pelaksanaan algoritma adalah 120. Bila n dijadikan dua kali semula, maka waktu pelaksanaan algoritma menjadi faktorial dari 2n. Berikut table perbandingan kompleksitas yang menunjukkan seberapa banyak jumlah operasi yang akan dikerjakan untuk berbagai ukuran masukan n [17].

Tabel 2.21 Perbandingan Pertumbuhan Kompleksitas (Sumber: www.fredswartz.com) n

O(1) 1 1 2 1 4 1 8 1 16 1 1.024 1 1.048.576 1

O(log n) 1 1 2 3 4 10 20

O(n) 1 2 4 8 16 1.024 106

O(n log n) 1 2 8 24 64 10.240 2 x 107

O(n2) 1 4 16 64 256 106 1012

O(n3) 1 8 64 512 4.096 108 1016

2n 2 4 16 256 65536 10307 too big

n! 1 2 24 40320 1014 5 x 1026385 too big

Pertumbuhan kompleksitas dari masing-masing Big-O pada tabel 2.21 menunjukkan bahwa untuk input n yang semakin besar, waktu O(1) sama sekali tidak terpengaruh, sedangkan laju pertumbuhan waktu O(log n), O(n), O(n log n) tidak terlalu cepat. Sementara waktu O(n2), O(n3), O(2n), dan O(n!) pengingkatan waktunya sangat cepat sehingga algoritma yang memiliki jenis kompleksitas ini dapat dipastikan waktu eksekusinya sangat lama. Jadi, urutan kompleksitas algoritma dapat ditulis menjadi O(1) < O(log n) < O(n) < O(n log n ) < O(n2) < O(n3) < O(2n) < O(n!) [18].


38

Gambar 2.10 Grafik Perbandingan Pertumbuhan Kompleksitas (Sumber: www.cs.odu.edu)

2.14 Teorema Master (Master Theorem)

Dalam Ilmu Komputer ada berbagai cara untuk melakukan design algoritma, salah satunya adalah dengan teknik divide and conquer. Algoritma yang berdasarkan teknik ini bekerja secara rekursif untuk membagi permasalahan menjadi beberapa sub permasalahan yang sama dengan masalah awal, hanya saja ukurannya yang berbeda. Sub permasalahan ini kemudian diselesaikan secara rekursif kemudian mengkombinasikan solusi-solusi dari sub permasalahan tersebut untuk mendapatkan solusi dari permasalahan awal [9]. Teknik ini telah menjadi basis dari banyak algoritma efisien untuk berbagai permasalahan, seperti pada algoritma pengurutan.

Ketika suatu algoritma menggunakan teknik divide and conquer secara rekursif, running-time nya dapat dideskripsikan sebagai suatu recurrence yang berdasarkan tiga dasar paradigma yaitu: divide, conquer, dan combine yang masingmasing berarti membagai masalah n menjadi 2 buah sub masalah a secara rekursif dengan waktu T(n/b), ketika ukuran sub masalah tidak dapat dibagi lagi, maka


39

dilakukan merging dengan biaya (cost) f(n). Algoritma semacam ini, dapat direpresentasikan sebagai fungsi recurrence yaitu:

T(n) = aT(n/b) + f(n)

Dimana a ≥ 1 dan b > 1 adalah konstanta positif dan f(n) adalah fungsi asimtot positif. Running-time dari algoritma rekursif dengan recurrence di atas dapat diselesaikan dengan menggunakan master theorem berdasarkan 3 kasus (case) yaitu: log a – ε ) untuk ε > 0, maka T(n) = Θ(nlogb a). 1. Jika f(n) = O(n b

2. Jika f(n) = Θ(nlogb a logk n) untuk k ≥ 0, maka T(n) = Θ(nlogb a logk + 1 n). 3. Jika f(n) = Ω(nlogb a + ε) untuk ε > 0 dan a f(n/b) ≤ cf(n) untuk c < 1 dan n cukup besar, maka T(n) = Θ( f(n) ).

Contoh, untuk recurrence berikut dapat ditentukan running-time nya dengan menggunakan master theorem. a. T(n) = 8T(n/2) + 1000n2 b. T(n) = 2T(n/2) + 10n c. T(n) = 2T(n/2) + n2

Solusi: a. Dari T(n) = 8T(n/2) + 1000n2, diperoleh a = 8, b = 2, dan f(n) = 1000n2, sehingga logba = log28 = 3.

Kemudian dilakukan pengecekan pada case keberapa f(n) berada.

f(n) = O(nlogb a – ε) → 1000n2 = O(n3 - ε) Dengan memilih ε = 1 maka diperoleh:

1000n2 = O(n3 - 1) = O(n2) Karena bentuk f(n) di atas memenuhi case 1 pada master theorem, maka:

T(n) = Θ(nlogb a) → T(n) = Θ(n3)


40

b. Dari T(n) = 2T(n/2) + 10n, diperoleh a = 2, b = 2, dan f(n) = 10n, sehingga logba = log22 = 1.

Kemudian dilakukan pengecekan pada case keberapa f(n) berada dengan mengasumsikan k = 0, sehingga diperoleh: f(n) = Θ(nlogb a) → 10n = Θ(n1) = Θ(n)

Karena bentuk f(n) di atas memenuhi case 2 pada master theorem, maka:

T(n) = Θ(nlogb a logk + 1 n) → T(n) = Θ(n log n) c. Dari T(n) = 2T(n/2) + n2, diperoleh a = 2, b = 2, dan f(n) = n2, sehingga logba

= log22 = 1. Kemudian dilakukan pengecekan pada case keberapa f(n) berada.

f(n) = Ω(nlogb a + ε) → n2 = Ω(n1 + ε) Dengan memilih ε = 1 dan c = ½ maka diperoleh:

n2 = O(n1 + 1) = Ω(n2), dan a f(n/b) ≤ c f(n) = 2(n/2)2 ≤ cn2 = 1/2n2 ≤ cn2 = 1/2n2 ≤ 1/2n2, untuk n ≥ 1

Karena bentuk f(n) di atas memenuhi case 3 pada master theorem, maka:

T(n) = Θ(f(n)) → T(n) = Θ(n2)

2.15 Parameter Analisis Perbandingan Algoritma

Agar perbandingan masing-masing algoritma dapat diperoleh seperti yang telah dipaparkan pada rumusan masalah (no 2 dan 3) pada bab 1, maka akan dijelaskan parameter-parameter yang akan digunakan, yang meliputi kompleksitas algoritma, waktu proses kompresi dan dekompresi, dan rasio kompresi.


41

1. Kompleksitas Algoritma Dasar teori dan cara pengukuran kompleksitas algoritma telah dijelaskan sebelumnya. Jadi, kompleksitas algoritma yang akan dibandingkan disini adalah kompleksitas masing-masing algoritma untuk proses encoding maupun decoding yang akan diperoleh pada saat perancangan, dimana algoritma yang memiliki kompleksitas yang tinggi berarti memiliki waktu eksekusi yang lama, dan sebaliknya.

2. Waktu Proses Kompresi dan Proses Dekompresi Waktu yang dimaksudkan di sini adalah waktu yang dibutuhkan suatu algoritma untuk melakukan proses kompresi maupun dekompresi terhadap suatu file pada saat pengimplementasian, dimana semakin cepat suatu algoritma melakukan proses kompresi atau dekompresi, maka ada kemungkinan algoritma tersebut baik (efisien), dan sebaliknya.

3. Rasio Kompresi Rasio kompresi adalah perbandingan file hasil kompresi dengan file aslinya, dimana semakin kecil rasio kompresi maka semakin baik algoritma yang digunakan, dan sebaliknya. Penghitungan rasio kompresi dirumuskan pada tabel 2.22 berikut.

100%

Tabel 2.22 Rumus Pengukuran Rasio Kompresi

Contoh: jika suatu file memiliki ukuran asli 150.000 byte, dan setelah dikompresi menjadi 35.000 byte, berarti rasio kompresinya adalah (35.000/150.000) x 100% = 23,33%, yang berarti telah terjadi pengurangan file sebesar 100% - 23,33% = 76.67% dari ukuran semula.

Jadi, ketiga parameter di atas akan dipertimbangkan untuk berbagai ukuran file, sehingga dapat disimpulkan keefektifan dan perbandingan setiap algoritma.


BAB III : PERANCANGAN DAN IMPLEMENTASI SISTEM

Recommend Documents