IMPLEMENTASI N-GRAM DALAM PENCARIAN TEKS SEBAGAI PENUNJANG APLIKASI PERPUSTAKAAN KITAB BERBAHASA ARAB
Ahmad Najibullah (51016100803)
Latar Belakang (1) • Penerapan Information Retrieval pada teks Berbahasa Arab • Banyak program pendidikan yang menggunakan kitab sebagai literatur utama, antara lain: bidang studi sastra arab, Institut atau Sekolah Tinggi Agama Islam, dan Pondok Pesantren. • Kurangnya aplikasi yang mendukung untuk pencarian informasi dari kitab-kitab tersebut
Tujuan • Membuat aplikasi perpustakaan kitab berbahasa arab dan Mengimplementasikan metode N-gram untuk pencarian teks sebagai penunjang Aplikasi tersebut.
Permasalahan • Bagaimana cara mereduksi term agar proses perbandingan semakin cepat dan tempat penyimpanan term semakin kecil? • Bagaimana menerapkan metode n-gram untuk pencarian pada kitab? • Bagaimana cara mengevaluasi keberhasilan sistem dalam pencarian teks berbahasa arab?
Batasan Masalah • Aplikasi dibangun sebagai aplikasi web dengan menggunakan bahasa pemrograman Java dengan library Google Web Toolkit dan database server MySQL. • Kitab-kitab yang digunakan sebagai data diambil dari website www.shamela.ws. • Daftar kata dasar dan stop word diambil dari Dr. Sheren Khoja.
Rancangan Program
Stemming Stopword Removal - Normalisasi - filtering
Term weighting
Normalisasi & filtering • penghilangan karakter-karakter selain huruf hijaiyah ( ﺕ, ﺏ,) ﺍ • Penghilangan karakter-karakter yang termasuk diacritics (harokat) • Normalisasi teks arab ke bentuk dasar. Misalnya : ﺇ, ﺃmenjadi ﺍ
Stopword Removal • Pembuangan kata-kata yang termasuk dalam stopword bahasa arab
contoh: ِﺍَﻝﻱ ِﻩ,ﻑﻱ ِ ,ِﻡﻥ – ِﻡﻥ: dari – ﻑِﻱ: di dalam – ِﺍﻝَﻱ ِﻩ: kepadanya
Term Weighting • Formula:
N wij tf ij . log 2 df j
• Keterangan: – Wij = bobot term i pada dokumen j – Tfij = frekuensi term i pada dokumen j – N = jumlah dokumen
Stemming • Khoja stemmer dengan tambahan beberapa rule baru
Konsep Khoja Stemmer start
check for prefixes
check definite article
Is two letters?
check prefix waw
check pattern
Is tree letters?
check pattern
Is four letters?
check for suffixes
end
Ilustrasi Khoja Stemmer start
ﺩﺭﺱ
ﻭﺍﻝﻡﺩﺭﺱﺓ
ﻡﺩﺭﺱ
ﻭﺍﻝﻡﺩﺭﺱ
ﺍﻝﻡﺩﺭﺱ
end
Digram (n=2)
Trigram (n=3)
Quadgram (n=4)
Kata
Pembuangan Diacritics
digram
ﺍﻝ
ﻝﺹ َﺓ. ﺹ َّ ﺍَﻝ
الصالﺓ
ﺹﻝ ال ﺍﺓ
Kata
ﺹالَﺓ َّ ﺍَﻝ
Pembuangan Diacritics
ﺍﻝﺹالة
trigram
ﺍﻝﺹ ﻝﺹﻝ صال الة
Kata
Pembuangan Diacritics
quadgram
ﺍﻝﺹﻝ ﺹالَﺓ َّ ﺍَﻝ
ﺍﻝﺹالة
لصال ﺹالة
Penghitungan similaritas • Koefisien Dice :
• Keterangan –S – Aw – Bq – Cwq
: nilai similaritas : jumlah N-gram unik Kamus : jumlah N-gram unik query : jumlah N-gram unik antara kamus dan query
Evaluasi • Conflation Precision (CR) – CP = AV/TV
• Conflation Recall (CP) – CR = AV/TAV
• Keterangan: – TAV = jumlah term yang relevant pada corpus – AV = jumlah term hasil query yang relevant – TV = jumlah total term hasil query
Skenario Uji Coba • Uji coba dan Evaluasi Stemming • Uji coba dan Evaluasi N-gram Matching untuk menentukan kombinasi dari varian digram, threshold dan penggunaan stemming. • Menerapkan hasil yang ditemukan pada skenario sebelumnya pada pencarian dokumen
Skenario I • Perbaikan Stemming Tipe perbaikan
input
Awalan “ ”ﺍﻝdan akhiran “”ﺍﺕ
َﺍَﻝ َﻡﻙ ﺏﺍﺕ َﺕ
Huruf awal seperti “khofadz”, huruf kedua “”ﻝ, dan bersifat jama’ Awalan “ ”ﺍﻝdan huruf tengah “”ﺍ Huruf tengah “”ﺍ Awalan “ ”ﺱdan “ ”ﻱserta huruf tengah “”ﺍ
output Sebelum sesudah
ﻙﺏﻱ
ﻙﺕﺏ
ﺏﺍﻝِﻍﻭ َﻥ َ
ﻍﻱﻥ
ﺏﻝﻍ
ﺏﺍﺏ َﺍَﻝ ﻱ َﺥﺍﻑ َ
ﻝﺏﺏ ﺥﻭﻑ
ﺏﺍﺏ ﺥﺍﻑ
ﻱﻙﻭﻥ َﺱ َ
ﺱﺍﻙ
ﻱﻙﻭﻥ
(stopword)
Hasil Uji Coba th > 0.4 CR CP
th > 0.5 CR CP
th > 0.6 CR CP
th > 0.7 CR CP
1.00
0.76
1.00
1.00
1.00
1.00
1.00
1.00
2
ﺍﻝﺏﺍﺉﻉ1.00
0.88
1.00
1.00
1.00
1.00
1.00
1.00
3
ﻑﻕﺍﻝ1.00
0.79
1.00
1.00
1.00
1.00
1.00
1.00
4
ﺍﻝﻡﺕﻉﺍﻕﺩﻱﻥ1.00
0.58
1.00
1.00
1.00
1.00
1.00
1.00
5
ﻱﺝﺍﺏ1.00
0.50
1.00
0.63
1.00
1.00
1.00
1.00
6
ﺏﺍﻝﻥﻉﻡﺍﺕ1.00
0.80
1.00
1.00
1.00
1.00
1.00
1.00
7
ﺍﻝﻥﻙﺍﺡ0.67
0.67
0.67
1.00
0.67
1.00
0.67
1.00
8
ﺍﻝﻅ ﺍﻩﺭ1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
9
ﺍﺹﺡﺍﺏﻩ ﻭ0.75
0.38
0.75
1.00
0.75
1.00
0.75
1.00
10
ﻭلالﻡﺍﻡ1.00
0.60
1.00
1.00
1.00
1.00
1.00
1.00
0.94
0.70
0.94
0.96
0.94
1.00
0.94
1.00
no
word 1
ﺍﺡﺕﻡﺍﻝﻱﻥ
rata-rata
• Nilai F-measure terbaik : 0.97
Hasil Uji Coba 1,2
1
Nilai kinerja
0,8
0,6
0,4
0,2
0
0,4
0,5
0,6 Threshold similarita
0,7 CR CP
Kesimpulan • Algoritma n-gram dapat diimplementasikan untuk penghitungan string matching. • Semakin tinggi nilai threshold yang ditentukan, maka nilai Conflation Precision semakin tinggi, tetapi nilai Conflation Recall semakin rendah. • Dari vairan n-gram yang digunakan pada tugas akhir ini, performa yang paling baik adalah digram, threshold 0.6 dengan proses stemming dengan nilai Conflation Precision 1.00 dan conflation recall 0.94. • Algoritma khoja stemmer berhasil diimplementasikan dengan beberapa tambahan rule baru dan mampu mereduksi hingga 27.5% jumlah terms dari total keseluruhan terms pada data uji coba dan lebih presisi. • Penggunaan stemmer dapat dapat mengurangi proses pembandingan string dalam penghitungan similaritas string. Juga dapat memperkecil term yang harus disimpan dalam database.
Daftar Pustaka • Mustafa, S.H., 2004, "Character Contiguity in Ngram-based Word Matching: the Case for Arabic Text Searching". Department of Computer Information System Faculty of Information Technology Yarmouk University Jordan. • Mustafa, S.H. & Alradaideh, Q. A., (in press), 2004, "Using N-gram for Arabic Text Searching", Journal of the American Society for Information Science & Technology (JASIST) • Khoja, S., 2001, “APT: Arabic part of speech tagger,” Proc. of the Student Workshop at NAACL.
Terimakasih……
