Теория: Префиксные деревья

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

Например, такие данные могут состоять из последовательности одинаковых символов. Рассмотрим в качестве исходной точки несколько слов из толкового словаря:

ОБЕСПЕЧИВАТЬ. Несовершенный вид к «обеспечить»...

ОБЕСПЕЧИТЬ. Совершенный вид к «обеспечивать». Предоставить материальные средства для жизни...

ОБЕСПЕЧИТЬСЯ. Совершенный вид к «обеспечиваться». Запастись, стать обеспеченным...

Как можно видеть из примера, существует несколько слов, которые начинаются на одну и ту же последовательность символов. В нашем случае у слов один и тот же корень, меняются только суффиксы и окончания.

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

В этом уроке мы более подробно познакомимся с принципами работы префиксных деревьев, их производными версиями и механизмами работы.

Зачем нужны префиксные деревья

При помощи одинаковых префиксов можно сгруппировать наши слова в следующем виде:

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

Префиксные деревья помогают прогнозировать пользовательский ввод — например, предлагая слово, наиболее близкое по составу введенных букв. Так работают системы проверки орфографии или дополнитель кода в среде разработки.

Механизм префиксов нашел свое место и в работе интернет-маршрутизации. Там он помогает эффективно хранить IP-адреса, группируемые по префиксам:

Как устроены префиксные деревья

В качестве примера префиксного дерева рассмотрим хранение слов или некоторых ассоциативных массивов.

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

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

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

Операции над деревом

Для начала представим префиксное дерево в виде кода на JavaScript:

class Trie {
  constructor(key, parent = null) {
    this.key = key
    this.children = {}
    this.parent = parent
    this.end = false
  }

  getWord() {
    let output = []
    let node = this

    while (node !== null) {
      output.unshift(node.key)
      node = node.parent
    }
    return output.join('')
  }
}

С префиксными деревьями можно проводить разные операции, в том числе поиск слов, вставка нового слова и удаление слова. Разберем их подробнее.

Поиск слова в дереве

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

Далее мы перемещаемся по указателям, соответствующим каждой следующей букве в искомом слове.

Как только все переходы будут выполнены, нужно выполнить проверку на наличие флага терминальности в поле end нашего класса.

Если флаг конца слова присутствует, то поиск считаем завершенным успешно — искомое слово найдено.

Представим теперь эту операцию в виде метода:

class Trie {
  // ...
  contains(word) {
    let node = this
    for (let i = 0; i < word.length; i++) {
      if (node.children[word[i]]) {
        node = node.children[word[i]]
      }
      else {
        return false
      }
    }
    return node.end
  }
}

Вставка слова

В таком случае операция вcтавки слова в дерево будет выглядеть следующим образом:

class Trie {
  // ...
  insert(word) {
    let node = this
    for (let i = 0; i < word.length; i++) {
      if (!node.children[word[i]]) {
        node.children[word[i]] = new Trie(word[i], node)
      }
      node = node.children[word[i]]
      if (i === word.length - 1) {
        node.end = true
      }
    }
  }
}

Удаление слова

Операция удаления слова принимает следующий вид:

class Trie {
  // ...

  remove(word) {
    let node = this
    const findWord = (node, word, index) => {
      if (index === word.length) {
        if (!node.end) {
          return false
        }
        node.end = false
        return Object.keys(node.children).length === 0
      }
      if (findWord(node.children[word[index]], word, index + 1)) {
        delete node.children[word[index]]
        return !node.end && Object.keys(node.children).length === 0
      }
      return false
    }
    findWord(node, word, 0)
  }
}

Сжатые префиксные деревья

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

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

Такие деревья гораздо удобнее использовать для чтения информации за счет уменьшения количества переходов по ссылкам между вершинами.

Рассмотрим пример такого дерева на рисунке ниже:

А так это дерево выглядит без сжатия:

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

Сжатые префиксные деревья отлично подходят для хранения данных, которые редко подвергаются изменениям.

Выводы

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