String Matching

 

Pengertian Algoritma Pencarian String (String Matching)

Algoritma pencarian string atau sering disebut juga algoritma pencocokan string yaitu algoritma untuk melakukan pencarian semua kemunculan string  pendek dan dan panjang, untuk string pendek yang disebut pattern dan  string yang lebih panjang  yang disebut teks.

string pendek   =  pattern[0..n-1]

string panjang  = teks[0..m-1]

Algoritma pencarian string ini dapat juga diklasifikasikan menjadi 3 bagian menurut arah pencariannya ,berikut ini adalah  algoritma yang termasuk dalam algoritma ini.

Dari arah yang paling alami yaitu dari kiri ke kanan, yang merupakan arah untuk membaca, algoritma yang termasuk kategori ini adalah:

counter(li)Algoritma Brute Force.  Anda bisa membaca lebih detail tentang algoritma tersebut pada judul artikel ini "Algoritma Brute Force"

counter(li)Algoritma dari Morris dan Pratt, yang kemudian dikembangkan oleh Knuth, Morris, dan Pratt

Kategori kedua yaitu dari arah kanan ke kiri, arah yang biasanya menghasilkan hasil terbaik secara praktikal, contohnya adalah:

counter(li)Algoritma dari Boyer dan Moore, yang kemudian banyak dikembangkan, menjadi Algoritma turbo Boyer-Moore, Algoritma tuned Boyer-Moore, dan Algoritma Zhu-Takaoka;

Dan kategori terakhir yaitu adalah dari arah yang ditentukan secara spesifik oleh algoritma tersebut, arah ini menghasilkan hasil terbaik secara teoritis, algoritma yang termasuk kategori ini adalah:

counter(li)Algoritma Colussi

counter(li)Algoritma Crochemore-Perrin

Persoalan Pencarian String

Diberikan:

counter(li)teks (text), yaitu (long) string yang panjangnya n karakter

counter(li)pattern, yaitu string dengan panjang m karakter (m < n) yang akan dicari di dalam teks.

Carilah (find atau locate) lokasi pertama di dalam teks yang bersesuaian dengan pattern.untuk bisa memahami persoalan diatas maka akan saya berikan contoh dibawah ini.

Contoh 1:

Pattern: hari

Teks: kami pulang hari kamis

      target

Contoh 2:

Pattern: not

Teks: nobody noticed him

       target

Contoh 3:

Pattern: apa

Teks: Siapa yang menjemput Papa  dari kota Balikpapan? 

Contoh Pencarian String (String Matching) Dengan Algoritma Brute Force

Contoh 4:

Teks     : nobody noticed him

Pattern : not

nobody noticed him

s=0   not

s=1    not

s=2     not

s=3      not

s=4       not

s=5        not

s=6         not

s=7          not

Pada contoh di atas berhenti pada langkah ke 7 karena sudah menemukan kata yang cocok pada langkah ke 7

Contoh 5:

Teks:     10010101001011110101010001

Pattern:  001011

    10010101001011110101010001

s=0 001011

s=1  001011

s=2   001011

s=3    001011

s=4     001011

s=5      001011

s=6       001011

s=7        001011

s=8         001011

Pada contoh di atas berhenti pada langkah ke 8 karena sudah menemukan kata yang cocok pada langkah ke 8.

Kompleksitas dengan algoritma brute-force

Kompleksitas kasus terbaik adalah O(n).

Kasus terbaik terjadi jika yaitu bila karakter pertama pattern P tidak pernah sama dengan karakter teks T yang dicocokkan

Pada kasus ini, jumlah perbandingan yang dilakukan paling banyak n kali misalnya:

Teks:  String ini berakhir dengan zz

Pattern: zz

Artikel Oleh Sri Wahyuni A J

Daftar Pustaka

[Anany Levitin]-Intro_2_Design&Analysis_Algorithms