Algoritma Boyer-Moore

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

Algoritma ini dianggap sebagai algoritma yang paling efisien pada aplikasi umum.Lecroq, Thierry Charras, Christian. 2001. Handbook of Exact String Matching Algorithm. ISBN 0-9543006-4-5 Tidak seperti algoritma pencarian string yang ditemukan sebelumnya, algoritma Boyer-Moore mulai mencocokkan karakter dari sebelah kanan pattern. Ide di balik algoritma ini adalah bahwa dengan memulai pencocokan karakter dari kanan, dan bukan dari kiri, maka akan lebih banyak informasi yang didapat.Boyer, Robert Moore, J. 1977. A Fast String Searching Algorithm. Comm. ACM 20: 762–772 doi:

 Cara kerja 
Misalnya ada sebuah usaha pencocokan yang terjadi pada , dan anggap ketidakcocokan pertama terjadi di antara  dan , dengan . Berarti,  dan  tidak sama dengan . Jika  adalah akhiran dari pattern sebelum  dan  adalah sebuah awalan dari pattern, maka penggeseran-penggeseran yang mungkin adalah:
 Penggeseran good-suffix yang terdiri dari menyejajarkan potongan  dengan kemunculannya paling kanan di pattern yang didahului oleh karakter yang berbeda dengan . Jika tidak ada potongan seperti itu, maka algoritma akan menyejajarkan akhiran  dari  dengan awalan dari pattern yang sama.
 Penggeseran bad-character yang terdiri dari menyejajarkan  dengan kemunculan paling kanan karakter tersebut di pattern. Bila karakter tersebut tidak ada di pattern, maka pattern akan disejajarkan dengan .

Secara sistematis, langkah-langkah yang dilakukan algoritma Boyer-Moore pada saat mencocokkan string adalah:
 Algoritma Boyer-Moore mulai mencocokkan pattern pada awal teks.
 Dari kanan ke kiri, algoritma ini akan mencocokkan karakter per karakter pattern dengan karakter di teks yang bersesuaian, sampai salah satu kondisi berikut dipenuhi:
 Karakter di pattern dan di teks yang dibandingkan tidak cocok (mismatch).
 Semua karakter di pattern cocok. Kemudian algoritma akan memberitahukan penemuan di posisi ini.
 Algoritma 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 algoritma 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

 Algoritma:
   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

 Algoritma:
   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 algoritma 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

 Algoritma:
 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, algoritma ini membutuhkan waktu sebesar O(mn), pada kasus terburuk, algoritma ini akan melakukan 3n pencocokkan karakter, tetapi pada performa terbaiknya algoritma ini hanya akan melakukan O(m/n) pencocokkan.

 Referensi 

 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

Kategori:Algoritme string
Kategori:Algoritme pencarian