!
METODE PENCARIAN DAN TEMU-KEMBALI NAMA BERDASARKAN KESAMAAN FONETIK
DEWI PRIMASARI
PROGRAM STUDI ILMU KOMPUTER FAKUL T AS MATEMA TIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR
1997
RINGKASAN DEWI PRIMASARL Metode Pencarian dan Temu-Kembali Nama Berdasarkan Kesamaan Fonetik (Searching and Retrieval Methods of Proper Name Based on Phonetics Similarity). Dibimbing oleh JULIO ADISANTOSO dan MEUlHlA RACHMANIAH. Sistem temu-kembali informasi membandingkan query pengguna pada dokmnen-
t
_~_
c,"
'o"
'"l _,
METODE PENCARIAN DAN TEMU-KEMBALI NAMA BERDASARKAN KESAMAAN FONETIK
DEWI PRIMASARI
Skripsi sebagai salah satu syarat nntuk memperoleh gelar
Srujana Sains pada Program Studi limn Komputer
PROGRAM STUDI ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR ·1997
Judul
Metode Pencarian dan Temu-Kembali Nama Berdasarkan Kesamaan Fonetik
Nama
Dewi Primasari
NIM
G30.0587
MeIWetujui,
Ir. Juli
disantoso, MKomp Pembimbing I
Tanggal Lulus : 8 September 1997
If. Meuthia Rachmaniah, MSc Pembimbing II
RIWAYATHIDUP Penulis dilahirkan di Bogar pacla tanggal 28 September 1974 sebagai anak sulung clari tiga bersauclara, anak clari pasangan Drs. Suyadi Prawirosentono, MBA clan Laksmini. Pacla tahun 1993, penulis lulus dari SMA Negeri I Bogar. Pacla tahun yang sarna, penulis juga berhasillulus seleksi masuk masuk IPB melalui jalur Undangan Seleksi Masuk IPB (USMI). Pacla tahun 1994, penulis memilih Program Studi llmu Komputer di Fakultas Matematika clan llmu Pengetahuan Alam.
PRAKATA Segala puji dan syukur penulis panjatkan kepada Allah SWT atas karunia-Nya sehingga karya Umiah ini dapat diselesaikan dengan baik
Topik yang dipilih dalam penelitian ini adalah temu-kembali
informasi dengan judul Metode Pencarian dao Temu-Kembali Nama Berdasarkan Kesamaan Fonetik. Penulis menghaturkan terima kasih kepada semua pibak yang telah membantu penyelesaian karya ilmiah ini. antara lain Bapak Ir. Julio Adisantoso. MKomp dan Ibu Jr. Meuthia Rachmaniah. MSc selaku pembimbing. Ungkapan terima kasih juga disampaikan kepada se1uruh keluarga, bapak, mama, adikadik dao mas Selo alas segala doa dan dorongannya kepada penulis. Semoga karya ilmiah ini bermanfaat untuk ikut mengembangkan sistem temu-kembali informasi di Indonesia.
Bogor, September 1997
Dewi Primasari
DAFTAR lSI Halaman DAFTAR TABEL
.......................................................................................................................... vi
DAFTAR GAMBAR
..................................................................................................................... vi
DAFTAR LAMPmAN ..................................................................................................................... vi PENDAHULUAN .......................................................................................................................... Latar Belakang ........ ....... .... ........... ....... ..... ........ ... ........... .................... ............ ..................... Tujuan ................................................................................................................................
1
1 1
TINJAUANPUSTAKA ............................................................................................................... 2 Orgaoisasi Data ....... ....... ... ...... .......... ...... .................................... ..................................... ..... 2 Algoritme. ... ................ ....... ...... ... ............. ... .......... .................. ................................................ 3 Sistem Evaluasi ..................................................................................................................... 8 Tata Bunyi ........................................................................................................................... 9 METODE PENELITIAN ............................................................................................................... Pengambilan Data ........ .......... ................... .... ............................. .......... .......................... ...... Pembuatan Program ................................................................................................................ Pengujian Program ................................................................................................................ Percobaan ........................................................................................................................... Analisis Data dan Pengambilan Kesimpulan .......................................................................... HASILDANPEMBA1lASAN .......................................................................................................... Karakteristik Dokumen .. ... ......... ....... .......... ........................ ................................................... Hasil Percobaan ......... ........... .... ........ ......... ............................................ .... ............................ Ana1isis Nilai Recall-Precision ............................................................................................... Tingkat Recall yang OptimaJ ............ ..... ... ......... .................................................................. Analisis Algoritme ................. ... ........ ..... .............................................................................. Kelebiban dan Kelemahan Metode Kesamaan Fonetik ........................................................
11
II 12 15 15 16 16 16 16 17 19 20 21
KESlMPULAN DAN SARAN .......................................................................................................... 22 Kesimpulan .................. ....... ...... .......... ... ... ............................... .......... ..... ........ ...................... 22 Saran ...................................................................................................................................... 22 DAFTARPUSTAKA
..................................................................................................................... 23
LAMP1RAN .....................................................................................................................................
24
DAFTAR TABEL Halaman 1. Bilangan pengganti huruf pada kode Soundex
............................................................... ....... .... 5
2. Bilangan pengganti huruf pada kode Phonix .... .........................................................................
6
3. Contoh penggunaan analisis trigram
6
............................................................ ................... ...........
4. Pembagian konsonan dalam bahasa Inggris
5. Query dan variannya
............................................................................... 10
..... .......... ................................................................................................
15
6. Nilai rata-rata recall-precision metode Soundex dan Phonix ...................................................
17
DAFTAR GAMBAR Halaman 1. Variasi nilai recall dan precision ................................................................................................ 8 2. Grafik recall-precision ................................................................................................................ 3. Diagram alir data (DFD) 1eve11 data nama
9
.................................................... .... ....... ................ 14
4. Diagram alir data (DFD) leve12 untnkfiltering .........................................................................
14
5. Diagram alir data (DFD) level 2 untnk query ..............................................................................
14
6. Tahapan penelitian ..................................................................................................................... 16 7. Grafik recall-precision pada empat metode kesamaan fonetik
...................................................
18
8. Pengelompokan konsonan .......................................................................................................... 21
DAFTAR LAMPIRAN Halaman 1. Nama dan kode hasilfiltering ..................................................................................................... 25 2. Nilai recall-precision percobaan penelitian dengan metode Soundex
......................................... 31
3. Nilai recall-precision percobaan penelitian dengan metode Phonix4
......................................... 32
4. Nilai recall-precision percobaan penelitian dengan metode Phonix8
......................................... 33
5. Nilai recall-precision percobaan penelitian dengan metode PhonixE
......................................... 34
PENDAHULUAN Latar Belakang Sistem temu-kembali informasi (infimnalion secara otomatis pada awalnya retrieval) dikembangkun untuk membantu mengatur literatur ilmu pengetahuan yang jmnlahnya sangat banyak Banyak sekali perguruan tinggi, perusahaan, dan perpustakaan mnmn yang telah menggunakan sistem temu-kembali informasi untuk mengakses buku, jurnal atau dokumen lainnya, Sebuah sistem temu-kembali membandingkan query pengguna pada dokumen>{\okumen yang disimpan dalam basis data (Pfeifer et ai" 1996), Istilah dokumen (document) biasanya dipakai sebagai kata benda, segala hasil keIja yang dibentuk oleh program aplikasi, dan bila direkam pada disk diberi nama file yang unik untuk memanggiInya (Microsoft Press, 1995), tetapi pada skripsi ini, dokumen mempunyai arti yang berbeda, yaitu sebuah obyek data, yang biasanya berbentuk teks walaupnn dapat juga terdiri dari berbagai tipe data, seperti foto, grafik, dan sebagainya (Frakes & Baeza-Yates, 1992), Dokumen>{\okumen itu sendiri sering tidak disimpan langsnng dalam sistem temu-kembali, tetapi direpresentasikan dalam sistem menurut karakteristiknya masing-masing, Karakteristik dokumen dapat berupa judu!, pengarang atau abstrak Hal ini dilakukan untuk meningkatkan efisiensi dengan cara menekan ukuran basis data dan waktu pencarian, Sistem temu-kembali informasi modern yang telah ada ummnnya difoknskan pada masalahmasalah temu-kembali informasi dengan queryquery berkonteks bahasa natural, Sebenarnya banyak pengguna dari sistem temu-kembali ini telah mengetahni nama pengarang atau editor yang dicari, tetapi sejauh ini hanya sedikit perhatian untuk tipe query ini, Di sini ketidakjelasan akar kala akibat pengetahuan informasi pengguna yang terbalas akan menjadi kendala, Sebagai contoh, (1) jilca pengguna salah mengeja nama pengarang yang dicari, maka pencarian tidak akan berhasil, dan (2) bila pengguna melakukan kesalahan pengetikan, maka pencarian ini juga tidak akan berhasil, Tipe error ini sangat sering muncul, bahkan jilca
pengguna telah mengetahui pengejaan nama yang benaL Beberapa pendekatan telah dibnat, seperti dengan menggunakan wildcard yang terperinci pada query untuk menemukan turnnan atau kata yang mmp, Algoritme Stemming untuk melakukan pencarian kata-kata dengan bentuk dasar telah dilakukan, tetapi metode ini hanya berguna untuk kata-kata mnmn dan tidak tepat digunakan untuk melakukan pencarian nama, Ukuran kesamaan non-lingnistik dapat dikelompokkan menjadi tiga kategori besar yang berbeda, yaitu (1) kesarnaan string, (2) kesamaan yang berhubungan dengan kesalahan pengetikan, dan (3) kesarnaan fonetik Pada penelitian ini akan dilakukan pencarian nama dengan metode kategori ketiga, yaitu dengan menggunakan algoritme Soundex dan Phonix, Algoritme Soundex dan Phonix adalah dua buah algoritme yang dibuat dengan melihat kesamaan bunyi bahasa, Kedna algoritme ini dikembangkan untuk bahasa Inggris, yang belwn tentu cocok bila diterapkan pada bahasa lain, misaInya bahasa Indonesia yang pengucapannya berbeda. Maka pada penelitian ini akan ditelaah apakah kedua algoritme tersebut dapat bekeIja dengan baik pada bahasa Indonesia. Pada dasarnya proses temu-kembali informasi dilakukan berdasarkan ukuran kesesuaian antara query dengan kata-kata yang terdapat dalam dokwnen. Yang menjadi masalab adalah pada sistem temu-kembali informasi, jumIah dokwnen yang relevan kadang-kadang terlalu sedikit atau terlalu banyak (Adisantoso, 1997). Untuk itu perlu diketahni berapa jumIah dokumen yang ditemu-kembalilcan agar cukup optimal. Sebenarnya penelitian untuk membandingkan kineIja beberapa metode terkenal dari ketiga kategori ukuran kesarnaan di alas telah dilakukan oleh Ulrich pfeifer, Thomas Poersh, dan Norbert Fuhr pada tahun 1996. Pada penelitian tersebut basis data yang digunakan adalah nama-nama orang Eropa atau Amerika, sedangkan pada penelitian ini akan digunakan basis data dengan nama-nama Indonesia yang mnmn. Tujuan Tujuan dari penelitian ini adalah sebagai berikut:
2
I.
2.
3.
Menelaah dan membandingkan efektifitas sistem temu-kembali antara aigoritme Soundex dan Phonix. Menganalisis kineIja masing-masing aigoritme terhadap hasis data yang berisi nama-nama Indonesia. Menentukan jumIah dokumen (tingkat recall) yang ditemu-kembalikan untuk setiap metode agar cukup optimal.
TINJAUAN PUSTAKA Sistem temu-kembali informasi secara otomatis pada molanya dikembangkan untuk membantu mengatur literatur ilmu pengetahuan yang sangat banyak. Sistem ini mengelola dokumen-dokumen yang terorganisasi dalam record pada berkas (file) dan mengelola pemtintaan (request) informasi. kemudian mengembalikannya dalam berkas teitentu sebagai tanggapan terhadap pemtintaan tersebut. Penemu-kembalian dokumen-dokumen tergantung pada ukuran kesamaan antara dokumen dan query yang diukur dengan membandingkan nilai beberapa atribut. Sistem temu-kembali informasi hams dibuat untuk mendokung operasi-<>perasi dasar, yaitu operasi pemasukan dokumen ke dalam hasis data, operasi penambahan dokumen, operasi penghapusan, operasi pencarian dokumen dengan cara tertentu, dan operasi penampiIan pada !ayar.
Organisasi Data Struktur Data Strnktur data dalam temu-kembali informasi sedikit banyak akan mempengarnhi efisiensi keIja sistem temu-kembali informasi tersebut, terutama dalam proses pencarian (Frakes & Baeza-Yates, 1992). Gleh karena itu tipe struktur data temukembali informasi ini hams dipilih dengan hatihati. Ada empat bentuk dasar untuk mengorganisasikan data, yaitu (I) larik (array), (2) search tree, (3) digital tree, dan (4) hash. Tipe larik adalah tipe terstruktur yang mempunyai komponen dalam jumIah yang tetap dan setiap komponen mempunyai tipe data yang sama (Santosa, \993). Pengnrutan Pengurutan data (sorting) didefinisikan sebagai suatu
secara umum proses
untuk
menynsun kembali himpunan obyek menggnnakan aturan tertentu (Santosa, 1993). Secara umum terdapat dna jenis pengnrutan data, yaitu (I) pengnrutan secara menaik (ascending), yaitu dari data yang nilainya paling kecil sampai paling besar dan (2) pengurutan secara menurun (descending), yaitu dari data yang nilainya paling besar sampai paling kecil. Tujuan pengnrutan data adalah untuk mempermudah pencarian data. Pernilihan aigoritme pengnrutan sangat ditentukan oleh struktur data yang dignnakan. Dengan aiasan ini, maka metode pengnrutan dapat diklasifikasikan menjadi dna kategori, yaitu pengnrutan larik dan pengurutan senarai Metode-metode pengnrutan larik sangat memperhatikan dan mempertimbangkan aspek efisiensi waktu dan kapasitas memory. Beberapa metode yang terkenal adalah metode penyisipan langsung, metode penyisipan biner, metode seleksi, metode bubble sort, metode shell sort, metode radix sort, dan metode quick sort. Secara umum metode quick sort lebih efisien daripada metode-metode lainnya (Stubbs & Webre, 1984), aigoritmenya adalah sebagai berikut : I. Baca larik yang akan diurutkan, rnisalkan r. 2. Inisialisasi kiri = I dan kanan = jumIah record yang ada. 3. KeIjakan langkah 4 sampai 5 bila kiri < kanan. 4. lnisialisasi j = kiri dan k = kanan + 1. 5. KeIjakan langkah 6 hingga 8 sampai j > Ie, 6. Tambah nilai j dengan I sampai r[j] >= r[kiri]. 7. Kurangi nilai k dengan I sampai r[k] <= r[kiri]. 8. Jika j < Ie, maka tukarkan posisi r[j] dengan r[k]. 9. Tukarkan posisi r[kiri] dengan r[k1 __•. 10. KeIjakan langkah 3 untuk kiri = I'aan kanan = k-1. 11. KeIjakan langkah 3 untuk kiri = k + I dan kanan = jumIah record yang ada. Pencarian Beberapa metode yang dapat diterapkan untuk pencarian diantaranya, yaitu pencarian berurutan (sequential searching), pencarian pada tabel yang sudah diurutkan (sorting table searching), pencarian biner (binary searching), dan pencarian berurutan berindeks (indexed sequential searching).
