STOPLIST DAN STEMMING
Secara umum ada dua proses utama dalam IR, yaitu Indexing dan Searching. Proses Indexing terdiri dari 4 subproses antara lain; Word Token (mengubah dokumen menjadi kumpulan term dengan cara menghapus semua karakter dalam tanda baca yang terdapat pada dokumen dan mengubah kumpulan term menjadi lowercase); StopWord Removal (Proses penghapusan kata-kata yang sering ditampilkan dalam dokumen seperti:and, or, not dan sebagainya); Stemming (Proses mengubah suatu kata bentukan menjadi kata dasar); dan Word Weighting (Proses pembobotan setiap term di dalam dokumen). Pada materi ini akan membahas mengenai subproses StopWord Removal/Stoplist dan subproses Steeming.
Link: (http://repository.usu.ac.id/bitstream/123456789/16465/4/Chapter%20II.pdf )
A. STOPLIST
- Pengertian
Proses stoplist merupakan proses pembuangan kata penghubung atau kata dalam bahasa indonesia, seperti dan, maka, lalu, dalam, yang, akan, dari, pada, itu, telah, dengan, dan sebagainya. Stoplist adalah proses yang dilakukan setelah proses tokenisasi. Dimana proses ini hanya menyaring kata/term yang dianggap penting. Tiap element yang terdapat pada tokenTerm dicocokan dengan daftar stoplist di database yang menyimpan kumpulan kata yang dianggap tidak penting (stopword), yang disebut kamus kata.
Link: (http://ejournal.uin-suska.ac.id/index.php/sitekin/article/viewFile/563/535 )
Stopword adalah mengambil kata-kata penting dari hasil token. Bisa menggunakan algoritma stoplist (membuang kata yang kurang penting) atau word list (menyimpan kata penting). Apabila menggunakan metode stoplist yaitu penghilangan kata tidak penting (stopword) pada deskripsi melalui pengecekan kata-kata hasil token deskripsi apakah termasuk didalam daftar kata tidak penting (stoplist) atau tidak. Jika termasuk didalam stoplist maka kata-kata tersebut akan di-remove dari deskripsisehingga kata-kata yang tersisa di dalam deskripsi di anggap sebagai katakatapenting atau keywords (pattern).
Tahapan proses stopword adalah sebagai berikut:
- Kata hasil token Stemming dibandingkan dengan tabel stopword.
- Dilakukan pengecekan apakah token sama dengan tabel stopword atau tidak.
- Jika token sama dengan tabel stopword maka akan di-remove.
- Jika token tidak sama dengan tabel stopword akan ditampilkan. Yaitu menghasilkan token hasil stopword yang termasuk katapenting (keyword).
Eliminasi stopwords memiliki banyak keuntungan, yaitu akan mengurangi space pada tabel term index hingga 40% atau lebih (Baeza, 1999). Proses stopword removal merupakan proses penghapusan term yang tidak memiliki arti atau tidak relevan. Proses ini dilakukan pada saat proses tokenisasi. Proses Filtering menggunakan daftar stopword yang digunakan oleh Tala (2003), yang merupakan stopword bahasa Indonesia yang berisi kata-kata seperti; ada, yang, ke, kepada, dan lain sebagainya.
Link: (http://ejournal.undip.ac.id/index.php/jsinbis)
B. STEMMING
- Pengertian dan Alur Algoritma
Menurut Pribadi, Adi. W (Pribadi & Hasibuan, 2003, p. 7), proses stemming adalah proses pemotongan atau penghilangan imbuhan dari suatu kata. Menurut Lovins (Lovins, 1968, p. 22), sebuah algoritma stemming adalah prosedur komputasi yang mengurangi kata dengan akar yang sama ke bentuk umum, biasanya dengan pengupasan setiap kata akhiran yang derivasional dan infleksional.
Link: (http://journal.uinjkt.ac.id/index.php/ti/article/viewFile/2031/1586)
Stemming merupakan suatu proses atau cara dalam menemukan kata dasar dari suatu kata. Stemming sendiri berfungsi untuk menghilangkan variasi-variasi morfologi yang melekat pada sebuah kata dengan cara menghilangkan imbuhan-imbuhan pada kata tersebut, sehingga nantinya di dapat suatu kata yang benar sesuai struktur morfologi bahasa Indonesia yang benar.
Proses Stemming digunakan untuk mengubah term yang masih melekat dalam term tersebut awalan, sisipan, dan akhiran. Proses stemming dilakukan dengan cara menghilangkan semua imbuhan (affixes) baik yang terdiri dari awalan (prefixes), sisipan (infixes), akhiran (suffixes) dan confixes (kombinasi dari awalan dan akhiran) pada kata turunan. Stemming digunakan untuk mengganti bentuk dari suatu kata menjadi kata dasar dari kata tersebut yang sesuai dengan struktur morfologi bahasa Indonesia yang benar (Tala, 2003). Arsitektur proses stemming untuk bahasa Indonesia dapat dilihat pada Gambar 2.
Link: (http://ejournal.undip.ac.id/index.php/jsinbis)
Ada tiga jenis metode stemming, antara lain :
a. 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. 2. 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.
b. N-Gram Conflation : ide dasarnya adalah pengelompokan kata-kata secara bersama berdasarkan karakter-karakter (substring) yang teridentifikasi sepanjang N karakter.
c. 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” 2. Jika suatu kata diakhiri dengan “es” tetapi bukan “aes” atau “ees” atau “oes”, maka “es” direplace dengan “e” 3. Jika suatu kata diakhiri dengan “s” tetapi bukan “us” atau “ss”, maka “s” direplace dengan “NULL”.
- Algoritma
Menurut Lennon, M. Pierce, D.S (Lennon, Peirce, Tarry, & Willett, 1981, pp. 177-183), ada 5 algoritma stemming yang dikenal, yaitu sebagai berikut ini:
a. Lovins steemer
Menurut Hooper & Paice (Hooper & Paice, 2005, p. 2), lovins stemmer menggunakan context-sensitive. Stemmer ini dikembangkan oleh Julie Beth Lovins dari Institut Teknologi Massachusetts pada tahun 1968. Ini adalah awal dari penggunaan stemming yang ditargetkan untuk temu kembali informasi dan Computational Linguistics (Interaksi Komputer dan Manusia mengunakan Bahasa Alami). Stemmer ini sangat inovatif pada zamannya walaupun mempunyai masalah saat diujikan pada Information Retrieval dan Computational Linguistics. Pendekatannya tidak dapat menyamai dengan kata aslinya juga tidak cukup kompleks untuk kata dasar dengan menggunakan banyak imbuhan, tidak dapat sesuai dengan daftar aturan. Hal yang menarik dalam Lovins stemmer adalah daftar aturan yang diperoleh dari proses pembelajaran dari contoh kata-kata. Mungkin jika proses ini menggunakan contoh kata-kata yang lebih besar lagi akan dapat menghasilkan hasil yang lebih memuaskan.
Permasalahan dalam algoritma Lovins adalah mengenai pemotongan imbuhan. Proses ini menggunakan aturan rekaman untuk mengembalikan kata imbuhan. Untuk memastikan kata dasar sesuai dengan maksud arti dari kata tersebut. Masalah utama dari algoritma Lovins adalah banyaknya hasil yang tidak sesuai dengan kata aslinya atau kata dasarnya. Stemmer ini tidak dapat mempresentasikan dokumen Temu Balik Informasi (TBI) karena pada saat menggunakan dalam skala besar, perekam akan membuat proses menjadi lambat.
. |
b. Paice/Husk Stemmer
Menurut Hooper & Paice (Hooper & Paice, 2005, p. 3), Paice/Husk stemmer dikembangkan oleh Chris Paice di Universitas Lancaster. Pada tahun 1980, Chris Paice meninggal dunia. Paice/Husk stemmer pertama kali dipublikasikan pada tahun 1990. Penelitiannya tentang stemmer dikembangkan oleh assistennya yang bernama Gareth Husk. Paice/Husk stemmer menyatakan bahwa setiap kata merupakan gabungan dari beberapa kata dasar. Walaupun Paice/Husk stemmer dikenal sangat efisien dankenal sangat kuat dan agresif. Paice/Husk stemmer menggunakan satu table atau daftar aturan yang masing-masing bagian mempunyai tugas untuk memotong imbuhan. Teknik memotong yang digunakan adalah menghindari masalah pengejaan kecuali diuraikan lebih awal. Dengan mengganti kata akhiran bukan dengan memotong akhiran, stemmer melakukannya tanpa memisahkan langkah-langkah dalam proses stemming. Ini membantu memelihara efisiensi dari algoritma akan membuat menjadi lebih efektif. Aturan dari indeks kata dasar dan kata berimbuhan untuk memudahkan pencarian yang efisien adalah:
- Sebuah akhir dari satu atau lebih karakter, yang diselenggarakan di urutan terbalik
- Sebuah bendera utuh opsional ‘*’.
- Sebuah digit menentukan total penghapusan (nol atau lebih).
- Sebuah string opsional tambahkan satu atau lebih karakter.
- Sebuah simbol kelanjutan, ‘>’ atau ‘.’ .
Algoritma Paice/Husk stemmer mempunyai empat langkah utama. Penjelasannya berikut ini:
- Pilih bagian yang relevan. Dengan memeriksa masukan kata dan mempertimbangkan aturan yang pertama yaitu bagian relevan dari table aturan.
- Periksa kecocokan aturan. Jika kata inputan tidak cocok dengan aturan maka akan dilanjutkan ke dalam langkah 4.
- Berlakunya aturan adalah dengan menghapus bagian dari imbuhan dan kemudian memeriksa simbol terminal dan terminal lainnya atau kembali ke langkah 1.Melihat aturan lainnya lalu pindah ke aturan selanjutnya di dalam table, jika bagian kata telah berubah maka selesai dan pindah ke langkah 2. Seperti digambarkan Gambar 5.
Link: (http://journal.uinjkt.ac.id/index.php/ti/article/viewFile/2031/1586)
c. Porter Stemmer
Porter, M.F. (1980: 130-137), Porter stemmer adalah pengembangan stemmer yang dibuat oleh Martin Porter di Universitas Cambridge pada tahun 1980. Stemmer berdasarkan pada akhiran di dalam bahasa Inggris (kurang lebih 1200 kata). Kebanyakan dengan menggunakan kombinasi akhiran yang sederhana. Stemmer ini mempunyai beberapa langkah. Secara rinci mempunyai lima langkah aturan. Jika suatu aturan akhiran disamakan dengan kata aslinya di mana kondisi-kondisi menyertakan aturan untuk diuji, apakah akan menghasilkan kata dasar. Jika akhiran sudah dapat dihilangkan, harus sesuai dengan yang diterapkan aturan tersebut (Porter, 1980).
Setiap aturan yang melewati kondisi-kondisi dan diterima oleh aturan dan akhiran dihilangkan dan kemudian pindah ke langkah selanjutnya. Jika aturan tidak diterima maka aturan selanjutnya akan memeriksanya sampai semua aturan dari beberapa aturan. Hasil pemotongan akan dikembalikan kepada stemmer setelah lima langkah itu selesai diperiksa. Porter stemmer digunakan sangat luas dalam banyak aplikasi. Porter stemmer adalah algoritma yang paling banyak digunakan dalam riset Temu Balik Informasi.
Langkah-langkah algoritma Stemming Porter adalah sebagai berikut:
- Periksa pada kata yang akan di Stemm jika terdapat partikel (“-kah”, “-lah”, “-pun”), maka hapus partikel yang melekat.
- Hapus kata ganti kepemilikan seperti “-ku”, “-mu”, “-nya”, jika ada.
- Hapus first order prefiks (awalan pertama) seperti “-meng”, “-meny”, “-men”, “-mem”, “-me”, “-peng”, “-peny”, “-pen”, “-pem”, “-di”, “-ter”, “-ke”.
- Hapus second order prefiks (awalan kedua) seperti “-ber”, “-per”.
- Hapus sufiks (akhiran) seperti “-kan”, “-i”, “-an”.
Link: (http://repository.usu.ac.id/bitstream/123456789/16465/4/Chapter%20II.pdf)
Menurut Munir, et al (Koryati, Mandala, Munir, & Harlili, 2004, pp. L-30) mengatakan bahwa Efektifitas algoritma stemming dipengaruhi oleh beberapa faktor. Diantaranya adalah sebagai berikut:
- Kesalahan dalam proses pemenggalan imbuhan dari kata dasarnya.
Kesalahan ini dapat berupa:
a. Overstemming: yaitu pemenggalan imbuahan yang melebihi dari yang seharusnya.
b. Understemming: yaitu pemenggalan imbuhan yang terlalu sedikit dari yang seharusnya.
c. Unchange: yaitu kasus khusus dari understemming, dimana tidak terjadi pemenggalan imbuhan sama sekali.
d. Spelling exception: yaitu huruf pertama kata dasar yang didapat tidak benar yang diakibatkan dari pemenggalan awalan.
- Kekurangan dalam perumusan aturan penambahan imbuhan pada kata dasar. Hal ini dapat terjadi karena morfologi bahasa Inggris yang kompleks, sehingga sangat sulit atau bahkan tidak mungkin untuk merumuskan aturan yang sempurna.
- Jumlah total aturan imbuhan yang didapat berhubungan dengan efektifitas proses temu kembali. Dimana semakin banyak pola penambahan imbuhan yang dapat dirumuskan, maka proses temu kembali akan semakin efektif.
Contoh :
Pada penelitian “Penerapan Algoritma Paice/Husk Untuk Stemming Pada Kamus Bahasa Inggris ke Bahasa Indonesia”, penulis mengunakan algorithm and experiments methodology (Moret & Shapiro, 2001). Penulis menganggap bahwa metodologi ini sangat cocok untuk diterapkan pada penelitian ini. Faktor-faktor yang mendukung penggunaan algorithm and experiments methodology pada penelitian ini adalah penulis melakukan eksperimen dengan menerapkan dan menguji algoritma pada suatu permasalahan dan setiap tahapan algorithm and experiments methodology dapat membantu penulis dalam menyelesaikan penelitian ini dengan sistematis.
Dalam Algorithm and Experiments Methodology terdapat tujuh tahapan yang harus dilakukan. tahapan-tahapan tersebut antara lain; empiricism in algorithm design, implementation, modes of empirical assessment, experimental setup, measure, present and analyze the data, dan conclusion (Moret & Shapiro, 2001).
Link: (http://journal.uinjkt.ac.id/index.php/ti/article/viewFile/2031/1586)
d. Steeming Bahasa Indonesia Algoritma Nazrief & Andriani
Algoritma ini paling sering dibicarakan dalam steeming bahasa indonesia. Algoritma ini merupakan hasil penelitian internal UI (Universitas Indonesia) dan tidak dipublikasikan secara umum. Namun, algoritma ini mempunyai dua masalah, yang pertama kemampuannya tergantung dari besarnya database kata dasar, dan yang kedua, hasil steeming tidak selalu optimal untuk aplikasi information retrieval.
Adapun langkah-langkah yang digunakan oleh algoritma Nazrief & Andriani yaitu sebagai berikut:
- Kata dicari di dalam daftar kamus. Bila kata tersebut ditemukan di dalam kamus, maka dapat diasumsikan kata tersebut adalah kata dasar sehingga algoritma dihentikan.
- Bila kata di dalam langkah pertama tidak ditemukan di dalam kamus, maka diperiksa apakah surfiks tersebut yaitu sebuah partikel(“-lah”, atau “-kah”). Bila ditemukan maka partikel tersebut dihilangkan.
- Pemeriksaan dilanjutkan pada kata ganti milik (“-ku”, “-mu”, “-nya”). Bila ditemukan maka kata ganti tersebut dihilangkan.
- Memeriksa akhiran (“-i”, “-an”). Bila ditemukan maka akhiran tersebut dihilangkan.Hingga langkah ke-4 dibutuhan ketelitian untuk memeriksa apakah akhiran “-an” hanya merupakan bagian dari kata akhiran “-kan” dan memeriksa lagi apakah partikel (“-lah”, “-kah”) dan kata ganti milik (“-ku”, “-mu”, “-nya”) yang telah dihilangkan pada langkah ke-2 dan 3 bukan merupakan bagian dari kata dasar.
- Memeriksa awalan (“se-”, “ke-”, “te-“, “be-“, “pe-“, “me-“). Bila ditemukan, maka awalan tersebut dihilangkan. Pemeriksaan dilakukan dengan berulang mengingat adanya kemungkinan multi-prefix.Langkah ke-5 ini juga membutuhkan ketelitian untuk memeriksa kemungkinan peluluhan awalan, perubahan prefix yang disesuaikan dengan huruf awal kata dan aturan kombinasi prefix-suffix yang diperbolehkan.
- Setelah menyelesaikan semua langkah dengan sukses, maka algoritma akan mengembalikan kata dasar yang ditemukan.
Link:(http://repository.widyatama.ac.id/xmlui/bitstream/handle/123456789/6830/Bab%202.pdf?sequence=11 )
e. Algoritma Winnowing
Algoritma Winnowing merupakan algoritma yang digunakan untuk deteksi penjiplakan. Input dari algoritma ini adalah dokumen teks yang diproses sehingga menghasilkan output berupa kumpulan nilai-nilai hash, nilai hash merupakan nilai numerik yang terbentuk dari perhitungan ASCII tiap karakter. Kumpulankumpulan nilai hash tersebut selanjutnya disebut fingerprint [11]. Fingerprint inilah yang digunakan dalam deteksi penjiplakan. Langkah awal dalam penerapan algoritma Winnowing adalah membuang karakter-karakter dari isi dokumen yang tidak relevan misal tanda baca spasi dan simbol lain. Langkah kedua isi dokumen yang telah dilakukan pembersihan selanjutnya dilakkukan pembentukan rangkaian gram, dimana n =5. Langkah ketiga dari rangkaian gram yang telah dibentuk dari nilai hash dengan nilai ASCII tiap karakter. Pembentukan nilai hash menggunakan persamaan rolling hash. Langkah keempat nilai-nilai hash yang telah terbentuk dibentuk window-window. Dari window-window yang telah terbentuk dilakukan pemilihan nilai hash terkecil pada tiap window untuk dijadikan fingerprint tiap dokumen. Nilai-nilai fingerprint inilah yang digunakan untuk menemukan tingkat presentase kesamaan sebuah dokumen dengan dokumen lain. Input dari algoritma ini sendiri adalah string dari dokumen tersebut, dan output nya berupa nilai-nilai hash yang dinamakan fingerprints dari dokumen tersebut. Syarat dari algoritma deteksi penjiplakan seperti whitespace insensitivity, yaitu pencocokan teks file seharusnya tidak terpengaruh oleh spasi, jenis huruf kapital, tanda baca dan sebagainya, noise surpression yaitu menghindari pencocokan teks file dengan panjang kata yang terlalu kecil atau kurang relevan dan bukan merupakan kata yang umum digunakan, dan position independence yaitu pencocokan teks file seharusnya tidak bergantung pada posisi kata-kata sehingga kata dengan urutan posisi berbeda masih dapat dikenali jika terjadi kesamaan. Winnowing telah memenuhi syarat-syarat tersebut dengan cara membuang seluruh karakter-karakter yang tidak relevan misal: tanda baca, spasi dan juga karakter lain, sehingga nantinya hanya karakter-karakter yang berupa huruf atau angka yang akan diproses lebih lanjut.
Algoritma winnowing lebih cepat waktu komputasinya daripada algoritma rabin-karp karena fingerprint dari algoritma rabin-karp lebih banyak sedangkan winnowing dipilih nilai minimum dari window nya. keunggulan algoritma winnowing bisa memberikan informasi posisi fingerprint. Penggunaan nilai window yang semakin besar dapat mempengaruhi dalam waktu proses, karena semakin besar nilai dari suatu window mempengaruhi proses pembentukan nilai-nilai hashing yang semakin kecil. Selain itu, nilai k-gram dan basis juga mempengaruhi dalam memberikan persentasi kemiripan yang diperoleh sistem itu sendiri.
Link: (http://repository.usu.ac.id/bitstream/123456789/16465/4/Chapter%20II.pdf )
f. Stemming Menggunakan Pendekatan Confix-Stripping
Pada Tahapan ini merupakan pengolahan Stemming dilakukan berdasarkan input daftar filter term, proses Stemmingini menggunakan algoritma Confix-Stripping. Langkah pertama pada algoritma stemmer ini dilakukanpengecekan rule Precedence yakni larangan kombinasi awalan danakhiran, kemudian mencocokkan term pada elemen diindex tertentudengan daftar “kata dasar” dalam database kamus. Jika cocok maka termtersebut langsung disimpan dalam variable stemTerm. Jika rule Precedencemengembalikan nilai benar proses pemenggalan akhiran dilakukan, jikatidak maka dilanjutkan dengan proses pemenggalan awalan. Kemudianproses recording yaitu proses penyesuaian kata dasar dengan aturanmengubah huruf pertama dari kata tersebut, apakah hasil recording samadengan kamus. Jika benar, maka kata dasar sama dengan hasil recordingjika tidak proses diulang. Proses perulangan ini dilakukan sampai batas 3x,jika proses berulang sampai pada batasan maka kata dasar sama denganhasil recording kemudian term yang ada langsung disimpan dalam variabeldan dianggap sebagai kata dasar. Alur Stemming dengan pendekatan Confix-Stripping dapat dilihat pada Gambar 3.
REFERENSI
Aji, Asmara Damar. Penerapan Algoritma Paice atau Husk untuk Stemming pada Kamus Bahasa Inggris ke Bahasa Indonesia. Fakultas Sains dan Teknologi,Universitas Negeri Syarif Hidayatullah. http://journal.uinjkt.ac.id, diakses 21 April 2017.
Amin, Fatkhul.2012.Sistem Temu kembali Informasi dengan metode Vector Space Model. Fakultas Teknologi Informasi, Universitas Sitkubank. http://ejournal.undip.ac.id/index.php/jsinbis, diakses 23 April 2017.
Bab 2. Landasan Teori. Universitas Sumatera Utara. http://repository.usu.ac.id, diakses 21 April 2017.
Bab II. Landasan Teori. Universitas Widyatama Bandung. http://repository.widyatama.ac.id diakses 21 April 2017.
- Rozanda, Nedi, dkk. Rancang Bangun Sistem Informasi Hadits Menggunakan Teknik Temu Kembali Informasi Model Ruang Vektor. Fakultas Sains dan Teknollogi, Universitas Islam Negeri Sultan Syarif Kasim Riau. http://ejournal.uin-suska.ac.id/index.php, diakses 23 April 2017.
Hapsari, Rinci Kembang dan Santoso, Yunus Juli. 2015. STEMMING ARTIKEL BERBAHASA INDONESIA DENGAN PENDEKATAN CONFIX-STRIPPING. Teknik Informatika, Institut Teknologi Adhi Tama Surabaya, Surabaya. https://www.google.co.id/url?q=http://mmt.its.ac.id/download/SEMNAS/SEMNAS%2520XXII/MTI/25.%2520Prosiding%2520Rinci%2520Kembang%2520Hapsari%2520%2520Ok.pdf&sa=U&ved=0ahUKEwiYi6ytrLzTAhUGpo8KHUDRBho4ChAWCCIwCQ&usg=AFQjCNH5-zlqI0vw2B1zQQbYzQjPji3vcQ, diakses 24 April 2017.
Download Presentasi