KINERJA ALGORITMA PARALEL UNTUK PENCARIAN KATA DENGAN METODE BOYER-MOORE MENGGUNAKAN PVM

KINERJA ALGORITMA PARALEL UNTUK PENCARIAN KATA DENGAN METODE BOYER-MOORE MENGGUNAKAN PVM

Maria Angela Kartawidjaja, Stania Vandika

ABSTRAK

Proses pencarian merupakan salah satu kegiatan penting dalam pemrosesan data. Proses pencarian dapat menghabiskan waktu jika ruang pencariannya besar, dan karena itu diperlukan suatu teknik pencarian yang efisien. Salah satu teknik yang dapat digunakan adalah komputasi parallel. proses pencarian kata secara paralel dengan menggunakan algoritma Boyer-Moore. Lingkup paralel diemulasikan menggunakan perangkat lunak PVM Parallel Virtual Machine. Dari hasil penelitian dapat disimpulkan bahwa kinerja komputasi paralel pencarian kata akan meningkat jika dibandingkan dengan kinerja komputasi sekuensial untuk pencarian kata yang terdiri dari satu huruf, dan akan menurun untuk pencarian kata yang terdiri dari dua huruf atau lebih.

PENCARIAN KATA DENGAN METODE BOYER-MOORE

Pencarian kata bertujuan untuk mencari sebuah kata yang terdiri dari beberapa karakter dalam sekumpulan kata. Kata yang akan dicari disebut sebagai kata kunci atau keywords. Prinsip dasar pencarian kata adalah pencocokan karakter-karakter kata kunci dengan karakter-karakter kata yang tersedia. Misalnya suatu kata kunci yang panjangnya m karakter akan dicari didalam sekumpulan kata yang terdiri dari n karakter dengan ketentuan n ≥ m.

Pada metode ini pencocokan kata dimulai dari karakter terakhir kata kunci menuju karakter awalnya. Jika terjadi perbedaan antara karakterter  akhir kata kunci  dengan kata yang dicocokkan, maka karakter-karakter dalam potongan kata yang dicocokkan tadi akan diperiksa satu per satu. Hal ini dimaksudkan untuk mendeteksi apakah ada karakter dalam potongan kata tersebut yang sama dengan karakter yang ada pada kata kunci. Apabila terdapat kesamaan, maka kata kunci akan digeser sedemikian rupa sehingga posisi karakter yang sama terletak sejajar, dan kemudian dilakukan kembali pencocokan karakter terakhir dari kata kunci. Sebaliknya jika tidak terdapat kesamaan karakter, maka seluruh karakter kata kunci akan bergeser ke kanan sebanyak m karakter, di mana m adalah panjang karakter dari kata kunci.

Ilustrasi pencarian kata, kata kunci "roni" pada kata "elektronik"

Dari Gambar 1(a), dapat dilihat bahwa karakter terakhir dari kata kunci adalah huruf "i" yang dicocokkan dengan huruf "k" pada kata "elektronik". Karena huruf "i" dan huruf "k" berbeda, maka akan dilakukan pencocokan huruf"k"dengan seluruh karakter  pada kata kunci. Karena huruf "k" tidak terdapat pada seluruh karakter kata kunci, maka kata kunci bergeser ke kanan sebanyak empat karakter sesuai dengan panjang karakter kata kunci seperti yang tampak pada Gambar 1(b).

Setelah dilakukan pergeseran, maka  dicocokkan kembali karakter terakhir pada  kata kunci yaitu huruf "i" dengan huruf "n". Karena kedua huruf ini berbeda, maka huruf "n" dicocokkan dengan keseluruhan karakter pada kata kunci. Karena pada kata kunci terdapat huruf "n", maka kata kunci akan bergeser sedemikian rupa sehingga huruf "n" pada kata kunci memiliki posisi yang sejajar dengan posisi huruf "n" pada kata yang dicocokkan seperti yang ditunjukkan pada Gambar 1(c).

Setelah itu dilakukan kembali pencocokan karakter terakhir pada kata kunci,yaitu huruf"i"dengan karakter yang terletak sejajar dengan huruf "i" tersebut. Karena karakter tersebut sama maka dicocokkan kembali karakter berikut yang berada di sebelah kiri huruf "i" sehingga keseluruhan karakter pada kata kunci selesai diperiksa.

KOMPUTASI PARALEL 

Komputasi paralel dalam pencarian kata bertujuan untuk mempersingkat waktu pencarian suatu kata kunci di dalam sekumpulan kata yang jika dilakukan pada satu komputer akan membutuhkan waktu yang panjang.

Pada konsep komputasi paralel ada beberapa ukuran yang umum digunakan dalam mengevaluasi kinerja sistem. Beberapa di antaranya adalah waktu eksekusi suatu  program, peningkatan kecepatan (speedup), effisiensi prosesor, efisiensi memori dan biaya. Pada penelitian ini digunakan waktu eksekusi dan peningkatan kecepatan untuk mengukur kinerja komputasi paralel. Pada suatu program paralel waktu eksekusi suatu program merupakan gabungan antara waktu komputasi dan waktu komunikasi, sehingga waktu eksekusi pada p proses dapat dinyatakan dengan :

                                    tp = tkomputasi + tkomunikasi  

dan peningkatan kecepatan proses atau speedup dapat dinyatakan dengan :

 dengan: t1  = waktu eksekusi pada satu proses.

                tp = waktu eksekusi pada proses.

                p  = jumlah proses. 

Peningkatan kecepatan proses adalah suatu besaran tak berdimensi yang nilainya berkisar antara 1 dan p, atau secara matematis dinyatakan dengan :

Peningkatan kecepatan proses dalam Persamaan disebut sebagai peningkatan kinerja relative, yang mengukur seberapa besar peningkatan kinerja komputasi yang dapat diperoleh dengan menggunakan sejumlah prosesor yang bekerja  bersama-sama dalam memecahkan suatu masalah.

PVM (PARALLEL VIRTUAL MACHINE)

PVM adalah suatu perangkat lunak yang dapat digunakan untuk mengemulasikan suatu lingkup paralel. Perangkat lunak ini dapat digunakan dalam sistem yang homogen maupun heterogen. Sistem PVM terdiri dari dua bagian, yaitu daemon dan kumpulanpustaka. Daemonter letak  pada semua komputer dan membentuk suatu lingkup kerja maya(virtual). Kumpulan pustaka dibutuhkan untuk melakukan kerjasama antara proses. Pustaka ini disediakan dalam Bahasa pemrograman C dan Fortran. PVM memungkinkan pembentukan sekumpulan proses yang tidak tergantung pada jumlah prosesor yang digunakan. Masing-masing proses dalam PVM memiliki suatu identifikasi yang unik. Setiap proses akan dipetakan pada prosesor secara otomatis kecuali jika diprogram secara eksplisit oleh pengguna. Pemrograman dengan PVM umumnya menggunakan model master-slave, di mana pada awalnya hanya ada satu proses yang berjalan yaitu proses master, dan kemudian proses master ini akan "menciptakan" (spawn) proses slave. Selain melakukan komputasi, proses master bertanggung jawab atas pembentukan proses-proses slave, inisialisasi, pengiriman dan pengumpulan data. Sedangkan proses slave hanya melakukan komputasi, yang beban kerjanya diatur oleh proses master. Hasil komputasi dari proses slave kemudian dikirim kembali ke master. Komunikasi antara proses master dan proses slave ini dilakukan dengan cara pengiriman pesan (message-passing)

PERANCANGAN SISTEM  

Proses master bertugas untuk melakukan seluruh kerja administrasi dan kerja komputasi. Sedangkan proses slave hanya bertugas melakukan komputasi. Komunikasi antar proses hanya berlangsung antara proses master dan proses slave, bukan antara sesama proses slave. Diagram alir kerja pada proses master ditunjukkan dalam Gambar 2, dan untuk proses slave dalam Gambar 3.

Gambar 2

Gambar 3

Langkah awal yang dilakukan proses master adalah inisialisasi semua data yang dibutuhkan seperti jumlah data, banyaknya proses yang digunakan, kata kunci yang dicari serta larik (array) untuk menampung kumpulan kata. Jika proses yang digunakan hanya satu, maka semua kumpulan kata akan digunakan oleh proses master untuk melakukan proses pencarian. Kumpulan kata akan dimasukkan ke dalam sebuah larik untuk digunakan dalam proses pencarian kata sesuai kata kunci. Setelah proses pencarian berakhir maka proses master akan menyimpan hasil yang diperoleh dalam suatu larik dan komputasi pun berakhir. Jika terdapat lebih dari satu proses, maka proses master melakukan spawning slave untuk menciptakan proses slave yang dibutuhkan. Kemudian proses master menghitung ukuran data yang akan dikirim kemasing-masing proses slave. Selanjutnya, proses master akan mengirim ukuran data tersebut beserta kata kunci ke proses slave. Langkah berikutnya, proses master melakukan pembacaan kata dari kumpulan data dan menyimpannya dalam suatu larik. Data tersebut kemudian dipartisi sesuai dengan jumlah proses  yangada. Lalu proses master mengirimkan partisidata ke masing-masing proses slave sedangkan partisi data miliknya tetap disimpan di dalam larik. Sesudah itu proses master melakukan pencarian kata sesuai dengan kata kunci, serta menyimpan hasil pencarian untuk digabungkan dengan hasil pencarian yang diterimanya dari proses slave.



========================================================================

IMPLEMENTASI ALGORITMA PARALEL UNTUK PENCARIAN KATA DENGAN METODE BOYER-MOORE MENGGUNAKAN PVM

Algoritme Boyer-Moore adalah salah satu algoritma pencarian string. Algoritme ini dianggap sebagai algoritme yang paling efisien pada aplikasi umum. Tidak seperti algoritme pencarian string yang ditemukan sebelumnya, algoritme Boyer-Moore mulai mencocokkan karakter dari sebelah kanan pattern. Ide di balik algoritme ini adalah bahwa dengan memulai pencocokan karakter dari kanan, dan bukan dari kiri, maka akan lebih banyak informasi yang didapat.

Cara Kerja :

Misalnya ada sebuah usaha pencocokan yang terjadi pada ${\displaystyle teks[i..i+n-1]}$, dan anggap ketidakcocokan pertama terjadi di antara ${\displaystyle teks[i+j]}$ dan ${\displaystyle pattern[j]}$, dengan ${\displaystyle 0<j<n}$. Berarti, ${\displaystyle teks[i+j+1..i+n-1]=pattern[j+1..n-1]}$ dan ${\displaystyle a=teks[i+j]}$ tidak sama dengan ${\displaystyle b=pattern[j]}$. Jika ${\displaystyle u}$ adalah akhiran dari pattern sebelum ${\displaystyle b}$ dan ${\displaystyle v}$ adalah sebuah awalan dari pattern, maka penggeseran-penggeseran yang mungkin adalah:

1. Penggeseran good-suffix yang terdiri dari menyejajarkan potongan ${\displaystyle teks[i+j+1..i+n-1]=pattern[j+1..n-1]}$ dengan kemunculannya paling kanan di pattern yang didahului oleh karakter yang berbeda dengan ${\displaystyle pattern[j]}$. Jika tidak ada potongan seperti itu, maka algoritme akan menyejajarkan akhiran ${\displaystyle v}$ dari ${\displaystyle teks[i+j+1..i+n-1]}$ dengan awalan dari pattern yang sama.
2. Penggeseran bad-character yang terdiri dari menyejajarkan ${\displaystyle teks[i+j]}$ dengan kemunculan paling kanan karakter tersebut di pattern. Bila karakter tersebut tidak ada di pattern, maka pattern akan disejajarkan dengan ${\displaystyle teks[i+n+1]}$.

Secara sistematis, langkah-langkah yang dilakukan algoritme Boyer-Moore pada saat mencocokkan string adalah:

1. Algoritme Boyer-Moore mulai mencocokkan pattern pada awal teks.
2. Dari kanan ke kiri, algoritme ini akan mencocokkan karakter per karakter pattern dengan karakter di teks yang bersesuaian, sampai salah satu kondisi berikut dipenuhi:
   1. Karakter di pattern dan di teks yang dibandingkan tidak cocok (mismatch).
   2. Semua karakter di pattern cocok. Kemudian algoritme akan memberitahukan penemuan di posisi ini.
3. Algoritme kemudian menggeser pattern dengan memaksimalkan nilai penggeseran good-suffix dan penggeseran bad-character, lalu mengulangi langkah 2 sampai pattern berada di ujung teks.

Kompleksitas
Tabel untuk penggeseran bad-character dan good-suffix dapat dihitung dengan kompleksitas waktu dan ruang sebesar O(n + σ) dengan σ adalah besar ruang alfabet. Sedangkan pada fase pencarian, algoritme ini membutuhkan waktu sebesar O(mn), pada kasus terburuk, algoritme ini akan melakukan 3n pencocokkan karakter, namun pada performa terbaiknya algoritme ini hanya akan melakukan O(m/n) pencocokkan.

Pseudecode

Berikut adalah pseudocode algoritme Boyer-Moore pada fase pra-pencarian:

procedure preBmBc(
    input P : array[0..n-1] of char,
    input n : integer,
    input/output bmBc : array[0..n-1] of integer
)
Deklarasi:
  i: integer

Algoritme:
  for (i := 0 to ASIZE-1)
     bmBc[i] := m;
  endfor
  for (i := 0 to m - 2)
     bmBc[P[i]] := m - i - 1;
  endfor

procedure preSuffixes(
    input P : array[0..n-1] of char,
    input n : integer,
    input/output suff : array[0..n-1] of integer
)

Deklarasi:
  f, g, i: integer

Algoritme:
  suff[n - 1] := n;
  g := n - 1;
  for (i := n - 2 downto 0) {
     if (i > g and (suff[i + n - 1 - f] < i - g))
        suff[i] := suff[i + n - 1 - f];
     else 
        if (i < g)
           g := i;
        endif
        f := i;
        while (g >= 0 and P[g] = P[g + n - 1 - f])
           --g;
        endwhile
        suff[i] = f - g;
     endif
  endfor

procedure preBmGs(
    input P : array[0..n-1] of char,
    input n : integer,
    input/output bmBc : array[0..n-1] of integer
)
Deklarasi:
  i, j: integer
  suff: array [0..RuangAlpabet] of integer

  preSuffixes(x, n, suff);

  for (i := 0 to m-1)
     bmGs[i] := n
  endfor
  j := 0
  for (i := n - 1 downto 0)
     if (suff[i] = i + 1)
        for (j:=j to n - 2 - i)
           if (bmGs[j] = n)
              bmGs[j] := n - 1 - i
           endif
        endfor
     endif
  endfor 
  for (i = 0 to n - 2)
     bmGs[n - 1 - suff[i]] := n - 1 - i;
  endfor

Dan berikut adalah pseudocode algoritme Boyer-Moore pada fase pencarian:

procedure BoyerMooreSearch(
    input m, n : integer,
    input P : array[0..n-1] of char,
    input T : array[0..m-1] of char,
    output ketemu : array[0..m-1] of boolean
)

Deklarasi:
i, j, shift, bmBcShift, bmGsShift: integer 
BmBc : array[0..255] of interger
BmGs : array[0..n-1] of interger

Algoritme:
preBmBc(n, P, BmBc) 
preBmGs(n, P, BmGs) 
i:=0
while (i<= m-n) do
    j:=n-1
    while (j >=0 n and T[i+j] = P[j]) do 
       j:=j-1
    endwhile
    if(j < 0) then
       ketemu[i]:=true;
    endif
    bmBcShift:= BmBc[chartoint(T[i+j])]-n+j+1
    bmGsShift:= BmGs[j]
    shift:= max(bmBcShift, bmGsShift)
    i:= i+shift

Contoh source code program sebagai berikut :

Hasil Program

Analisis dan Kesimpulan
Berdasarkan dari apa yang kami implementasikan yaitu pencarian kata menggunakan alogritma Boyer-Moore bahwasannya algoritme ini akan mencocokkan karakter per karakter pattern dari kanan ke kiri dengan karakter di teks yang bersesuaian.


Untuk file bisa di download disini


Nama Anggota kelompok : Umar Faruk (16051204015)
                                             Ilham Miftakhul Huda (16051204006)