Algoritma Boyer-Moore

Algoritme Boyer-Moore adalah salah satu algoritme pencarian string, dipublikasikan oleh Robert S. Boyer, dan J. Strother Moore pada tahun 1977.

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 $teks[i..i+n-1]$, dan anggap ketidakcocokan pertama terjadi di antara $teks[i+j]$ dan $pattern[j]$, dengan $0<j<n$. Berarti, $teks[i+j+1..i+n-1]=pattern[j+1..n-1]$ dan $a=teks[i+j]$ tidak sama dengan $b=pattern[j]$. Jika $u$ adalah akhiran dari pattern sebelum $b$ dan $v$ adalah sebuah awalan dari pattern, maka penggeseran-penggeseran yang mungkin adalah:

1. Penggeseran good-suffix yang terdiri dari menyejajarkan potongan $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 $pattern[j]$. Jika tidak ada potongan seperti itu, maka algoritme akan menyejajarkan akhiran $v$ dari $teks[i+j+1..i+n-1]$ dengan awalan dari pattern yang sama.
2. Penggeseran bad-character yang terdiri dari menyejajarkan $teks[i+j]$ dengan kemunculan paling kanan karakter tersebut di pattern. Bila karakter tersebut tidak ada di pattern, maka pattern akan disejajarkan dengan $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.

Pseudocode

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

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.

Lihat pula

• Daftar algoritme
• Algoritme pencarian string
• Algoritme Knuth-Morris-Pratt

Pranala luar

• Artikel original tentang Boyer-Moore
• Halaman berisi penjelasan tentang Boyer-Moore dan juga sebuah applet yang menganimasikan cara kerjanya