Search Engine Part 2: Radix Trie for Fast and Compact Indexing Выше я уже описала базовый принцип работы сжатого префиксного дерева: вместо хранения одного символа на узел мы храним максимально длинный общий префикс (lcp), а узлы создаются только там, где действительно есть продолжение слова. Это позволяет избавиться от дублирования префиксов и сделать структуру индекса компактнее. Подробный пример вставки в radix trie большой и проще его реализацию посмотреть прямо в проекте Алгоритм поиска в radix trie тоже интересный. Начинается как правило с корневого узла, куда мы кидаем полное слово из запроса: на каждом шаге для всех наследных узлов текущего уровня вычисляется lcp между оставшейся частью искомого слова и префиксом наследного узла. Все повторяет вставку, верно? Пока мы не встаем на одном из кейсов: - слово полностью совпало с lcp: если остаток слова исчерпан и узел конечный - ура, мы словили match. Если узел не конечный, значит запрос совпал лишь с префиксом более длинного слова, и нужное слово не найдено. - префикс узла полностью совпал c lcp: спускаемся глубже по дереву, уменьшая остаток слова. - частичное совпадение: пропускаем (тут уже на вкус, возможно кому то будет ок). Пример поиска: func (t Trie) Search(word string) (map[string]int, error) { current := t.root rest := word for { nextNode, nextRest, matched, exact := t.next(current, rest) if !matched { return nil, nil } // слово не найдено if exact { return copyDocs(nextNode.docs), nil } // exact match current, rest = nextNode, nextRest } } // next tries to advance from current node using rest of the word. // Returns: // // nextNode - child node to continue from // nextRest - remaining part of the word after consuming prefix // matched - whether ANY progress was made // exact - whether the word fully matched on this node boundary func (t Trie) next(current Node, rest string) (Node, string, bool, bool) { for _, child := range current.children { p := lcp(rest, child.prefix) // case 0: // no common prefix at all - try next child if p == 0 { continue } // case 1: // rest fully consumed if p == len(rest) { // exact match only if node is terminal if child.terminal { return child, "", true, true } // query word matched only a prefix of a longer word in a tree - so it's not found return nil, "", false, false } // case 2: // child prefix fully matched, go deeper if p == len(child.prefix) { return child, rest[p:], true, false } // case 3: // partial overlap: // - the word does not exist in the trie return nil, "", false, false } return nil, "", false, false } Как я уже упоминала - я протестировала работу trigram и radix trie через индексацию 651к документов из википедии, результат сравнения которых можно увидеть на таблице. Radix trie экономнее по обьему за счет сжатия, да еще и дает огромную фору по времени trigram (2.4 ms против 24 ms), + нет лишних узлов для повторяющихся префиксов. При этом можно хранить полные слова, а не набор триграмм. Итого поиск работает за время, пропорциональное длине слова, плюс поиском наследников за O(n) на каждом уровне. Получаем готовый autocomplete) Но и это не конец (я как минимум не запихнула все дерево в массив)) поэтому я еще буду играть. Но даже с текущей заменой на radix поиск стал значительно шустрее. А поиграть самостоятельно вы можете тоже, проект открыт для экспериментов и предложений) https://github.com/dariasmyr/fts-engine