Замотивировавшись большим ресёрчем про Fast and Space Efficient Trie Searches, я решила немного переосмыслить архитектуру своего самодельного FTS-движка и заменить реализацию индексного дерева. Но прежде чем переходить к новому подходу, важно понять, как именно работала предыдущая версия и какие ограничения в ней проявились.
До недавнего времени поиск по тексту был реализован через обычное префиксное дерево. Для удобства я буду называть его trigram trie, поскольку глубина этого дерева была фиксированной и равнялась трём.
В основе лежала довольно простая идея:
1. Каждое слово разбивалось на триграммы — подстроки длиной 3.
2. Каждая триграмма индексировалась в дереве.
3. В терминальном узле триграммы хранился список документов, в которых она встречается, а также количество вхождений.
Само дерево представляло собой префиксное дерево фиксированной глубины, где:
- арность (за определением забавного термина сюда) каждого узла равна размеру английского алфавита - 26;
- переход к следующему узлу осуществляется по индексу соответствующего ascii ловеркейс символа.
type Node struct {
docs map[string]int
children [26]*Node
}
func search(rootNode *Node) {
node := rootNode
for i := 0; i < 3; i++ {
index := trigram[i] - 'a'
if index < 0 || index >= 26 {
return fmt.Errorf("invalid character in trigram %v", trigram)
}
if node.children[index] == nil {
node.children[index] = newNode()
}
node = node.children[index]
}
// Increase doc entry count
node.docs[docID]++
}
Иными словами, путь каждой триграммы составляет 3 узла от корня. Реализация простая, индексируется тоже быстро, НО цена за это - плохое масштабирование. Из основных проблем - отсутствие сжатия индекса: даже частично совпадающие префиксы приводили к созданию новых узлов, при том что бОльшая часть из 26 возможных переходов в каждом узле оставалась неиспользованной. Кроме того, поскольку полные слова не хранились напрямую, поиск требовал пересчёта и пересечения бОльшего количества ссылок на документы - получаем раздутое дерево с замедленным выполнением запросов.
Захотелось пересмотеть структуру индексного дерева и поискать к более компактной, сжимаемой реализации.
Radix trie (или compressed unary search tree)
Radix trie представляет из себя такое же префиксое дерево, где каждый узел хранит не один символ, а группу символов - максимально длинный префикс, который уникален для этого пути. При вставке слова входим в цикл с наследниками узла, где с каждым проводим поиск самого длинного общего префикса (lcp) а дальше выбираем:- Если префикс частично совпадает, узел делим на промежуточный узел с общим префиксом и узлы-наследники с остатками слова.
- Если префикс полностью совпадает, идём на уровень глубже по дереву, пока не достигнем конца слова, тогда помечаем узел как терминальный (конечный) и пишем туда индекс документа с количеством вхождений.
Пример структуры:
type Node struct {
prefix string // группа символов
terminal bool // является ли узел концом слова
docs map[string]int // postings: ID документа + количество вхождений
children []*Node // наследники - продолжения слова
}
Помимо того, что храним в 1 узле группу символов, мы еще и аллоцируем только те наследные узлы, которые куда то ведут (содержат продолжение слова). Быстро? Да, потому что храним все слово. Выгодно? Очень.
Изначально рассматривала идею прикрутить бинарный поиск по списку, но отбросила эту идею: как показала индексация 650к статей из вики, первая пара уровней содержат не больше 26 наследников, которые можно легко перебрать за линейку)
В следующей части расскажу, как это выглядит на практике
#fts #projects