Содержание


Работа со структурами данных в языках Си и Python

Часть 10. B-деревья и TRIE-деревья

Comments

Серия контента:

Этот контент является частью # из серии # статей: Работа со структурами данных в языках Си и Python

Следите за выходом новых статей этой серии.

Этот контент является частью серии:Работа со структурами данных в языках Си и Python

Следите за выходом новых статей этой серии.

TRIE-деревья

В современных текстовых редакторах (неважно online или offline) обязательно присутствует функция проверки орфографии вводимого текста на основе встроенного словаря. Эта функция должна извлечь из текста все слова и проверить их написание на соответствие со словарем. Для построения подобных словарей используется древовидная структура данных, которая называется TRIE-дерево (или дерево префиксов). Предположим, имеется следующий фрагмент текста:

THE THEN THIN THIS TIN SIN SING.

Требуется составить дерево из слов, входящих в это предложение, однако в этих словах присутствует много повторяющихся символов. TRIE-дерево предназначено для решения подобной задачи, как показано на рисунке 1.

Рисунок 1. TRIE-дерево
Рисунок 1. TRIE-дерево
Рисунок 1. TRIE-дерево

Символ $ в терминальных узлах дерева - это endmarker, который позволит продолжить составление дерева со всеми возможными сочетаниями символов. Представленное дерево построено на основе английского алфавита, поэтому каждый узел может иметь не более 27 потомков - 26 букв и endmarker. На практике у большинства узлов будет меньше 27 потомков.

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

В листинге 1 представлен один из возможных вариантов определения базовой структуры TRIE-дерева.

Листинг 1. Базовая структура для представления узлов TRIE-дерева
enum trie_node_type
{
  TRIE_LEAF,
  TRIE_SUBTRIE
};

typedef enum trie_node_type * trie_pointer;

В TRIE-дереве листья обозначаются как TRIE_LEAF, а поддеревья обозначаются как TRIE_SUBTRIE. Поэтому можно определить два типа узлов, как показано в листингах 2 и 3.

Листинг 2. Структура для описания поддерева
//константы для управления скоростью поиска и использования памяти
#define LOG_TRIE_BRAHCH_FACTOR 4 
#define TRIE_BRANCH_FACTOR (1<<L0G_TRIE_BRANCH_FACT0R)

struct trie_subtrie
{
  enum trie_node_type type;
  struct trie_leaf * exact_match;
  //количество ключей, для которых узел является префиксом
  int count;
  trie_pointer next_level[TRIE_BRANCH_FACTOR];
};
Листинг 3. Структура для описания узла
struct trie_leaf
{
  enum trie_node_type type;
  unsigned char * key; // уникальный поисковый ключ
  size_t len_key; // длина ключа
  trie_result result; //используется для вставки нового ключа
};

В листинге 4 представлена структура для описания самого TRIE-дерева и функция для его создания.

Листинг 4. Создание TRIE-дерева
struct trie
{
  trie_pointer root;
}; 

struct trie * trie_create(void)
{
  struct trie * trie = malloc(sizeof(*trie));
  if(trie)
  {
    trie->root=0;
  }
  return trie;
}

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

Листинг 5. Функции для удаления узлов TRIE-дерева
//функция для удаления всего дерева
void trie_destroy(struct trie * trie)
{
  if(trie)
  {
    destroy_node(trie->root);
    free(trie);
  }
}

//функция для удаления узла TRIE-дерева
static void destroy_node(trie_pointer node)
{
  if(node == 0) return;
  
  switch(*node)
  {
    case TRIE_LEAF:
    {
      struct trie_leaf * p = (struct trie_leaf * ) node;
      destroy_leaf(p);
      break;
    }
    case TRIE_SUBTRIE:
    {
      struct trie_subtrie * p = (struct trie_subtrie * )node;
      int i;
      destroy_leaf(p->exact_match);
      for(i=0; i<TRIE_BRANCH_FACTOR;i++)
          destroy_node(p->next_level[i]);
      free(p);
      break;
    }
    default:
  }
}

// функция для удаления терминального узла
static void destroy_leaf(struct trie_leaf * leaf)
{
  if(leaf)
  {
    free(leaf->key);
    free(leaf);
  }
}

B-деревья

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

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

Характеристики B-дерева:

  1. m - порядок (максимальное количество дочерних узлов);
  2. каждый узел, кроме корневого, должен иметь как минимум m/2 дочерних узлов;
  3. корневой узел имеет как минимум 2 дочерних узла;
  4. все листья находятся на одном уровне;
  5. узел, имеющий k потомков, может иметь k-1 ключей.

Что касается ограничения на величину m, то оно зависит от характеристик жесткого диска, в частности от размера его блока.

Каждый узел в B-tree имеет упорядоченный набор ключей и набор указателей на своих потомков. Например, если у узла n0 имеются три потомка - n1, n2, n3, то ключами узла n0 должны быть два разделителя - a1 и a2, при этом - все ключи поддерева n1 должны быть меньше a1, все ключи поддерева n2 должны быть меньше a2, и т.д.

B-tree - это сбалансированное дерево, поэтому у каждого узла есть две константы:

  • U - максимально возможное число дочерних узлов;
  • L - минимально возможное число дочерних узлов.

Когда происходит вставка или удаление узла, эти константы рекурсивно проверяются по всему дереву сверху вниз. Если в каком-то узле возникает отклонение от значений L и U, то узлы будут объединяться или разделяться для восстановления баланса.

B-деревья широко применяются в базах данных и файловых системах. Также встречаются различные варианты B-деревьев, например, 2-3-дерево, где каждый узел может иметь не более трех потомков.

На рисунке 2 показан пример B-дерева. Когда количество ключей в узле превышает определенный порог, то этот узел разделяется на два узла, между которыми ключи делятся поровну. Каждый ключ в узле является корнем для поддерева, в котором хранятся ключи, находящиеся в диапазоне между соответствующими ключами корневого узла.

Рисунок 2. B-дерево
Рисунок 2. B-дерево
Рисунок 2. B-дерево

Так как B-дерево относится к сбалансированным, то путь от корня до любого листа требует одинакового количества шагов. Существует связь между максимальным количеством ключей в узле и максимальным количеством его потомков. Если число ключей обозначить как 2d, то число узлов обычно будет на единицу больше - 2d + 1. Также существует зависимость между высотой дерева h и количеством ключей n.

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

Существуют два типа B-деревьев: B+ и B*. На рисунке 3 представлено B+-дерево. В данной реализации все данные хранятся в отдельном слое дерева - в листьях, при этом они отсортированы. Этот слой может быть организован в связный список, что является основным отличием от обычного B-дерева.

Рисунок 3. B+-дерево
Рисунок 3. B+-дерево
Рисунок 3. B+-дерево

B*-дерево используется в файловых системах HFS и Reiser4 и отличается B+-деревьев тем, что когда узел полностью заполнен данными, то он не разбивается на 2 узла. Вместо этого ищется место в уже существующем соседнем узле, и только после того, как оба узла будут заполнены, они разделяются на три узла.

Операции с B-деревом

Для поиска или вставки узла в такое дерево требуется всего один проход. Поиск в B-дереве отличается от поиска в обычном бинарном дереве тем, что в последнем случае он основан на выборе между правым и левым узлом. В случае с B-деревом - это линейный поиск между соседними ключами.

При вставке ключа нужно учесть несколько вариантов: ключ может добавляться как в узел, так и в лист. В первом случае если происходит переполнение узла, то он делится пополам. На рисунке 4 показано, как может происходить формирование B-дерева в случае, когда в него последовательно вставляются натуральные числа от 1 до 7. В этом примере каждый узел может содержать не более двух ключей.

Рисунок 4. Создание B-дерева
Рисунок 4. Создание B-дерева

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

  • ключ является разделителем;
  • при удалении ключа число ключей может стать меньше необходимого минимума.

Заключение

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

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

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


Ресурсы для скачивания


Похожие темы

  • Работа со структурами данных в языках Си и Python. Часть 1.
  • Работа со структурами данных в языках Си и Python. Часть 2.
  • Работа со структурами данных в языках Си и Python. Часть 3.
  • Работа со структурами данных в языках Си и Python. Часть 4.
  • Работа со структурами данных в языках Си и Python. Часть 5.
  • Работа со структурами данных в языках Си и Python. Часть 6.
  • Работа со структурами данных в языках Си и Python. Часть 7.
  • Работа со структурами данных в языках Си и Python. Часть 8.
  • Работа со структурами данных в языках Си и Python. Часть 9.
  • Работа со структурами данных в языках Си и Python. Часть 10.

Комментарии

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

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=Linux, Open source
ArticleID=681837
ArticleTitle=Работа со структурами данных в языках Си и Python: Часть 10. B-деревья и TRIE-деревья
publish-date=06212011