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

Dim daftarState As List(Of Integer) = HitungSemuaState(input, kataKunci)

* Gunakan fungsi ini untuk menghitung semua state pada data input

Public Function HitungSemuaState(input As String, kataKunci As String(), Optional limitBawahKarakter As Char = "a"c, Optional limitAtasKarakter As Char = "z"c) As List(Of Integer)
	rancangSistem(kataKunci, limitBawahKarakter, limitAtasKarakter)

	Dim stateSekarang As Integer = 0
	Dim hasil As New List(Of Integer)()

	For i As Integer = 0 To input.Length - 1
		stateSekarang = HitungStateSelanjutnya(stateSekarang, input(i), limitBawahKarakter)

		If Out(stateSekarang) = 0 Then
			Continue For
		End If

		For j As Integer = 0 To kataKunci.Length - 1
			If Convert.ToBoolean(Out(stateSekarang) And (1 << j)) Then
				hasil.Insert(0, i - kataKunci(j).Length + 1)
			End If
		Next
	Next

	Return hasil
End Function

* Gunakan fungsi ini untuk merancang sistem pencarian data

Private Function rancangSistem(daftarKata As String(), Optional limitBawahKarakter As Char = "a"c, Optional limitAtasKarakter As Char = "z"c) As Integer
	Out = Enumerable.Repeat(0, Out.Length).ToArray()
	FF = Enumerable.Repeat(-1, FF.Length).ToArray()

	For i As Integer = 0 To maksState - 1
		For j As Integer = 0 To maksKarakter - 1
			GF(i, j) = -1
		Next
	Next

	Dim states As Integer = 1

	For i As Integer = 0 To daftarKata.Length - 1
		Dim kataKunci As String = daftarKata(i)
		Dim stateSekarang As Integer = 0

		For j As Integer = 0 To kataKunci.Length - 1
			Dim c As Integer = Convert.ToInt32(kataKunci(j)) - Convert.ToInt32(limitBawahKarakter)

			If GF(stateSekarang, c) = -1 Then
				GF(stateSekarang, c) = System.Math.Max(System.Threading.Interlocked.Increment(states), states - 1)
			End If

			stateSekarang = GF(stateSekarang, c)
		Next

		Out(stateSekarang) = Out(stateSekarang) Or (1 << i)
	Next

	For c As Integer = 0 To maksKarakter - 1
		If GF(0, c) = -1 Then
			GF(0, c) = 0
		End If
	Next

	Dim q As New List(Of Integer)()
	For c As Integer = 0 To Convert.ToInt32(limitAtasKarakter) - Convert.ToInt32(limitBawahKarakter)
		If GF(0, c) <> -1 AndAlso GF(0, c) <> 0 Then
			FF(GF(0, c)) = 0
			q.Add(GF(0, c))
		End If
	Next

	While Convert.ToBoolean(q.Count)
		Dim state As Integer = q(0)
		q.RemoveAt(0)

		For c As Integer = 0 To Convert.ToInt32(limitAtasKarakter) - Convert.ToInt32(limitBawahKarakter)
			If GF(state, c) <> -1 Then
				Dim failure As Integer = FF(state)

				While GF(failure, c) = -1
					failure = FF(failure)
				End While

				failure = GF(failure, c)
				FF(GF(state, c)) = failure
				Out(GF(state, c)) = Out(GF(state, c)) Or Out(failure)
				q.Add(GF(state, c))
			End If
		Next
	End While

	Return states
End Function

Hasil akhir adalah: (klik untuk perbesar gambar)

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.