Indexing and Retrieval Engine untuk Dokumen Berbahasa Indonesia dengan Menggunakan Inverted Index PDF

Preview

Summary

INDEXING AND RETRIEVAL ENGINE UNTUK DOKUMEN BERBAHASA INDONESIA DENGAN MENGGUNAKAN INVERTED INDEX Wahyu Hidayat1 1 Departemen Teknologi Informasi, Fakultas Ilmu Terapan, Telkom University 1 [email protected] Abstrak Dokumen teks tergolong dalam data tidak terstruktur. Jika dibandin...

Description

Accelerat ing t he world's research.

Indexing and Retrieval Engine untuk Dokumen Berbahasa Indonesia dengan Menggunakan Inverted Index Wahyu Hidayat

Related papers

Download a PDF Pack of t he best relat ed papers 

Klasifikasi Kont en Berit a Digit al Bahasa Indonesia Menggunakan Support Vect or Machines (S… APMMI Asosiasi Profesi Mult imedia Indonesia, Acmad Nurhadi G07mda MIST ER ROCKERS Implement asi Algorit ma Naive Bayes Classifier Berbasis PSO Unt uk Klasifikasi Kont en Berit a Digit al B… Acmad Nurhadi

INDEXING AND RETRIEVAL ENGINE UNTUK DOKUMEN BERBAHASA INDONESIA DENGAN MENGGUNAKAN INVERTED INDEX Wahyu Hidayat1 1

Departemen Teknologi Informasi, Fakultas Ilmu Terapan, Telkom University 1 [email protected]

Abstrak Dokumen teks tergolong dalam data tidak terstruktur. Jika dibandingkan dengan informasi yang tersimpan dalam bentuk yang terstruktur (misalnya pada tabel dalam sebuah database), maka data tidak terstruktur relatif lebih sulit dalam hal pengelolaan, penyimpanan, pencarian ulang maupun pengamanannya. Dalam paper ini dipaparkan sebuah metode indexing dan retrieval yang mampu menyimpan dokumen teks sebagai inverted index yang memiliki berbagai keunggulan penyimpanan data terstruktur. Proses indexing melibatkan beberapa tahap yaitu parsing, stopping, stemming, sorting dan merging. Proses indexing dilakukan terhadap 6464 buah file txt dalam Alquran Terjemahan Indonesia. Setelah itu indeks yang dihasilkan digunakan dalam proses pencarian dokumen yang hasilnya dibandingkan dengan hasil pencarian dokumen konvensional secara full text search. Baik hasil pencarian maupun waktu yang dibutuhkan semuanya dicatat untuk mengukur performa retrieval engine dengan parameter precision, recall dan waktu. Hasil pengujian menunjukkan bahwa proses indexing tidak mengurangi nilai recall, namun menurunkan nilai precision hingga 41,88% demi meningkatkan kecepatan pencarian hingga 3800 kali lipat. Kata kunci : inverted index, indexing and retrieval, precision, recall

1.

Pendahuluan

Informasi yang tersimpan dalam bentuk dokumen dikategorikan sebagai informasi yang tersimpan dalam bentuk yang tidak terstruktur. Jika dibandingkan dengan informasi yang tersimpan dalam bentuk yang terstruktur (misalnya pada tabel dalam sebuah database), maka jenis informasi ini relatif lebih sulit dalam hal pengelolaan, penyimpanan, pencarian uang maupun pengamanannya. Untuk mencari informasi tertentu dari sekumpulan dokumen, biasanya dilakukan dengan mengumpulkan dokumen-dokumen yang mengandung kata kunci tertentu. Sayangnya, bila proses ini dilakukan secara manual akan memerlukan waktu yang cukup lama apalagi jika jumlah dan atau ukuran dokumen cukup besar. Pencarian data secara full text search juga melibatkan proses pembacaan disk secara intensif yang relatif lebih lama dibanding pembacaan pada memory utama (RAM). Hal ini akan memperlambat kinerja sistem. Salah satu solusi yang dapat diterapkan untuk menangani permasalahan tersebut adalah dengan membuat indeks kata dari himpunan dokumen tersebut. Dengan demikian proses pencarian cukup dilakukan terhadap indeks sehingga dapat

menghindari proses pembacaan ke disk yang tidak perlu. Dalam paper ini dipaparkan tentang sebuah indexing and retrieval engine untuk dokumen berbahasa Indonesia. Proses indexing akan melalui serangkaian tahap yang memungkinkan data tidak terstruktur yang ada dalam dokumen disimpan dalam bentuk indeks yang terstruktur dan dapat memiliki kelebihan-kelebihan data terstruktur dalam hal kemudahan pengelolaan, penyimpanan, pencarian uang maupun pengamanan data. Dalam setiap tahapnya dicatat output dan waktu yang dibutuhkan. Dua hal ini dapat menunjukkan performa dari indexing engine dan tahap mana yang membutuhkan waktu yang lebih lama. Informasi ini juga akan dapat berguna bagi penelitian lain dalam domain information retrieval, khususnya bagi penelitian yang memiliki objek penelitan berupa teks berbahasa Indonesia atau bahasa lain yang serumpun. Berbekal informasi tentang performa engine dalam memproses teks berbahasa Indonesia maka penelitian lebih lanjut akan dapat diarahkan untuk menyempurnakan tahaptahap dalam indexing and retrieval engine yang telah diusulkan dalam penelitian ini.

2.

Tinjauan Pustaka

2.1 Indexing dan Retrieval Information retrieval adalah proses mencari materi (biasanya dalam bentuk dokumen) dalam bentuk yang tidak terstruktur (biasanya dalam bentuk teks) dari koleksi yang berukuran sangat besar (yang biasanya tersimpan dalam bentuk elektronik) sesuai dengan informasi yang dibutuhkan. Tidak hanya untuk membantu proses pencarian data dalam bentuk yang tidak terstruktur, information retrieval juga dapat digunakan dalam proses penelusuran dan penyaringan koleksi dokumen untuk diproses lebih lanjut [1]. Dalam domain information retrieval, proses indexing adalah sebuah proses yang sangat penting. Indexing terhadap dokumen dilakukan untuk mengubah dokumen menjadi bentuk yang lebih terstruktur serta memungkinkan proses retrieval, yaitu proses menampilkan dokumen yang mengandung elemen informasi yang dicari. Langkah-langkah dalam proses indexing adalah sebagai berikut [1]: 1. Mengumpulkan dokumen yang akan diindeks kemudian memberikan ID yang unik pada tiap dokumen 2. Tokenizing, yaitu proses memecah dokumen menjadi serangkaian token atau unit-unit yang lebih kecil 3. Normalisasi token secara linguistik, misalnya dengan melakukan stopping (mengabaikan stopwords) dan stemming (ekstraksi kata dasar) 4. Mengindeks dokumen dengan struktur inverted index yang terdiri dari dictionary dan posting. Proses indexing biasanya melibatkan proses sorting dan grouping antara tiap token. Indeks yang dihasilkan merupakan pemetaan antara token dan id dokumen tempat token tersebut ditemukan, biasanya disertai pula dengan frekuensi kemunculan token pada dokumen tersebut. Senada dengan [1], dalam [3] disebutkan bahwa indexing dokumen dengan inverted index dapat dilakukan melalui beberapa tahap berikut: 1. Parsing Dokumen Dokumen dipecah-pecah menjadi kata-kata dan tiap kata disimpan dalam tabel bersama ID dokumen dimana kata tersebut muncul. 2. Sorting Token Tabel diurutkan berdasarkan kata. 3. Merging Token Kata-kata yang sama dan terdapat pada dokumen yang sama digabungkan dalam satu entri. 4. Hitung Frekuensi Pada tahap ini frekuensi kemunculan kata dihitung dan ditambahkan ke dalam tabel

Proses indexing dapat dilakukan secara otomatis maupun secara manual. Indexing secara otomatis (automatic indexing), umumnya meliputi alphabet normalization, stopping dan stemming, seperti yang dijelaskan dalam [5] 1. Alphabet Normalization Dalam proses indexing biasanya karakter alfabet dikonversikan ke dalam uppercase atau lowercase sedangkan karakter-karakter lain dapat dianggap sebagai separator atau diabaikan. Angka dapat diabaikan atau diikutsertakan dalam proses indexing, tergantung pada kebutuhan sistem. 2. Stopping Kata-kata yang sering muncul dan tidak membantu mendeskripsikan dokumen disebut stopwords. Proses stopping atau mengabaikan stopwords akan dapat mengurangi daftar kata yang diindeks. Masing-masing sistem biasanya menentukan sendiri daftar stopwords yang digunakan [5] 3. Stemming Stemming adalah proses mengekstrak stem atau kata dasar dari sebuah kata. Proses stemming dapat memperkecil ukuran indeks sehingga mempercepat proses pencarian. Metode stemming yang umum digunakan adalah stemming dengan berbasis kamus dan aturan morfologi. Daftar kata yang dihasilkan dari proses stoppping dan stemming dapat digunakan untuk mendeskripsikan isi dokumen. Salah satu cara untuk menentukan apakah sebuah kata merupakan indikator yang baik terhadap isi dokumen adalah dengan memperhatikan frekuensi kemunculan kata dalam dokumen [5]. 2.2 Precision dan Recall Untuk mengukur performa sebuah retrieval engine biasanya minimal digunakan 2 parameter yaitu precision dan recall. Keduanya merupakan besaran yang dapat menunjukkan performa dari sebuah retrieval engine. Semakin tinggi nilai keduanya maka semakin baik kinerja retrieval engine tersebut . 2.2.1 Precision Precision adalah salah satu besaran yang umum digunakan untuk mengukur performa sebuah information retrieval engine. Precision tidak sama dengan tingkat akurasi. Precision merupakan persentase relevant document dari seluruh hasil query yang ditampilkan. Semakin tinggi nilai precision, maka semakin besar pula peluang bahwa hasil pencarian yang ditampilkan adalah hasil pencarian yang relevan [2]. (1)

di mana tp = true positive fp = false positive Nilai precision yang tinggi menunjukkan tingginya komposisi true positive pada hasil pencarian. Oleh karena itu, sebuah retrieval engine yang memiliki nilai precision yang tinggi akan semakin jarang salah mengklaim sebuah dokumen sebagai relevan, padahal dokumen tersebut tidak relevan. 2.2.2

Recall

Recall merupakan persentase relevant documents yang berhasil ditampilkan dalam hasil pencarian. Recall biasanya digunakan untuk mengukur sensitivitas sebuah retrieval engine. Semakin tinggi nilai recall, maka semakin besar pula peluang bahwa dokumen yang relevan berhasil ditampilkan dalam hasil pencarian [2]

1.

Parsing Pada proses parsing, dokumen dipecah menjadi token berdasarkan daftar karakter separator yang telah ditentukan oleh user. Semua token yang dihasilkan kemudian dikonversikan ke dalam bentuk lowercase dan dipasangkan dengan identifier dokumen dimana token itu ditemukan.

2.

Stopping Pada proses stopping, token-token yang dihasilkan proses parsing dibandingkan dengan daftar stopwords dan akan diabaikan bila ternyata token tersebut ada di dalam daftar stopwords. Proses ini bertujuan mengabaikan token-token yang tidak perlu di-indeks. Adapun detail dari proses stopping dapat dilihat pada bagan berikut:

Begin

(2) di mana: tp = true positive fn = false negative

Ambil 1 term dari daftar

Nilai recall yang tinggi menunjukkan semakin “sensitif”nya retrieval engine tersebut dalam mendeteksi dokumen yang relevan. Oleh karena itu, sebuah retrieval engine yang memiliki nilai recall yang tinggi akan semakin banyak menemukan dokumen yang relevan. Nilai recall yang tinggi juga menunjukkan bahwa engine tersebut semakin jarang mengklaim bahwa dokumen tersebut adalah tidak relevan padahal sebenarnya dokumen tersebut relevan. 3.

False

Term terdapat dalam kamus ?

True

False

Abaikan

Masukkan ke daftar term penting

Cara Kerja Indexing and Retrieval Engine

Berikut ini adalah gambaran umum dalam proses indexing dan retrieval:

Akhir daftar ?

True Kamus StopWords (*.txt)

Softcopy Dokumen (*.txt)

Kamus KataDasar (*.txt)

End

Parsing

Stopping

Stemming

Sorting & Merging

Gambar 2. Proses Stopping Query Query

User Hasil Query

Inverted Files

Gambar 1. Gambaran Indexing & Retrieval Engine Berdasarkan Gambar 1, urutan langkah kerja pada proses indexing dokumen adalah sebagai berikut:

3.

Stemming Token yang dihasilkan dari proses stopping diekstrak menjadi kata dasarnya. Proses stemming bertujuan untuk mengelompokkan token yang memiliki kata dasar yang sama. Algoritma stemming yang digunakan merupakan algoritma stemming berbasis aturan morfologi. Adapun aturan morfologi yang digunakan adalah sesuai dengan 35 kombinasi imbuhan dalam bahasa Indonesia yang dijelaskan dalam [4]. Detail dari proses stemming dapat dilihat pada bagan berikut:

4.

Gambar diberi judul dengan “Gambar” dan “Tabel” dan diberi nomor, contoh, Gambar 1, gambar 2, tabel 1, tabel 2, dan seterusnya. Judul Gambar ditempatkan dirata tengah bawah gambar. Judul table ditempatkan di rata tengah atas table. Baik gambar dan table ditempatkan di rata tengah antara margin kanan dan kiri halaman. Table/gambar harus ditempatkan pada halaman yang sama dengan judul table/gambar.. 4.

Ambil 1 term dari daftar

Term ada di kamus? True False Lakukan pembuangan imbuhan secara bertahap

False

Uji Performa Indexing and Retrieval Engine

4.1 Parameter dan Skenario Pengujian

Begin

Catat term tersebut sebagai kata dasar

Sorting & Merging

Menemukan stem ?

True False

Ambigu stem?

True

False

Lakukan penanganan ambigu stem

Catat stem yang dihasilkan sebagai kata dasar term

Akhir daftar ?

True

End

Gambar 3. Proses Stemming

Untuk menguji performa indexing and rerieval engine yang dibangun maka dilakukan indexing terhadap 6464 buah dokumen teks (*.txt) berahasa Indonesia dalam Alquran Terjemahan Bahasa Indonesia. Dalam proses indexing ditetapkan bahwa tidak akan mengindex angka dan untuk setiap kata yang diindex minimal memiliki panjang 3 karakter. Adapun stemming yang digunakan adalah stemming berbasis aturan morfologi dalam bahasa indonesia yang dijelaskan dalam [4]. Untuk mengukur performa indexing engine digunakan 2 parameter yaitu 1. Persentase penghematan ukuran index Rasio diperoleh dari membagi jumlah token setelah dilakukan proses stopping dan stemming dengan jumlah token sebelum prosesn stopping dan setemming. Hasilnya dikali dengan 100% sehingga persentase penghematan ukuran index dihitung dalam satuan persen (%) 2. Waktu indexing Waktu yang dibutuhkan untuk setiap proses indexing akan diukur dan dicatat untuk melihat tahap mana yang membutuhkan waktu paling lama Setelah index berhasil dibangun maka sekumpulan kata kunci yang dipilih secara acak akan digunakan sebagai kata kunci untuk pencarian dengan menggunakan retrieval engine dan pencarian dengan menggunakan full text search. Adapun pencaian dengan full text search diwaliki oleh fitur pencarian dokumen pada Microsoft Windows dengan service indexing yang sudah dinonaktifkan. Masing-masing hasil pencarian dan waktu yang dibutuhkan dicatat untuk mengukur performa retrieval engine dengan parameter berikut ini:

1.

2.

3.

Precision Precision diukur dengan membagi jumlah dokumen relevan yang ditemukan dalam hasil pencarian dengan jumlah dokumen hasil pencarian seperti pada persamaan (1). Nilai precision merupakan bilangan bulat dengan antara 0 sampai 1. Semakin tinggi nilai precision, berarti semakin rendah tingkat false positive nya, artinya semakin jarang menemukan dokumen yang tidak relevan dalam hasil pencarian. Recall Recall diukur dengan membagi jumlah dokumen relevan yang ditemukan pada hasil pencarian dengan jumlah seluruh dokumen relevan seperti pada persamaan (2). Nilai recall merupakan bilangan bulat dengan antara 0 sampai 1. Semakin tinggi nilai recall, berarti semakin tinggi tingkat sensitivitas retreival engine tersebut, artinya semakin besar peluang bahwa dokumen relevan berhasil ditemukan dalam hasil pencarian. Waktu Waktu yang dibutuhkan untuk menampilkan hasil pencarian akan diukur untuk membandingkan performa indexing and retrieval engine dengan full text search. Waktu dihitung dalam satuan detik mulai dari kata kunci dimasukan sampai daftar dokumen hasil pencarian ditampilkan.

Dari proses indexing diperoleh hasil bahwa proses stopping mengurangi jumlah token yang akan diindeks sebesar 44,49 % dari jumlah token hasil proses parsing. Proses stemming yang dapat mengurangi jumlah token yang akan diindeks sebesar 33,37% dari jumlah token hasil proses stopping. Dengan demikian, secara keseluruhan proses stopping dan stemming dapat mengurangi ukuran indeks sebesar 55,51%. Detailnya adalah sebagai sebagai berikut: Tabel 1. Hasil Proses Indexing Keterangan

Parsing

227.160 token

Stopping

126.094 token

Stemming

stem dari 126.094 token

Sorting dan Merging

Tabel 2. Catatan Waktu Proses Indexing Waktu yang Proses

94.541 entri indeks

Penulisan

menuliskan 94.541 entri indeks ke

Indeks

disk

dibutuhkan (detik)

Parsing

36

Stopping

22

Stemming

74

Sorting dan Merging

15

Penulisan Indeks

214

Untuk menguji performa retrieval engine digunakan keyword-keyword yang telah diketahui jumlah dokumen relevan nya dan dipilih secara acak: Tabel 3. Contoh Daftar Keyword dan Jumlah Dokumen yang Relevan

Keyword

4.2 Hasil Pengujian

Proses

Terlihat pula bahwa waktu yang paling banyak dibutuhkan adalah saat proses penulisan indeks, yaitu selama 214 detik atau sekitar 59,27% dari total waktu proses indexing. Berikut adalah detail catatan waktu tiap tahapnya:

sekutu mempersekutukan mempersekutukan tuhannya malaikat yang terdekat makan minum ayah zuhur

Jumlah dokumen yang relevan 45 60 4 1 21 30 1

Adapun pada saat melakukan pengujian terhadap retrieval engine diperoleh hasil sebagai berikut:

Tabel 4. Contoh Hasil Pencarian dengan Retrieval Engine

Keyword

sekutu mempersekutukan mempersekutukan tuhannya malaikat yang terdekat makan and minum ayah zuhur

5.

Pencarian dengan inverted index Waktu Hasil pencarian Pencarian (detik) (dokumen) 0,043 130 0,042 130 0,078

305

0,061

220

0,048 0,010 0,001

152 31 1

Terlihat bahwa untuk pecarian dengan inverted index jumlah hasil pencarian melebihi jumlah dokumen yang relevan, hal ini menyebabkan penurunan pada nilai precision hingga 41.88%. Namun demikian, seluruh dokumen yang relevan ditemukan dalam proses pencarian sehingga nilai recallnya tetap !00%. Sebagai pembandingnya, hasil pengujian terhadap pencarian dengan full text search pada Windows menunjukkan bahwa jumlah hasil pencarian sama persis dengan jumlah dokumen yang relevan, selain itu semua dokumen yang relevan ditemukan dalam hasil pencarian. Hal ini menyebabkan pencarian dengan full text search memiliki nilai precision sebesar 100% dan nilai recall sebanyak 100%. Ditinjau dari sisi waktu, pencarian dengan retrieval engine membutuhkan waktu yang jauh lebih sedikit dibanding pencarian konvensional dengan full text search. yaitu sekitar 3800 kali lebih cepat. Berikut adalah detail contoh hasil pencarian full text search: Tabel 5. Contoh Hasil Pencarian Full text search

Keyword

sekutu mempersekutukan mempersekutukan tuhannya Malaikat yang terdekat makan minum ayah zuhur

Pencarian dengan fasilitas search pada Windows Waktu Hasil pencarian Pencarian (detik) (dokumen) 21,13 45 21,09 60 20,51

4

20,43

1

20,36 20,95 22,85

21 30 45

Kesimpulan Dari uraian sebelumnya maka dapat disimpulkan bahwa proses indexing memakan waktu paling lama saat proses penulisan indeks yaitu sekitar 59,27% dari total waktu indexing. Namun demikian, saat dilakukan pencarian, index tersebut dapat mempercepat proses pencarian hingga 3800 kali lipat dibandingkan dengan pencarian konvensional dengan menggunakan full text search. Adapun performa retrieval engine ditinjau dari parameter recall adalah 100%, setara dengan pencarian dengan full text search, Namun demikian, ditinjau dari parameter precision, pencarian dengan retrieval engine mengalami penurunan precision hingga 41,88%. Akhirnya dapat disimpulkan bahwa proses indexing tidak mengurangi nilai recall, namun menurunkan nilai precision hingga 41,88% demi meningkatkan kecepatan pencarian hingga 3800 kali lipat. Daftar Pustaka: [1]

[2] [3]

[4] [5]

Manning, C.D., Raghavan, P., and Schutze, H. 2009, An Introduction to Information Retrieval, Cambridge University Press Olson, David L.; Delen, Dursun, 2008 Advanced Data Mining Techniques,...