Contoh-contoh komputer yang termasuk generasi pertama hingga generasi modern

 

Permasalahan String Processing

---

Nama : Muh Rifki Juliansyah

NPM : 19312023

Kelas IF 20 B

1. Definisi String Matching (Pencocokan String).

      Akibat perkembangan teknologi informasi dan komunikasi yang sangat pesat, pencarian informasi yang tepat dan sesuai kebutuhan menjadi sangat penting dengan semakin mudahnya memperoleh informasi dari seluruh dunia. Oleh karena itu, teknik untuk memperoleh dokumen dengan isi yang sesuai dengan kebutuhan informasi sangat diperlukan. Untuk mengetahui isi dokumen yang benar-benar sesuai dengan kebutuhan informasi, diperlukan metode pencarian string(string searching) isi dokumen yang bagus. Proses pencocokan string(string matching) yang merupakan bagian utama dalam proses pencaarian string memegang peranan penting untuk mendapatkan dokumen yang sesuai dengan kebutuhan informasi tersebut.

           Pencocokan string merupakan masalah yang hampir ditemukan dalam kegiatan sehari-hari, yaitu berhubungan dengan text-processing. Hal ini dimulai dari permasalahan sederhana sampai pada permasalahan yang kompleks.Pencarian pola string banyak diimplementasikan pada aplikasi-aplikasi antara lain pencarian string pada microsoft word,web browser,search engine,dan lainnya.

           Pengertian string menurut Dictionary of Algorithms and Data Structures, Nationanl Institute of Standards and Technology(NIST) adalah susunan dari karakter-karakter(angka,alfabet, atau karakter yang lain) dan biasanya direpresentasikan sebagai struktur data array. String berupa kata,frase, atau kalimat.

          Pencocokan string(string matching) menurut  Dictionary of Algorithms and Data Structure, National Institute of Standards and Technology(NIST),diartikan sebagai sebuah permasalahan untuk menemukan pola susunan karakter string dalam di dalam string lain atau bagian dari isi teks.Pencocokan string merupakan bagian penting dari sebuah proses pencarian string(string searching) dalam sebuah dokumen.Hasil dari pencarian sebuah string dalam dokumen tergantung dari teknik pencocokan string yang digunakan.

    Algoritma Pencocokan string merupakan algoritma yang digunakan untuk melakukan pencarian sebuah string yang terdiri dari beberapa karakter(yang biasa disebut pattern)dalam sejumlah besar teks.

2. Algoritma Pencocokan String Knuth-Morris-Pratt(KMP)

 Algoritma Knuth-Morris-Pratt merupakan salah satu algoritma pencarian string, yang dikembangkan secara terpisah oleh Donald E. Knuth pada tahun 1967 dan James H. Morris bersama Vayghan R. Pratt pada tahun 1966, kemudian dipublikasikan secara bersamaan pada tahun 1977. Algoritma Knuth-Morris-Pratt melakukan perbandingan karakter teks dan karakter pada pola dari kiri ke kanan. Ide dari algoritma ini adalah bagaimana memanfaatkan karakter-karakter pola yang sudah diketahui ada di dalam teks sampai terjadinya ketidakcocokan untuk melakukan pergeseran.

3.   Langkah-langkah Algoritma Pencocokan  String Knuth-Morris-Pratt.

Secara sistematis, langkah-langkah yang dilakukan algoritma Knuth-Morris-Pratt pada saat mecocokan string;

1. Algoritma Knuth-Morris-Pratt mulai mencocokan pattern pada awal teks.
2. Dari kiri ke kanan, algoritma ini akan mencocokan karakter per karakter pattern dengan karakter di teks yang bersesuaian, sampai salah satu kondisi berikut dipenuhi.
3. Karakter di pattern dan di teks yang dibandingkan tidak cocok(mismatch).
4. Semua karakter di pattern cocok. Kemudian algoritma akan memberitahukan penemuan diposisi ini.
5. Algortima kemudian menggeser pattern berdasarkan tabel, lalu mengulangi langkah 2 sampai pattern berada diujung teks.