Pencarian Dokumen Menggunakan Operator Boolean

1. Pendahuluan

Sebagai tugas dalam mata kuliah Pemrosesan Teks, dibuat program sederhana pencarian dokumen berdasarkan kata-kata, bekerja sesuai operator boolean dan menggunakan bahasa pemrograman Perl. Program membaca suatu file korpus dengan struktur tertentu, menghasilkan file indeks (inverted), yang selanjutnya file tersebut digunakan dalam pencarian kata. Program bekerja menggunakan antarmuka baris perintah (command line interface) pada masukan maupun keluaran.

Tujuan yang diharapkan dari pembuatan program yaitu:

  1. Membaca file (Koleksi.txt) dan mengambil data yang diperlukan (TITLE dan TEXT).
  2. Melakukan tokenisasi pada teks (kata per kata), sebelumnya semua tanda baca dibuang.
  3. Membuat struktur data untuk penyusunan inverted index, termasuk penyimpanan dan pembacaan file indeks untuk pencarian.
  4. Pencarian kata dan membuat peringkat hasil dari dokumen yang ditemukan (menggunakan pembobotan tf x idf). Operator boolean yang didukung adalah AND.

2. Struktur Data dan Algoritma

Penyimpanan indeks menggunakan module Storable (persistence data structures), dengan demikian seluruh data terkait disusun dalam suatu hash. Penyimpanan dan pengambilan indeks melalui fungsi store dan retrieve. Berikut struktur data dari hash rec.

Field

Keterangan

Contoh

N_dok

Total dokumen

30

kata

Hash frekuensi kata pada tiap dokumen, format = kata: dokumen { frekuensi }

harga: 3 {2}, 5 {1}

minyak: 1 {2}, 3 {1}, 5 {2}

pos_dok

Array Posisi awal dokumen pada korpus

(0, 1023, 2011, 4010)

Pembuatan inverted index dilakukan dengan memasukkan kata dalam hash rec{kata}, setelah proses tokenisasi dari teks menjadi kata. Setiap kata yang tersimpan dalam hash secara otomatis optimal untuk pencarian. Banyak dokumen yang mengandung kata (n) dapat diketahui dari panjang hash tersebut. Posisi awal tiap-tiap dokumen disimpan untuk nantinya digunakan dalam membaca teks dan menampilkan hasil (seek file ke posisi tertentu).

Pencarian kata pada indeks dilakukan menurut tahap berikut:

  1. Pada setiap kata yang dicari dilakukan pencarian (lookup) pada hash rec{kata} yang hasilnya adalah hash dok{frekuensi} dari tiap-tiap kata.
  2. Operasi AND dilakukan dengan membuat hash and{kata} dan mengisi hash tersebut sesuai nomor dokumen yang ditemukan (kompleksitas θ(n)). Dokumen hasil adalah item pada hash yang memiliki jumlah sebanding dengan banyaknya kata yang dicari.
  3. Pembobotan dokumen menggunakan tf x idf, dilakukan bersamaan dengan operasi AND. Caranya dengan mengisi hash bobot{kata} sesuai frekuensi kata pada dokumen yang ditemukan, dikali log2(N_dok / n dok). Bobot ini akan digunakan dalam pengurutan hasil.

Hasil pencarian berupa array hasil (berisi nomor dokumen) lalu diurutkan menurut bobot. Teks dokumen selanjutnya dibaca dari file korpus dan diambil bagian yang cukup mewakili yaitu DOCID dan TITLE. Sebagai hasil akhir ditampilkan nomor, docid, title dan bobot. Agar tidak terlalu banyak, tampilan dibatasi 20 dokumen paling atas.

3. Pemakaian Program

Program terbagi 2, yaitu indexer.pl untuk membaca file korpus (Koleksi.txt) dan membuat file indeks (index.dat) serta search.pl untuk membaca file indeks dan melakukan pencarian. Berikut contoh dari pemakaian indexer.pl dan search.pl.

[wawan@wawan_gtw ~]$ ./indexer.pl

Indeks 30 dokumen selesai.

[wawan@wawan_gtw ~]$ ./search.pl harga minyak

  1.  DOK-13  Harga Minyak Jatuh Karena Dolar Menguat [52.788]

  2.  DOK-25  Ambil Untung Tekan IHSG BEI Selasa Pagi [13.662]

  3.  DOK-11  Konsumsi BBM PLN Ditargetkan 7,91 Juta Kiloliter [11.814]

[wawan@wawan_gtw ~]$ ./search.pl harga minyak mahal

1. DOK-13 Harga Minyak Jatuh Karena Dolar Menguat [57.695]

[wawan@wawan_gtw ~]$ ./search.pl harga minyak mahal sekali

— dokumen tidak ditemukan —

4. Penutup

Meskipun program sudah berjalan baik, tetapi dalam banyak hal dapat ditingkatkan lebih lanjut. Misalnya efisiensi pada file indeks (Storable) yang sangat boros tempat. Selanjutnya operator boolean yang didukung dapat ditingkatkan, misalnya or dan not. Pada akhirnya, semoga program sederhana ini dapat bermanfaat sebagai pembelajaran lebih lanjut pada topik Pemrosesan Teks.

5. Lampiran

1. Contoh Koleksi.txt

<DOC>
<DOCID> DOK-13 </DOCID>
<TITLE> Harga Minyak Jatuh Karena Dolar Menguat </TITLE>
<TEXT>
New York, (ANTARA News) – Harga minyak jatuh pada Kamis waktu setempat, atau Jumat pagi WIB, seiring menguatnya dolar AS dan kekhawatiran permintaan yang mengalahkan Badai Ike.
</TEXT>
</DOC>

2. File indexer.pl

#!/usr/bin/perl
# indexer.pl

use strict;
use Storable;

# baca dari file Koleksi.dat; pemisah record = </DOC>
# manual Perl: $/ = The input record separator, newline by default.
open(FH, "Koleksi.txt") or die("Koleksi.txt: $!");
$/ = "</DOC>\n";

# struktur data untuk index.dat
my %rec = (         
  'N_dok'=>0,       # total dokumen
  'kata'=>{},       # hash frekuensi kata, kata: dok{frek}
  'pos_dok'=>()     # array posisi awal tiap record
  );

# simpan posisi 0 untuk dokumen ke-1
push @{$rec{'pos_dok'}}, 0;
my $N_dok = 0;

while (<FH>) {
  # tambah jumlah dokumen
  $N_dok++;
  # simpan posisi awal dokumen
  push @{$rec{'pos_dok'}}, tell FH;
  # ambil hanya title dan text
  while (m/<(TITLE|TEXT)>(.+)<\/\1>/gs) {
    # buang tanda baca (standar perl)
    (my $text = $2) =~ s/[[:punct:]]+//gs;
    # tambahkan frekuensi kata dari tiap-tiap dokumen
    while ($text =~ m/\b([[:alpha:]]+)\b/gs) {
      $rec{'kata'}{lc $1}{$N_dok}++;
    }
  }
}

# simpan data ke file index.dat
$rec{'N_dok'} = $N_dok;
store \%rec, 'index.dat';

print "Indeks $N_dok dokumen selesai.\n";
3. File search.pl
#!/usr/bin/perl
# search.pl

use strict;
use Storable;

# periksa kata yg dicari dari argumen --
die("Sintak: $0 <kata 1> <kata 2> ... <kata n>\n") if !@ARGV;

# ambil index + data dari file index.dat --
my $rec = retrieve('index.dat');
my %and = (); my %bobot = (); my $x;

# proses tiap-tiap kata yg dicari --
foreach my $str (@ARGV) {
  # ambil hash dari kata --
  last if (!$rec->{'kata'}{lc $str});
  my %hash = %{ $rec->{'kata'}{lc $str} };
  my @key = keys %hash;
  # hitung idf per kata untuk bobot dokumen --
  my $idf = log($rec->{'N_dok'} / scalar @key) / log(2);
  # jumlahkan dokumen per kata, hitung bobot tf x idf --
  foreach $x (@key) { 
    $and{$x}++;
    $bobot{$x} += $hash{$x} * $idf;
  }
}

# periksa dokumen yg jumlah kata == dicari --
my @hasil = ();
foreach $x (keys %and)
  { push @hasil, $x if $and{$x} == scalar @ARGV }

# hentikan bila tidak didapat hasil --
die("-- dokumen tidak ditemukan --\n") if !@hasil;

# urutkan dokumen hasil sesuai bobot --
my @urut = sort { $bobot{$b} <=> $bobot{$a} } @hasil;

# baca dari file Koleksi.dat; record separator = </DOC> --
open(FH, "Koleksi.txt") or die("Koleksi.txt: $!");
$/ = "</DOC>\n";

my $nomor = 0; my $str;
foreach $x (@urut) {
  # ambil text dari awal dokumen --
  seek(FH, $rec->{'pos_dok'}[$x-1], 0);
  next if (!($str = <FH>));
  # cetak nomor, docid, title dan bobot --
  printf "%3d. ", ++$nomor;
  print $2 while ($str =~ m/<(DOCID|TITLE)>(.+)<\/\1>/gs);
  printf "[%2.3f]\n", $bobot{$x};
  # batasi hingga 20 baris --
  last if $nomor >= 20;
}

4 Komentar »

  1. aang nahrowi said

    Boleh Minta email mpu gondrong,ada yg mau ditanyaain ttg perl??

  2. eka said

    saya pengen coba ya programnya.. mudah2n ini bisa membantu saya dalam menyelesaikan tugas akhir sistem informasi retrieval saya.

  3. eka said

    mas boleh minta emailnya ga? mohon kesediaanya dalam membatu tgs saya ya mas gondrong..
    keliatannya jago ni perlnya…

  4. ayiz said

    Mpu…saya mau tanya klo use strict; use Storable; fungsinya buat apa ya?trus apa ada codingnya?
    kalo bisa minta emailnya juga ya…

    Trima kasih Mpu Gondrong…

RSS feed for comments on this post · TrackBack URI

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s