Algoritma pencarian string

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

Algoritma pencarian string atau sering disebut juga pencocokan string adalah algoritma untuk melakukan pencarian semua kemunculan string pendek pattern[0..n-1] yang disebut pattern di string yang lebih panjang teks[0..m-1] yang disebut teks. [1]

Pencocokkan string merupakan permasalahan paling sederhana dari semua permasalahan string lainnya, dan dianggap sebagai bagian dari pemrosesan data, pengkompresian data, analisis leksikal, dan temu balik informasi. Teknik untuk menyelesaikan permasalahan pencocokkan string biasanya akan menghasilkan implikasi langsung ke aplikasi string lainnya[2].

Contoh algoritma pencocokkan string[sunting | sunting sumber]

Algoritma-algoritma pencocokkan string dapat diklasifikasikan menjadi tiga bagian menurut arah pencariannya.

Tiga kategori itu adalah :

salah satunya algoritma SUSAN

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

Algoritma brute force merupakan algoritma pencocokan string yang ditulis tanpa memikirkan peningkatan performa. Algoritma 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 algoritma brute force pada saat mencocokkan string adalah:

  1. Algoritma brute force mulai mencocokkan pattern pada awal teks.
  2. Dari kiri ke kanan, algoritma 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 algoritma akan memberitahukan penemuan di posisi ini.
  3. Algoritma kemudian terus menggeser pattern sebesar satu ke kanan, dan mengulangi langkah ke-2 sampai pattern berada di ujung teks.

Berikut adalah Algoritma brute force yang sedang bekerja mencari string:

Algoritma brute force yang sedang bekerja mencari string.

Pseudocode[sunting | sunting sumber]

Pseudocode algoritma 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 

Algoritma:
        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
  2. ^ (Inggris)Breslauer, Dany. 1992. Efficient String Algorithms. dokumen

Lihat pula[sunting | sunting sumber]

Pranala luar[sunting | sunting sumber]