Konstruksi Inverted Index

Temu Kembali Informasi: Rekonstruksi Inverted Index dan Implementasi Stopwords Wayan Sriyasa/G651080154 Departemen Ilmu Komputer, FMIPA, IPB

Rekonstruksi Inverted Index dan Implementasi Stopwords Pendahuluan Proses pencarian informasi dalam suatu dokumen ada beberapa cara yang dapat dilakukan antara lain dengan membaca seluruh isi dokumen tersebut, namun cara yang demikian tentunya akan sangat tidak efektif apabila informasi yang akan kita cari cukup banyak dalam korpus yang berukuran besar secara berulang. Untuk itu diperlukan metode yang lebih efisien dimana pembacaan dilakukan hanya sekali kemudian data yang berupa daftar kata yang mengarah ke suatu dokumen disimpan untuk digunakan pada proses pencarian selanjutnya. Salah satu cara yang bisa digunakan untuk tujuan ini adalah dengan membangun index untuk setiap kata yang ada didalam dokumen. Proses indexing dapat kita lakukan dengan membuat daftar frekuensi kemunculan kata disetiap dokumen kedalam sebuah tabel seperti berikut: Term

Doc#

fahri

DOC#1 Fahri menghampiri apartemen Maria untuk minta bantuan karena komputer yang digunakan untuk menyusun tesis mengalami Error.

1

menghampiri 1 apartemen

1

Maria

1

Untuk

1

…. Dst

1

Selama

2

Membantu

2

Menyusun

2

…. Dst

2

DOC#2 Selama membantu menyusun tesis, timbul perasaan cintanya Maria kepada Fahri

Gambar 1. Proses pengelompokan kata/term dan frekuensinya pada tiap dokumen.

Setelah dilakukan pemisahan kata perkata dari setiap dokumen, kemudian dibuat tabel frekuensi seperti terlihat pada ilustrasi diatas. Tabel tersebut disebut sebagai term document matrix. Proses ini dikenal sebagai forward indexing dan proses pencarian dengan menggunakan metode indexing ini memerlukan waktu yang berbanding lurus dengan jumlah datanya (O(n)), dimana ukuran matrix akan sangat besar. Inverted index adalah salah satu solusi yang dapat digunakan untuk mengatasi permasalahan ini. Dimana ide yang dipakai adalah dengan menggabungkan term yang sama pada satu dokumen dengan dokumen yang lainnya dan untuk mengetahui kemunculan suatu term ditiap dokumen maka digunakanlah frekuensi dari kemunculan term tersebut. Berikut contoh tabel yang baru: Term Apartemen Cintanya Fahri Fahri

Doc# Frek 1 1 2 1 1 1 2 1 1

Temu Kembali Informasi: Rekonstruksi Inverted Index dan Implementasi Stopwords Wayan Sriyasa/G651080154 Departemen Ilmu Komputer, FMIPA, IPB

Tabel Dictionary dan Posting

Terms

T erm apartemen bantuan cintanya digunakan error fahri karena kepada komputer maria membantu mengalami menghampiri menyus un minta peras aan s elama tes is timbul untuk yang

nD oc tF rek 1 1 1 1 1 1 1 1 1 1 2 2 1 1 1 1 1 1 2 2 1 1 1 1 1 1 2 2 1 1 1 1 1 1 2 2 1 1 1 2 1 1

Pointer

D oc# 1 1 2 1 1 1 2 1 2 1 1 2 2 1 1 2 1 1 2 2 1 2 2 1 1

F rek 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1

Gambar 2. Tabel Dictionary & Posting serta pointer.

Dua bagian dari inverted index, yaitu dictionary & posting. Dictionary biasanya disimpan didalam memori dengan pointer yang mengarah ke setiap posting list yang disimpam didalam disk. Rekonstruksi Inverted Index Untuk menambah kecepatan indexing pada waktu retrieval, kita perlu membangun index ini lebih lanjut. Langkah utama adalah: 1. Mengumpulkan & membaca dokumen yang akan di-index. 2. Melakukan tokenisasi/pemisahan kata/term yang terdapat pada dokumen. 3. Melakukan standarisasi kata/term yang nantinya digunakan pada index. 4. Melakukan indexing dokumen dengan kata/term yang muncul didalamnya kedalam tabel dictionary dan posting. Index dibangun dengan melakukan pengurutandan pengelompokan. Urutan setiap kata/term didalam dokumen ditandai dengan IdDokumen-nya masing-masing. Instance yang mengandung kata/term yang sama dikelompokkan menjadi satu berdasarkan kata/term tersebut dan kemudian berdasarkan IdDokumen-nya. Kemudian kata/term dan IdDokumen kemudian dipisahkan sehingga dihasilkan tabel dictionary dan posting list. Tabel dictionary menyimpan kata/term dan memiliki pointer yang berfungsi sebagai penunjuk ke daftar posting untuk tiap-tiap kata/term. Setiap posting list menyimpan daftar dokumen dimana kata/term muncul dan juga menyimpan informasi seperti frekuensi kata/term atau posisi kata/term tersebut didalam dokumen. Ilustrasi dibawah menunjukkan bagaima dictionary dan posting list dibentuk. 2

Temu Kembali Informasi: Rekonstruksi Inverted Index dan Implementasi Stopwords Wayan Sriyasa/G651080154 Departemen Ilmu Komputer, FMIPA, IPB

Gambar 3. Proses pembentukan dictionary & posting list pada inverted index. Sumber: Manning, et.al. 2008

Inverse Documen Frequency (idft) Pada dasarnya, tidak semua kata/term yang muncul pada sebuah dokumen dapat dijadikan sebagai penciri dokumen itu. Berdasarkan hal ini diperlukan sebuah cara untuk mengurangi efek dari kata/term yang muncul terlalu sering pada suatu korpus sehingga dihasilkan kata/term yang dapat mencirikan masing-masing dokumen tersebut. Salah satu ide yang cukup relevan untuk itu adalah dengn menghitung document frequency (dft ), yang didefiniskan sebagai jumlah dokumen dalam korpus yang megandung kata/term t. Karena untuk jumlah dokumen yang cukup banyak akan lebih efektif jika dilihat dari statistik pada level dokumennya.

3

Temu Kembali Informasi: Rekonstruksi Inverted Index dan Implementasi Stopwords Wayan Sriyasa/G651080154 Departemen Ilmu Komputer, FMIPA, IPB

Inverse Document Frequency (idft) dapat kita tentukan dengan melakukan pembandingan jumlah dokumen (N) pada suatu korpus terhadap dft-nya, sebagai berikut: N idft  log ........................(1) dft idft menunjukkan bagaimana distribusi kata/term diantara koleksi dokumen didalam korpus. Tabel berikut merupakan ilustrasi dari frekuensi kata/term dan nilai idft -nya: Kata/term yang di dan itu dari

freq 245 214 211 125 100

dft 21 21 21 21 21

idft Log(21/21) = 0 Log(21/21) = 0 Log(21/21) = 0 Log(21/21) = 0 Log(21/21) = 0

Pada ilustrasi diatas, kata/term dengan frekuensi yang rendah akan memiliki idft yang tinggi, hal ini menunjukkan bahwa relevansi kata/term tersebut berbanding lurus dengan idft-nya. Ketika ukuran Nt semakin membesar, nilai idft akan semakin mengecil, dan jika dft = N, maka nilai idft = 0, sehingga kata/term yang demikian tidak memberikan ciri apapun terhadap sebuah dokumen. Kata/term yang demikian dapat kita abaikan dan nantinya dapat kita pakai sebagai stopwords. Seperti korpus yang dipakai, kata-kata "yang, di, dan, itu, dari" merupakan beberapa kata yang dapat dijadikan sebagai stopwords pada korpus tersebut.

Pembobotan tf-idf Dengan mengkombinasikan frekuensi kata/term dengan idft akan diperoleh bobot komposit dari setiap kata/term disetiap dokumen. Skema pembobotan tf-idft , dimana pembobotan kata/term t pada suatu dokumen d dapat dihitung sebagai:

tf-idft,d = tft,d x idft

........................(2)

dari persamaan ini terlihat bahwa:  Nilai tertinggi akan muncul bilamana t muncul berulang kali didalam korpus dengan jumlah dokumen yang sedikit (sehingga kata/term tersebut sangat berperan sebagai penciri dokumen).  Nilai rendah terjadi ketika kata/term muncul didalam dokumen lebih jarang, atau muncul dibanyak dokumen (sehingga kata/term yang demikian kurang baik sebagai penciri sebuah dokumen).  Nilai terrendah akan terjadi jika kata/term muncul hampir disemua dokumen. Persamaan (2), terlihat bahwa setiap dokumen diperlakukan sebagai vektor dengan satu komponen yang berhubungan dengan setiap kata/term didalam dictionary. Implementasi Implementasi dari tulisan ini adalah mencoba melakukan konstruksi inverted index, melakukan pembobotan dan penentuan stopwords. Inverted index dibuat dengan menyimpan kata/term kedalam hash setelah proses tokenisasi selesai dan akan dibandingkan ukuran indeks dengan dan tanpa stopwords. 4

Temu Kembali Informasi: Rekonstruksi Inverted Index dan Implementasi Stopwords Wayan Sriyasa/G651080154 Departemen Ilmu Komputer, FMIPA, IPB

Langkah 1. Pembuatan Inverted Index Cuplikan script berikut merupakan langkah pembentukan inverted index: ################################################# ## Step 1: Buat inverted index ## ################################################# while () { $JumDok++; $JumDok1++; chomp; ## baca judul dokumen if ($_=~ /<TITLE>(.*)<\/TITLE>/) { $judul[$JumDok] = $1; print "Judul ke-$JumDok1 = $judul[$JumDok]\n"; } ## Baca isi dokumen disetiap judul while (m/<(TITLE|TEXT)>(.+)<\/\1>/gs) { ## Buang tanda baca standar Perl (my $text = $2) =~ s/[[:punct:]]+//gs; ## parsing kata ditiap dokumen while ($text =~ m/\b([[:alpha:]]+)\b/gs) { ## convert jd huruf kecil $kata = lc $1; ## simpan frekuensi kata ditiiap dokumen ke variabel tf (posting) ++$tf[$JumDok]{$kata}; ## simpan frekuensi kata diseluruh dokumen (dicitionary) ++$dictio{$kata}; ## tulis ke file tf.csv print OUT "Dokumen ke: $JumDok1, $kata,$tf[$JumDok]{$kata}\n"; } } }

Langkah 2. Perhitungan dft, idft dan tf x idft ########################################################## ## Step 2. hitung frekeunsi kemunculan kata ditiap dokumen dalam ########################################################## $n = $#tf + 1; foreach $x (sort keys %dictio){ $Jum = 0; for $i (0..$#tf) { if ($tf[$i]{$x} > 0 ) { $Jum++; } if ($Jum > 0 ) { $df{$x} = $Jum; $bobot[$i]{$x} = log($n/$df{$x})/log(2); } } }

5

korpus --> df

##

Temu Kembali Informasi: Rekonstruksi Inverted Index dan Implementasi Stopwords Wayan Sriyasa/G651080154 Departemen Ilmu Komputer, FMIPA, IPB

Langkah 3. Pemilihan Stopwords Pada korpus ini stopwords dipilih dengan kriteria kata yang memiliki nilai 1 < dft dan dft > 10, kriteria ini dipilih berdasarkan karakteristik korpus serta pertimbangan nilai idft . Berikut cuplikan script yang melakukan fungsi ini: ## Step3 . Bikin index dengan dan tanpa stopwords ################################################# ##Bikin index dengan stopwords, stopwords dipilih dengan kategori ##kata yang memiliki 1 1) { print OUT3 "$x, $dictio{$x}, $df{$x}.\n"; } } ################################################# ## Bikin index tanpa stopwords ## ################################################# foreach $x (sort keys %dictio) { print OUT2 "$x,$dictio{$x},$df{$x}\n"; }

Hasil dan Pembahasan Berikut hasil run dari script yang telah dibuat:

Gambar 5. Hasil run script

6

##

Temu Kembali Informasi: Rekonstruksi Inverted Index dan Implementasi Stopwords Wayan Sriyasa/G651080154 Departemen Ilmu Komputer, FMIPA, IPB

Implementasi stopwords berhasil mengurangi ukuran index cukup signifikan yakni dari sebanyak 2194 buah kata unik dengan jumlah kata mencapai 9243 buah kata dapat dikurangi hingga 5010 buah kata dengan perbendaharaan kata unik sebanyak 766 kata, efisiensi jumlah kata yang dihasilkan mencapai hingga 45,8% dan efisiensi jumlah kata unik hingga 65%. Berikut tabel perbandingan index dengan dan tanpa stopwords: Stopwords Efisiensi (%) Tanpa Dengan Total jumlah kata 9243 5010 45.80 Total kata unik 2194 766 65.09 Kata/Term

Berikut grafik distribusi frekuensi kata pada korpus, grafik 1 merupakan sebaran kata tanpa stopwords dan grafik 2 sebaran kata setelah menggunakan stopwords. Sebaran Kata Dalam Korpus Tanpa Stopwords 300

250

Frekuensi

200

150

100

50

0 i n i i i n l r k n i i k n n n n i t n l t n k ng esa sa ya tkan ang pas rea ans rika ong an ulu aa asl lisas ga ka am feks ka nyaong aga ikun iring wa esta aa au dah gka ap nya ks isian iwa oni lite ka ka ang ga kter a j p e an ku hi an a g ir a n n c n p u n nc au y b ru an ka ep tisi a nst se gk kim m ad ol j b sia u ru a in din kh thip ten sod se r p gu o b j i m ba e m n su a u ah erla c an ep dr an ke so rlind enu m m g n t i se ning k r ho m n h b e ep ba nw e pe di pe m pe rk di tri hk m di be bu um n e m

Kata

Sebaran Kata Setelah Digunakan Stopwords Dengan Stopwords 80 70

50 40 30 20 10

Kata

Gambar 6. Sebaran kata didalam korpus tanpa dan dengan stopwords. 7

tani

sebaiknya

paham

menderita

eksportir

keterkaitan

apbd

dibandingk

pelaku

sumber

kamis

mendapat

buahbuaha

tertentu

pasaran

atas

indosiarcom

pejabat

tapi

dosis

diselundupk

sapi

apabila

dokumen

masuk

bea

sedang

mereka

kabupaten

flu

0

oleh

Frekuensi

60

Temu Kembali Informasi: Rekonstruksi Inverted Index dan Implementasi Stopwords Wayan Sriyasa/G651080154 Departemen Ilmu Komputer, FMIPA, IPB

Pada grafik sebaran frekuensi kata diatas, terlihat bahwa sebaran tersebut memenuhi hukum Zipf, dimana kata-kata yang menjadi stopwords kurang lebih berkumpul pada bagian kiri dan kanan. Bagian inilah yang dapat kita abaikan karena tidak memberikan ciri terhadap dokumen yang bersangkutan. Kesimpulan Untuk mempercepat proses pencarian informasi, perlu dilakukan indexing terhadap masing-masing dokumen tersebut. Inverted index adalah salah satu teknik indexing yang cukup efektif dalam IR. Bagian penting dari inverted indexing adalah dictionary yang berisi pointer mengarah ke list posting. Tidak semua kata/term dapat menjadi penciri sebuah dokumen. Kata/term yang bukan merupakan penciri sebuah dokumen disebut sebagai stopwords. Peranan kata/term sebagai penciri sebuah dokumen dapat ditentukan dengan menghitung idft dimana semakin tinggi nilai-nya menunjukkan semakin penting kata tersebut dalam mencirikan swebuah dokumen. Selain idft , faktor lain yang juga berperan dalam penentuan ciri adalah dengan menentukan bobot dari suatu dokumen yaitu dengan menghitung bobot komposit dari setiap kata/term di setiap dokumen. Referensi ----------------. http://nlp.stanford.edu/IR-book/html/htmledition/irbook.html ----------------. http://en.wikipedia.org/wiki/Natural_language_processing Adisantoso, J; dan Ridha, A. 2009. Materi Kuliah: Sistem Temu Kembali Informasi. Istitut Pertanian Bogor. Indonesia. Feldman, R; Sanger, J. 2007. THE TEXT MINING HANDBOOK: Advanced Approaches in Analyzing Unstructured Data. Cambridge University Press. USA. Manning, C.D; Raghavan, P Dan Schutze, H. 2008. Introduction To Information Retrieval. Cambridge University Press. USA. Rijsbergen, C.J. 2008. Information Retrieval. Department Of Computing Science, University Of Glasgow. USA.

8

Temu Kembali Informasi: Rekonstruksi Inverted Index dan Implementasi Stopwords Wayan Sriyasa/G651080154 Departemen Ilmu Komputer, FMIPA, IPB

Lampiran script: ################################################## ## variable file yang akan dipakai: ## ## OUT => simpan frekuensi kata ditiap dokumen ## ## OUT2 => simpan dictionary tanpa stopwords ## ## OUT3 => simpan dicitonary dengan stopwords ## ################################################## open(IN, "korpus.txt") or die("File not found..."); open(OUT, ">tf.csv"); open(OUT2,">nostopwords.csv"); open(OUT3, ">stopwords.csv"); ################################################# ## Variable untuk hitung jumlah dokumen ## ################################################# $JumDok = -1; $JumDok1 = 0; $/ = "\n"; ################################################# ## Step 1: Buat inverted index ## ################################################# while () { $JumDok++; $JumDok1++; chomp; ## baca judul dokumen if ($_=~ /<TITLE>(.*)<\/TITLE>/) { $judul[$JumDok] = $1; print "Judul ke-$JumDok1 = $judul[$JumDok]\n"; } ## Baca isi dokumen disetiap judul while (m/<(TITLE|TEXT)>(.+)<\/\1>/gs) { ## Buang tanda baca standar Perl (my $text = $2) =~ s/[[:punct:]]+//gs; ## parsing kata ditiap dokumen while ($text =~ m/\b([[:alpha:]]+)\b/gs) { ## convert jd huruf kecil $kata = lc $1; ## simpan frekuensi kata ditiiap dokumen ke variabel tf (posting) ++$tf[$JumDok]{$kata}; ## simpan frekuensi kata diseluruh dokumen (dicitionary) ++$dictio{$kata}; ## tulis ke file tf.csv print OUT "Dokumen ke: $JumDok1, $kata,$tf[$JumDok]{$kata}\n"; } } } ################################################# ## Step 2. hitung frekeunsi kemunculan kata ## ## ditiap dokumen dalam korpus --> df ## ## hitung idf = LOG(N/df) dan tf*idf ## ################################################# $n = $#tf + 1; foreach $x (sort keys %dictio){ $Jum = 0; for $i (0..$#tf) { if ($tf[$i]{$x} > 0 ) { $Jum++; } if ($Jum > 0 ) { $df{$x} = $Jum; $bobot[$i]{$x} = log($n/$df{$x})/log(2);

9

Temu Kembali Informasi: Rekonstruksi Inverted Index dan Implementasi Stopwords Wayan Sriyasa/G651080154 Departemen Ilmu Komputer, FMIPA, IPB } } } ################################################## ## Step3. Bikin index dengan dan tanpa stopwords## ## stopwords dipilih dengan kategori ## ## kata yang memiliki 1 1) { print OUT3 "$x, $dictio{$x}, $df{$x}.\n"; } } ################################################# ##Bikin index tanpa stopwords ## ################################################# foreach $x (sort keys %dictio) { print OUT2 "$x,$dictio{$x},$df{$x}\n"; } #################################################### ## Cetak ke layar informasi ## ## jumlah dokumen yang di-index ## #################################################### print "Sebanyak $JumDok1 dokumen telah di-index.\n"; ####################################################

10