BAB 2 LANDASAN TEORI

BAB 2 LANDASAN TEORI

2.1. Pengertian Aplikasi Berbasis Web Aplikasi merupakan program yang berisikan perintah-perintah untuk melakukan pengolahan data. Secara umum, aplikasi adalah suatu proses dari cara manual yang ditransformasikan ke dalam komputer dengan membuat sebuah sistem atau program agar data dapat diolah dan berdaya guna secara optimal. Aplikasi berbasis web adalah aplikasi yang dijalankan melalui browser. Aplikasi ini pertama kali dibangun hanya dengan menggunakan bahasa yang disebut dengan HTML (HyperText Markup Language) dan protokol yang digunakan dinamakan HTTP (HyperText Transfer Protocol). Konsep yang mendasari aplikasi berbasis web sebenarnya sederhana, apalagi jika menggunakan konsep web dinamis, maka dimungkinkan untuk dibentuk aplikasi berbasis web yang berinteraksi langsung dengan basis data (database). Adapun kelebihan aplikasi berbasis web dibandingkan dengan aplikasi berbasis desktop atau android adalah pengguna bebas menggunakannya dimana saja dan kapan saja, asalkan tersedia jaringan internet sehingga aplikasi dapat digunakan dari berbagai perangkat, seperti personal computer, smartphone, dan tablet. Pengguna juga tidak perlu melakukan instalasi aplikasi terlebih dahulu seperti yang harus dilakukan pertama kali ketika ingin menjalankan aplikasi berbasis desktop atau android, namun, pengguna dapat langsung menggunakan aplikasi berbasis web ini sesaat setelah aplikasi tersebut dibuka.

2.2. Pengertian Kamus Kamus adalah buku yang memuat kata dan ungkapan, disusun menurut abjad berikut keterangan tentang makna dan terjemahannya. Di dalamnya, sering ditemukan istilah qqn dan qqch yang mengacu kepada seseorang dan sesuatu (Hendry, et al. 2012).

Universitas Sumatera Utara

2.3. Pengertian Pencocokan String (String Matching) Konsep pencocokan string atau string matching dapat diartikan sebagai sebuah cara untuk mencari string yang sama di dalam satu kumpulan teks atau basis data (database). Konsep pencocokan string ini mirip dengan fungsi Find dalam aplikasi pengolah kata atau fungsi Query di dalam basis data (Dewanto, 2007). Secara garis besar, konsep pencocokan string dapat dibedakan menjadi dua konsep besar, antara lain (Syaroni & Munir 2005): 1. Exact string matching, yaitu pencocokan string secara benar dengan susunan karakter dalam string yang dicocokkan memiliki jumlah dan urutan karakter dalam string yang sama. Jadi, jika string yang akan dicari memiliki panjang pola karakter sebanyak 6 karakter, maka kata yang keluar sebagai hasil dari pencocokan tersebut adalah sebanyak 6 karakter. 2. Inexact string matching atau Fuzzy string matching, yaitu pencocokan string secara samar, maksudnya adalah pencocokan string dimana string yang dicocokkan memiliki kemiripan, dimana keduanya memiliki susunan karakter yang berbeda, baik dari segi jumlah karakter atau urutan, namun memiliki kemiripan dari segi tekstual/penulisan (approximate string matching) atau kemiripan ucapan (phonetic string matching). Berdasarkan bentuk kemiripannya, inexact string matching juga dapat dibedakan menjadi dua, yaitu: a. Approximate

string

matching

merupakan

pencocokan

string

berdasarkan kemiripan dari segi penulisan yang meliputi jumlah dan susunan karakter di dalam dokumen. b. Phonetic string matching merupakan pencocokan string berdasarkan kemiripan dari segi pengucapan, meskipun terdapat perbedaan penulisan kedua string tersebut jika dibandingkan. Kedua konsep pencocokan string, baik exact string matching atau inexact string matching sama-sama memiliki manfaat. Jika pengguna ingin mencari string di dalam dokumen yang sama persis dengan string masukan, maka gunakanlah exact string matching. Namun, jika pengguna ingin pencarian string yang mendekati dengan string masukan atau terjadi kesalahan penulisan string masukan maupun dokumen objek pencarian, maka gunakanlah inexact string matching (Syaroni & Munir 2005).


2.4. Pengertian Algoritma Kata “algoritma” diturunkan dari nama belakang seorang tokoh matematikawan Persia bernama Muhammad ibn Musa Al-Khuwarizmi. Secara umum, algoritma merupakan metode umum yang digunakan untuk menyelesaikan kasus-kasus tertentu (Ananda, et al. 2009). Secara spesifik, algoritma adalah sekumpulan prosedur komputasi yang terdefinisi dengan baik dan memiliki beberapa nilai atau himpunan nilai sebagai nilai masukan dan menghasilkan nilai atau himpunan nilai sebagai nilai keluaran. Sebuah algoritma pada dasarnya adalah urutan langkah-langkah komputasi yang mengubah nilai input menjadi nilai output (Cormen, et al. 2001). 2.4.1. Algoritma pencocokan string (string matching) Algoritma pencocokan string adalah sebuah proses pencarian tempat dari satu atau beberapa string yang ditemukan dalam sebuah kumpulan string atau teks. Jalan paling sederhana adalah dengan cara membaca karakter satu persatu dan melakukan perhitungan kesalahan posisi yang ada dari string yang dicari (Dewanto, 2007).

2.4.1.1. Algoritma Quick Search Algoritma Quick Search diperkenalkan oleh Daniel Sunday, yang merupakan algoritma penyederhanaan dari algoritma Boyer-Moore tanpa peraturan good suffix dalam pencarian string (Lin, et al. 2014). Algoritma ini terdiri dari dua fase, yaitu fase preprocessing dan fase pencarian, dimana fase preprocessing akan dikerjakan terlebih dahulu. Algoritma ini menggunakan bad-character shift dan mengerjakan pencarian string dari kiri ke kanan selama proses pencocokan string berlangsung (Naser, 2010). Berikut akan dijelaskan cara kerja algoritma Quick Search mulai dari fase preprocessing sampai fase pencarian teks. 1. Fase Preprocessing Fase preprocessing akan menghasilkan tabel berupa nilai pergeseran yang akan digunakan pada saat fase pencarian teks. Pada fase ini, berlaku dua kondisi yang berfungsi untuk menentukan nilai pergeseran pada tabel 𝑞𝑠𝐵𝑐 (Quick Search badcharacter shift). Nilai pergeseran ditentukan dari Gambar 2.1 berikut.


Gambar 2.1. Fase preprocessing algoritma Quick Search

Keterangan: 𝑞𝑠𝐵𝑐

: Quick Search bad-character shift

𝑥

: pattern

𝑚

: panjang pattern

𝑐

: karakter di dalam teks

𝑖

: indeks karakter di dalam teks

Karakter [𝑐] adalah satu karakter dari teks yang letaknya berada di paling kanan setelah pattern. Ada 2 kondisi dimana nilai pergeseran dapat dicari berdasarkan Gambar 2.1. Nilai pergeseran bernilai 𝑚 + 1 untuk semua perulangan dari 𝑖 = 0 sampai 𝑖 = 𝐴𝑆𝐼𝑍𝐸 − 1, dimana ASIZE merupakan karakter dan simbol pada kode ASCII (American Standard Code for Information Interchange). Nilai pergeseran bernilai 𝑚 − 1 untuk semua karakter pattern dari 𝑖 = 0 sampai 𝑖 = 𝑚 − 𝑖. Sebagai contoh dari pengaplikasian algoritma Quick Search akan diberikan susunan teks NADHIRADWISABRINA dan pattern yang akan dicari dari teks tersebut adalah RINA. Dari susunan teks dan pattern yang diberikan, diketahui bahwa pattern adalah RINA dengan panjang pattern sebanyak 4 karakter. 1. Pada fase preprocessing, karakter yang memuat teks diurutkan sesuai abjad untuk membuat tabel Quick Search bad-character shift. Teks tersebut memiliki karakter sebanyak 9 huruf, yaitu A, B, D, H, I, N, R, S, dan W. Untuk proses awal, nilai pergeseran bernilai 𝑚 + 1 untuk semua karakter [𝑐] dari indeks 𝑖 = 0 sampai 𝑖 = 𝐴𝑆𝐼𝑍𝐸 − 1 sehingga akan didapatkan nilai pergeseran yang ditunjukkan pada Tabel 2.1. berikut. Tabel 2.1. Nilai pergeseran karakter [𝒄] bernilai 𝒎 + 𝟏 Char

A

B

D

H

I

N

R

S

W

𝑞𝑠𝐵𝑐 (char)

5

5

5

5

5

5

5

5

5


2. Pada tahap kedua, nilai pada tabel diganti menjadi 𝑚 − 1 untuk semua karakter pattern dari 𝑖 = 0 sampai 𝑖 = 𝑚 − 𝑖, dimana i adalah indeks karakter pattern yang besarnya dari 0 sampai 𝑚 − 1. Dengan demikian, akan didapat nilai perhitungannya sebagai berikut. 𝑞𝑠𝐵𝑐 [𝑥[𝑖]] = 𝑚 − 1 𝑞𝑠𝐵𝑐 [𝑥[0]] = 4 − 0 = 4 𝑞𝑠𝐵𝑐 [𝑥[1]] = 4 − 1 = 3 𝑞𝑠𝐵𝑐 [𝑥[2]] = 4 − 2 = 2 𝑞𝑠𝐵𝑐 [𝑥[3]] = 4 − 3 = 1 Kemudian, nilai pergeseran awal diganti dengan nilai pergeseran baru sesuai dengan indeks pada karakter pattern. Pattern RINA memiliki nilai indeks dari 0 sampai 3 sehingga untuk [𝑥[0]] diisi karakter R akan memiliki nilai pergeseran baru, yaitu 4. Untuk [𝑥[1]] diisi karakter I akan memiliki nilai pergeseran baru, yaitu 3, begitu seterusnya sampai pada pattern terakhir. Setelah semua perhitungan selesai, maka nilai pergeseran akan berubah menjadi seperti pada Tabel 2.2. Tabel 2.2. Nilai pergeseran karakter [𝒄] bernilai 𝒎 − 𝟏 Char

A

B

D

H

I

N

R

S

W


1

5

5

5

3

2

4

5

5

Setelah semua tahapan pada fase preprocessing selesai, maka akan didapat nilai pergeseran seperti yang ditunjukkan pada Tabel 2.3. berikut ini.

Tabel 2.3 Tabel nilai pergeseran fase preprocessing algoritma Quick Search Char

A

B

D

H

I

N

R

S

W


1

5

5

5

3

2

4

5

5

2. Fase Pencarian Setelah fase preprocessing selesai, maka akan dilanjutkan ke fase pencarian. Ketika dimasukkan pattern RINA untuk menemukan teks NADHIRADWISABRINA, maka nilai pergeseran berfungsi untuk menentukan seberapa banyak pergeseran yang


akan dilakukan pattern untuk menemukan teks yang dicari. Pencarian teks pertama kali akan dilakukan seperti pada Tabel 2.4. berikut.

Tabel 2.4. Fase pencarian teks N

A

D

H

R

I

N

A

I

R

A

D

W

I

S

A

B

R

I

N

A

Pada percobaan pertama, pattern tidak sesuai dengan teks sehingga nilai pergeseran selanjutnya dicari dari satu karakter setelah pattern paling kanan, yaitu I, dimana nilai pergeseran untuk karakter [𝐼], 𝑞𝑠𝐵𝑐 [𝐼] = 3. Maka, pattern akan bergeser sejauh 3 karakter ke kanan sebagaimana terlihat pada Tabel 2.5.

Tabel 2.5. Fase pencarian teks (a) N

A

D

H

I

R

A

R

I

N

A

D

W

I

S

A

B

R

I

N

A

Pada percobaan kedua, pattern masih tidak sesuai dengan teks sehingga pencarian terus dilanjutkan. Nilai pergeseran selanjutnya akan diambil dari karakter [𝐷] yang nilainya adalah 5 sehingga pattern akan bergeser sejauh 5 karakter ke kanan. Pada tahap ini, nilai pergeseran menjadi 𝑞𝑠𝐵𝑐 [𝐷] = 5. Pergeseran akan terlihat seperti pada Tabel 2.6. berikut.

Tabel 2.6. Fase pencarian teks (b) N

A

D

H

I

R

A

D

W

I

S

A

R

I

N

A

B

R

I

N

A

Untuk percobaan ketiga, pattern masih tidak sesuai dengan teks dan pergeseran masih terus dilanjutkan dengan mengambil nilai pergeseran dari karakter [𝐵] yang bernilai 5 sehingga nilai pergeseran menjadi 𝑞𝑠𝐵𝑐 [𝐵] = 5 dan akan bergeser sejauh 5 karakter ke kanan sebagaimana terlihat pada Tabel 2.7.


Tabel 2.7. Fase pencarian teks (c) N

A

D

H

I

R

A

D

W

I

S

A

B

R

I

N

A

R

I

N

A

Pada percobaan terakhir, pattern sesuai dengan teks, dimana pattern RINA sesuai dengan 4 karakter terakhir pada teks NADHIRADWISABRINA. Algoritma Quick Search akan terus bergerak ke kanan hingga karakter teks berakhir. Namun, karena pada kondisi tersebut pattern dan teks sudah mencapai ujung, maka proses pencarian telah berakhir.

2.4.1.2. Algoritma Berry Ravindran Algoritma Berry Ravindran ditemukan oleh T. Berry dan S. Ravindran pada tahun 1999. Algoritma ini merupakan perpaduan antara algoritma Quick Search dan algoritma ZhuTakaoka yang mana cara kerjanya juga terdiri dari dua buah fase, yaitu fase preprocessing dan fase pencarian serta memulai pencocokan pattern dari kiri ke kanan. Pergeseran algoritma ini lebih cepat dengan melakukan perhitungan pergeseran dari dua buah karakter sebelah kanan dari posisi pencocokan string (Trisnandar, et al. 2015). Algoritma ini sering diimplementasikan dalam berbagai fungsi pencarian string, seperti untuk fungsi Find and Replace, pencocokan DNA, dan lain sebagainya. Untuk fase preprocessing, dilakukan perhitungan untuk menentukan jumlah pergeseran dan setelah itu dilakukan fase pencarian dengan cara melakukan pencocokan string dari arah kiri menuju ke kanan. Apabila terjadi ketidakcocokan, maka pattern akan digeser sesuai dengan aturan algoritma Berry Ravindran (Trisnandar, et al. 2015). Seperti yang sudah dijelaskan sebelumnya bahwa algoritma Berry Ravindran memiliki dua fase, yaitu fase preprocessing dan fase pencarian. Berikut akan dijelaskan cara kerja algoritma Berry Ravindran dimulai dari fase preprocessing sampai fase pencarian teks.

1. Fase Preprocessing Fase preprocessing akan menghasilkan tabel berupa nilai pergeseran yang akan digunakan pada saat fase pencarian teks. Pada fase ini, berlaku beberapa kondisi yang


berfungsi untuk menentukan nilai pergeseran pada tabel 𝑏𝑟𝐵𝑐 (Berry Ravindran badcharacter shift). Nilai pergeseran ditentukan dari Gambar 2.2. berikut.

Gambar 2.2. Fase preprocessing algoritma Berry Ravindran

Keterangan: 𝑏𝑟𝐵𝑐

: Berry Ravindran bad-character shift

𝑥

: pattern

𝑚

: panjang pattern

𝑎, 𝑏

: karakter di dalam teks

Karakter [𝑎, 𝑏] adalah dua karakter dari teks secara berurutan yang letaknya berada di paling kanan setelah pattern. Ada 4 kondisi dimana nilai pergeseran dapat dicari berdasarkan Gambar 2.2. Nilai pergeseran bernilai 1 apabila karakter 𝑎 adalah 𝑥[𝑚 − 1]. Nilai pergeseran bernilai 𝑚 − 𝑖 + 1 apabila karakter 𝑎 dan 𝑏 berturut-turut adalah 𝑥[𝑖] dan 𝑥[𝑖 + 1]. Nilai pergeseran bernilai 𝑚 + 1 apabila karakter 𝑏 = 𝑥[0], dan yang terakhir, nilai pergeseran bernilai 𝑚 + 2 untuk karakter 𝑎 dan 𝑏 lainnya. Sebagai contoh dari pengaplikasian algoritma Berry Ravindran akan diberikan susunan teks NADHIRADWISABRINA dan pattern yang akan dicari dari teks tersebut adalah RINA. Dari susunan teks dan pattern yang diberikan, diketahui bahwa pattern adalah RINA dengan panjang pattern sebanyak 4 karakter. 1. Pada fase preprocessing, pattern diurutkan sesuai abjad untuk membuat tabel Berry Ravindran bad-character shift. Pattern tersebut memiliki karakter sebanyak 4 huruf, yaitu A, I, N, R, dan ditambah simbol * sebagai inisialisasi untuk karakter lain selain 4 huruf tersebut. Untuk proses awal, nilai pergeseran bernilai 𝑚 + 2 untuk karakter [𝑎, 𝑏] sehingga akan didapatkan nilai pergeseran seperti pada Tabel 2.8. berikut ini.


Tabel 2.8. Nilai pergeseran karakter [𝒂, 𝒃] bernilai 𝒎 + 𝟐 𝑏𝑟𝐵𝑐

A

I

N

R

*

A

6

6

6

6

6

I

6

6

6

6

6

N

6

6

6

6

6

R

6

6

6

6

6

*

6

6

6

6

6

2. Selanjutnya, pada tahap kedua, nilai pada tabel diganti menjadi 𝑚 + 1 untuk setiap karakter 𝑏 = 𝑥[0]. Artinya, karakter 𝑏 diganti menjadi karakter awal pada pattern sehingga menjadi 𝑏𝑟𝐵𝑐 [𝑎][𝑅]. Ketika 𝑎 bernilai 0, maka 𝑏𝑟𝐵𝑐 akan menjadi 𝑏𝑟𝐵𝑐 [0][𝑅]. Dengan demikian, nilai pergeserannya akan berubah seperti pada Tabel 2.9. berikut. Tabel 2.9. Nilai pergeseran karakter 𝒃 = 𝒙[𝟎] bernilai 𝒎 + 𝟏 𝑏𝑟𝐵𝑐

A

I

N

R

*

A

6

6

6

5

6

I

6

6

6

6

6

N

6

6

6

6

6

R

6

6

6

6

6

*

6

6

6

6

6

Ketika nilai 𝑎 = 1, maka 𝑏𝑟𝐵𝑐 akan berganti menjadi 𝑏𝑟𝐵𝑐 [1][𝑅] yang memiliki nilai pergeseran sama, yaitu 𝑚 + 1. Hal tersebut berlaku seterusnya sampai nilai 𝑎 = 4 sehingga didapat nilai 𝑏𝑟𝐵𝑐, yaitu 𝑏𝑟𝐵𝑐 [4][𝑅] seperti pada Tabel 2.10.


Tabel 2.10. Nilai pergeseran karakter 𝒃 = 𝒙[𝟎] bernilai 𝒎 + 𝟏 (a) 𝑏𝑟𝐵𝑐

A

I

N

R

*

A

6

6

6

5

6

I

6

6

6

5

6

N

6

6

6

5

6

R

6

6

6

5

6

*

6

6

6

5

6

3. Pada tahap ketiga, nilai pergeseran diganti menjadi 𝑚 − 𝑖, dimana 𝑖 adalah perulangan. Perulangan berlangsung ketika nilai 𝑖 = 0 sampai 𝑖 < 𝑚 − 1 atau sampai nilai indeks terakhir dari pattern. Jika pattern memiliki panjang karakter sebanyak 4, maka indeks karakter adalah 4 – 1 = 3. Ketika nilai 𝑖 = 0, maka karakter 𝑥[𝑖] dan 𝑥[𝑖 + 1] berturut-turut adalah karakter R dan I sehingga menjadi 𝑏𝑟𝐵𝑐 [𝑅][𝐼] = 3 dan nilai pergeseran akan berubah menjadi seperti Tabel 2.11. Tabel 2.11. Nilai pergeseran karakter [𝒂, 𝒃] adalah 𝒙[𝒊] dan 𝒙[𝒊 + 𝟏] bernilai 𝒎 − 𝒊

𝑏𝑟𝐵𝑐

A

I

N

R

*

A

6

6

6

5

6

I

6

6

6

5

6

N

6

6

6

5

6

R

6

4

6

5

6

*

6

6

6

5

6

Perulangan terus berlangsung ketika nilai 𝑖 = 1, maka indeks berada pada posisi 𝑥[1] dan 𝑥[2] yang diisi karakter I dan N. Selanjutnya, nilai pergeseran akan berubah menjadi seperti pada Tabel 2.12. berikut ini.


Tabel 2.12. Nilai pergeseran karakter [𝒂, 𝒃] adalah 𝒙[𝒊] dan 𝒙[𝒊 + 𝟏] bernilai 𝒎 − 𝒊 (a)

𝑏𝑟𝐵𝑐

A

I

N

R

*

A

6

6

6

5

6

I

6

3

3

5

6

N

6

6

6

5

6

R

6

4

6

5

6

*

6

6

6

5

6

Ketika nilai 𝑖 = 2, maka indeks berada pada posisi 𝑥[2] dan 𝑥[3] yang diisi karakter N dan A sehingga nilai pergeserannya akan terlihat seperti pada Tabel 2.13. berikut. Perulangan akan berhenti ketika nilai 𝑖 sudah memenuhi kondisi, dimana 𝑖 < 𝑚 − 1. Tabel 2.13. Nilai pergeseran karakter [𝒂, 𝒃] adalah 𝒙[𝒊] dan 𝒙[𝒊 + 𝟏] bernilai 𝒎 − 𝒊 (b)

𝑏𝑟𝐵𝑐

A

I

N

R

*

A

6

6

6

5

6

I

6

3

3

5

6

N

2

6

6

5

6

R

6

4

6

5

6

*

6

6

6

5

6

4. Pada tahap akhir, nilai pergeseran berganti menjadi 𝑥[𝑚 − 1] untuk karakter 𝑎 atau karakter terakhir pada pattern. Apabila karakter terakhir pada pattern adalah A, maka 𝑏𝑟𝐵𝑐 menjadi 𝑏𝑟𝐵𝑐 [𝐴][𝑏] dan pada baris A, nilai yang dihasilkan adalah 1 sebagaimana terlihat pada Tabel 2.14.


Tabel 2.14. Nilai pergeseran karakter 𝒂 bernilai 𝒙[𝒎 − 𝟏] 𝑏𝑟𝐵𝑐

A

I

N

R

*

A

1

1

1

1

1

I

6

3

3

5

6

N

2

6

6

5

6

R

6

4

6

5

6

*

6

6

6

5

6

Setelah semua tahapan pada fase preprocessing selesai, maka akan didapat nilai pergeseran seperti yang ditunjukkan pada Tabel 2.15. berikut ini.

Tabel 2.15. Tabel nilai pergeseran pada fase preprocessing algoritma Berry Ravindran

𝑏𝑟𝐵𝑐

A

I

N

R

*

A

1

1

1

1

1

I

6

3

3

5

6

N

2

6

6

5

6

R

6

4

6

5

6

*

6

6

6

5

6

2. Fase Pencarian Setelah fase preprocessing selesai, maka akan dilanjutkan ke fase pencarian. Ketika dimasukkan pattern RINA untuk menemukan teks NADHIRADWISABRINA, maka nilai pergeseran berfungsi untuk menentukan seberapa banyak pergeseran yang akan dilakukan pattern untuk menemukan teks yang dicari. Pencarian teks pertama kali akan dilakukan seperti pada Tabel 2.16. berikut.

Tabel 2.16. Fase pencarian teks N

A

D

H

R

I

N

A

I

R

A

D

W

I

S

A

B

R

I

N

A

Pada percobaan pertama, pattern tidak sesuai dengan teks sehingga nilai pergeseran selanjutnya dicari dari dua karakter setelah pattern paling kanan, yaitu I dan R, dimana


nilai pergeseran untuk karakter [𝐼, 𝑅] adalah 𝑏𝑟𝐵𝑐 [𝐼][𝑅] = 5. Maka, pattern akan bergeser sejauh 5 karakter ke kanan seperti pada Tabel 2.17. berikut.

Tabel 2.17. Fase pencarian teks (a) N

A

D

H

I

R

A

D

W

R

I

N

A

I

S

A

B

R

I

N

A

Pada percobaan kedua, pattern masih tidak sesuai dengan teks sehingga pencarian terus dilanjutkan. Nilai pergeseran selanjutnya akan diambil dari karakter [𝐼, 𝑆] yang nilainya adalah 6 sehingga pattern akan bergeser sejauh 6 karakter ke kanan. Pada tahap ini, 𝑏𝑟𝐵𝑐 menjadi 𝑏𝑟𝐵𝑐 [𝐼][𝑆] = 6 seperti pada Tabel 2.18. berikut.

Tabel 2.18. Fase pencarian teks (b) N

A

D

H

I

R

A

D

W

I

S

A

B

R

I

R

I

N

A

N

A

Untuk percobaan ketiga, pattern masih tidak sesuai dengan teks dan pergeseran masih terus dilanjutkan dengan mengambil nilai pergeseran dari karakter [𝑁, 𝐴] yang bernilai 2 sehingga 𝑏𝑟𝐵𝑐 menjadi 𝑏𝑟𝐵𝑐 [𝑁][𝐴] = 2 dan akan bergeser sejauh 2 karakter ke kanan sebagaimana terlihat pada Tabel 2.19.

Tabel 2.19. Fase pencarian teks (c) N

A

D

H

I

R

A

D

W

I

S

A

B

R

I

N

A

R

I

N

A

Pada percobaan terakhir, pattern sesuai dengan teks, dimana pattern RINA sesuai dengan 4 karakter terakhir pada teks NADHIRADWISABRINA. Algoritma Berry Ravindran akan terus bergerak ke kanan hingga karakter teks berakhir, dengan nilai 𝑏𝑟𝐵𝑐 [0][0] = 6. Namun, karena pada kondisi tersebut pattern sudah mencapai ujung teks, maka proses pencarian berakhir.


2.5. Penelitian yang Relevan Berikut ini beberapa penelitian yang terkait dengan algoritma Quick Search dan algoritma Berry Ravindran, yaitu sebagai berikut: 1. Trisnandar et al. (2015) dalam jurnal yang berjudul Aplikasi Pengenalan dan Konversi Aksara Sunda dengan Algoritme Berry Ravindran Berbasis Android. Di dalam jurnal tersebut dinyatakan bahwa algoritma Berry Ravindran merupakan algoritma yang paling efisien untuk menyelesaikan pencocokan string. Algoritma ini bekerja dengan memulai pencocokan pattern yang dicari dari kiri ke kanan. Pergeseran algoritma ini lebih cepat dengan melakukan perhitungan pergeseran dari dua buah karakter sebelah kanan dari posisi pencocokan string. Algoritma ini melakukan perhitungan pergeseran karakter menggunakan kombinasi algoritma Smith dan algoritma Zhu Takaoka. 2. Jeklin Indriani Purba (2016) dalam skripsi yang berjudul Implementasi Pencocokan String Menggunakan Algoritma Berry Ravindran pada Aplikasi Kamus Bahasa Indonesia – Simalungun Berbasis Android. Di dalam skripsi tersebut dijelaskan bahwa algoritma Berry Ravindran terdiri dari fase preprocessing dan fase pencarian. Pada fase preprocessing, algoritma Berry Ravindran ditingkatkan pada perhitungan pergeseran untuk pattern bukan karakter teks sehingga hal tersebut akan mengurangi waktu proses pencarian. Setelah dilakukan fase preprocessing, maka selanjutnya dilakukan pencocokan string dari arah kiri menuju kanan. Apabila terjadi ketidakcocokan, maka pattern digeser sesuai dengan aturan algoritma Berry Ravindran. 3. Petrus Dwi Purwoko (2006) dalam skripsi yang berjudul Perbandingan Algoritma Turbo BM, Algoritma Quick Search, dan Algoritma Shift-Or. Di dalam skripsi tersebut dijelaskan bahwa algoritma Quick Search merupakan salah satu algoritma penyederhanaan dari algoritma Boyer Moore (merupakan varian yang lebih sederhana) yang dalam prakteknya dianggap paling efisien dan mudah untuk diimplementasikan. Algoritma Quick Search menggunakan metode pencocokan string dari kiri ke kanan. Algoritma ini hanya menggunakan tabel bad-character shift dan tabel qsBc untuk menyimpan nilai pergeserannya. Bad-character shift dari algoritma ini sedikit dimodifikasi untuk karakter terakhir dari pattern.


BAB 2 LANDASAN TEORI

Recommend Documents