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

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

ACT-дерево (также известное как Алфавитно-компактное префиксное дерево, от англ. Alphabet-Compressed Trie) — это оптимизированная версия классического префиксного дерева (Trie), предназначенная для эффективного хранения и поиска строк в большой коллекции. Его ключевая особенность — сжатие последовательных узлов с одним потомком в единый узел, что значительно уменьшает потребление памяти и ускоряет операции поиска.

Основная идея и отличие от классического Trie

В обычном Trie каждая буква строки представлена отдельным узлом. Например, для слов "cat" и "car" будет структура:

root -> c -> a -> t
              -> r

Здесь узел 'c' имеет одного потомка 'a', который, в свою очередь, имеет двух потомков 't' и 'r'. ACT-дерево же "сжимает" цепочки узлов с одним потомком. В том же примере цепочка "ca" может быть объединена в один узел, хранящий подстроку "ca" целиком:

// Упрощённая структура узла ACT-дерева на Go
type ACTNode struct {
    // Строка (подстрока), хранимая в узле
    fragment string
    // Дочерние узлы
    children map[byte]*ACTNode
    // Флаг конца слова
    isEnd bool
}

// Пример сжатого представления для "cat" и "car":
// Корень -> узел("ca") -> узел("t") (isEnd=true)
//                       -> узел("r") (isEnd=true)

Ключевые преимущества ACT-дерева

• Экономия памяти: Устраняет избыточные узлы, особенно для длинных строк с общими префиксами.
• Ускорение поиска: За счёт сжатия уменьшается количество переходов между узлами при поиске.
• Эффективность для больших алфавитов: Хорошо подходит для языков с большим набором символов (например, юникод), где классический Trie может стать чрезмерно "разреженным".

Типичные операции и их сложность

• Вставка (Insert): В худшем случае O(m), где m — длина строки. Требуется разбиение существующих фрагментов при необходимости.
• Поиск (Search): В худшем случае O(m). Поиск может потребовать сравнения символов внутри фрагментов узлов.
• Удаление (Delete): O(m), но может требовать обратного "разжатия" узлов для сохранения структуры.

Пример реализации на Go

Рассмотрим базовую реализацию ACT-дерева с операциями вставки и поиска:

package main

import (
    "fmt"
    "strings"
)

// Узел ACT-дерева
type ACTNode struct {
    fragment string       // Строка, хранимая в этом узле
    children map[byte]*ACTNode
    isEnd    bool         // Помечает конец слова
}

// Создание нового узла
func newNode(fragment string) *ACTNode {
    return &ACTNode{
        fragment: fragment,
        children: make(map[byte]*ACTNode),
        isEnd:    false,
    }
}

// ACT-дерево
type ACTree struct {
    root *ACTNode
}

func NewACTree() *ACTree {
    return &ACTree{root: newNode("")}
}

// Вставка слова в дерево
func (t *ACTree) Insert(word string) {
    current := t.root
    i := 0

    for i < len(word) {
        // Ищем существующий дочерний узел
        next, exists := current.children[word[i]]
        if !exists {
            // Если нет дочернего узла, создаём новый с оставшейся частью слова
            current.children[word[i]] = newNode(word[i:])
            current.children[word[i]].isEnd = true
            return
        }

        // Находим общий префикс фрагмента в узле и остатка слова
        commonPrefix := t.commonPrefix(next.fragment, word[i:])
        if commonPrefix < len(next.fragment) {
            // Разбиваем существующий узел
            splitNode := newNode(next.fragment[commonPrefix:])
            splitNode.children = next.children
            splitNode.isEnd = next.isEnd

            // Обновляем текущий узел
            next.fragment = next.fragment[:commonPrefix]
            next.children = make(map[byte]*ACTNode)
            next.children[splitNode.fragment[0]] = splitNode
            next.isEnd = commonPrefix == len(word[i:])
        }

        i += commonPrefix
        current = next
        if i == len(word) {
            current.isEnd = true
        }
    }
}

// Поиск слова в дереве
func (t *ACTree) Search(word string) bool {
    current := t.root
    i := 0

    for i < len(word) {
        next, exists := current.children[word[i]]
        if !exists {
            return false
        }

        // Проверяем фрагмент в узле
        if !strings.HasPrefix(word[i:], next.fragment) {
            return false
        }

        i += len(next.fragment)
        current = next
    }

    return current.isEnd
}

// Вспомогательная функция для нахождения общего префикса
func (t *ACTree) commonPrefix(a, b string) int {
    minLen := len(a)
    if len(b) < minLen {
        minLen = len(b)
    }
    i := 0
    for i < minLen && a[i] == b[i] {
        i++
    }
    return i
}

// Пример использования
func main() {
    tree := NewACTree()
    words := []string{"cat", "car", "cart", "category"}
    
    for _, word := range words {
        tree.Insert(word)
    }
    
    fmt.Println(tree.Search("cat"))   // true
    fmt.Println(tree.Search("car"))   // true
    fmt.Println(tree.Search("ca"))    // false (не полное слово)
    fmt.Println(tree.Search("dog"))   // false
}

Применение на практике

• Автодополнение (Auto-complete): Быстрый поиск всех слов по заданному префиксу.
• Проверка орфографии: Хранение словаря с возможностью быстрого поиска.
• Маршрутизация в сетях: IP-таблицы маршрутизации (в форме PATRICIA-дерева — частного случая ACT).
• Базы данных и поисковые системы: Индексация текстовых данных.

Сравнение с другими структурами данных

• Против обычного Trie: ACT-дерево экономичнее по памяти, но сложнее в реализации из-за операций разделения узлов.
• Против хеш-таблиц: ACT-дерево позволяет эффективно искать по префиксу, что недоступно в обычных хеш-таблицах.
• Против сбалансированных деревьев поиска: ACT-дерево специализировано для строк и обычно быстрее для операций с префиксами.

Вывод: ACT-дерево — это мощная оптимизация префиксного дерева, которая сочетает в себе быстрый поиск и эффективное использование памяти. Хотя его реализация сложнее классического Trie, эта структура данных незаменима в задачах, требующих работы с большими наборами строк и операций поиска по префиксу. В языке Go, с его emphasis на эффективность, ACT-дерево может быть отличным выбором для реализации высокопроизводительных текстовых поисковых систем и словарей.