~ AHO-CORASICK ALGORITHM ~

Algoritma Aho-Corasick

Dalam ilmu komputer , algoritma Aho-Corasick adalah algoritma pencarian string yang ditemukan oleh Alfred V. Aho dan Margaret J. Corasick. ^[1] Ini adalah sejenis algoritma pencocokan kamus yang menempatkan elemen dari serangkaian string terbatas ("kamus") dalam teks masukan. Ini cocok dengan semua senar secara bersamaan. Kompleksitas algoritma linier di sepanjang senar ditambah panjang teks yang dicari ditambah jumlah output yang sesuai. Perhatikan bahwa karena semua kecocokan ditemukan, ada jumlah kuadrat dari kecocokan jika setiap pertandingan substring (misalnya kamus = a , aa , aaa , aaaa dan string masukan adalah aaaa ).
Secara informal, algoritma ini membangun sebuah mesin negara yang terbatas yang menyerupai sebuah trie dengan tambahan link antara berbagai node internal. Tautan internal tambahan ini memungkinkan transisi yang cepat antara korespondensi string yang gagal (misalnya pencarian kucing dalam trie yang tidak mengandung kucing , namun berisi keranjang , dan dengan demikian akan gagal pada simpul yang diawali oleh ca ), ke cabang lain dari trie yang dibagi awalan umum (misalnya, pada kasus sebelumnya, cabang atribut mungkin merupakan transisi lateral terbaik). Hal ini memungkinkan robot untuk transisi antara string pertandingan tanpa perlu untuk mundur.
Ketika kamus string diketahui sebelumnya (misalnya database virus komputer ), konstruksi robot dapat dilakukan sekali off-line dan robot yang dikompilasi disimpan untuk digunakan nanti. Dalam kasus ini, waktu luangnya linier sepanjang input ditambah jumlah entri yang cocok.
Algoritma pencocokan string Aho-Corasick membentuk basis dari perintah Unix asli fgrep .
  

Contoh

Dalam contoh ini, kita akan mempertimbangkan sebuah kamus yang terdiri dari kata-kata berikut: {a, ab, bab, bc, bca, c, caa}.
Grafik di bawah ini adalah struktur data Aho-Corasick yang dibangun dari kamus yang ditentukan, dengan setiap baris dalam tabel mewakili sebuah simpul di dalam trie, dengan jalur kolom yang menunjukkan urutan karakter (unik) dari akar ke simpul.
Struktur data memiliki satu simpul untuk setiap awalan setiap string dalam kamus. Jadi jika (bca) ada di kamus, maka akan ada simpul untuk (bca), (bc), (b), dan (). Jika sebuah simpul ada dalam kamus maka itu adalah simpul biru. Jika tidak, itu adalah node abu-abu.
Ada busur "anak" berwarna hitam dari setiap simpul ke simpul yang namanya ditemukan dengan menambahkan satu karakter. Jadi ada busur hitam dari (bc) sampai (bca).
Ada busur "sufiks" yang diarahkan biru dari setiap simpul ke simpul yang merupakan sufiks ketat terpanjang yang mungkin ada dalam grafik. Misalnya, untuk node (caa), sufiksnya yang ketat adalah (aa) dan (a) dan (). Hal terpanjang yang ada pada grafik adalah (a). Jadi ada busur biru dari (caa) sampai (a). Busur biru dapat dihitung dalam waktu linier dengan berulang kali melintasi busur biru dari induk simpul sampai simpul traversing memiliki anak yang sesuai dengan karakter simpul target.
Ada busur "kamus akhiran" hijau dari setiap simpul ke simpul berikutnya dalam kamus yang dapat dicapai dengan mengikuti busur biru. Misalnya, ada busur hijau dari (bca) ke (a) karena (a) adalah simpul pertama dalam kamus (yaitu simpul biru) yang dicapai saat mengikuti busur biru ke (ca) dan kemudian ke ( Sebuah). Busur hijau dapat dihitung dalam waktu linier dengan berulang kali melintasi busur biru sampai ditemukan simpul yang terisi, dan memo informasi ini.

A visualization of the trie for the dictionary on the right. Suffix links are in blue; dictionary suffix links in green. Nodes corresponding to dictionary entries are highlighted in blue.

Dictionary {a, ab, bab, bc, bca, c, caa}

Path	In dictionary	Suffix link	Dict suffix link
()	–
(a)	+	()
(ab)	+	(b)
(b)	–	()
(ba)	–	(a)	(a)
(bab)	+	(ab)	(ab)
(bc)	+	(c)	(c)
(bca)	+	(ca)	(a)
(c)	+	()
(ca)	–	(a)	(a)
(caa)	+	(a)	(a)

Pada setiap langkah, simpul saat ini diperluas dengan menemukan anaknya, dan jika itu tidak ada, temukan anak suffix-nya, dan jika itu tidak berhasil, temukan anak akhiran sufiksnya, dan seterusnya, akhirnya berakhir di akar node jika tidak ada yang terlihat sebelumnya
Ketika algoritma mencapai sebuah node, ia menampilkan semua entri kamus yang berakhir pada posisi karakter saat ini dalam teks masukan. Hal ini dilakukan dengan mencetak setiap simpul yang dicapai dengan mengikuti akhiran kamus, mulai dari simpul tersebut, dan berlanjut sampai mencapai simpul tanpa akhiran kamus. Selain itu, simpul itu sendiri dicetak, jika itu adalah entri kamus.
Eksekusi pada input string abccab menghasilkan langkah-langkah berikut:

Analysis of input string abccab

Node	Remaining string	Output:end position	Transition	Output
()	abccab		start at root
(a)	bccab	a:1	() to child (a)	Current node
(ab)	ccab	ab:2	(a) to child (ab)	Current node
(bc)	cab	bc:3, c:3	(ab) to suffix (b) to child (bc)	Current Node, Dict suffix node
(c)	ab	c:4	(bc) to suffix (c) to suffix () to child (c)	Current node
(ca)	b	a:5	(c) to child (ca)	Dict suffix node
(ab)		ab:6	(ca) to suffix (a) to child (ab)	Current node