Algoritma Pencarian String (String Matching)

Algoritma Pencarian String (String Matching)

Algoritma Pencarian String (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:
    1. Algoritma Brute Force.  Anda bisa membaca lebih detail tentang algoritma tersebut pada judul artikel ini "Algoritma Brute Force"
    2. 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:
    1. 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:
    1. Algoritma Colussi
    2. Algoritma Crochemore-Perrin

Persoalan Pencarian String

Diberikan:
  1. teks (text), yaitu (long) string yang panjangnya n karakter
  2. 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


Semoga penjelasan singkat diatas membantu yaa? hehe


Kata Kunci : Algoritma Pencarian String (String Matching), Contoh Algoritma Pencarian String, Contoh Skripsi Teknik Informatika, Teknik Informatika,  Contoh Skripsi, Skripsi.

5 comments

avatar

Mantap gan ilmunya,,,,makasih udah di share

Balas
avatar

gan bisa share yang string mathing menggunakan optimal missmatch? terima kasih

Balas
avatar

Kalo tentang crochemore perrin ada gak?
Referensinya dikit banget

Balas
avatar

gan, algo ini kira" bisa digunakan untuk aplikasi chatbot ngga ya?

Balas
avatar

Contoh penerapan algoritmanya bagaimana?

Balas