Algoritma Stemming Bahasa Indonesia Perl

Algoritma Stemmer Bahasa Indonesia

Program pencari kata dasar (stemmer) dalam Bahasa Indonesia, dibuat dengan bahasa pemrograman Perl. Program ini bekerja menggunakan kamus kata dasar, menurut pola kata berimbuhan sesuai pedoman Ejaan Yang Disempurnakan (EYD). Semoga bermanfaat.

1. Pendahuluan

Struktur pembentukan kata dalam Bahasa Indonesia adalah sebagai berikut:

[awalan-1] + [awalan-2] + dasar + [akhiran] + [kepunyaan] + [sandang]

Masing-masing bagian tersebut (yang dalam kotak bisa ada atau tidak), digabungkan dengan kata dasar membentuk kata berimbuhan. Di bawah ini imbuhan yang banyak digunakan dalam Bahasa Indonesia :

1. Kata sandang: -lah, -kah, -pun, -tah.
2. Kata kepunyaan: -ku, -mu, -nya.
3. Akhiran: -i, -an, -kan.
4. Awalan: me-, ber-, pe-, di-, ke-, ter-, se-.

Dalam proses penggabungan awalan, terdapat aturan-aturan berikut:

Awalan	Perubahan Bentuk	Aturan
me | pe	meng | peng	+ V | k | g | h | q … Misal: mengambil = meng + ambil V = Vokal (a, i, u, e, o)
	meny | peny	+ s … Misal: penyakit = peny + sakit
	mem | pem	+ b | f | p | v … Misal: membuat = mem + buat
	men | pen	+ c | d | j | s | z … Misal: mencari = men + cari
	me | pe	+ m | n | r | l | y | w | x | + V … Misal: melukis = me + lukis
ber | per | ter	be | pe | te	+ r + V … Untuk mencari r yang luluh dengan mencoba kombinasi ‘r + V …’ atau ‘V …’. Misal: peramal = pe + ramal
	ber | per | ter	+ K | V …, Misal: terambil = ter + ambil K = Konsonan (selain Vokal)

Dalam pasangan awalan dan akhiran, terdapat pasangan yang tidak diperbolehkan, yaitu:

Awalan	Akhiran Tidak Sah
ber- | ke- | se- | per-	-i, Misal: ber-tanyai-i
di- | me- | ter-	-an, Misal: di-tinggal-an
ke- | se- | pe-	-kan, Misal: pen-dapat-kan

Dalam program stemmer, aturan susunan awalan dan akhiran mengesampingkan pengecualian yang jarang. Misalnya untuk kata ajar, yang digabung dengan per- menjadi pelajar. Juga seperti pasangan ke- -i untuk ke-tahu-i, ini akan dianggap tidak sah.

Terdapat 4 subrutin inti dalam proses mencari kata dasar, yaitu:

Subrutin	Fungsi	Input	Output
BuangLuluh	Melakukan penyesuaian kata yang luluh terhadap awalan me- dan pe-.	kata	kata (bila ada di kamus) atau undef (bila tidak ada)
BuangBelakang	Membuang akhiran kata, yaitu: -lah, -kah, -pun, -tah, -ku, -mu, -nya, -i, -an, -kan.	kata, awalan1, awalan2	kata | undef
BuangDepan	Membuang awalan kata, yaitu: me-, ber-, pe-, di-, ke-, ter-, se-.	kata	kata | undef, awalan
BuangImbuhan	Membuang imbuhan kata, merupakan subrutin induk dari proses pemotongan kata.	kata	kata | undef

Dalam subrutin BuangImbuhan terdapat proses pembuangan awalan (AW), akhiran (AK), kata kepunyaan (KK), kata sandang (KS) dan kata dasar (D) seperti di bawah. Pada tiap tahap pembuangan dilakukan pengecekan ke kamus untuk mengakhiri pemotongan.

Tahap	Kombinasi	Imbuhan	Contoh
1.	D	-	ikat
2.	D + AK	-an	ikat-an
3.	AW + D	me-	meng-ikat
4.	AW + D + AK	me- + -kan	meng-ikat-kan
5.	AW + AW + D	me- + per-	mem-per-ikat
6.	AW + AW + D + AK	ke- + ter- + -an	ke-ter-ikat-an

Contoh pencarian kata dasar untuk kata ‘kebersamaannyalah’ ada di bawah ini. Kata asal akan berubah bentuk (dicetak tebal bila berbeda dari sebelumnya) pada proses Buang Depan yang selanjutnya diperiksa hasil potongnya pada Buang Belakang.

Tahap	Proses	Kata Asal	Hasil Potong	Kata Akhir
1.	Cek Kamus	kebersamaan nyalah	-	kebersamaan nyalah
2.	Buang Belakang	kebersamaan nyalah	kebersama	kebersamaan nyalah
3.	Buang Depan	kebersamaan nyalah	bersamaan nyalah	bersamaan nyalah
4.	Buang Belakang	bersamaan nyalah	bersama	bersamaan nyalah
5.	Buang Depan	bersamaan nyalah	samaan nyalah	samaan nyalah
6.	Buang Belakang	samaan nyalah	sama	sama

2. Hasil Program

Program membuka file berikut (pada direktori yang aktif):

1. kamus.txt, yaitu berisi daftar kata dalam Bahasa Indonesia. Kamus ini sebagai dasar untuk menentukan apakah suatu kata telah ditemukan kata dasarnya.
2. indonesian.stp, yaitu berisi daftar kata yang akan diabaikan (stopwords) dalam pencarian kata dasar. Kata yang akan diabaikan baik dalam bentuk berimbuhan maupun setelah didapat kata dasarnya.
3. Koleksi.dat, yaitu file korpus sebagai obyek proses stemming. Definisi kata adalah alfabet (a-z) dan pemisah kata adalah selain alfabet, angka, dan garis bawah (_). Pemisah ini sesuai definisi word boundary dari Perl (\b). Kata majemuk, seperti buku-buku, dianggap 2 kata yaitu buku dan buku.
4. hasil.txt, yaitu file yang akan menampung hasil dari proses stemming. File ini akan selalu dibuat baru setiap kali program dijalankan.

Contoh hasil keluaran program berbentuk seperti di bawah. Bentuk ini disesuaikan dari format Tugas 2, karena hasil stemmer adalah (dianggap) kata dasar dan status benar atau salah tidak diketahui. Status di sini adalah urutan kata tersebut bila tidak ditemukan di kamus. Kata yang dihasilkan tidak diurutkan sesuai alfabet sehingga acak sesuai posisi kata tersebut di hashes.

No.	Kata Asal	Hasil Stemmer	Status
1	menkop	menkop	1
2	mengeruhkan	keruh	-
675	penyakit	sakit	-
2802	makan	makan	-
11188	royong	royong	4185
11189	digembok	gembok	-

Pada baris akhir dari hasil program akan ditampilkan statistik keseluruhan, yaitu: “Total kata: 11515, Berhasil: 7374 (64.04%), Gagal: 4141 (35.96%)”. Total kata merupakan jumlah seluruh kata yang ditemukan dalam dokumen dikurangi stopwords. Jumlah Berhasil adalah jumlah kata bila ditemukan dalam kamus, sedangkan jumlah Gagal bila kata tidak ditemukan di kamus. Berhasil atau Gagal ini belum menunjukkan hasil yang sesungguhnya, perlu dianalisa secara manual untuk menentukan benar atau salah.

Sebagai informasi tambahan ditampilkan pula statistik unjuk kerja program (menggunakan module Benchmark). Pada prosesor AMD Sempron 1,8GHz, memory 512MB, Perl v5.6.1 MSWin32, dibagi menurut 3 bagian:

1. Membaca semua file dan mengolah Koleksi.dat hingga didapat daftar kata yang unik. Tahap ini menghabiskan waktu 0,437 detik (59,46%).
2. Melakukan stemming seluruh kata. Tahap ini berlangsung 0,172 detik (23,40%).
3. Menulis hasil ke file hasil.txt. Tahap ini selama 0,126 detik (17,14%).

3. Analisa Kesalahan

Untuk mengetahui ketepatan hasil stemming perlu dilakukan analisa secara manual. Mengingat jumlah kata yang cukup besar (11515 kata), pengamatan mencakup sebagian saja, yaitu masing-masing 1000 kata teratas dari Berhasil dan Gagal. Hasil analisa dari kata dasar yang salah seperti tabel di bawah ini. Hasil stemmer dianggap salah dengan aturan berikut:

1. Terjadi pengubahan kata tetapi kata tersebut dianggap tidak tepat, misal: mengakui (aku, bukan kaku).
2. Tidak terjadi pengubahan kata meskipun kata dasarnya ada dalam kamus, misal: mengetahui (tahu).
3. Imbuhan tidak berhasil dipisahkan, meskipun kata tersebut sah sebagai Bahasa Indonesia, misal: rinciannya (rinci), diujicobakan (ujicoba).

Kata-kata yang asalnya sudah salah, seperti pernggantian (harusnya pergantian), penjelaskan (harusnya penjelasan) atau tidak terdapat di kamus, bila tidak didapat kata dasarnya maka dianggap hasil stemming adalah benar.

Jenis Kesalahan	Contoh	Hasil Stemmer	Seharusnya	Byk
Nama orang, tempat, istilah, singkatan	ryamizard, denpasar, puskesmas didubeskan	-tetap-	-sudah benar-	-
Bahasa asing	conduct, trial, pressure	-tetap-	-sudah benar-	-
Kesalahan kata, susunan imbuhan, imbuhan kata asing	pernggantian, meingkatkan, maasalah, penjelaskan, berkapitalisasi, ngejar	-tetap-	ganti, tingkat, masalah, jelas, kapital, kejar	-
Kata majemuk	ketidakhadirannya, diperjualbelikan, diujicobakan	-tetap-	tidakhadir, jualbeli, jualbeli	14
Aturan khusus	mengetahui, belajar, perbaiki	-tetap-	tahu, ajar, baik	3
Kesalahan peluluhan kata	memintainya, pengakuannya, mengamati mengukur	minta, kaku, kamat, kukur	pinta, aku, amat, ukur	4
Kesalahan kata yang kata dasarnya ada di kamus	memada, alan, domi, terlah	pada, al, dom, ter	-tidak tahu-	-
Kata dikenali sebagai bahasa Indonesia tapi tidak ada di kamus / tidak baku	rinciannya, milyaran, perijinan, resikonya, mengendor	-tetap-	rinci, milyar, ijin, risiko, kendur	5
Kata terlalu banyak dipotong (overstemming)	menahannya	nah	tahan	1
Kata terlalu sedikit dipotong (understemming)	menempati	empati	tempat	1

Secara statistik, dari 2000 kata tersebut terdapat 28 kata yang mengalami kesalahan pencarian kata dasar, sehingga tingkat keberhasilannya adalah 98,6 % (dengan asumsi semua kata yang ada di kamus adalah benar).

4. Kesimpulan dan Saran

Mengingat keterbatasan tenaga dan waktu, program ini dapat disempurnakan lebih lanjut. Pengambilan 2000 kata acak dari hasil stemming belum mencukupi untuk menilai ketepatan program secara keseluruhan.

Beberapa kesimpulan terkait hasil eksekusi program:

• Banyak kegagalan mencari kata dasar terjadi akibat kesalahan pengetikan atau pemakaian kata yang tidak baku. Misalnya: penyelesaiaan, musyarwarah, kangguru, baikdari, memimipin, duren, milyar.
• Banyak kegagalan akibat istilah-istilah, singkatan, kata-kata asing / daerah / pergaulan, dan nama orang / tempat / sesuatu. Misalnya: double, menkopolkam, samsung, nggak, dekrit, tampubolon, syamsuddin, shalawat, hongkong, klaten.
• Banyak kegagalan akibat kata majemuk. Misalnya: diserahterimakan, ketidakhadirannya, penandatanganannya, diperjualbelikan, ketidakpuasan.
• Banyak kegagalan akibat penggunaan imbuhan dalam bahasa asing. Misal: brutalisme, meminimalisasi, eksportir, nirlaba, berkapitalisasi, premanisme.

Beberapa hal yang dapat diperbaiki:

• Mencakup kata-kata yang perlu diperlakukan khusus, seperti: ber + ajar = belajar. Agar terhindar dari inefisiensi kata-kata tersebut dapat dibuat dalam array khusus, misalnya berupa file khusus yang berisi pemetaan kata dasar dan seharusnya. Misal untuk ajar dapat dipetakan lajar => ajar.
• Melonggarkan aturan pemotongan. Misalnya ber + kerja = bekerja, sedangkan bentuk yang umum misal ber + karya = berkarya. Pelonggaran ini cukup dilematis, mengingat bila dilakukan ada kemungkinan muncul kata-kata yang tidak sesuai aturan.
• Mencakup algoritma pemecahan kata majemuk yang berimbuhan. Hal ini cukup sulit mengingat kombinasi kata yang dapat bermacam-macam. Bisa pula kata-kata majemuk yang umum disertakan dalam kamus.
• Menambah perbendaharaan kata di kamus, yaitu mencakup pula kata-kata hasil serapan dari bahasa asing (misal: klasik), istilah-istilah yang umum (misal: puskesmas), maupun kata-kata yang tidak baku namun biasa digunakan (misal: milyar, ijin).
• Membuat aturan baru tentang pemotongan imbuhan dalam bahasa asing. Misalnya kapitalisasi (kapital), personalitas (person), miskomunikasi (komunikasi), dst.
• Membuat kategorisasi kata, misalnya kata-kata yang masuk dalam kata kerja dan kata benda. Ketika terjadi peluluhan kata, seperti meng + urus, kecenderungan kata dasarnya adalah urus dan bukan kurus.
• Pendalaman lebih lanjut terhadap tata Bahasa Indonesia, termasuk penggunaan buku teks Bahasa Indonesia, misal: buku Pedoman EYD.

Demikian semoga bermanfaat.

5. Referensi

1. Fadillah Z Tala. A Study of Stemming Effects on Information Retrieval in Bahasa Indonesia. Institute for Logic, Language and Computation, Universiteit van Amsterdam, The Netherlands. 2003.
2. Jelita Asian, Hugh E. Williams, S.M.M. Tahaghogi. Stemming Indonesian. School of Computer Science and Information Technology, RMIT University, Australia. 2003.

6. Lampiran

File lengkap: stemmer.7z (format 7zip)