Terjemahan bahasa Indonesia di Lafzi

Alhamdulillah di Lafzi telah ditambahkan terjemahan bahasa Indonesia di setiap ayat hasil pencarian. Berikut penampakannya:

Terjemahan adalah terjemahan versi Depag RI yang diambil dari tanzil.net/trans. Selain terjemahan, ditambahkan juga fasilitas untuk menyalin teks Al-Quran dan untuk membuka ayat yang dimaksud di Al-Quran online milik KSU (quran.ksu.edu.sa). Tampilan huruf (font) Arab yang digunakan juga diganti dengan yang lebih bagus (menurut saya).

Dengan tambahan ini dan perbaikan algoritme seperti posting sebelumnya, maka Lafzi yang sekarang bisa dianggap sebagai versi 2.

Perbaikan algoritme Lafzi

Setelah hampir 2 tahun ditinggalkan, akhirnya sempat juga mengutak-atik kembali Lafzi. Kali ini dilakukan perbaikan terhadap algoritme untuk pemberian skor dan metode sorotan pada hasil pencarian. Tujuannya yaitu untuk memperbaiki hasil pencarian. Perhatikan gambar berikut, yakni Lafzi yang menggunakan algoritme lama untuk mencari lafal “wal yatalattof” (kata pada pertengahan Al-Quran).

Terlihat hasil yang “menyebar” tidak teratur, bahkan lafal yang dicari pun tidak ditemukan. Bandingkan dengan Lafzi yang menggunakan algoritme baru pada gambar berikut.

Tepat sasaran, alhamdulillah :)

Algoritme baru yang dimaksud yaitu perubahan cara menghitung skor keterurutan, yang tadinya menggunakan metode longest-increasing subsequence menjadi metode longest-contiguous subsequence. Metode yang baru ini sebenarnya lebih simpel, sayangnya tidak dari dulu kepikirannya. Metode ini juga mendukung fungsi sorotan hasil pencarian yang lebih terkelompok.

Selain itu, skor kemunculan yang tadinya hanya menggunakan posisi kemunculan pertama query pada dokumen, sekarang seluruh posisi kemunculan juga diperhitungkan. Ini juga ada kaitannya dengan penggunaan metode longest-contiguous subsequence.

Demikian sedikit laporan perbaikan untuk kali ini. Silakan cek Lafzi pada alamatnya: http://apps.cs.ipb.ac.id/lafzi.

Antarmuka pengguna

Alhamdulillah, sudah dibuat antarmuka pengguna (halaman utama). Sederhana saja, yang penting tidak terlalu polos :)

Aplikasi ini diberi nama “Lafzi” yang artinya fonetis dalam bahasa Arab. Semoga benar-benar bisa di-publish di web agar bisa dimanfaatkan.

Highlight hasil pencarian

Salah satu hal yang membantu pengguna dalam suatu mesin pencari adalah highlight atau penandaan hasil pencarian. Penandaan ini maksudnya menandai bagian mana dari dokumen yang dicari yang cocok dengan query yang dimasukkan, bisa dengan memberi bold pada kata-kata yang cocok (seperti pada Google) atau memberi warna berbeda pada kata-kata yang cocok.

Contohnya seperti berikut (pada Google dengan kata kunci “search term highlighting”) :

Nah, pada pekerjaan penelitian saya, perlu juga dilakukan semacam ini agar pengguna lebih mudah menemukan kata mana dari sebuah dokumen yang dianggap cocok oleh sistem.

Namun ternyata tidak mudah. Karena pencarian yang dilakukan adalah pencarian approximate atau tidak tepat sama, maka penandaan yang dilakukan pun juga tidak bisa pas. Sebenarnya ada data tentang posisi kemunculan query pada dokumen, namun posisi tersebut adalah posisi pada kode fonetik (teks Latin atau transliterasinya). Padahal yang akan ditampilkan adalah teks Arab atau teks Al-Quran asli. Maka harus dikira-kira bagian mana yang cocok dengan bermodal informasi posisi kemunculan term.

Karena itu, tidak bisa langsung “membungkus” kata yang dianggap cocok untuk di-bold misalnya. Maka dalam implementasinya di HTML saya menggunakan 2 lapisan. Lapisan pertama adalah teks Quran itu sendiri, sedangkan lapisan kedua berada di belakangnya yaitu beberapa elemen <DIV> berwarna pada posisi kemunculan term tertentu. Elemen-elemen <DIV> inilah yang menyusun efek “sorotan” atau highlight pada posisi tertentu, dengan lebar yang disesuaikan agar pas dengan teks di depannya.

Seperti ini hasilnya (dengan kata kunci “alhamdulillah”) :

Terlihat bahwa “sorotan” tidak tepat pada kata yang dituju karena memang hanya perkiraan tempat kemunculan. Ada yang “sorotan” terlalu panjang, ada yang tergeser ke depan, ada yang tergeser ke belakang, tapi alhamdulillah ada juga yang pas :)

Meskipun tidak sempurna, paling tidak sedikit membantu pengguna untuk mengetahui bagian mana dari ayat yang cocok dengan yang dicari. Sekian.

Ranking keterurutan term

Kembali menulis tentang penelitian…

Jadi pada posting-posting sebelumnya saya mengurutkan hasil pencarian (ranking) hanya dengan menghitung jumlah term (dalam hal ini trigram) yang sama antara dokumen dengan query. Semakin banyak yang sama, maka semakin tinggi rank-nya.

Namun cara seperti demikian ternyata mengandung kekurangan, yaitu trigram yang cocok pada dokumen ditemukan dalam posisi yang acak-acakan (urutannya tidak sama dengan pada query). Misalnya seperti ini (posisi trigram yang ditemukan pada dokumen) :

23, 24, 2, 3, 4, 56, 59
67, 23, 25, 5, 32, 33, 56

Terlihat bahwa trigram muncul pada posisi yang kacau, artinya sebenarnya bukan itu dokumen yang hendak dicari. Oleh karena itu, coba dicari bagaimana memberi ranking pada dokumen yang ditemukan agar yang urutannya bagus mendapat ranking yang tinggi.

Didapatkan teknik yang sesuai, yaitu mencari LIS atau longest increasing subsequence. Artinya dicari subsekuens terurut yang terpanjang dari sebuah barisan. Misalnya untuk contoh di atas:

23, 24, 2, 3, 4, 56, 59     => 2, 3, 4, 56, 59
67, 23, 25, 5, 32, 33, 56   => 23, 25, 32, 33, 56

Dengan cara ini, ranking pada suatu dokumen adalah panjang LIS dari posisi kemunculan trigram. Semakin panjang LIS-nya (yang juga artinya semakin banyak trigram yang cocok) maka ranking-nya semakin tinggi. Alhamdulillah dengan cara ini hasil pencarian menjadi lebih baik dari sebelumnya.

Menggunakan file teks untuk penyimpanan indeks

Pada posting sebelumnya, saya menggunakan database relasional untuk menyimpan inverted index. Namun atas arahan supervisor, saya akhirnya menggunakan file teks saja (flat file).

Salah satu alasannya karena ternyata database relasional yang digunakan tidak dimanfaatkan fitur “relasional”-nya alias hanya difungsikan sebagai penyimpanan record saja, selain itu juga karena data bersifat statis tanpa ada perubahan. Maka lebih baik jika bisa menggunakan database nonrelasional (jenis NoSQL) agar lebih efisien. Namun karena tidak ada sistem NoSQL yang simpel untuk data saya yang terbilang kecil, maka saya putuskan menggunakan file teks saja untuk menyimpan datanya.

Sebenarnya konsepnya sama, yang berbeda hanya saat menulis indeks. Kalau yang menggunakan database kita menulis ke tabel, maka dengan file teks kita menulis daftar term dan posting list ke file teks.

Index:

term1|1,5,7,10,15
term2|6,9,10,15
term3|3,4
...

Namun kalau hanya menulis ke file teks saja tanpa teknik tertentu, maka akan cukup repot saat proses pencarian atau pemrosesan query nantinya. Kalau dengan database mudah, karena kita cukup menggunakan perintah SELECT ... WHERE term = 'AAA'. Namun bagaimana kalau data kita ternyata ada di file teks?

Ada satu teknik yang disarankan, yaitu memecah antara daftar term dan posting list. Jadi file indeks kita terdiri dari 2 file, yaitu daftar term dan posting list.

Terms:

term1|0
term2|12
term3|22
...

Posting:

1,5,7,10,15
6,9,10,15
3,4
...

Kenapa perlu dipisahkan? Karena daftar posting bisa sangat besar ukurannya, dan kita tidak perlu me-load file besar itu seluruhnya. Sebaliknya, daftar term biasanya ukurannya tidak terlalu besar, jadi kalaupun kita load seluruhnya ke memori tidak menjadi masalah. Daftar term hendaknya terurut, agar saat kita mencari term tertentu bisa kita efisienkan, misalnya dengan binary search. Kalau saya sendiri menggunakan hash table karena term-nya tidak terlalu banyak.

Nah, angka di sebelah term adalah offset. Misalkan term2 offset-nya 12, artinya term2 memiliki daftar posting pada file posting list mulai byte ke-12 sampai akhir baris. Jadi kita cukup membaca byte ke-12 sampai akhir baris saja tanpa harus membaca seluruh file posting list.

Implementasi saya dengan PHP bisa menggunakan fungsi fseek untuk membaca file langsung pada byte sekian.

Dengan mekanisme pemisahan seperti ini, pencarian daftar posting yang sesuai untuk term tertentu dapat dilakukan dengan cepat. Dengan binary search dapat dilakukan pada O(log n), sedangkan dengan hash table pada O(1).

Dan sebenarnya, kita sedang membuat DBMS kita sendiri, karena cara membaca terindeks seperti ini juga digunakan oleh DBMS untuk mencari record dengan cepat :)

Pemrosesan query dengan inverted index

Melanjutkan posting sebelumnya, posting ini membahas cara pemrosesan query dengan inverted index yang telah terbentuk. Misalkan indeks kita seperti berikut (frekuensi term diabaikan untuk penyederhanaan) :

Dan misalkan query yang dimasukkan adalah “baseball summer”. Maka query perlu dipecah menjadi term. Dengan demikian kita memiliki 2 buah term, yaitu “baseball” dan “summer”.

Untuk setiap term ini, cari pada indeks. Karena menggunakan database, maka cukup dengan query untuk SELECT posting list dengan term tertentu untuk mendapatkan posting list yang sesuai. Dihasilkan daftar posting seperti berikut :

• “baseball” → (1)
• “summer” → (1, 2, 4)

Kedua posting list itu digabungkan, maka terbentuk array :

(1, 2, 4, 1)

Kemudian array tersebut diurutkan :

(1, 1, 2, 4)

Kemudian dihitung frekuensi masing-masing elemen array dan diurutkan berdasarkan frekuensinya, dihasilkan :

doc_id  |   freq
     1  |      2
     2  |      1
     4  |      1

Dengan demikian dapat dilihat hasil pencarian dengan query yang diberikan adalah (terurut ranking-nya) :

• Doc 1
• Doc 2
• Doc 4

 

Membangun inverted index dengan database relasional

Dalam program untuk melakukan pencarian, salah satu metode agar pencarian bisa dilakukan dengan efisien adalah dengan melakukan pengindeksan (indexing). Dengan mengindeks dokumen yang akan dicari, maka pencarian dokumen dengan query tertentu tidak perlu dilakukan secara sekuensial atau diperiksa satu-persatu.

Inverted index adalah indeks yang terbentuk dari proses pengindeksan. Secara umum strukturnya sebagai berikut:

Dapat dilihat tabel sebelah kiri adalah “dokumen” atau teks yang akan diindeks. Sedangkan sebelah kanan adalah hasil pengindeksan. Jadi term (sederhananya: kata) yang ada pada dokumen menunjuk ke ID dokumen yang mengandung term tersebut.

Secara intuitif, indeks seperti ini mirip dengan indeks pada buku. Pada buku yang cukup tebal sering dijumpai halaman “Indeks” yang cara kerjanya sama dengan inverted index seperti ini. Lebih lengkap mengenai inverted index silakan baca buku Introduction to Information Retrieval.

Untuk membangun indeks seperti ini dengan database relasional (misalnya MySQL), perlu dibuat tabel yang merepresentasikan struktur indeks ini. Pada posting sebelumnya saya membuat struktur tabel indeks, namun rasanya itu kurang efisien, sehingga struktur tabel indeks harus diubah. Tabel “index” yang lama hanya menjadi tabel sementara dalam proses pengindeksan. Sedangkan tabel indeks yang sebenarnya diubah menjadi berikut, beserta contoh isinya:

Jadi daftar dokumen yang mengandung term tertentu disimpan sebagai string dalam kolom posting_list, begitu pula frekuensi term pada dokumen (freq_list).

Untuk membentuk indeks seperti itu dalam database, saya membaginya menjadi dua fase sebagai berikut:

Fase I (pembangunan indeks sementara)

1. Baca seluruh teks dari dokumen
2. Untuk setiap dokumen yang dibaca:
   1. Lakukan tokenisasi atau ekstraksi term dari teks dokumen
   2. Hitung frekuensi setiap term dalam dokumen
   3. Untuk setiap term yang didapat, masukkan ke tabel indeks sementara (term, ID dokumen, frekuensi term)
3. Selesai, indeks sementara terbentuk

Fase II (pembangunan indeks)

1. Baca seluruh term unik dari tabel indeks sementara
2. Untuk setiap term:
   1. Baca daftar ID dokumen yang mengandung term tersebut (dari tabel indeks sementara)
   2. Selain ID, baca frekuensi term dalam dokumen dan jumlah dokumen yang mengandung term
   3. Gabungkan daftar ID dokumen dengan koma, inilah posting_list
   4. Gabungkan daftar frekuensi term dengan koma, inilah freq_list
   5. Masukkan dalam tabel indeks yang sesungguhnya (term, jumlah dokumen, ID dokumen, frekuensi term)
3. Selesai, indeks terbentuk
4. Hapus tabel indeks sementara

Dengan langkah-langkah di atas, maka akan terbentuk inverted index seperti ilustrasi yang dibuat. Implementasi saya dengan PHP dan term berupa trigram dapat dilihat pada repositori kode.

Mengenai cara pencarian dengan struktur indeks seperti ini, Insya Allah akan dibahas kemudian.

Pembuatan database

Update pekerjaan skripsi. Telah dibuat skema database untuk keperluan sistem. Skema relasi tabel yang dibuat sebagai berikut:

Sederhana, hanya untuk menyimpan informasi tentang dokumen dan untuk indeks nantinya. Skema ini diimplementasikan pada DBMS MySQL.

Sejauh ini yang sudah dilakukan adalah mengisi tabel surah dan sebagian tabel doc. Tabel doc baru diisi pada field id, surat, ayat, dan teks, sedangkan kode fonetiknya belum diisikan karena prosedur pengodeannya belum diimplementasikan. Sedangkan tabel index dan trigram akan diisi pada saat proses pengindeksan nantinya.

 

Pengodean fonetik dari teks Al-Quran

Salah satu bagian penting dalam penelitian untuk skripsi, yaitu mengodekan teks Al-Quran (teks bahasa Arab) ke dalam kode fonetik tertentu. Untuk itu saya merancang prosedur pengodeannya berdasarkan:

• Cara membaca Al-Quran (tajwid)
• Kesalahan umum cara pelafalan Al-Quran

Berikut langkah-langkahnya yang harus dilakukan secara berurutan.

1. Penghilangan seluruh spasi

Seluruh spasi dihilangkan karena tidak berpengaruh terhadap pelafalan.

2. Penghilangan seluruh tanda tasydid

Aturan:

• ــَّـ diganti ــَـ (begitu pula fathatain)
• ــِّـ diganti ــِـ (begitu pula kasratain)
• ــُّـ diganti ــُـ (begitu pula dhammatain)

3. Penggabungan huruf mati

Huruf mati bertemu dengan huruf yang sama, maka huruf mati dihapus (idgham mutamatsilain).

4. Perubahan pada akhir ayat

Untuk huruf yang berada pada akhir ayat, diterapkan aturan:

• ة diganti menjadi ه
• Seluruh tanwin diganti dengan harakat tunggal

5. Substitusi tanwin

Seluruh tanwin (fathatain, kasratain, dhammatain) diganti dengan nun mati untuk penyeragaman.

Aturan:

• ــًـ diganti menjadi ــَـنْ
• ــٍـ diganti menjadi ــِـنْ
• ــٌـ diganti menjadi ــُـنْ

6. Pemendekan vokal panjang

Seluruh vokal panjang (mad) diganti dengan vokal pendek. Khusus bilaا ي و tidak bertanda.

Aturan:

• ــَـا atau ــَـى diganti dengan ــَـ
• ــِـي diganti dengan ــِـ
• ــُـو diganti dengan ــُـ
• آ diganti denganأَ

7. Penghilangan huruf-huruf yang tidak dibaca

Huruf-huruf yang tidak dibaca dihilangkan:

• Alif tanpa harakat
• Lam tanpa harakat (pada alif-lam syamsiyyah)
• Alif maqsura (ى)
• Huruf-huruf lain tanpa harakat

8. Substitusi huruf iqlab

Aturan:

• نْب diganti dengan مْب

9. Peleburan huruf idgham

Aturan:

• نْي diganti dengan ي kecuali pada kata دُنْيَ dan بُنْيَن
• نْن diganti dengan ن
• نْم diganti dengan م
• نْو diganti dengan و kecuali pada kata صِنْوَن dan قِنْوَن
• نْل diganti dengan ل
• نْر diganti dengan ر

10. Penghilangan seluruh tanda vokal

11. Substitusi fonetik

Seluruh huruf dan huruf-huruf yang serupa pelafalannya disubstitusi dengan kode tertentu.

Huruf	Kode
ز ج	Z
ح خ ه	H
ع ء ؤ ئ ا أ إ	X
س ش ث ص	S
د ذ ض ظ	D
ت ط ة	T
ك ق	K
غ	G
ف	F
م	M
ن	N
ل	L
ب	B
ي	Y
و	W
ر	R

Dengan prosedur di atas, misalkan untuk ayat Al-Quran berikut (Surah Al-Qadr ayat 4) :

تَنَزَّلُ الْمَلَائِكَةُ وَالرُّوحُ فِيهَا بِإِذْنِ رَبِّهِم مِّن كُلِّ أَمْرٍ

Maka akan diubah menjadi kode berikut :

TNZLLMLXKTWRHFHBXDNRBHMNKLXMR

Namun prosedur ini masih memiliki kekurangan, di antaranya karena tidak memperhitungkan tanda waqaf sehingga beberapa hukum bacaan saat waqaf tidak dapat ditangani. Kelemahan lain adalah tidak semua hukum tajwid tingkat lanjut dapat ditangani, di antaranya idgham mutaqarribain, dan idgham mutajanisain.

Dengan demikian, langkah selanjutnya adalah implementasi prosedur ini dalam bahasa pemrograman. Semoga dimudahkan. Bila ada masukan silakan mengisikan pada kolom komentar.