BAB 2 LANDASAN TEORI

BAB 2 LANDASAN TEORI

Pada bab ini akan dibahas tentang teori-teori dan konsep dasar yang mendukung pembahasan dari sistem yang akan dibuat.

2.1. Katalog Perpustakaan

Katalog perpustakaan merupakan suatu media yang dibutuhkan oleh perpustakaan agar dapat memudahkan pengunjung dalam memperoleh informasi mengenai koleksi apa saja yang dimiliki oleh perpustakaan. Ada beberapa pengertian tentang katalog perpustakaan, antara lain yaitu : a. Gates (1989) menyatakan bahwa katalog perpustakaan adalah suatu daftar yang sistematis dari buku dan bahan-bahan lain dalam suatu perpustakaan, dengan informasi deskriptif mengenai pengarang, judul, penerbit, tahun terbit, bentuk fisik, subjek, dan ciri khas bahan. b. Sulistyo-Basuki (1991) menyatakan bahwa katalog perpustakaan adalah senarai dokumen yang dimiliki sebuah perpustakaan atau kelompok perpustakaan. c. Taylor (1992) menyatakan bahwa katalog perpustakaan merupakan susunan yang sistematis dari seperangkat cantuman bibliografis yang merepresentasikan kumpulan dari suatu koleksi tertentu. Koleksi tersebut terdiri dari berbagai jenis bahan, seperti buku, terbitan berkala, peta, rekaman suara, gambar, notasi musik, dan sebagainya.

Universitas Sumatera Utara

7

2.2. Fitur atau Layanan Autocomplete

Autocomplete merupakan pola yang pertama kali muncul dalam bantuan fungsi aplikasi dekstop, dimana pengguna mengentrikan teks ke dalam kotak kemudian saran pengetikan akan muncul secara otomatis (Morville & Callender, 2010). Autocomplete memecahkan beberapa masalah umum pada pengetikan (Morville & Callender, 2010) yaitu : a. Mengetik membutuhkan waktu. b. Pengguna tidak dapat mengeja kata dengan baik. c. Pengguna sering bingung ketika mengetikkan kata-kata, sulit mengingat istilah yang tepat. Autocomplete melibatkan program yang dapat melakukan prediksi terhadap sebuah kata atau frasa yang pengguna ingin tulis tanpa harus menulis keseluruhan kata atau frasa secara lengkap (Kusuma, 2012). Autocomplete bekerja ketika pengguna menulis huruf pertama atau beberapa huruf/karakter dari sebuah kata, program yang melakukan prediksi akan mencari satu atau lebih kemungkinan kata sebagai pilihan. Jika kata yang dimaksud ada dalam pilihan kata prediksi maka kata yang dipilih tersebut akan disisipkan pada teks (Kusuma, 2012). Saat ini autocomplete tidak hanya terdapat pada dekstop, tetapi terdapat juga pada web browser, email-programs, search engine interface, source code editors, database query tools, word processor, dan command line interpreters (Kusuma, 2012). Ilustrasi penggunaan layanan autocomplete dapat dilihat pada gambar 2.1.

kecerd

search

Kecerdasan Buatan

Gambar 2.1. Ilustrasi Penggunaan Autocomplete

Universitas Sumatera Utara

8

2.3. Approximate String Matching

Approximate string matching merupakan pencocokan string dengan dasar kemiripan dari segi penulisannya (jumlah karakter dan susunan karakter), tingkat kemiripan ditentukan dengan jauh tidaknya beda penulisan dua buah string yang dibandingkan tersebut (Haryanto, 2011). Operasi mengubah string ini bisa berupa mengubah satu huruf ke huruf yang lain, menghapus satu huruf dari string, atau memasukkan satu huruf ke dalam string. Operasi-operasi ini digunakan untuk menghitung jumlah perbedaan yang diperlukan untuk pertimbangan kecocokan suatu string dengan string sumber, jumlah perbedaan tersebut diperoleh dari penjumlahan semua pengubahan yang terjadi dari masingmasing operasi. Penggunaan perbedaan tersebut diaplikasikan dalam berbagai macam algoritma, seperti Hamming, Levenshtein, Damerau-Levenshtein, Jaro-Winkler, Wagner-Fischer, dan lain-lain (Husain, 2013). Operasi penghitungan tersebut meliputi tiga operasi string seperti di bawah ini (Adiwidya, 2009).

2.3.1. Operasi penghapusan Operasi penghapusan dilakukan dengan menghapus karakter pada indeks tertentu untuk menyamakan string sumber (S) dengan string target (T), misalnya S= networking dan T= network. Penghapusan dilakukan untuk karakter i pada lokasi ke8, penghapusan karakter n pada lokasi ke-9, penghapusan karakter g pada lokasi ke10. Operasi penghapusan tersebut menunjukkan tranformasi S ke T, ilustrasinya adalah sebagai berikut :

1 2 3 4 5 6 7 8

9 10

T= n e t w o r k - - S= n e t w o r k

i n g

Universitas Sumatera Utara

9

2.3.2. Operasi penyisipan Operasi penyisipan dilakukan dengan menyisipkan karakter pada indeks tertentu untuk menyamakan string sumber (S) dengan string target (T), misalnya S= program dan T= pemrograman. Operasi penyisipan dapat dilakukan dengan menyisipkan e pada posisi 2, menyisipkan m pada posisi 3, menyisipkan a pada posisi 10 dan menyisipkan n pada posisi 11. Yang dapat diilustrasikan sebagai berikut:

1 2 3 4 5 6 7 8

9 10 11

T= p e m r o g r a m a S= p

n

- - r o g r a m - e m

a n

2.3.3. Operasi penukaran Operasi penukaran dilakukan dengan menukar karakter pada indeks tertentu untuk menyamakan string sumber (S) dengan string target (T), misalnya S= computer dan T= komputer. String S ditranformasikan menjadi T dengan melakukan penggantian (substitusi) pada posisi ke-1. Huruf C ditukar menjadi K. Prosesnya dapat diilustrasikan sebagai berikut:

1 2 3 4 5 6 7 8 T= k o m p u t e r S= c o m

p u t

e r

k

2.4. Algoritma Hamming Distance

Algoritma Hamming Distance merupakan salah satu dari algoritma approximate string matching yang ditemukan oleh Richard Hamming pada tahun 1950, algoritma

Universitas Sumatera Utara

10

ini pertama sekali digunakan untuk mendeteksi kesalahan dan memperbaiki telekomunikasi sebagai estimasi error. Sehingga algoritma Hamming Distance sering disebut jarak sinyal, pada masa sekarang algoritma ini banyak digunakan untuk teori informasi, teori pengkodean, dan kriptografi. Cara kerja algoritma Hamming Distance yaitu dengan mengukur jarak antara dua string yang ukurannya sama dengan membandingkan simbol-simbol yang terdapat pada kedua string pada posisi yang sama. Hamming distance dari dua string adalah jumlah simbol dari kedua string yang berbeda (Jaya, 2013). Sebagai contoh algoritma Hamming distance dapat diilustrasikan sebagai berikut : 1

2 3 4 5 6 7 8

T=

a l g o

r i

S=

a l g o

r r m m a i

t

9

m a

t

Dari ilustrasi di atas, nilai Hamming Distance yang diperoleh yaitu 2, dimana hanya diperlukan 2 operasi penukaran untuk mengubah string „algorrmma‟ menjadi string „algoritma‟. Algoritma Hamming Distance juga digunakan untuk mengukur jarak antar dua string binary misalnya jarak antara „10011101‟ dengan „10001001‟ yaitu 2, algoritma Hamming Distance tidak dapat digunakan untuk mengukur atau membandingkan string dengan panjang yang berbeda, algoritma yang mampu membandingkan string dengan panjang yang berbeda yaitu algoritma Levenshtein Distance, algoritma ini tidak hanya melakukan operasi penukaran tetapi juga melibatkan operasi penyisipan dan penghapusan (Jaya, 2013).

2.5. Algoritma Levenshtein Distance

Algoritma Levenshtein Distance ditemukan oleh Vladimir Levenshtein, seorang ilmuan asal Rusia pada tahun 1965 (Janowski, 2010), algoritma ini sering juga disebut dengan Edit Distance (Husain,2013). Yang dimaksud dengan distance adalah jumlah modifikasi yang dibutuhkan untuk mengubah suatu bentuk string ke bentuk string yang lain, sebagai contoh hasil penggunaan algoritma ini, string “komputer” dan “computer” memiliki distance 1 karena hanya perlu dilakukan satu operasi saja untuk

Universitas Sumatera Utara

11

mengubah satu string ke string yang lain. Dalam kasus dua string di atas, string “computer” dapat menjadi “komputer” hanya dengan melakukan satu penukaran karakter „c‟ menjadi „k‟ (Andhika, 2010). Algoritma Levenshtein Distance digunakan secara luas dalam berbagai bidang, misalnya mesin pencari, pengecek ejaan (spell checking), pengenal pembicaraan (speech recognition), pengucapan dialek, analisis DNA, pendeteksi pemalsuan, dan lain-lain. Algoritma ini menghitung jumlah operasi string paling sedikit yang diperlukan untuk mentransformasikan suatu string menjadi string yang lain (Adiwidya, 2009). Algoritma Levenshtein Distance bekerja dengan menghitung jumlah minimum pentranformasian suatu string menjadi string lain yang meliputi penghapusan, penyisipan, dan penukaran (Husain, 2013). Selisih perbedaan antar string dapat diperoleh dengan memeriksa apakah suatu string sumber sesuai dengan string target. Nilai selisih perbedaan ini disebut juga Edit distance/ jarak Levenhstein. Jarak Levenshtein antar string s dan string t tersebut adalah fungsi D yang memetakan (s,t) ke suatu bilangan real nonnegatif, sebagai contoh diberikan dua buah string s = s(1)s(2)s(3)...s(m) dan t = t(1)t(2)t(3)...t(n) dengan | s | = m dan | t | = n sepanjang alfabet V berukuran r sehingga s dan t anggota dari V*. S(j) adalah karakter pada posisi ke-j pada string s dan t(i) adalah karakter pada posisi ke-i pada string t. Sehingga jarak Levenshtein dapat didefinisikan sebagai (Harahap, 2013).

D(s, t )

= d( s1, t1 ) + d( s2, t2 ) + … + d( sl, tl )

(1)

𝑙

𝐷 𝑠, 𝑡

=

𝑑 𝑠𝑖, 𝑡𝑖

(2)

𝑖=1

dimana

:

si , t i

V untuk i = 1,2,…,l

d( si, ti ) = 0

jika si = ti dan

d( si, ti ) = 1

jika si

ti

Universitas Sumatera Utara

12

D ( s, t) adalah banyaknya operasi minimum dari operasi penghapusan, penyisipan dan penukaran untuk menyamakan string s dan t. Pada implementasi pencocokan antar string, ketiga operasi tersebut dapat dilakukan sekaligus untuk menyamakan string sumber dengan string target seperti pada contoh berikut ini. Jika diberikan string sumber (S) = “pemrograman” dan T = “ algoritma” merupakan string target, dengan | s | = 12, | t | = 9, maka proses pencocokan string dapat diilustrasikan sebagai berikut : 1 2 3 4 5 6 7 8 9 10 11 12 T= a l g o S= p e

r i

m r o

a l g o

i

t m a g r

- -

-

a m a n

t m

Pada contoh di atas terlihat bahwa proses penukaran karakter „p‟ pada indeks ke-1, „e‟ pada indeks ke-2, ‟m‟ pada indeks ke-4, ‟o‟ pada indeks ke-6, ‟g‟ pada indeks ke-7, ‟r‟ pada indeks ke-8, penyisipan karakter „g‟ pada indeks ke-3 dan proses penghapusan karakter „m‟ pada indeks ke-10, „a‟ pada indeks ke-11 dan „n‟ pada indeks ke-12. Maka jarak Levenshtein antara s dan t adalah sebagai berikut ini.

12

𝐷 𝑠, 𝑡 =

𝑑 𝑠𝑖, 𝑡𝑖 𝑖=1

= d( s1, t1 ) + d( s2, t2 ) + d( s3, t3 ) + d( s4, t4 ) + d( s5, t5 ) +

d( s6, t6 ) + d( s7, t7 ) + d( s8, t8 ) + d( s9, t9 ) + d( s10, t10 ) + d( s11, t11 ) + d( s12, t12 ) = d( a, p ) + d( l, e ) + d( g, - ) + d( o, m ) + d( r, r ) + d( i, o) + d( t, g ) + d( m, r) + d( a, a ) + d( -, m )+ d( -, a) + d(-, n) = 1+1+1+1+0+1+1+1+0+1+1+1 = 10

Universitas Sumatera Utara

13

Sehingga jarak Levenshtein antara string s = “pemrograman” dan t = “algoritma” adalah D(s, t) = 10.

2.6. Penelitian Terdahulu

Pada bagian ini akan dijelaskan beberapa penelitian terdahulu, layanan autocomplete telah banyak digunakan pada penelitian terdahulu. Seperti layanan autocomplete pada teks editor (Chiquita, 2011), dengan menggunakan algoritma Boyer-Moore dan Dynamic Programming. Penelitian selanjutnya yaitu layanan autocomplete diterapkan pada IDE (integrated development environment) (Kusuma, 2012), dengan menggunakan algoritma Brute Force. Kemudian layanan autocomplete juga pernah diterapkan pada Smart Phones (Pradhana, 2012), dengan menggunakan kombinasi algoritma Brute Force, Boyer-Moore dan Knuth-Morris Pratt. Untuk lebih jelasnya, pada tabel 2.1 berikut akan dijelaskan penelitian-penelitian yang telah dibuat sebelumnya. Tabel 2.1. Penelitian sebelumnya yang berkaitan dengan Autocomplete No.

Judul

Pengarang

Tahun

Kelebihan

Kekurangan

Penerapan Algoritma Boyer-Moore-

Algoritma Boyer-Moore

Dynamic

lebih mangkus

Programming 1

untuk Layanan

Christabella Chiquita B

dibandingkan dengan 2011

algoritma yang lain serta

Auto-Complete

sangat tepat digunakan

dan Auto-

sebagai layanan auto-

Correct

complete

Tidak ada

Pencocokan string untuk fitur autocompletion 2

pada text editor atau integrated development

Algoritma brute force Muhammad Wachid Kusuma

2012

dapat diterapkan untuk

Cara kerja algoritma

membentuk fitur

brute force berjalan

autocomplete pada text

lambat

editor dengan baik

environment (IDE)

Universitas Sumatera Utara

14

Tabel 2.1. Penelitian sebelumnya yang berkaitan dengan Autocomplete (Lanjutan) No.

Judul

Pengarang

Tahun

Kelebihan

Kekurangan

Penerapan algoritma string Penerapan String

matching seperti Brute

Matching pada Fitur 3

Force, Boyer-Moore dan

Waktu pengecekan

KMP pada fitur auto

membuat sistem mejadi

Fitur Auto Text di

correct mampu

lambat

Smart Phones

memberikan hasil yang

Auto Correct dan

Fandi Pradhana

2012

benar-benar

Sedangkan penelitian terdahulu yang berkaitan dengan algoritma Levenshtein Distance yaitu penggunaan algoritma Levenshtein Distance dan metode empiris untuk menampilkan saran perbaikan kesalahan pengetikan dokumen berbahasa Indonesia (Adriyani, 2012), selanjutnya algoritma Levenshtein Distance pernah digunakan untuk penerapan string suggestion dengan tambahan alternatif algoritma lain dalam aplikasi (Andhika, 2010), kemudian algoritma Levenshtein Distance juga diterapkan pada sistem pengoreksian kata kunci dengan studi kasusnya yaitu pada website Universitas Halmahera (Benisius, 2010). Untuk lebih jelasnya, pada tabel 2.2 berikut akan dijelaskan penelitian-penelitian yang telah dibuat sebelumnya. Tabel 2.2. Penelitian yang berkaitan dengan algoritma Levenshtein Distance

No.

Judul

Pengarang

Tahun

Penerapan Algoritma Levenshtein Distance 1

untuk Mengoreksi Kesalahan Pengejaan

Kelebihan

Kekurangan

Algoritma Levenshtein Muhammad Bahari Ilmy

2006

Distance mampu menghitung tingkat kemiripan string pada

Tidak ada

teks editor

pada Editor Teks

Dengan adanya konsep pemrograman dinamis pada algoritma Levenshtein

Dynamic

Distance menjadikan

Programming dalam 2

Levenshtein Distance

Rizka Irawan

untuk Mengetahui

Ardiyanto

Keterbedaan Dua String

algoritma ini memberikan 2008

banyak kemajuan dalam

Tidak ada

bidang teknologi komputer, dimana dengan lahirnya berbagai fitur seperti spellchecker dan detektor plagiarisme

Universitas Sumatera Utara

15

Tabel 2.2. Penelitian yang berkaitan dengan algoritma Levenshtein Distance (Lanjutan) No.

Judul

Pengarang

Tahun

Kelebihan

Kekurangan

Algoritma program dinamis edit distance ini memiliki kompleksitas O(m.n) yang jauh lebih baik daripada algoritma pengecekan secara Algoritma program 3

Dinamis Edit Distance untuk Pengecekan

exhaustive search O(3m+n), Samsu Sampena

2009

Ejaan

selain itu algoritma edit distance dapat digunakan untuk banyak hal, diantaranya untuk pendeteksian plagiarisme, pencocokan bentuk,

Untuk kemampuan pengecekan ejaan secara konteks dibutuhkan pengembangan lebih lanjut menjadi kajian NLP (Natural Language Processing)

perbandingan DNA, dan speech recognition

Metode Levenshtein Distance

Sistem Pengoreksian Kata Kunci Menggunakan Metode 4

Levenshtein Distance

Benisius

2010

(Studi Kasus: Website Universitas Halmahera)

mendukung operasi string

Sistem yang

sampai

dibangun belum

dengan 255 karakter

mampu

sehingga dapat

melakukan

digunakan untuk operasi

pencarian secara

string pada

terurut (rangking)

skala yang lebih besar lagi.

Penerapan String

Database harus

Suggestion dengan Algoritma Levenshtein 5

Distance dan Alternatif Algoritma

Fatardhi Rizky Andhika

2010

Lain dalam Aplikasi

Mampu memberikan saran

selalu di update

atau pembenaran terhadap

agar

kumpulan masukan string

fungsionalitas

pengguna

string sugesstion meningkat

Implementasi Algoritma Levenshtein Distance dan Metode Empiris untuk 6

Menampilkan Saran Perbaikan Kesalahan Pengetikan Dokumen Berbahasa Indonesia

Mampu mengatasi kesalahan Ni Made Muni Adriyani

2012

Masih sebatas

pengetikan dengan

pengecekan pola

mekanisme penambahan,

kalimat Berbahasa

penyisipan dan penghapusan

Indonesia

karakter

Universitas Sumatera Utara

16

Tabel 2.2. Penelitian yang berkaitan dengan algoritma Levenshtein Distance (Lanjutan) No.

Judul

Pengarang

Tahun

Kelebihan

Kekurangan

Implementasi Algoritma Cocke-

Algoritma CYK dan

Younger-Kasami 7

(CYK) dan

Berry Safaat

Levenshtein untuk

Harahap

Mengoreksi Kesalahan Pengejaan Kalimat

Levenshtein mampu 2013

menampilkan saran perbaikan tulisan kalimat

Masih bergantung pada akurasi prediksi jenis kata oleh openNLP.

Bahasa Inggris

Bahasa Inggris

Universitas Sumatera Utara