SETYO HARTANTO : PEMBAHASAN STOPLIST DAN STEMMING

Stop list

Stop list merupakan fitur yang dimiliki sistem information retrieval (search engine), dimana term/kata-kata yang dianggap umum akan diabaikan dalam proses indexing (contoh : I, and, or, is, of, was). Kata-kata yang umum tersebut disebut sebagai stop word. Sistem yang baik memiliki suatu list stop word sebagai acuan dalam mengindex, untuk memilih term-term yang umum ataupun tidak. Stop list berpengaruh juga terhadap hasil pencarian. Misal kita mempunyai sebuah query “information is retrieval” dan “informatin retrieval” (keduanya dicari dengan tanpa menyertakan tanda kutip). Jika suatu sistem information retrieval menyertakan fitur stop list, seharusnya kedua query tersebut menghasilkan search result yang sama karena kata “is” adalah stop word dan tidak akan diindex oleh sistem (diabaikan dalam proses retrieving).

Stemming

Stemming adalah proses untuk menggabungkan atau memecahkan setiap varian-varian suatu kata menjadi kata dasar. Stem (akar kata) adalah bagian dari kata yang tersisa setelah dihilangkan imbuhannya (awalan dan akhiran). Contoh : connect adalah stem dari connected, connecting, connection, dan connections. Metode stemming memerlukan input berupa term yang terdapat dalam dokumen. Sedangkan outputnya berupa stem.

Ada tiga jenis metode stemming, antara lain :

  • Successor Variety (SV) : lebih mengutamakan penyusunan huruf dalam kata dibandingkan dengan pertimbangan atas fonem. Contoh untuk kata-kata : corpus, able, axle, accident, ape, about menghasilkan SV untuk kata apple :

Karena huruf pertama dari kata “apple” adalah “a”, maka kumpulan kata yang ada substring “a” diikuti “b”, “x”, “c”, “p” disebut SV dari “a” sehingga “a” memiliki 4 SV.

Karena dua huruf pertama dari kata “apple” adalah “ap”, maka kumpulan kata yang ada substring “ap” hanya diikuti “e” disebut SV dari “ap” sehingga “ap” memiliki 1 SV.

  • N-Gram Conflation : ide dasarnya adalah pengelompokan kata-kata secara bersama berdasarkan karakter-karakter (substring) yang teridentifikasi sepanjang N karakter.
  • Affix Removal : membuang suffix dan prefix dari term menjadi suatu stem. Yang paling sering digunakan adalah algoritma Porter Stemmer karena modelnya sederhana dan effisien.

Jika suatu kata diakhiri dengan “ies” tetapi bukan “eies” atau “aies”, maka “ies” direplace dengan “y”

Jika suatu kata diakhiri dengan “es” tetapi bukan “aes” atau “ees” atau “oes”, maka “es” direplace dengan “e”

Jika suatu kata diakhiri dengan “s” tetapi bukan “us” atau “ss”, maka “s” direplace dengan “NULL”.

Ada banyak algoritma yang digunakan untuk melakukan proses stemming, khususnya stemming bahasa indonesia. Algoritma-algoritma tersebut antara lain : Algoritma Nazief dan Andriani, algoritma Arifin dan Setiono, algoritma Idris dan Mustofa, algoritma Vega, algoritma Ahmad, Yussof dan Sembok, Porter dsb. Algoritma yang diimplementasikan dalam tutorial ini menggunakan algoritma Porter.  Algoritma Porter ditemukan oleh Martin Porter 1980. Algoritma tersebut digunakan untuk stemming bahasa inggris, kemudian karena proses stemming bahasa inggris berbeda dengan bahasa indonesia maka, dikembangkan algoritma porter khusus untuk bahasa indonesia (Porter Stemmer for Bahasa Indonesia) oleh W.B. Frakes pada tahun 1992. Berikut Flowchart untuk algoritma Porter untuk bahasa Indonesia:

Alur Alogritma Stemming

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
  4. 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.
  5. Akhiran yang dihapus (“-i”, “-an” atau “-kan”) dikembalikan, lanjut ke langkah 4.
  6. Hapus Derivation Prefix. Jika pada langkah 3 ada sufiks yang dihapus maka pergi ke langkah 4a, jika tidak pergi ke langkah 4b.
  7. Periksa tabel kombinasi awalan-akhiran yang tidak diijinkan. Jika ditemukan maka algoritma berhenti, jika tidak
  8. Pergi ke langkah 4b.
  9. 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.
  10. Melakukan Recoding.
  11. Jika semua langkah telah selesai tetapi tidak juga berhasil maka kata awal diasumsikan sebagai root word. Proses selesai.

 

Implementasi Algoritma Rabin-Karp Menggunakan Stemming Nazief Dan Adriani Untuk Mendeteksi Tingkat Kemiripan File Teks Yang Berbentuk Skripsi

Di dunia pendidikan khususnya di kalangan universitas, rentan terjadi praktek plagiarisme. Misalnya dalam hal pembuatan Tugas Akhir, Skripsi. Untuk mendeteksi kemiripan antar Skripsi, banyak universitas masih melakukannya secara manual sehingga menghabiskan waktu yang lama dan tenaga yang ekstra. Seiring dengan perkembangan ilmu pengetahuan dan teknologi, algoritma untuk mencari tingkat kesamaan dokumen telah dikembangkan oleh para ahli. Stemming adalah salah satu cara untuk meningkatkan performa information retrieval. Data yang digunakan pada penelitian ini adalah skripsi mahasiswa S1 Ilmu komputer Universitas Sumatera Utara. Penulis menggunakan algoritma stemming Nazief dan Adriani dalam mencari kata dasar/root word untuk setiap kata dalam skripsi yang diuji. Setelah didapat kata dasar dari setiap kata, kemudian dari kata dasar tersebut dibentuk gram, dan dicari nilai hashnya menggunakan algoritma Rabin-Karp. Setelah didapat nilai hash, maka nilai hash skripsi yang diuji dibandingkan dengan nilai hash skripsi yang sudah tersimpan di database sistem menggunakan rumus Dice Coefficient Similarity. Hasil perbandingan antar skripsi dalam bentuk persen, disimpan ke database sistem dan ditampilkan di sistem secara berurut dari yang paling besar total persentase kemiripannya sampai yang paling kecil.
Kata kunci: plagiarisme, stemming, information retrieval, Rabin-Karp, Dice Coefficient Similarity.

 

Penerapan Algoritma Stoplist Genetika pada Peringkasan Teks Dokumen Bahasa Indonesia

Pada saat ini, perkembangan teknologi informasi sangat cepat, salah satunya adalah penggunaan internet. Tujuannya adalah untuk mendapatkan informasi dengan cepat dan akurat. Seiring  bertambahnya informasi, maka  berbanding lurus dengan dokumen yang ada di dunia internet, salah satu contohnya adalah dokumen berita, Dokumen berita merupakan kumpulan informasi tentang  banyak peristiwa penting terjadi dan terbaru secara berkala. Memahami isi dokumen berita melalui ringkasan teks memerlukan waktu yang lebih singkat dibandingkan membaca seluruh isi dokumen, sehingga ringkasan teks menjadi sangat penting. Namun demikian, membuat ringkasan manual dengan dokumen yang banyak akan memerlukan waktu dan biaya yang besar. Sehingga diperlukan suatu sistem peringkasan secara otomatis untuk mengatasi masalah waktu baca dan biaya. Peringkasan teks adalah suatu proses yang menghasilkan dokumen yang lebih kecil 50% dari ukuran dokumen dengan tujuan memperoleh informasi dalam waktu singkat. Menurut peringkasan teks adalah proses pencarian informasi yang  penting dari sumber (atau beberapa sumber) untuk menghasilkan dokumen yang ringkas bagi pengguna. Pada penelitian, melakukan  penentuan tingkat kepentingan atau  pembobotan dari sebelas fitur teks untuk meringkas dokumen. Penelitian ini merupakan kelanjutan dari penelitian yaitu meringkas dokumen teks. Hasil ringkasan diuji dengan menggunakan F-measure, Precision, Recall.

Presentasi :

Download

Referensi :