Структура данных Trie: забытая жемчужина

С самых первых дней нашей жизни как программистов мы все имели дело со структурами данных: массивы, связанные списки, деревья, наборы, стеки и очереди — наши повседневные спутники, и опытный программист знает, когда и зачем их использовать. В этой статье мы увидим, как структура данных, которой часто пренебрегают, trie , действительно проявляется в предметных областях со специфическими функциями, такими как словесные игры.

Словесные игры как пример

Для начала давайте рассмотрим простую словесную головоломку: найдите все допустимые слова на доске с буквами 4x4, соединяя соседние буквы по горизонтали, вертикали или диагонали. Например, на следующей доске мы видим буквы «W», «A», «I» и «T», соединяющиеся в слово «WAIT».

Наивным решением для поиска всех допустимых слов было бы исследовать доску, начиная с верхнего левого угла, а затем продвигаясь в глубину к более длинным последовательностям, начиная снова со второй буквы в первом ряду и так далее. На доске 4x4, позволяющей перемещаться по вертикали, горизонтали и диагонали, имеется 12029640 последовательностей длиной от одного до шестнадцати символов.

Теперь наша цель — найти наилучшую структуру данных для реализации этой проверки допустимых слов, т. е. нашего словаря. Несколько моментов, о которых следует помнить:

• Нам нужна только одна копия каждого слова, т. е. с логической точки зрения наш словарь представляет собой набор.
• Нам нужно ответить на следующие вопросы для любого заданного слова:
  • Содержит ли текущая последовательность символов действительное слово?
  • Существуют ли более длинные слова, начинающиеся с этой последовательности? Если нет, мы можем отказаться от нашего исследования вглубь, так как углубление не даст никаких правильных слов.

Чтобы проиллюстрировать второй пункт, рассмотрим следующую доску: Нет смысла изучать последующие ходы, так как в словаре нет слов, начинающихся с «ASF».

Мы хотели бы, чтобы наша структура данных отвечала на эти вопросы как можно быстрее. ~O(1) время доступа (для проверки последовательности) было бы идеально!

Мы можем определить интерфейс Vocabulary следующим образом (см. здесь репозиторий GitHub):

 public interface Vocabulary { boolean add(String word); boolean isPrefix(String prefix); boolean contains(String word); }

Структура данных Trie против альтернатив

Для реализации метода contains() требуется вспомогательная структура данных, позволяющая эффективно находить элементы, в то время как метод isPrefix() требует от нас поиска «следующего большего элемента», т. е. нам нужно каким-то образом поддерживать сортировку словаря.

Мы можем легко исключить наборы на основе хэшей из нашего списка кандидатов: в то время как такая структура даст нам постоянную проверку на наличие contains() , она будет работать довольно плохо на isPrefix() , в худшем случае требуя, чтобы мы сканировали весь задавать.

По совершенно противоположной причине мы также можем исключить отсортированные связанные списки, поскольку они требуют сканирования списка, по крайней мере, до первого элемента, который больше или равен искомому слову или префиксу.

Двумя допустимыми вариантами являются использование отсортированного списка на основе массива или двоичного дерева.
В отсортированном списке, поддерживаемом массивом, мы можем использовать двоичный поиск, чтобы найти текущую последовательность, если она присутствует, или следующий больший элемент по цене O(log2(n)) , где n — количество слов в словаре.

Мы можем реализовать словарь на основе массива, который всегда сохраняет такой порядок, используя стандартные java.util.ArrayList и java.util.Collections.binarySeach :

 public class ListVocabulary implements Vocabulary { private List<String> words = new ArrayList<String>(); /** * Constructor that adds all the words and then sorts the underlying list */ public ListVocabulary(Collection<String> words) { this.words.addAll(words); Collections.sort(this.words); } public boolean add(String word) { int pos = Collections.binarySearch(words, word); // pos > 0 means the word is already in the list. Insert only // if it's not there yet if (pos < 0) { words.add(-(pos+1), word); return true; } return false; } public boolean isPrefix(String prefix) { int pos = Collections.binarySearch(words, prefix) ; if (pos >= 0) { // The prefix is a word. Check the following word, because we are looking // for words that are longer than the prefix if (pos +1 < words.size()) { String nextWord = words.get(pos+1); return nextWord.startsWith(prefix); } return false; } pos = -(pos+1); // The prefix is not a word. Check where it would be inserted and get the next word. // If it starts with prefix, return true. if (pos == words.size()) { return false; } String nextWord = words.get(pos); return nextWord.startsWith(prefix); } public boolean contains(String word) { int pos = Collections.binarySearch(words, word); return pos >= 0; } }

Если бы мы решили использовать бинарное дерево, реализация могла бы быть еще короче и элегантнее (опять же, вот ссылка на код):

 public class TreeVocabulary extends TreeSet<String> implements Vocabulary { public TreeVocabulary(Collection<String> c) { super(c); } public boolean isPrefix(String prefix) { String nextWord = ceiling(prefix); if (nextWord == null) { return false; } if (nextWord.equals(prefix)) { Set<String> tail = tailSet(nextWord, false); if (tail.isEmpty()) { return false; } nextWord = tail.iterator().next(); } return nextWord.startsWith(prefix); } /** * There is a mismatch between the parameter types of vocabulary and TreeSet, so * force call to the upper-class method */ public boolean contains(String word) { return super.contains(word); } }

В обоих случаях мы можем ожидать производительности O(log n) для каждого метода доступа ( contains() и isPrefix() ). Что касается требований к пространству, то как реализация с поддержкой массива, так и реализация с поддержкой дерева требуют O(n+M) , где n — количество слов в словаре, а M — размер словаря в байтах, т. е. сумма длины строки в словаре.

Trie-приложения: когда и зачем использовать Tries

Логарифмическая производительность и линейная память неплохие. Но есть еще несколько характеристик нашего домена приложения, которые могут привести к повышению производительности:

• Мы можем с уверенностью предположить, что все слова в нижнем регистре.
• Мы принимаем только буквы az — без знаков препинания, без дефисов, без ударений и т. д.
• Словарь содержит множество форм флективных форм: множественное число, спряженные глаголы, составные слова (например, house -> housekeeper). Таким образом, многие слова имеют один и тот же корень .
• Слова имеют ограниченную длину. Например, если мы работаем на доске 4x4, все слова длиннее 16 символов можно отбросить.

Вот здесь-то и вступает в действие слово «три» (произносится как «попытка»). Но что такое «три»? Попытки — это игнорируемые структуры данных, которые можно найти в книгах, но редко в стандартных библиотеках.

Для мотивации давайте сначала рассмотрим детище компьютерных наук: бинарное дерево. Теперь, когда мы анализируем производительность двоичного дерева и говорим, что операция x равна O(log(n)) , мы постоянно говорим о логарифмическом основании 2. Но что, если вместо двоичного дерева мы использовали троичное дерево, где у каждого узла есть три потомка (или разветвление из трех). Тогда мы будем говорить о логарифмической базе 3. (Это улучшение производительности, хотя и только на постоянный коэффициент.) По сути, наши деревья стали бы шире, но короче, и мы могли бы выполнять меньше поисков, поскольку нам не нужно спускаться совсем вниз. так глубоко.

Делая шаг вперед, что, если бы у нас было дерево с разветвлением, равным количеству возможных значений нашего типа данных?

Это мотивация попытки. И, как вы, наверное, уже догадались, trie — это действительно дерево, так сказать, trie-дерево!

Но, в отличие от большинства бинарных деревьев, которые вы использовали бы для сортировки строк, тех, которые хранили бы целые слова в своих узлах, каждый узел дерева содержит один символ (и даже не тот, как мы скоро увидим) и имеет максимальное разветвление, равное длине алфавита. В нашем случае длина алфавита равна 26; поэтому узлы дерева имеют максимальное разветвление 26. И хотя сбалансированное двоичное дерево имеет глубину log2(n) , максимальная глубина дерева равна максимальной длине слова! (Опять же, шире, но короче.)

Внутри дерева слова с одной и той же основой (префиксом) совместно используют область памяти, соответствующую основе.

Чтобы визуализировать разницу, давайте рассмотрим небольшой словарь, состоящий из пяти слов. Предположим, что греческие буквы обозначают указатели, и обратите внимание, что в дереве красные символы обозначают узлы, содержащие допустимые слова .

Реализация Java-трея

Как мы знаем, в дереве указатели на дочерние элементы обычно реализуются с помощью левой и правой переменных, потому что максимальное разветвление фиксировано на двух.

В дереве, индексирующем алфавит из 26 букв, каждый узел имеет 26 возможных потомков и, следовательно, 26 возможных указателей. Таким образом, каждый узел представляет собой массив из 26 (указателей) поддеревьев, где каждое значение может быть либо нулевым (если такого дочернего элемента нет), либо другим узлом.

Как же тогда нам искать слово в дереве? Вот метод, который, учитывая String s , идентифицирует узел, соответствующий последней букве слова, если он существует в дереве:

 public LowercaseTrieVocabulary getNode(String s) { LowercaseTrieVocabulary node = this; for (int i = 0; i < s.length(); i++) { int index = LOWERCASE.getIndex(s.charAt(i)); LowercaseTrieVocabulary child = node.children[index]; if (child == null) { // There is no such word return null; } node = child; } return node; }

Метод LOWERCASE.getIndex(s.charAt(i)) просто возвращает позицию i -го символа в алфавите. В возвращаемом узле node логического свойства указывает, что узел соответствует последней букве слова, т. е. букве, отмеченной красным в предыдущем примере. Поскольку каждый узел хранит счетчик количества потомков, если этот счетчик положительный, то в словаре есть более длинные слова, которые имеют текущую строку в качестве префикса. Примечание: узлу на самом деле не нужно хранить ссылку на символ, которому он соответствует, потому что он подразумевается в своей позиции в дереве.

Анализ производительности

Что делает древовидную структуру действительно эффективной в этих ситуациях, так это то, что стоимость поиска слова или префикса фиксирована и зависит только от количества символов в слове, а не от размера словаря.

В нашем конкретном домене, поскольку у нас есть строки длиной не более 16 символов, необходимо ровно 16 шагов, чтобы найти слово, которое есть в словаре, в то время как любой отрицательный ответ, т. е. слово или префикс, не входит в дерево, может быть получен не более 16 шагов! Учитывая, что ранее мы игнорировали длину строки при вычислении сложности времени выполнения как для отсортированного списка на основе массива, так и для дерева, которое скрыто при сравнении строк, мы также можем игнорировать его здесь и безопасно заявить, что поиск выполнен за O(1) раз.

Принимая во внимание требования к пространству (и помня, что мы указали с помощью M размер словаря в байтах), дерево может иметь M узлов в худшем случае, если никакие две строки не имеют общего префикса. Но поскольку мы заметили, что в словаре существует высокая степень избыточности, необходимо выполнить большое сжатие. Словарь английского языка, который используется в примере кода, имеет размер 935 017 байт и требует 250 264 узлов с коэффициентом сжатия около 73%.

Однако, несмотря на это, даже сжатое дерево обычно требует больше памяти, чем дерево или массив. Это связано с тем, что для каждого узла необходимо как минимум 26 x sizeof(pointer) байт, плюс некоторые накладные расходы для объекта и дополнительных атрибутов. На 64-битной машине каждому узлу требуется более 200 байтов, тогда как для строкового символа требуется один или два байта, если рассматривать строки UTF.

Попытки и тесты производительности

Итак, что насчет производительности? Реализации словаря тестировались в двух разных ситуациях: проверка 20 000 000 случайных строк и поиск всех слов на 15 000 досок, случайно сгенерированных из одного и того же списка слов.

Были проанализированы четыре структуры данных: отсортированный список на основе массива, двоичное дерево, дерево, описанное выше, и дерево, использующее массивы байтов, соответствующие алфавитному индексу самих символов (незначительная и легко реализуемая оптимизация производительности). Вот результаты в мс:

Среднее количество ходов, сделанных для решения доски, составляет 2188. Для каждого хода выполняется поиск слова и поиск префикса, т. е. для проверки всех досок было выполнено более 32 млн просмотров слов и 32 млн просмотров префиксов. Примечание: это можно сделать за один шаг, я разделил их для ясности изложения. Сжатие их за один шаг сократило бы время на сборку досок почти вдвое и, вероятно, еще больше способствовало бы созданию тройки.

Как видно из вышеизложенного, поиск слов работает лучше с trie даже при использовании строк и даже быстрее при использовании алфавитных индексов, причем последний работает более чем в два раза быстрее, чем стандартное двоичное дерево. Разница в решении досок еще более очевидна: быстрое решение trie-alphabet-index более чем в четыре раза быстрее, чем список и дерево.

Подведение итогов

Дерево — это очень специализированная структура данных, которая требует гораздо больше памяти, чем деревья и списки. Однако, когда применяются определенные характеристики домена, такие как ограниченный алфавит и высокая избыточность в первой части строк, это может быть очень эффективным решением для оптимизации производительности.

использованная литература

Подробное объяснение попыток и алфавитов можно найти в главе 5 книги Роберта Седжвика «Алгоритмы, 4-е издание». На сопутствующем веб-сайте в Принстоне есть код для реализации Alphabet и TrieST, который более обширен, чем мой пример.

Описание дерева и реализации для различных языков также можно найти в Википедии, а также вы можете взглянуть на этот ресурс дерева Бостонского университета.