BAB 2 TINJAUAN PUSTAKA

BAB 2 TINJAUAN PUSTAKA

2.1. Algoritma String Matching

Algoritma string matching merupakan komponen dasar dalam pengimplementasian berbagai perangkat lunak praktis yang sudah ada. String matching digunakan untuk menemukan satu atau lebih string yang disebut dengan pattern (string yang akan dicocokkan ke dalam text) dalam string yang disebut dengan text (string yang diinput) (Charras & Lecroq 2004). Pengertian string menurut Dictionary of Algorithms and Data Structures, National Institute of Standards and Technology (NIST) adalah susunan dari karakter-karakter (angka, alfabet atau karakter yang lain) dan biasanya direpresentasikan sebagai struktur data array. String dapat berupa kata, frase, atau kalimat. Pencocokan string merupakan bagian penting dari sebuah proses pencarian string (string searching) dalam sebuah dokumen. Hasil dari pencarian sebuah string dalam dokumen tergantung dari teknik atau cara pencocokan string yang digunakan. Pencocokan string (string matching) menurut Dictionary of Algorithms and Data Structures, National Institute of Standards and Technology

(NIST), diartikan sebagai sebuah permasalahan untuk menemukan pola

susunan karakter string di dalam string lain atau bagian dari isi teks (Munir & Syahroni 2005). Setiap algoritma string matching memiliki kelebihan serta kekurangan dalam melakukan pencarian sebuah pattern (Thatoo, et al. 2006).

Universitas Sumatera Utara

7

2.2. Algoritma Reverse Colussi Algoritma merupakan urutan langkah-langkah untuk menyelesaikan masalah yang disusun secara sistematis. Algoritma Reverse Colussi merupakan satu dari sekian banyak algoritma string matching atau sering disebut pencocokan string. Algoritma Reverse Colussi merupakan perbaikan dari algoritma Boyer – Moore dan idenya berasal dari Colussi. Proses pencocokan tiap-tiap karakter pada algoritma Reverse Collusi menggunakan sepasang karakter yang telah didefinisikan pada tabel rcBc dan rcGs. Algoritma Reverse Colussi mempunyai posisi ke dalam dua kategori yakni special position dan non-special position. Dimana special position akan diproses terlebih dahulu. Algoritma Reverse Colussi terdiri dari dua fase, yaitu fase pemrosesan awal dan fase pencarian. Pada fase pemrosesan awal dilakukan pencarian sepasang karakter, special position, dan

non-special position untuk menentukan pergeseran pattern. Pada fase

pencarian, dilakukan operasi pencocokan pattern terhadap teks. Reverse Colussi mempunyai 2 tabel untuk menentukan dan menemukan dalam pencocokan string, yakni tabel rcBc, dan rcGs (Admizan, 2014). Perbandingan dilakukan dalam urutan tertentu yang diberikan oleh fase pemrosesan awal .Waktu dari algoritma Reverse Colussi pada fase preprocessing adalah O(m2) dan fase pencarian adalah O(n) (Hussain, et al. 2013). Proses inti pencarian Algoritma Reverse Colussi yaitu dilakukan dengan teknik random dimana teknik ini memungkinankan pengecekan karakter selalu dari ujung kanan karakter dan pengecekan selanjutnya ditentukan oleh nilai tabel

h

yang sudah

didefinisikan (Charras & Lecroq 2004). Langkah pertama yang dilakukan adalah tahapan preprocessing yaitu meciptakan dua buah tabel shif / pergesaran rcBc (Reverse Colussi Bad Character) & rcGs (Reverse Colussi Good Suffixes). Kedua tabel ini diciptakan merujuk kepada pattern yang akan dicari oleh karena itu jika pattern berubah maka tabel juga akan berubah. Hasil preprocessing untuk pattern TAMAT dari teks TATOMATAMATANGGA terlihat pada tabel 2.4 dan 2.10


8

2.2.1. Fase Pemrosesan Awal Fase ini bertujuan untuk menetukan special positition dan juga non-special position menggunakan tabel rcGs (Reverse Colussi Get suffix), pencarian sepasang karakter menggunakan tabel rcBc (Reverse Colussi Bad character). Untuk melakukan pencarian sepasang karakter , langkah yang harus dilakukan pertama kali adalah membuat tabel loccated. 2.2.1.1. Tabel loccated Tabel ini berfungsi untuk melakukan perwakilan karakter dari setiap pattern yang dimasukkan , setelah itu karakter yang di dapat akan menjadikan karakter tersebut ke dalam tabel rcBc. Syarat menentukan tabel loccated adalah sebagai berikut : 1. Mengambil perwakilan karakter dari pattern , dan dimulai dari kiri tabel. 2. Nilai awal dari tiap-tiap karakter adalah (-1) , sebelum angka tersebut digantikan oleh index, index dimulai dari 0. 3. Menentukan tabel loccated dimulai dari panjang pattern (m) dikurangi 1

Tabel 2.1 Nilai loccated indeks

0

1

2

3

4

char

A

M

T

*

pattern

T

A

M

A

T

locc

3

2

0

-1

2.2.1.2. Tabel rcBc Dalam membuat tabel rcBc, tabel ini berfungsi untuk menampung pencarian sepasang karakter, dengan syarat : 1. Karakter (present matched charcter) yang digunakan adalah perwakilan dari pattern yang sudah didapat dari tabel loccated 2. Panjang dari pergeseran (length of previous shifts) adalah panjang dari pattern .


9

3. Bila ditemukan sepasang karakter , ambil jumlah sisa karakter dari pattern tersebut untuk mengisi nilai . 4. Dimulai dari m-1( 5-1), berarti dimulai dari karakter ke 4 Tabel 2.2 Pencarian nilai rcBc (1) Pattern : TAMAT Panjang : 5 A A

A

M

5 A

A

3 A

T

3 A

*

1 A

1

Pattern : TAMAT Panjang : 5 M A M A T *

M

2 M

5 M

2 M

2 M

2


10

Tabel 2.3 Pencarian nilai rcBc (2) Pattern : TAMAT Panjang : 5 T A

T

4

M

T

4

A

T

4

T

T

4

*

T

4

Pattern : TAMAT Panjang : 5 * A

*

5

M

*

5

A

*

5

T

*

5

*

*

5

Ketika proses pencarian sepasang karakter selesai , langkah selanjutnya adalah melakukan pengisian dari nilai tabel diatas ke dalam tabel rcBc. Tabel 2.4 Nilai tabel rcBc Length

1

2

3

4

5

5 2 4 5

3 5 4 5

3 2 4 5

1 2 4 5

2 2 4 5

Character

A M T *


11

Setelah tabel rcBc terbentuk proses selanjutnya adalah membuat tabel rcGs. Sebelum tabel rcGs terbentuk ada beberapa tabel yang harus dibuat, yakni tabel link, hmin , kmin, rmin, dan terakhir adalah rcGs beserta tabel h, dimana tabel h berfungsi untuk menentukan atau melakukan pengecekan karakter pertama kali yang harus di cek pada saat fase pencocokan pattern (Haryadi, 2011).

2.2.1.3. Tabel link Untuk mengisi tabel link ada bebrapa point yang harus diperhatikan adalah sebagai berikut: 1. 2. 3. 4.

link dari 0 adalah (-1) Bila belum pernah jumpa ,nilai link diberi nilai (-1) link(n) adalah loccated dari nilai terakhir . located awal proses dimulai dari 0

Tabel 2.5 Pencarian nilai tabel link Pattern : TAMAT Panjang : 5 Ada 4 pasangan yaitu[ [TA] [AM] [MA] [AT] ] T 0

A 1

M 2

A 3

T 4

Link [A] = -1 TA

Locc [T] = 0 Link [M] = -1

AM

Locc [A] = 1 Link [A] = 1

MA

Locc [M] = 2 Link [T] = 0

AT

i p (i) link (i)

Locc [A] = 3

0 T -1

1 A -1

2 M -1

3 A 1

4 T 0

5


12

2.2.1.4. Tabel hmin Tabel hmin berfungsi untuk menampung atau menyimpan jumlah pergeseran untuk setiap special position, berikut persyaratannya : 1. Nilai indeks 0 adalah 0 2. Proses ini bertujuan mencari karakter yang tidak sama , lalu nilai diambil dari indek karakter tersebut. 3. Apabila karakter yang dicari selalu sama atau tidak dapat maka nilai akan diberikan dari panjang pattern, yakni 4. Tabel 2.6 Pencarian nilai tabel hmin Pattern : TAMAT Panjang : 5 Mencari karakter yang sama

T

A

M

A

T

0

1

2

3

4

1 2 Indek/ posisi

3 4 5 4

I p (i) hmin (i)

0 T 0

1 A 4

4

2 M 4

4

4

3

3 A 4

4 T 3

5

4


13

2.2.1.5 . Tabel kmin Fungsi dari tabel kmin untuk membantu mengambil nilai dari rmin nanti , dimana syarat dari tabel ini adalah : 1. Proses dari kanan ke kiri , dan isi semua nilai dengan nilai 0, 2. Panjang pattern (m) = 5 , k (kmin) , 5 1, 3. kmin[hmin[k]] = k , 4. Ambil kmin dari terakhir kali dieksekusi. Tabel 2.7 Pencarian nilai tabel kmin Pattern : TAMAT Panjang : 5 Mencari nilai kmin

K=5

kmin[hmin[k]] = k kmin[hmin[5]] = 5 kmin [4] = 5 K=4 kmin[hmin[k]] = k kmin[hmin[4]] = 4 kmin [3] = 4 K=3 kmin[hmin[k]] = k kmin[hmin[3]] = 3 kmin [4] = 3 K=2 kmin[hmin[k]] = k kmin[hmin[2]] = 2 kmin [4] = 2 K=1 kmin[hmin[k]] = k kmin[hmin[1]] = 1 kmin [4] = 1 Proses : kmin [4] = 1 | kmin [3] = 4


14

2.2.1.6 . Tabel rmin Tabel rmin berfungsi untuk menampung nilai pergeseran dari non-special position, dimana proses ini dilakukan dari kiri ke kanan dengan syarat : 1. i = m-1 , i >=0 2. hmin [i +1] == i r=i+1 rmin [i] = r Tabel 2.8 Pencarian nilai tabel rmin Pattern : TAMAT Panjang : 5 Mencari nilai rmin Jadi langkah awal dimulai dari i(indeks) m-1 = 5-1=4 ; m=4 0 i= 4 (hmin [i +1] == i) r=i+1 hmin [4+1] == 4 r=5 hmin [5] == 4 isi rmin dengan nilai r rmin [4] = 5 i= 3 (hmin [i +1] == i) r=i+1 hmin [3+1] == 3 r=4 hmin [4] == 3 isi rmin dengan nilai r rmin [3] = 4 i= 2 hmin [i +1] == i hmin [2+1] == 2 hmin [3] == 2 rmin [2] = 4 i= 1 hmin [i +1] == i hmin [1+1] == 1 hmin [2] == 1 rmin [1] = 4 i= 0 hmin [i +1] == i hmin [0+1] == 1 hmin [1] == 0 rmin [0] = 4 indeks p (i) rmin (i)

0 T 4

1 A 4

2 M 4

3 A 4

4 T 5

5

0


15

2.2.1.7 Tabel rcGs dan h Tabel rcGs ini berfungsi untuk menampung nilai pergeseran atupun pencocokan karakter. Nilai rcGs didapat bersamaan dengan nilai h, tabel h bertujuan untuk melakukan pengecekan Special karakter yang harus pertama kali dicek pada saat melakukan pencocokan string (Haryadi, 2011). Berikut persyaratan komputasi dari tabel rcGs dan h. Tabel 2.9 Pencarian nilai tabel rcGs dan h Komputasi untuk mengambil nilai tabel rcGs (Charras & Lecroq 2004) i=1 for (k = 1 , k <= m , ++k) if (hmin[k] != m-1 && kmin[hmin[k]] == k ) { h[i] = hmin [k] rcGs [i++] = k } i = m-1 for ( j= m-2 , j>= 0, --j) if (kmin[j] == 0 ) { h [i] = j rcGs [i--] = rmin[j] } rcGs[m] = rmin [0] } Proses K=1

Dimulai dari indeks =1 K=1 5 hmin [k] != m-1 hmin [1] != 4 4 != 4 FALSE , lanjut ke langkah selanjutnya

K=2

hmin [k] != m-1 hmin [2] != 4 4 != 4 FALSE , lanjut ke langkah selanjutnya

K=3

hmin [k] != m-1 hmin [3] != 4 4 != 4 FALSE , lanjut ke langkah selanjutnya

K=4

hmin [k] != m-1 hmin [4] != 4 3 != 4

Ubah nilai h[i] h[i] = hmin [k] h[1]= hmin [4] h[1] = 3 // nilai h1 sudah terisi


16

K=5

Proses J=3

Kmin [hmin[k]]== k rcGs[i++] =k Kmin[3]==4 rcGs [1] = 4 // nilai rcGs 1 sudah 4 == 4 terisi True , masuk ke langkah pemberian i = i +1= 2 nilai rcgs dan h hmin [k] != m-1 hmin [5] != 4 4 != 4 Kmin [hmin[k]]== k Kmin[4]==5 1 == 5 False,Lanjut ke kondisi selanjutnya Lanjut ke kondisi selanjutnya i =m-1 i = 4 m =5 j== m-2 --j = 3 0 Kmin [j]==0 Kmin[3] == 0 4 == 0 False, lanjut kelangkah selanjutnya

J=2

Kmin [j]==0 Kmin[2] == 0 0 == 0 True, lanjut kelangkah selanjutnya

J=1


J=0


rcGs

h[i] = j h[4] = 2 // nilai h dari 4 adalah 2 rcGs = [i--] rcGs[4] = rmin [j] rcGs[4] = rmin [2] rcGs[4] = 4 // nilai rcGs 4 adalah 4 h[i] = j h[3] = 1 // nilai h dari 3 adalah 1 rcGs = [i--] rcGs[3] = rmin [j] rcGs[3] = rmin [1] rcGs[3] = 4 // nilai rcGs 3 adalah 4 h[i] = j h[2] = 0 // nilai h dari 2 adalah 0 rcGs = [i--] rcGs[2] = rmin [j] rcGs[2] = rmin [0] rcGs[2] = 4 // nilai rcGs 2 adalah 4

rcGs (m) = rmin [0] rcGs 5= 4 Notes: Warna hijau berfungsi sebagai mark hasil dari nilai tabel rcGs dan h


17

Setelah proses fase pemrosesan awal selesai maka didapat tabel rcGs beserta tabel h seperti tabel 2.8 berikut : Tabel 2.10 Tabel rcGs i p(i) link(i) hmin(i) kmin(i) rmin(i) rcGs(i) h(i)

0 T -1 0 0 4 0

1 A -1 4 0 4 4 3

2 M -1 4 0 4 4 0

3 A 1 4 4 4 4 1

4 T 0 3 1 5 4 2

5

4 0 0 4

2.2.2 Fase pencocokan pattern Setelah tabel rcBc dan rcGs selesai terbentuk , pencocokan pattern dilakukan berdasarkan nilai dari kedua tabel tersebut. Pada algoritma Reverse Colussi , perbandingan karakter dilakukan dengan menggunakan urutan tertentu yang didapat dari tabel h. Untuk menentukan pengecekan pada lompatan pada saat melakukan pencocokan string membutuhkan tabel h, gambaran pengecekan karakter dapat dilihat pada gambar 2.2 berikut.

Gambar 2.1 Pengecekan karakter


18

Persyaratan dalam menentukan pencocokan pattern ada 2 metode ,yakni: 1. Jika belum pernah menjumpai karakter yang sama maka gunakan nilai dari tabel rcBc . 2. Jika sudah pernah menjumpai karakter yang sama,minimal 1 karakter metode eksekusi maka gunakan nilai dari tabel rcGs.

Karena pada pertama kali tidak cocok maka digunakan tabel rcBc Shift by 2 (rcBc [M][s], s = 5), and chages s = 2

Gambar 2.2 Percobaan pencocokan karakter (1)

Shift by 4 rcGs[3], and chages = 4 Gambar 2.3 Percobaan pencocokan karakter (2)


19

Shift by 4 rcGs[5], and chages 4 Gambar 2.4 Percobaan pencocokan karakter (3)

Shift by 4, (rcBc [G[s]], s=4), and chages s=4 Gambar 2.5 Percobaan pencocokan karakter (4) Karena pergeseran selanjutnya adalah 4 dan teks yang akan dieksekusi hanya tersisa 1, maka pencarian selesai. Dari hasil diatas untuk melakukan pencocokan pattern TAMAT pada

teks TATOMATAMATAANGGA memerlukan percobaan sebanyak 4 kali

dengan jumlah perbandingan komparasi sebanyak 11.


20

2.3 Penelitian yang Relevan Berikut beberapa penelitian yang relevan dengan penelitian ini: 1.

Rizki Primandar Admizan (2014) dalam skripsi yang berjudul Perbandingan Algoritma Reverse Colussi dengan Algoritma Karp-Rabin Dalam Mencari Dan Mencocokkan String Pada Word Game . Dengan melakukan perbandingan performansi dari algoritma Reverse Colussi dan algoritma Karp-Rabin maka akan dapat diketahui cara kerja dan performansi dalam kecepatan dan ketepatan dari kedua algoritma tersebut. Agar selanjutnya algoritma yang lebih bagus dapat digunakan pada perangkat lunak pencocokan kata.

2.

Didik Haryadi (2011) dalam penelitian yang berjudul Pencocokan String dengan Algoritma Reverse Colussi . Penelitian ini untuk mengetahui kompleksitas algoritma yang menjadi perbaikan dari Reverse Colussi yaitu Booyer Moore dan

Colussi

dimana hasil dari penelitian ini adalah Algoritma Reverse Colussi menghasilkan jumlah perbandingan karakter lebih sedikit dibanding dengan Booyer Moore.


BAB 2 TINJAUAN PUSTAKA

Recommend Documents