Algoritma Aho-Corasick


Algoritma Aho-Corasick adalah salah satu algoritma yang dapat digunakan untuk mencari dimana sebuah string (dalam kasus ini dinamakan sebagai pola) apakah ditemukan di dalam kumpulan string lain dengan ukuran yang lebih besar. Contoh yang dibahas kali ini adalah mengenai pencarian kata dari sebuah input teks.
Aho-Corasick adalah algoritma berbasis kamus yang mencari beberapa set pola pada data input. Pencocokan juga dilakukan secara bersamaan, sehingga kejadian pencocokan dapat ditemukan selama beberapa kali untuk setiap substring yang terdapat dalam data input. Secara informal, algoritma ini melakukan penyusunan FSM (Finite State Machine) yang menyerupai pohon dengan beberapa link diantara node internalnya. Link internal ini memungkinkan perpindahan secara cepat diantara string yang tidak cocok pada cabang lain yang memliki prefiks yang sama. Hal ini menyebabkan sistem dapat berpindah secara cepat tanpa perlu melakukan backtracking / penelusuran ulang.


Langkah-langkah penggunaan algoritma ini adalah

1. Tentukan teks yang digunakan sebagai input
Diasumsikan data input adalah sebagai berikut:
internationalization

2. Tentukan kata kunci yang digunakan dalam pencarian
Diasumsikan pola adalah sebagai berikut
on
tion
int
na

3. Lakukan pencarian kata kunci menggunakan algoritma ini

* Gunakan fungsi ini untuk menghitung semua state pada data input

* Gunakan fungsi ini untuk merancang sistem pencarian data


Hasil akhir adalah: (klik untuk perbesar gambar)

cmd140


Contoh modul / source code dalam bahasa VB (Visual Basic) dapat didownload disini:



Jika membutuhkan jasa kami dalam pembuatan program, keterangan selanjutnya dapat dilihat di Fasilitas dan Harga
Jika ada yang kurang paham dengan langkah-langkah algoritma diatas, silahkan berikan komentar Anda.
Selamat mencoba.

Tinggalkan sebuah komentar

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *