Stemming Bahasa Indonesia dengan Algoritma Nazief dan Andriani

Stemming merupakan bagian yang tidak terpisahkan dalam Information Retrieval (IR). Tidak banyak algoritma yang dikhususkan untuk stemming bahasa Indonesia dengan berbagai keterbatasan didalamnya. Algoritma Porter salah satunya, Algoritma ini membutuhkan waktu yang lebih singkat dibandingkan dengan stemming menggunakan Algoritma Nazief & Adriani, namun proses stemming menggunakan Algoritma Porter memiliki prosentase keakuratan (presisi) lebih kecil dibandingkan dengan stemming menggunakan Algoritma Nazief & Adriani. Algoritma Nazief & Adriani sebagai algoritma stemming untuk teks berbahasa Indonesia yang memiliki kemampuan prosentase keakuratan (presisi) lebih baik dari algoritma lainnya. Algoritma ini sangat dibutuhkan dan menentukan dalam proses IR dalam dokumen Indonesia.

Stemming adalah salah satu cara yang digunakan untuk meningkatkan performa IR dengan cara mentransformasi kata-kata dalam sebuah dokumen teks ke bentuk kata dasarnya. Algoritma stemming untuk bahasa yang satu berbeda dengan algoritma stemming untuk bahasa lainnya. Sebagai contoh bahasa Inggris memiliki morfologi yang berbeda dengan bahasa Indonesia sehingga algoritma stemming untuk kedua bahasa tersebut juga berbeda. Proses stemming pada teks berbahasa Indonesia lebih rumit/kompleks karena terdapat variasi imbuhan yang harus dibuang untuk mendapatkan root word(kata dasar) dari sebuah kata.. Pada umumnya kata dasar pada bahasa Indonesia terdiri dari kombinasi:

Prefiks 1 + Prefiks 2 + Kata dasar + Sufiks 3 + Sufiks 2 + Sufiks 1

Sehingga dapat digambarkan menggunakan flowchar sebagai berikut:

Algoritma Nazief & Adriani yang dibuat oleh Bobby Nazief dan Mirna Adriani ini memiliki tahap-tahap sebagai berikut:

1. Pertama cari kata yang akan diistem dalam kamus kata dasar. Jika ditemukan maka diasumsikan kata adalah root word. Maka algoritma berhenti.
2. Inflection Suffixes (“-lah”, “-kah”, “-ku”, “-mu”, atau “-nya”) dibuang. Jika berupa particles (“-lah”, “-kah”, “-tah” atau “-pun”) maka langkah ini diulangi lagi untuk menghapus Possesive Pronouns (“-ku”, “-mu”, atau “-nya”), jika ada.
3. Hapus Derivation Suffixes (“-i”, “-an” atau “-kan”). Jika kata ditemukan di kamus, maka algoritma berhenti. Jika tidak maka ke langkah 3a
   1. Jika “-an” telah dihapus dan huruf terakhir dari kata tersebut adalah “-k”, maka “-k” juga ikut dihapus. Jika kata tersebut ditemukan dalam kamus maka algoritma berhenti. Jika tidak ditemukan maka lakukan langkah 3b.
   2. Akhiran yang dihapus (“-i”, “-an” atau “-kan”) dikembalikan, lanjut ke langkah 4.
4. Hapus Derivation Prefix. Jika pada langkah 3 ada sufiks yang dihapus maka pergi ke langkah 4a, jika tidak pergi ke langkah 4b.
   1. Periksa tabel kombinasi awalan-akhiran yang tidak diijinkan. Jika ditemukan maka algoritma berhenti, jika tidak
   2. pergi ke langkah 4b.
   3. For i = 1 to 3, tentukan tipe awalan kemudian hapus awalan. Jika root word belum juga ditemukan lakukan langkah 5, jika sudah maka algoritma berhenti. Catatan: jika awalan kedua sama dengan awalan pertama algoritma berhenti.
5. Melakukan Recoding.
6. Jika semua langkah telah selesai tetapi tidak juga berhasil maka kata awal diasumsikan sebagai root word. Proses selesai.

Tipe awalan ditentukan melalui langkah-langkah berikut:

1. Jika awalannya adalah: “di-”, “ke-”, atau “se-” maka tipe awalannya secara berturut-turut adalah “di-”, “ke-”, atau “se-”.
2. Jika awalannya adalah “te-”, “me-”, “be-”, atau “pe-” maka dibutuhkan sebuah proses tambahan untuk menentukan tipe awalannya.
3. Jika dua karakter pertama bukan “di-”, “ke-”, “se-”, “te-”, “be-”, “me-”, atau “pe-” maka berhenti.
4. Jika tipe awalan adalah “none” maka berhenti. Jika tipe awalan adalah bukan “none” maka awalan dapat dilihat pada Tabel 2. Hapus awalan jika ditemukan.

Tabel 1. Kombinasi Awalan Akhiran Yang Tidak Diijinkan

Awalan	Akhiran yang tidak diizinkan
be-	-i
di-	-an
ke-	-i, -kan
me-	-an
se-	-i, -kan

Tabel 2. Cara Menentukan Tipe Awalan Untuk awalan “te-”

Following Characters				Tipe Awalan
Set 1	Set 2	Set 3	Set 4
“-r-“	“-r-“	–	–	none
“-r-“		–	–	ter-luluh
“-r-“	not (vowel or “-r-”)	“-er-“	vowel	ter
“-r-“	not (vowel or “-r-”)	“-er-“	not vowel	ter-
“-r-“	not (vowel or “-r-”)	not “-er-“	–	ter
not (vowel or “-r-”)	“-er-“	vowel	–	none
not (vowel or “-r-”)	“-er-“	not vowel	–	te

Tabel 3. Jenis Awalan Berdasarkan Tipe Awalannya

Tipe Awalan	Awalan yang harus dihapus
di-	di-
ke-	ke-
se-	se-
te-	te-
ter-	ter-
ter-luluh	ter

Untuk mengatasi keterbatasan pada algoritma di atas, maka ditambahkan aturan-aturan dibawah ini:

1. Aturan untuk reduplikasi.

1. Jika kedua kata yang dihubungkan oleh kata penghubung adalah kata yang sama maka root word adalah bentuk tunggalnya, contoh : “buku-buku” root word-nya adalah “buku”.
2. Kata lain, misalnya “bolak-balik”, “berbalas-balasan, dan ”seolah-olah”. Untuk mendapatkan root word-nya, kedua kata diartikan secara terpisah. Jika keduanya memiliki root word yang sama maka diubah menjadi bentuk tunggal, contoh: kata “berbalas-balasan”, “berbalas” dan “balasan” memiliki root word yang sama yaitu “balas”, maka root word “berbalas-balasan” adalah “balas”. Sebaliknya, pada kata “bolak-balik”, “bolak” dan “balik” memiliki root word yang berbeda, maka root word-nya adalah “bolak-balik”.

2. Tambahan bentuk awalan dan akhiran serta aturannya.

1. Untuk tipe awalan “mem-“, kata yang diawali dengan awalan “memp-” memiliki tipe awalan “mem-”.

1. Tipe awalan “meng-“, kata yang diawali dengan awalan “mengk-” memiliki tipe awalan “meng-”.

Berikut contoh-contoh aturan yang terdapat pada awalan sebagai pembentuk kata dasar.

1. Awalan SE-

Se + semua konsonan dan vokal tetap tidak berubah

Contoh :

• Se + bungkus   = sebungkus
• Se + nasib   = senasib
• Se + arah    = searah
• Se + ekor    = seekor

2. Awalan ME-

Me + vokal (a,i,u,e,o) menjadi sengau “meng”

Contoh :

• Me + inap = menginap
• Me + asuh = mengasuh
• Me + ubah = mengubah
• Me + ekor  = mengekor
• Me + oplos = mengoplos

Me + konsonan b menjadi “mem”

Contoh :

• Me + beri = member
• Me + besuk = membesuk

Me + konsonan c menjadi “men”

Contoh :

• Me + cinta  = mencinta
• Me + cuci  = mencuci

Me + konsonan d menjadi “men”

Contoh :

• Me + didik  = mendidik
• Me + dengkur = mendengkur

Me + konsonan g dan h menjadi “meng”

Contoh :

• Me + gosok  = menggosok
• Me + hukum  = menghukum

Me + konsonan j menjadi “men”

Contoh :

• Me + jepit = menjepit
• Me + jemput = menjemput

Me + konsonan k menjadi “meng” (luluh)

Contoh :

• Me + kukus = mengukus
• Me + kupas  = mengupas

Me + konsonan p menjadi “mem” (luluh)

Contoh :

• Me + pesona = mempesona
• Me + pukul = memukul

Me + konsonan s menjadi “meny” (luluh)

Contoh :

• Me + sapu = menyapu
• Me + satu = menyatu

Me + konsonan t menjadi “men” (luluh)

Contoh :

• Me + tanama = menanam
• Me + tukar  = menukar

Me + konsonan (l,m,n,r,w) menjadi tetap “me”

Contoh :

• Me + lempar = melempar
• Me + masak = memasak
• Me + naik  = menaik
• Me + rawat = merawat
• Me + warna = mewarna

3. Awalan KE-

Ke + semua konsonan dan vokal tetap tidak berubah

Contoh :

• Ke + bawa = kebawa
• Ke + atas = keatas

4. Awalan PE-

Pe + konsonan (h,g,k) dan vokal menjadi “per”

Contoh :

• Pe + hitung + an = perhitungan
• Pe + gelar + an = pergelaran
• Pe + kantor +   = perkantoran

Pe + konsonan “t” menjadi “pen” (luluh)

Contoh :

• Pe + tukar  = penukar
• Pe + tikam = penikam

Pe + konsonan (j,d,c,z) menjadi “pen”

Contoh :

• Pe + jahit = penjahit
• Pe + didik = pendidik
• Pe + cuci = pencuci
• Pe + zina = penzina

Pe + konsonan (b,f,v) menjadi “pem”

Contoh :

• Pe + beri = pemberi
• Pe + bunuh = pembunuh

Pe + konsonan “p” menjadi “pem” (luluh)

Contoh :

• Pe + pikir  = pemikir
• Pe + potong  = pemotong

Pe + konsonan “s” menjadi “peny” (luluh)

Contoh :

• Pe + siram  = penyiram
• Pe + sabar = penyabar

Pe + konsonan (l,m,n,r,w,y) tetap tidak berubah

Contoh :

• Pe + lamar = pelamar
• Pe + makan = pemakan
• Pe + nanti = penanti
  • Pe + wangi = pewangi

Penerapannya dapat dilihat pada penggalan source code berikut:

<?php
require_once(‘Algoritma_stemming.php’);
?>
<h3>STEMMING KATA DASAR</h3>
<form method=”post” action=””>
<input type=”text” name=”katadasar” id=”katadasar” size=”20″>
<input class=”btnForm” type=”submit” name=”btnSubmitAdd” value=”Submit”/>
</form>
<?php
if(isset($_POST[‘katadasar’])){
$teksAsli = $_POST[‘katadasar’];
//echo $teksAsli;
$length = strlen($teksAsli);
//echo $length;
$pattern = ‘[A-Za-z]’;
$kata = ”;
if(eregi($pattern,$teksAsli)){
$kata = $teksAsli;
$stemming = NAZIEF($kata);//Memasukkan kata ke fungsi Algoritma Nazief
echo $stemming.'<br/>’;
$kata = ”;
}

}
?>

Untuk algoritma Nazief dan Andriannya sebagai berikut:

<?php
require_once(‘koneksi.php’);//Koneksi ke database
// fungsi-fungsi
/*

DP + DP + root word + DS + PP + P

*/

function cekKamus($kata){
// cari di database
$sql = “SELECT * from tb_katadasar where katadasar =’$kata’ LIMIT 1”;
//echo $sql.'<br/>’;
$result = pg_query($sql) or die(pg_error());
if(pg_num_rows($result)==1){
return true; // True jika ada
}else{
return false; // jika tidak ada FALSE
}
}

function Del_Inflection_Suffixes($kata){
$kataAsal = $kata;
if(eregi(‘([km]u|nya|[kl]ah|pun)$’,$kata)){ // Cek Inflection Suffixes
$__kata = eregi_replace(‘([km]u|nya|[kl]ah|pun)$’,”,$kata);
.
.
.
return $__kata;
}
return $kataAsal;
}

// Cek Prefix Disallowed Sufixes (Kombinasi Awalan dan Akhiran yang tidak diizinkan)
function Cek_Prefix_Disallowed_Sufixes($kata){
if(eregi(‘^(be)[[:alpha:]]+(i)$’,$kata)){ // be- dan -i
return true;
}
.
.
.
if(eregi(‘^(se)[[:alpha:]]+(i|kan)$’,$kata)){ // se- dan -i,-kan
return true;
}
return false;
}

// Hapus Derivation Suffixes (“-i”, “-an” atau “-kan”)
function Del_Derivation_Suffixes($kata){
$kataAsal = $kata;
if(eregi(‘(i|an)$’,$kata)){ // Cek Suffixes
$__kata = eregi_replace(‘(i|an)$’,”,$kata);
if(cekKamus($__kata)){ // Cek Kamus
return $__kata;
}
/*– Jika Tidak ditemukan di kamus –*/
.
.
.

}
return $kataAsal;
}

// Hapus Derivation Prefix (“di-”, “ke-”, “se-”, “te-”, “be-”, “me-”, atau “pe-”)
function Del_Derivation_Prefix($kata){
$kataAsal = $kata;

/* —— Tentukan Tipe Awalan ————*/
if(eregi(‘^(di|[ks]e)’,$kata)){ // Jika di-,ke-,se-
$__kata = eregi_replace(‘^(di|[ks]e)’,”,$kata);
if(cekKamus($__kata)){
return $__kata; // Jika ada balik
}
$__kata__ = Del_Derivation_Suffixes($__kata);
if(cekKamus($__kata__)){
return $__kata__;
}
/*————end “diper-”, ———————————————*/
if(eregi(‘^(diper)’,$kata)){
$__kata = eregi_replace(‘^(diper)’,”,$kata);
if(cekKamus($__kata)){
return $__kata; // Jika ada balik
}
.
.
.
}
/*————end “diper-”, ———————————————*/
}
if(eregi(‘^([tmbp]e)’,$kata)){ //Jika awalannya adalah “te-”, “me-”, “be-”, atau “pe-”
.
.
.
.
}
/* — Cek Ada Tidaknya Prefik/Awalan (“di-”, “ke-”, “se-”, “te-”, “be-”, “me-”, atau “pe-”) ——*/
if(eregi(‘^(di|[kstbmp]e)’,$kata) == FALSE){
return $kataAsal;
}

return $kataAsal;
}

function NAZIEF($kata){

$kataAsal = $kata;

/* 1. Cek Kata di Kamus jika Ada SELESAI */
if(cekKamus($kata)){ // Cek Kamus
return $kata; // Jika Ada kembalikan
}

/* 2. Buang Infection suffixes (\-lah”, \-kah”, \-ku”, \-mu”, atau \-nya”) */
$kata = Del_Inflection_Suffixes($kata);

/* 3. Buang Derivation suffix (\-i” or \-an”) */
$kata = Del_Derivation_Suffixes($kata);

/* 4. Buang Derivation prefix */
$kata = Del_Derivation_Prefix($kata);

return $kata;

}
?>

Pada proses stemming menggunakan Algoritma Nazief & Adriani, kamus yang digunakan sangat mempengaruhi hasil stemming. Semakin lengkap kamus yang digunakan maka semakin akurat pula hasil stemming.

Sumber: Agusta, L.2009. Perbandingan Algoritma Stemming Porter Dengan Algoritma Nazief dan Adriani Untuk Stemming Dokumen Teks Bahasa Indonesia. Konferensi Nasional Sistem dan Informatika 2009. <URL: http://yudiagusta.files.wordpress.com/2009/11/196-201-knsi09-036-perbandingan-algoritma-stemming-porter-dengan-algoritma-nazief-adriani-untuk-stemming-dokumen-teks-bahasa-indonesia.pdf >. Diakses 10 Juli 2010.