Пользователь
0,0
рейтинг
17 сентября 2012 в 10:31

Разработка → Сжатые префиксные деревья tutorial

Тема префиксных деревьев поиска уже неколько раз поднималась на хабре. Здесь, например, кратко описывается, что такое префиксное дерево и зачем оно нужно, и рассматриваются основные операции над такими деревьями (поиск, вставка, удаление). К сожалению, ничего при этом не говорится про реализацию. В этом недавнем посте рассматривается «питонья библиотека datrie», являющаяся Cython-оберткой библиотеки libdatrie. По последней ссылке имеется хорошее описание реализации частично сжатых префиксных деревьев в виде детерминированных конечных автоматов (с использованием массивов). Я решил внести свои пять копеек в эту тему, рассмотрев реализацию на языке С++ префиксных деревьев с помощью указателей. Кроме того, была и еще одна цель — сравнить между собой поиск строк с помощью сбалансированного двоичного дерева поиска (АВЛ-дерево) и сжатого префиксного дерева.



Введение


Напомним, что префиксное дерево — это структура данных, предназначенная для хранения объектов с поразрядной структурой, например, строк. Далее мы будем рассматривать реализацию префиксных деревьев для хранения именно строк в алфавите ASCII, каждая строка заканчивается терминальным символом, который больше нигде в строке не встречается. На рисунках и в примерах терминальный символ будем обозначать знаком доллара, а в коде — нулевым символом (таким образом, в нашей реализации строки будут стандартными C-строками, что позволит использовать нам стандартную бибилиотеку string.h). На другие алфавиты все нижеизложенное должно переноситься элементарно.

В обычном префиксном дереве каждому ребру приписан некоторый символ, в вершинах же хранится различная служебная (или пользовательская) информация. Таким образом, любой путь от корня дерева до некоторого его листа определяет ровно одну строку. Считается, что эта строка хранится в заданном дереве. Например, на следующем рисунке префиксное дерево хранит следующий набор строк {abab$, aba$, bc$, b$, bac$, baca$}. Корень слева, листья (их число совпадает с числом строк) — справа. Путь, соответствующий строке baca$, выделен красным цветом.



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

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



 

Представление дерева с помощью указателей


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



Еще одна проблема — исходящая степень узла дерева может быть произвольной (вплоть до размера используемого алфавита). Для решения этой проблемы применим стандартный прием, а именно, будем хранить в каждом узле список дочерних узлов. Список будет односвязным и хранить в узле мы будем только голову списка (старшая дочь). Это позволит нам заодно отказаться от пустого корня. Теперь дерево будет представляться указателем на голову списка дочерних узлов старого корня (т.е. мы заменяем дерево на лес). Таким образом, каждый узел теперь будет содержать ровно два указателя: link — на старший дочерний узел, next — на свою младшую сестру. На следующем рисунке показан процесс такой трансформации, синие стрелки соответствуют указателям link, красные — указателям next.



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

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



Теперь можно перейти и к реализации. Узел дерева — это цепочка символов key, ее длина len (цепочка не обязана заканчиваться терминальным символов, поэтому нужно явно знать ее длину), и два указателя link и next. Плюс минимальный конструктор, который создает тривиальное дерево, состоящее из одного узла с заданным ключом (для копирования символов будем использовать стандартную функцию strncpy), и еще более минимальный деструктор.

struct node // структура для представления узлов дерева
{
	char* key;
	int len;
	node* link;
	node* next;
	node(char* x, int n) : len(n), link(0), next(0) 
	{ 
		key = new char[n]; 
		strncpy(key,x,n);	
	}
	~node() { delete[] key; }
};


Поиск ключей


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

int prefix(char* x, int n, char* key, int m) // длина наибольшего общего префикса строк x и key
{
	for( int k=0; k<n; k++ )
		if( k==m || x[k]!=key[k] ) 
			return k;
	return n;
}

В случае поиска нас интересуют три случая:
  1. общий префикс может быть пустым, тогда надо рекурсивно продолжить поиск в младшей сестре данного узла, т.е. перейти по ссылке next;
  2. общий префикс равен искомой строке x — поиск успешный, узел найден (тут мы существенно используем тот факт, что конец строки за счет наличия в нем терминального символа может быть найден только в листе дерева);
  3. общий префикс совпадает с ключом, но не совпадает с x — переходим рекурсивно по ссылке link к старшему дочернему узлу, передавая ему для поиска строку x без найденного префикса.

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

node* find(node* t, char* x, int n=0) // поиск ключа x в дереве t
{
	if( !n ) n = strlen(x)+1; 
	if( !t ) return 0;
	int k = prefix(x,n,t->key,t->len);
	if( k==0 ) return find(t->next,x,n); // поищем у сестры
	if( k==n ) return t;
	if( k==t->len ) return find(t->link,x+k,n-k); // поищем у старшей дочери
	return 0; 
}

Длина n строки x по умолчанию равна нулю (и тогда она явно вычисляется), чтобы можно было вызывать функцию поиска, указывая только корень дерева и строку для поиска:

  ...
  node* p = find(t,"baca");
  ...

На следующем рисунке показан процесс поиска трех строк (один успешный и два не очень) в вышеприведенном дереве.



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

Вставка ключей


Вставка нового ключа (как и в двоичных деревьях поиска) очень похожа на поиск ключа. Естественно с несколькими отличиями. Во-первых, в случае пустого дерева нужно создать узел (тривиальное дерево) с заданным ключом и вернуть указатель на этот узел. Во-вторых, если длина общего префикса текущего ключа и текущей строки x больше нуля, но меньше длины ключа (второй случай недачного поиска), то надо разбить текущий узел на два, оставив в родительском узле найденный префикс, и поместив в дочерний узел p оставшуюся часть ключа. Эта операция реализуется функцией split. После разделения нужно продолжить процесс вставки в узле p строки x без найденного префикса.



Код разделения узла:

void split(node* t, int k) // разбиение узла t по k-му символу ключа
{
	node* p = new node(t->key+k,t->len-k);
	p->link = t->link;
	t->link = p;
	char* a = new char[k];
	strncpy(a,t->key,k);
	delete[] t->key;
	t->key = a;
	t->len = k;
}

Код вставки:

node* insert(node* t, char* x, int n=0) // вставка ключа x в дерево t
{
	if( !n ) n = strlen(x)+1;
	if( !t ) return new node(x,n);
	int k = prefix(x,n,t->key,t->len);
	if( k==0 ) t->next = insert(t->next,x,n);
	else if( k<n )
	{
		if( k<t->len ) // режем или нет?
			split(t,k);
		t->link = insert(t->link,x+k,n-k);
	}
	return t;
}


Пример вставки ключей abaca$ и abcd$ в вышерасмотренное дерево приведен на следующем рисунке.



Заметим, что в случае, если заданная строка x уже содержится в дереве, то никакой вставки сделано не будет. С этой точки зрения префиксное дерево ведет себя как добропорядочное множество.

Удаление ключей


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



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



Код функции слияния достаточно тривиальный — образуем новый ключ, переподвешиваем поддерево узла p к узлу t, удаляем узел p:

void join(node* t) // слияние узлов t и t->link
{
	node* p = t->link;
	char* a = new char[t->len+p->len];
	strncpy(a,t->key,t->len);
	strncpy(a+t->len,p->key,p->len);
	delete[] t->key;
	t->key = a;
	t->len += p->len;
	t->link = p->link;
	delete p;
}

За слияние отвечает старший узел, потому что у младшего нет информации о своем родителе. Критериями проведения слияния является 1) удаление ключа по ссылке link, а не по next; 2) после удаления у новой ссылки link нет ссылки next (дочерний узел всего один, значит его можно слить с текущим).

node* remove(node* t, char* x, int n=0) // удаление ключа x из дерева t
{
	if( !n ) n = strlen(x)+1;
	if( !t ) return 0;
	int k = prefix(x,n,t->key,t->len);
	if( k==n ) // удаление листа
	{
		znode* p = t->next;
		delete t;
		return p;
	}
	if( k==0 ) t->next = remove(t->next, x, n);
	else if( k==t->len ) 
	{
		t->link = remove(t->link, x+k, n-k);
		if( t->link && !t->link->next ) // у узла t имеется единственная дочь?
			join(t);
	}
	return t;
}

Примеры удаления ключей без слияния:



и со слиянием:



Эффективность


Было проведено небольшое численное исследование по сравнению АВЛ-деревьев и префиксных деревьев по времени работы и потребляемой памяти. Результаты получились для меня несколько обескураживающими (возможно, сказалась кривизна чьих-то рук). Но по порядку… Для тестирования было сформировано 8 тестовых набор строк. Их краткие характеристики перечислены в таблице.



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



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



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



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

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

Спасибо за внимание!

Буду благодарен за комментарии и замечания!
Николай Ершов @nickme
карма
130,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (23)

  • НЛО прилетело и опубликовало эту надпись здесь
    • 0
      1) На первых двух графиках сравниваются между собой два времени, какая разница, какая там шкала? На третьем шкала обозначена… На серьезную статобработку данных времени и сил пока нет :)
      2) Стек выдержал :) Кстати, да, надо было бы глубину дерева измерить. А в принципе, можно и итеративную реализацию сделать…
      3) А какая длина массива должна быть (это в случае, когда дерево мутируется)? На самом деле я уже думал над таким вариантом — держать в узле вектор указателей на всех дочерей узла…
      • НЛО прилетело и опубликовало эту надпись здесь
        • 0
          1) С этим замечанием согласен, на графике время отнормировано на размер (в символах) используемого набора строк, иначе разброс для одного графика оказывался очень большим. Сейчас попробую пересчитать чистое время… На третьем графике шкала обозначена в подписи :) — по оси Y отложено количество байт на один символ (символ у меня занимает один байт)…
          2,3) Про продакшн никто и не говорит :)
    • +1
      Глубина рекурсии в префиксных деревьях обычно мала: глубина дерева не больше самого длинного ключа, а число связей не больше размера алфавита. Если ключи разумные, а не «Война и Мир», то все нормально.
      • +1
        А вы не пробовали хранить в нодах не списки, а АВЛ-деревья с алфавитом? Сжать префиксное дерево тогда не получится, но зато поиск будет быстрым. Предположительно.
        • 0
          Была мысль вместо односвязного списка хранить двоичное дерево (то же АВЛ), но что-то страшно стало :) А вот с алфавитом все немного интереснее выглядит, надо будет подумать…
  • 0
    Внутренние участки без ветвлений — специфическая ситуация, редко возникающая на реальных данных. С самого начала строить структуру данных вокруг оптимизации этого момента мне кажется преждевременным. Попробуйте добавить к сравнению эту реализацию, разделяя слова «долларом».
    • +1
      Доля правды в ваших словах есть. Вот распределение длин ключей во внутренних узлах дерева для двух тестовых наборов:



      Однако, хранить в одном узле один символ (при двух указателях) — это, по-моему, перебор. Хотя, с другой стороны, такой вариант (несжатое префиксное дерево) у меня реализован, но статистику я с него еще не снимал…

      Ссылку попозже посмотрю, спасибо!
  • +1
    Не хватает оптимизаций по памяти, in-place constructor и прочего. На каждый чих выделять кусок памяти — некрасиво.

    P. S. Пролистал, вечером буду детально разбираться, но выглядит как и все прочие ваши статьи на 5+.
    • +1
      Эти куски памяти к тому же и очень мелкие :(
      • +1
        А это неважно, функции работы с выделением памяти — дорогие, даже для маленьких размеров :(
        • +2
          Это я к тому, что суммарный объем необходимой памяти, в принципе, один и тот же, поэтому, чем меньше куски, тем больше их нужно, тем больше операций с памятью…
          • +1
            Пулы обьектов спешат на помощь!
  • +2
    «Полностью сжатое дерево», которое вы реализовали, вроде бы Patricia Tree называется (еще Radix Trie или PAT-trie).

    В libdatrie достаточно большие накладные расходы на поддержку юникода: для каждого символа производится преобразование между «внешним» алфавитом и внутренним, и время поиска зависит линейно от количества интервалов во внешнем алфавите. Т.е. сравнение времени поиска не совсем 1 к 1 (вопрос о полезности этой фичи — отдельный).

    К тому же в libdatrie каждому ключу сопоставляется целое число (это +4 байта к каждому ключу), а в вашей реализации нет, поэтому замеры памяти нечестные :)

    Префиксные деревья, кстати, довольно плохо текстовую информацию все-таки сжимают. Самая эффективная схема хранения пока, насколько знаю, — это LOUDS-trie (в котором данные упаковываются с помощью разных битовых трюков). Есть MARISA-trie code.google.com/p/marisa-trie/, в котором строки хранятся в LOUDS-trie, а остатки не хранятся «как есть», а помещаются в LOUDS-trie следующего уровня (поэтому «рекурсивное trie») — на моих данных (3млн русских слов в utf8) marisa-trie тратит примерно в 10 раз меньше памяти, чем lidatrie. При этом каждому ключу в MARISA-trie тоже сопоставляется значение (4байтовое целое число), но это число не произвольное, а получается из ключа с использованием perfect hash-функции (которая вычисляет значение на основе положения ключа в дереве) — и поэтому эти значения памяти не требуют совсем.

    Но MARISA-trie — это хак, причем я так и не понял, зачем он) Эта схема не поддерживает вставку новых значений и удаление существующих, а раз так, то MARISA-trie становится просто небыстрым не до конца минимизированным DAWG.

    В DAWG текстовые данные занимают еще меньше места, т.к. строится минимальный автомат для данных строк. Те же 3 млн русских слов в utf8 в DAWG занимают меньше 3М с учетом значений (в 30+ раз меньше, чем в libdatrie) в реализации code.google.com/p/dawgdic/ — это DAWG, который основан на минимизации Double-Array Trie (той же структуры, что и в libdatrie).

    Если интересно, еще обзор различных структур данных делал (применительно к питону, на английском, с уклоном в префиксные деревья): kmike.ru/python-data-structures/
    • 0
      Спасибо большое за ссылки, обязательно поизучаю на досуге! С libdatrie, кстати, я сравнение не делал… Относительно терминологии, мне больше нравится Radix Tree и русский вариант — дерево цифрового поиска.
      • 0
        упс, точно)
      • +1
        В libdatrie Double-Array используется, кстати, именно чтоб экономить память на узлах — в узлах не нужно хранить указатели. У вас там 3 указателя на узел (1 на текст и 2 для связи — это по 12 или 24 байта на узел в зависимости от разрядности ОС). По моим тестам (опять-таки те 3млн слов) Double-Array был эффективнее (по памяти) PAT-trie примерно в 2 раза, несмотря на то, что узлов больше.

        Кроме того, хранение всего в линейных массивах должно ускорять работу, т.к. данные префетчатся в кеш процессора (а хождение по указателям для современных процессоров — это кошмар, т.к, нужно брать данные из разных участков памяти и пре-заполнение кеша не работает). По скорости самым быстрым считается HAT-trie, в котором структура данных спроектирована именно исходя из интересов современных процессоров, чтоб данные в кеш процессора попадали (но там гибрид trie и хэш-таблицы получился, и из-за этого всякие trie-операци медленные и корявые).
  • 0
    Кстати, кто-нибудь может подскажет, где найти стандартные тестовые наборы для такого рода задач?
  • 0
    Если вам действительно интересно, можете прочитать работу на близкую тему: ceur-ws.org/Vol-899/paper1.pdf
  • 0
    > И вот здесь все оказалось не так, как задумывалось. Сбалансированное двоичное дерево тратит на поиск в среднем примерно в два раза меньше времени, чем префиксное.

    Разве должно было быть иначе?

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.