Algoritma pencarian string

Dari Wikipedia bahasa Indonesia, ensiklopedia bebas
Lompat ke: navigasi, cari

Algoritme pencarian string atau sering disebut juga pencocokan string adalah algoritme untuk melakukan pencarian semua kemunculan string pendek yang disebut pattern di string yang lebih panjang yang disebut teks.[1]

Algoritme-algoritme pencocokkan string dapat diklasifikasikan menjadi tiga bagian menurut arah pencariannya.

  • Dan kategori terakhir, dari arah yang ditentukan secara spesifik oleh algoritme tersebut, arah ini menghasilkan hasil terbaik secara teoretis, algoritme yang termasuk kategori ini adalah:
    1. Algoritme Colussi
    2. Algoritme Crochemore-Perrin

salah satunya algoritme SUSAN

Algoritme brute force dalam pencarian string[sunting | sunting sumber]

Algoritme brute force merupakan algoritme pencocokan string yang ditulis tanpa memikirkan peningkatan performa. Algoritme ini sangat jarang dipakai dalam praktik, namun berguna dalam studi pembanding dan studi-studi lainnya.

Cara kerja[sunting | sunting sumber]

Secara sistematis, langkah-langkah yang dilakukan algoritme brute force pada saat mencocokkan string adalah:

  1. Algoritme brute force mulai mencocokkan pattern pada awal teks.
  2. Dari kiri ke kanan, 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 terus menggeser pattern sebesar satu ke kanan, dan mengulangi langkah ke-2 sampai pattern berada di ujung teks.

Berikut adalah Algoritme brute force yang sedang bekerja mencari string:

Algoritme brute force yang sedang bekerja mencari string.

Pseudocode[sunting | sunting sumber]

Pseudocode algoritme brute force ini:

procedure BruteForceSearch(
        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: integer 

Algoritme:
        for (i:=0 to  m-n) do
               j:=0
               while (j < n and T[i+j] = P[j]) do    
                        j:=j+1
               endwhile
               if(j >= n) then
                         ketemu[i]:=true;
               endif 
        endfor

Referensi[sunting | sunting sumber]

  1. ^ (Inggris)Lecroq, Thierry Charras, Christian. 2001. Handbook of Exact String Matching Algorithm. ISBN 0-9543006-4-5

Lihat pula[sunting | sunting sumber]

Pranala luar[sunting | sunting sumber]