Knuth-Morris-Pratt algorithm

String matching Knuth-Morris-Pratt algorithm

Idea

After a shift of the pattern, the naive algorithm has forgotten all information about previously matched symbols. So it is possible that it re-compares a text symbol with different pattern symbols again and again. This leads to its worst case complexity of Θ(nm) (n: length of the text, m: length of the pattern).
The algorithm of Knuth, Morris and Pratt [KMP 77] makes use of the information gained by previous symbol comparisons. It never re-compares a text symbol that has matched a pattern symbol. As a result, the complexity of the searching phase of the Knuth-Morris-Pratt algorithm is in O(n).
However, a preprocessing of the pattern is necessary in order to analyze its structure. The preprocessing phase has a complexity of O(m). Since mn, the overall complexity of the Knuth-Morris-Pratt algorithm is in O(n).

Personal Brand

Blog ini digunakan sebagai media komunikasi dan monitoring perkembangan penulisan paper ilmiah dengan judul Penyaringan Konten Dengan Menggunakan String Matching Pada Proses Deep Packet Inspection sebagai tugas akhir matakuliah Jaringan Informasi. Artikel-artikel dalam blog ini adalah artikel yang dikumpulkan dari berbagai sumber di internet, buku, tutorial CCNA dan juga tulisan penulis sendiri. Artikel-artikel tersebut digunakan sebagai bahan referensi dalam penyusunan paper ilmiah.

Paper ilmiah akan dibagi menjadi dua bagian yaitu Konseptual dan Implementasi . Paper konseptual akan membahas :

1.       Definisi Deep Packet Inspection

2.       Network Packet

3.       Definisi String Matching

4.       Algoritma Knuth-Morris-Pratt (KMP)

Contoh Penerapan String Matching - Algoritma Bruter Force

Definisi Deep Packet Inspection

Deep Packet Inspection

DPI adalah sebuah teknologi yang diterapkan di Router atau peralatan pemantau lainnya, yang memungkinkan untuk memantau aliran data secara real-time dan membuat keputusan terhadap aliran data tersebut.
DPI dapat melakukan pemeriksaan terhadap data dari header information hingga payload yang merupakan isi dari data-data yang dikirim melalui Router.
 

Beberapa fungsi dari DPI diantaranya:

1.      Network security

Sebagian besar DPI, digunakan oleh operator jaringan untuk melakukan deteksi serangan dan menyaring lalu lintas malware yang disalurkan kedalam jaringannya.

Perbedaan DPI dan IDS/IPS

Intrusion Detection System (IDS)/ Intrusion Prevention System (IPS) menggunakan packet header information sebagai parameter dalam pengambilan keputusan untuk melanjutkan paket atau tidak melanjutkan paket tersebut.. Keakuratan informasi yang diperoleh menjadi masalah dalam IDS/IPS karena keterbatasannya dalam mendapatkan informasi dari paket yang masuk, dimana IDS/IPS hanya memeriksa 4 layer dalam OSI Layer termasuk didalamnya IP Packet yang berisi IP source, IP Destination, Source Port, dan Destination Port. Berbeda dengan IDS/IPS, Deep Packet Inspection (DPI) dapat melakukan inspeksi pada 7 Layer dalam OSI Layer dimana DPI tidak hanya memeriksa packet header information saja tapi juga memeriksa payload dalam paket-paket yang masuk dalam jaringan. Sehingga keakuratan informasi yang digunakan sebagai parameter pengambilan keputusan menjadi lebih lengkap, dan dapat membuat system keamanan menjadi lebih kuat. 

String Matching

Pencarian string merupakan kegiatan yang sangat sering dilakukan oleh pengguna komputer. Dalam kehidupan sehari-hari, user (pengguna komputer) pasti berhubungan dengan yang namanya pencarian string. Untuk mencari suatu kata misalnya di dalam program Microsoft Word atau pun di web browser seperti Mozilla Firefox atau Internet Explorer, user akan berhubungan dengan bagian find yang merupakan penerapan langsung dari algoritma pencarian string di dalam program aplikasi. Pencarian string di dalam teks disebut juga dengan pencocokan string (string matching atau pattern matching). Perumusan persoalan pencarian string yaitu dengan diberikannya teks atau long string dengan panjang n karakter dan pattern yaitu string yang akan dicari di dalam teks dengan panjang m karakter, dengan m lebih kecil dari n karakter.

Algoritma Knuth-Morris-Pratt (KMP)

Algoritma Knuth-Morris-Pratt (KMP)

Algoritma Knuth Morris Pratt (KMP) dikembangkan oleh D. E. Knuth, bersama dengan J. H. Morris dan V. R. Pratt. Untuk pencarian string dengan algoritma Brute Force , setiap kali ditemukan ketidakcocokan dengan teks, maka pattern akan digeser satu karakter ke kanan. Berbeda dengan algoritma Brute Force, informasi yang digunakan masih dipelihara untuk melakukan jumlah pergeseran. Algoritma menggunakan informasi tersebut untuk membuat pergeseran yang lebih jauh, tidak hanya satu karakter Perbandingan antara algoritma brute force dengan algoritma KMP ditunjukkan dengan perpindahan posisi pattern terhadap posisi teks. Dimana dalam hal pencocokan string, pattern yang dicocokkan berawal dari kiri teks.