Metin işleme ve metin madenciliği disiplinlerinde, belirli anahtar kelimeleri metin içinde hızlı ve etkili bir biçimde tespit etme gerekliliği sıklıkla karşılaşılan bir zorunluluktur. Bu bağlamda, Aho-Corasick algoritması, bu tür metin işleme görevleri için geliştirilmiş güçlü bir algoritma olarak öne çıkar.

Metin madenciliği, metin içeriğinin detaylı bir analizini yapmayı ve özellikle büyük metin koleksiyonlarında belirli örüntüleri, kelimeleri veya terimleri tespit etmeyi amaçlayan bir veri madenciliği disiplinidir. Bu bağlamda, büyük metin kümesi üzerinde belirli anahtar kelimeleri tespit etmek, metin madenciliği uygulamalarının önemli bir bileşenidir. Bu tür görevler için, Aho-Corasick algoritması metin içerisinde aynı anda birden fazla anahtar kelimeyi arayıp bulma işleminde etkili bir yaklaşım sunmaktadır.

Trie Veri Yapısı

Aho-Corasick algoritmasının temel yapısı Trie (ağaç) veri yapısına dayanmaktadır. Trie, metin işleme alanında etkili bir biçimde kullanılan bir veri yapısıdır. Kelimeleri veya karakter dizilerini temsil etmek için tasarlanmış olan Trie, metin içinde bu kelimeleri hızlı bir şekilde tespit etme amacıyla kullanılır. Trie yapısındaki her bir düğüm, bir karakteri veya kelimenin bir parçasını sembolize eder ve bir kelimenin sonunu işaretler. Bu özelliği sayesinde, Trie yapısı metin içindeki kelimeleri hiyerarşik bir şekilde organize eder ve arama işlemini optimize eder.

Aho-Corasick Algoritması Nasıl Çalışır?

Aho-Corasick algoritması, metin içindeki anahtar kelimeleri bulma görevini gerçekleştirirken Trie veri yapısını kullanır. Bu algoritma, anahtar kelimelerin Trie’deki yollarını oluşturur ve bu yolları gezerek metin içindeki anahtar kelimeleri bulur. Ayrıca, başarısız geçişleri (fail transitions) hesaplayarak arama süresini optimize eder.

1. Trie Yapısının Oluşturulması

İlk adım, metin içinde aranacak anahtar kelimelerin Trie veri yapısına eklenmesidir. Her bir anahtar kelime, Trie’deki bir yol olarak temsil edilir. Örnek bir Trie yapısı oluşturmak için şu adımları takip ederiz:

1. Trie veri yapısının kök düğümünü oluştur.
2. Anahtar kelimeleri sırayla Trie’ye eklerken her karakter için bir düğüm oluştururuz ve bu düğümü Trie’deki ilgili düğüme bağlarız.

2. Başarısız Geçişlerin Hesaplanması

Başarısız geçişler (fail transitions), metin içinde aranacak anahtar kelimelerin Trie yapısında hızlı bir şekilde gezilmesini sağlar. Her düğümün bir “fail_state” (başarısız geçiş) bağlantısı vardır ve bu bağlantılar Trie’deki başarısız geçişleri yönlendirir. Başarısız geçişler hesaplanırken şu adımlar takip edilir:

1. Kök düğümünün tüm çocukları için fail_state bağlantıları başlangıçta kök düğüme yönlendirilir.
2. BFS (breadth-first search) algoritması kullanılarak Trie yapısı üzerinde gezilir ve her düğüm için fail_state bağlantıları hesaplanır. Bu bağlantılar, başarısız geçişlerin doğru bir şekilde yönlendirilmesini sağlar.

3. Metin İçinde Anahtar Kelimelerin Aranması

Metin içinde anahtar kelimeleri aramak için Trie yapısını kullanırız. Metin üzerinde gezinirken her karakter için şu adımları izleriz:

1. Mevcut durumu (state) Trie yapısındaki kök düğüm olarak başlatırız.
2. Mevcut karakteri alırız ve bu karakteri Trie’de bir sonraki durumu (state) bulmak için kullanırız.
3. Eğer bir sonraki durum (state) yoksa veya anahtar kelimenin sonu değilse, fail_state bağlantılarını takip ederiz.
4. Anahtar kelimenin sonu bulunursa, bu kelimenin pozisyonunu kaydederiz.

Aşağıda, Aho-Corasick algoritmasının basit bir pseudocode örneği verilmiştir:

function AhoCorasick(text, keywords):
    create Trie from keywords
    set fail transitions in Trie
    result = empty dictionary
    
    state = root of Trie
    for i = 0 to len(text) - 1:
        while state is not found in Trie and state is not root:
            state = state.fail_state
        
        state = find_next_state(state, text[i])
        
        if state is None:
            state = root of Trie
        
        for output in state.outputs:
            if output not in result:
                result[output] = empty list
            result[output].append(i - len(output) + 1)
    
    return result

Bu pseudocode, Aho-Corasick algoritmasının ana mantığını ve işleyişini göstermektedir. Algoritma, metin içindeki anahtar kelimeleri hızlı bir şekilde bulmak için Trie yapısını kullanır ve başarısız geçişlerin hesaplanmasıyla performansını optimize eder.

GoLang’de Aho-Corasick uygulaması:

package main

import (
	"fmt"
)

type TrieNode struct {
	children    map[rune]*TrieNode
	fail        *TrieNode
	isEndOfWord bool
	keyword     string
}

type AhoCorasick struct {
	root *TrieNode
}

func newTrieNode() *TrieNode {
	return &TrieNode{
		children: make(map[rune]*TrieNode),
		fail:     nil,
	}
}

func NewAhoCorasick(keywords []string) *AhoCorasick {
	root := newTrieNode()
	ac := &AhoCorasick{root: root}

	for _, keyword := range keywords {
		ac.insert(keyword)
	}

	ac.setFailTransitions()

	return ac
}

func (ac *AhoCorasick) insert(keyword string) {
	node := ac.root
	for _, char := range keyword {
		if _, found := node.children[char]; !found {
			node.children[char] = newTrieNode()
		}
		node = node.children[char]
	}
	node.isEndOfWord = true
	node.keyword = keyword
}

func (ac *AhoCorasick) setFailTransitions() {
	queue := make([]*TrieNode, 0)
	root := ac.root

	for _, child := range root.children {
		child.fail = root
		queue = append(queue, child)
	}

	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]

		for char, child := range node.children {
			failNode := node.fail

			for failNode != root && failNode.children[char] == nil {
				failNode = failNode.fail
			}

			if nextNode, found := failNode.children[char]; found {
				child.fail = nextNode
			} else {
				child.fail = root
			}

			queue = append(queue, child)
		}
	}
}

func (ac *AhoCorasick) Search(text string) map[string][]int {
	result := make(map[string][]int)
	node := ac.root

	for i, char := range text {
		for node != ac.root && node.children[char] == nil {
			node = node.fail
		}

		if nextNode, found := node.children[char]; found {
			node = nextNode
		} else {
			node = ac.root
		}

		if node.isEndOfWord {
			if _, exists := result[node.keyword]; !exists {
				result[node.keyword] = []int{}
			}
			result[node.keyword] = append(result[node.keyword], i-len(node.keyword)+1)
		}
	}

	return result
}

func main() {
	keywords := []string{"what", "hat", "ver", "er"}
	text := "whatever, err ... , wherever"

	ac := NewAhoCorasick(keywords)
	results := ac.Search(text)

	fmt.Println(results)
}

Program çalıştırıldığında çıktısı aşağıdaki gibi olacaktır.

map[er:[10 22] ver:[5 25] what:[0]]

Programın çalışır haline şuradan erişilebilir.

Kaynaklar

• https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm
• https://cp-algorithms.com/string/aho_corasick.html
• http://web.stanford.edu/class/archive/cs/cs166/cs166.1186/lectures/02/Small02.pdf