Что такое ACT-дерево

ACT-дерево (Aho-Corasick Trie) — это структура данных для эффективного поиска множества подстрок (паттернов) в тексте. Оно основано на алгоритме Ахо-Корасик, который объединяет префиксное дерево (trie) с конечным автоматом для быстрого перехода между состояниями.

Ключевые особенности:

• Построение: Строится на основе набора шаблонов (строк, которые нужно найти).
• Эффективность: Позволяет искать все вхождения всех шаблонов в тексте за одно сканирование текста. Сложность алгоритма составляет O(n + m + k), где n — длина текста, m — сумма длин всех шаблонов, k — число найденных вхождений.
• Структура: Использует три типа ссылок:
  • Переходы по символам: Стандартные переходы в trie.
  • Суффиксные ссылки (failure links): Позволяют быстро перейти в состояние, соответствующее самому длинному суффиксу текущего префикса, который также является префиксом одного из шаблонов. Это позволяет избежать повторного сканирования текста при несовпадении.
  • Выходные ссылки (output links): Указывают на другие состояния, которые соответствуют шаблонам, являющимся суффиксами текущего префикса.

Пример использования в Go:

Для работы с алгоритмом Ахо-Корасик в Go часто используют сторонние библиотеки, например, github.com/cloudflare/ahocorasick.

package main

import (
    "fmt"
    "github.com/cloudflare/ahocorasick"
)

func main() {
    // Определяем набор паттернов (строк для поиска)
    patterns := [][]byte{
        []byte("he"),
        []byte("she"),
        []byte("his"),
        []byte("hers"),
    }

    // Создаем матчер Ахо-Корасик
    matcher := ahocorasick.NewMatcher(patterns)

    // Текст, в котором будем искать паттерны
    text := []byte("ushers")

    // Выполняем поиск
    matches := matcher.Match(text)

    // Выводим найденные совпадения
    fmt.Printf("Текст: '%s'n", string(text))
    fmt.Println("Найденные совпадения:")
    for _, match := range matches {
        // match.Index - начальная позиция совпадения в тексте
        // match.Pattern - индекс паттерна в исходном массиве patterns
        fmt.Printf("  Паттерн '%s' найден на позиции %dn", string(patterns[match.Pattern]), match.Index)
    }

    fmt.Println("n--- Другой пример ---")
    text2 := []byte("this is his and hers book")
    matches2 := matcher.Match(text2)
    fmt.Printf("Текст: '%s'n", string(text2))
    fmt.Println("Найденные совпадения:")
    for _, match := range matches2 {
        fmt.Printf("  Паттерн '%s' найден на позиции %dn", string(patterns[match.Pattern]), match.Index)
    }
}

Применение:

ACT-дерево широко применяется в задачах, где требуется быстрый поиск множества ключевых слов или фраз в больших объемах текста, например:

• Антивирусное ПО: Поиск сигнатур вредоносного кода.
• Системы обнаружения вторжений (IDS/IPS): Поиск известных паттернов атак в сетевом трафике.
• Поисковые системы: Индексация и поиск по ключевым словам.
• Анализ текста: Фильтрация спама, цензура, извлечение информации.
• Биоинформатика: Поиск последовательностей в ДНК/РНК.