Algoritma Turbo Boyer-Moore

Algoritma Turbo Boyer-Moore

Berbicara mengenai algoritma Turbo Boyer-Moore maka tidak terlepas dari algoritma pendahulunya yaitu algoritma Boyer-Moore. Algoritma Boyer-Moore adalah algoritma pencarian string yang dipublikasikan pertama kali oleh Robert S. Boyer, dan J. Strother Moore pada tahun 1977.

Menurut Christian Thierry Charras dalam bukunya Handbook of Exact String Matching Algorithm mengatakan algoritma Boyer-Moore adalah algoritma yang paling efisien pada aplikasi umum. Algoritma Boyer-Moore bekerja dengan memulai pencocokan pattern dari kanan bukan dari kiri. Dengan memulai pencocokan karakter dari kanan, maka akan lebih banyak informasi yang didapat (Boyer, 1977).

Bila dibandingkan dengan algoritma Boyer-Moore, algoritma Turbo Boyer-Moore tidak membutuhkan pemrosesan ekstra. Algoritma ini mengingat faktor dari teks yang cocok dengan akhiran dari pattern selama attempt terakhir. Dengan demikian, teknik ini mempunyai dua keunggulan (Charras, 2001):

1. Teknik ini memungkinkan untuk melompati faktor dari teks tersebut.
2. Teknik ini mengijinkan sebuah penggeseran turbo.

Algoritma Boyer-Moore menggunakan dua shift function yang dinamakan good suffix shift dan bad character shift. Untuk lebih jelasnya misalkan ada sebuah teks T[i…i+n-1] dan pattern P[i…i+m-1] dengan m < n dimana dilakukan pencocokan dan pencocokan terjadi pada T[i…i+n-1], dan ketidakcocokan pertama terjadi diantara T[i+j] dan P[j], dengan 0 < j < n. Berarti, T[i+j+1…i+n-1] = P[j+1…n-1] dan a = T[i+j] ≠ b = P[j].

Algoritma Turbo Boyer-Moore mengijinkan suatu pergeseran turbo yang dapat terjadi bila attempt yang sedang dilakukan, akhiran dari pattern yang cocok dengan teks yang lebih pendek dari bagian teks yang diingat dari attempt sebelumnya. Misalkan v1 adalah faktor dari attempt sebelumnya, maka v2 adalah bagian dari pattern yang cocok pada attempt yang sedang dilakukan pengecekan, sehingga v1zv2 adalah akhiran dari pattern. Kemudian anggap a adalah karakter di teks dan b adalah karakter dari pattern yang sedang dicocokan pada attempt tersebut. Maka av2, adalah akhiran dari pattern, dan juga akhiran dari v1 ketika |v2|<|v1|. Dua karakter a dan b muncul dengan jarak p di teks, dan kahiran dari v1=v2 dari pattern mempunyai periode p=|zv2|, karena v1 merupakan pinggiran dari v1zv2, sehingga tidak mungkin melewati dua kemunculan karakter a dan b di teks. Pergeseran terkecil yang mungkin dilakukan adalah sebesar |v1|-|v2|, yang disebut sebagai pergeseran turbo.

Berikut ini adalah pseudocode dari algoritma Turbo Boyer-Moore (Gozali, 2009) :

Procedure fillBadChar(input pattern:string)
{digunakan untuk mengisi tabel badchar}
m,n,j,shift,ts,bcs,k : integer
makeRightMostTable(pattern)
j  <- 0="" br="" u=""> m <- br="" pattern.length=""> shift <- br="" m=""> while i <= tabel.indeks do
j <- 0="" br=""> y <- nama_tabel="" tabel="">.atribut[i]
n <- br="" y.length=""> while (j <= n-m) do
k = m-1
while k >= 0 and x[k]=y[k+j]
-1
if u≠0 and k=m-1-shift then
k <- br="" k-u=""> end if
end while
if i<0 br="" then=""> shift <- br="" goodsuffix=""> u <- -="" br="" m="" shift=""> else
v = m – 1 – k
ts <- 1="" badchar="" br="" i="" j="" k="" m="" y=""> shift <- bcs="" br="" max="" ts=""> if(shift = goodsuffix[i]) then
u = min(m-shift,v)
else
if(ts < bcs) then
shift <- br="" mac="" shift="" u=""> end if
u <- br="" o=""> end if
end if
end while
end while

Gambar.1 Pergeseran turbo (Tjung, 2009 : 34)

Technorati Tags: Algorithm,String Matching

Gambar.2 Pergeseran turbo
Keterangan : Jika pergeseran harus lebih dari |v1|+1 (Tjung, 2009 : 34)

Misalkan terjadi kasus dimana |v2|>|v1|, dan panjang dari pergeseran bad-character lebih besar dari pergeseran good-suffix maupun pergeseran turbo. Seperti pada Gambar.1, dengan 2 karakter c dan d yang berbeda karena jika v1≠0 maka penggeseran sebelumnya adalah penggeseran good suffix. Sebagai akibatnya, jika penggeseran dengan panjang yang lebih besar dari penggeseran turbo namun lebih kecil dari |v1|+1 maka c dan d akan disejajarkan dengan karakter yang sama di teks. Oleh karena itu, dalam kasus ini panjang penggeseran minimal adalah |v1|+1 yang dapat dilihat pada Gambar.2.

Nah berikut ini adalah koding dari algoritma Turbo Boyer-Moore dalam JAVA :

Import java.util.ArrayList;

import java.util.List;

public class TBM

{

  private int m;

  private int[] bmGs;

  private int[] bmBc;

  private char[] x;

  private static void preBmBc(char[] x, int[] bmBc)

  {

    int m = x.length;

    for (int i = 0; i < bmBc.length; i++)

      bmBc[i] = m;

    for (i = 0; i < m - 1; i++)

      bmBc[x[i]] = (m - i - 1);

  }

  private static void suffixes(char[] x, int[] suff) {

    int f = 0; int m = x.length;

    suff[(m - 1)] = m;

    int g = m - 1;

    for (int i = m - 2; i >= 0; i--)

      if ((i > g) && (suff[(i + m - 1 - f)] < i - g)) {

        suff[i] = suff[(i + m - 1 - f)];

      } else {

        if (i < g)

          g = i;

        f = i;

        while ((g >= 0) && (x[g] == x[(g + m - 1 - f)]))

          g--;

        suff[i] = (f - g);

      }

  }

  private static void preBmGs(char[] x, int[] bmGs)

  {

    int m = x.length;

    int[] suff = new int[m];

    suffixes(x, suff);

    for (int i = 0; i < m; i++)

      bmGs[i] = m;

    int j = 0;

    for (i = m - 1; i >= 0; i--)

      if (suff[i] == i + 1)

        for (; j < m - 1 - i; j++)

          if (bmGs[j] == m)

            bmGs[j] = (m - 1 - i);

    for (i = 0; i <= m - 2; i++)

      bmGs[(m - 1 - suff[i])] = (m - 1 - i);

  }

  public static List findAll(String pattern, String source) {

    char[] x = pattern.toCharArray(); char[] y = source.toCharArray();

    int m = x.length; int n = y.length;

    List result = new ArrayList();

    int[] bmGs = new int[m];

    int[] bmBc = new int[65536];

    preBmGs(x, bmGs);

    preBmBc(x, bmBc);

    int u;

    int j = u = 0;

    int shift = m;

    while (j <= n - m) {

      int i = m - 1;

      while ((i >= 0) && (x[i] == y[(i + j)])) {

        i--;

        if ((u != 0) && (i == m - 1 - shift))

          i -= u;

      }

      if (i < 0) {

        result.add(Integer.valueOf(j));

        shift = bmGs[0];

        u = m - shift;

      } else {

        int v = m - 1 - i;

        int turboShift = u - v;

        int bcShift = bmBc[y[(i + j)]] - m + 1 + i;

        shift = Math.max(turboShift, bcShift);

        shift = Math.max(shift, bmGs[i]);

        if (shift == bmGs[i]) {

          u = Math.min(m - shift, v);

        } else {

          if (turboShift < bcShift)

            shift = Math.max(shift, u + 1);

          u = 0;

        }

      }

      j += shift;

    }

    return result;

  }

  public static TBM compile(String pattern) {

    char[] x = pattern.toCharArray();

    int m = x.length;

    int[] bmGs = new int[m];

    int[] bmBc = new int[65536];

    preBmGs(x, bmGs);

    preBmBc(x, bmBc);

    TBM tbm = new TBM();

    tbm.m = m;

    tbm.bmBc = bmBc;

    tbm.bmGs = bmGs;

    tbm.x = x;

    return tbm;

  }

  public List findAll(String source) {

    char[] y = source.toCharArray();

    int n = y.length;

    List result = new ArrayList();

    int u;

    int j = u = 0;

    int shift = this.m;

    while (j <= n - this.m) {

      int i = this.m - 1;

      while ((i >= 0) && (this.x[i] == y[(i + j)])) {

        i--;

        if ((u != 0) && (i == this.m - 1 - shift))

          i -= u;

      }

      if (i < 0) {

        result.add(Integer.valueOf(j));

        shift = this.bmGs[0];

        u = this.m - shift;

      } else {

        int v = this.m - 1 - i;

        int turboShift = u - v;

        int bcShift = this.bmBc[y[(i + j)]] - this.m + 1 + i;

        shift = Math.max(turboShift, bcShift);

        shift = Math.max(shift, this.bmGs[i]);

        if (shift == this.bmGs[i]) {

          u = Math.min(this.m - shift, v);

        } else {

          if (turboShift < bcShift)

            shift = Math.max(shift, u + 1);

          u = 0;

        }

      }

      j += shift;

    }

    return result;

  }

}