Префиксные деревья (prefix tree, trie)

Лекция 4: Префиксные деревья (Prefix tree, trie) Курносов Михаил Георгиевич к.т.н. доцент Кафедры вычислительных систем Сибирский государственный университет телекоммуникаций и информатики http://www.mkurnosov.net Словарь со строковыми ключами  При анализе вычислительной сложности операций бинарных деревьев поиска, АВЛ-деревьев, красно-черных деревьев, Splay trees, списков с пропусками (Skip lists) мы полагали, что время выполнения операции сравнения двух ключей (=, <, >) выполняется за время O(1)  Если ключи – это длинные строки (char []), то время выполнения операции сравнения становится значимым и его следует учитывать! struct rbtree *rbtree_lookup(struct rbtree *tree, int key) { while (tree != NULL) { if (key == tree->key) return tree; else if (key < tree->key) tree = tree->left; else key1 = key2 tree = tree->right; key1 < key2 } return tree; key1 > key2 } O(1) 2 Префиксные деревья (Trie)  Префиксное дерево (Trie, prefix tree, digital tree, radix tree) – это структура данных для реализации словаря (ассоциативного массива), ключами в котором являются строки  Авторы: Briandais, 1959; Fredkin, 1960  Происхождение слова “trie” – retrieval (поиск, извлечение, выборка, возврат)  Альтернативные названия: o бор (Д. Кнут, Т. 3, 1978, выборка) o луч (Д. Кнут, Т. 3, 2000, получение) o нагруженное дерево (А. Ахо и др., 2000) 3 Префиксные деревья (Trie)  Префиксное дерево (Trie, prefix tree, digital tree, radix tree) – это структура данных для реализации словаря (ассоциативного массива), ключами в котором являются строки  Практические применения: o Предиктивный ввод текста (predictive text) – поиск возможных завершений слов o Автозавершение (Autocomplete) в текстовых редакторах и IDE o Проверка правописания (spellcheck) o Автоматическая расстановка переносов слов (hyphenation) o Squid Caching Proxy Server 4 Префиксные деревья (Trie) Б Т Словарь Ключ (Key) Значение (Value) ТИГР 180 ТАПИР 300 БАРИБАЛ 150 БАРСУК 15 И A Г П Р И $ Р А Р И С Б У А К Л $ 180 $ 300 Неупорядоченное дерево поиска (ребра одного узла не упорядочены по алфавиту) $ 150 15 5 Префиксные деревья (Trie)  Префиксное дерево (trie) содержит n ключей (строк) и ассоциированные с ними значения (values)  Ключ (key) – это набор символов (c1, c2, …, cm) из алфавита A = {a1, a2, …, ad}  Каждый узел содержит от 1 до d дочерних узлов И A Г П Р И $ Р  Символ $ – это маркер конца строки (ключа) А Р И С Б У А К Л $ 180 $  За каждым ребром закреплен символ алфавита Б Т 300 $ 150 15 6 Префиксные деревья (Trie)  Ключи не хранятся в узлах дерева!  Позиция листа в дереве определяется значением его ключа  Значения (values) хранятся в листьях Б Т И A Г П Р И $ Р А Р И С Б У А К Л $ 180 $ 300 $ 150 15 7 Префиксные деревья (Trie) Ключ Тигр Значение 180 Барибал 150 Тапир 300 Волк 60 Барсук 15 Бегемот 4000 Барс Т И A Г П Р И $ Р 55  Высота h = max(keyi), i = 1, 2, …, n Е А Р И Б С $ У О Г Л Е К М $ 60 180 $  Символ $ – это маркер конца строки В Б 300 А Л $ 150 55 К О $ Т 15 $ 4K 8 Узел префиксного дерева (Trie)  Ключ – это набор символов (c1, c2, …, cm) из алфавита A = {a1, a2, …, ad}  Каждый узел содержит от 1 до d указателей на дочерние узлы  Значения хранятся в листьях Value Т И A … cd А Г П Р Р И С $ Р $ 15 180 c1 c2 Б $ 300  Как хранить c1, c2, …, cd (массив, список, BST, hash table)? 9 Вставка элемента в префиксное дерево (Trie) 1. Инициализируем k = 1 root 2. В текущем узле (начиная с корня) отыскиваем символ ci, равный k-ому символу ключа key[k] Value 3. Если ci ≠ NULL, то делаем текущим узел, на который указывает ci; переходим к следующему символу ключа (k = k + 1) и пункту 2 c1 c2 … cd Value Value c1 c2 … cd c1 c2 … cd Value c1 c2 … cd 4. Если ci = NULL, создаем новый узел, делаем его текущим, переходим к следующему символу ключа и пункту 2 5. Если достигли конца строки ($) вставляем значение в текущий в узел 10 Вставка элемента в префиксное дерево (Trie)  Добавление элемента (Тигр, 180) Т И Г Р $ 180 11 Вставка элемента в префиксное дерево (Trie)  Добавление элемента (Тигр, 180)  Добавление (Тапир, 300) Т И A Г П Р И $ Р 180 $ 300 12 Вставка элемента в префиксное дерево (Trie)  Добавление элемента (Тигр, 180)  Добавление (Тапир, 300)  Добавление (Барибал, 150) Т И Б A Г П Р И $ Р А Р И Б 180 $ 300 А Л $ 150 13 Вставка элемента в префиксное дерево (Trie)  Добавление элемента (Тигр, 180)  Добавление (Тапир, 300)  Добавление (Барибал, 150)  Добавление (Барсук, 15) Т И Б A Г П Р И $ Р А Р И С Б У А К Л $ 180 $ 300 $ 150 15 14 Вставка элемента в префиксное дерево (Trie)  Добавление элемента (Тигр, 180)  Добавление (Тапир, 300)  Добавление (Барибал, 150)  Добавление (Барсук, 15)  Добавление (Барс, 55) Т И Б A Г П Р И $ Р А Р И Б 180 $ 300 А Л $ 150 С $ 55 У К $ 15 15 Вставка элемента в префиксное дерево (Trie) function TrieInsert(root, key, value) node = root for i = 1 to Length(key) do child = GetChild(node, key[i]) if child = NULL then child = TrieCreateNode() SetChild(node, key[i], child) end if node = child end for node.value = value end function  GetChild(node, c) – возвращает указатель на дочерний узел, соответствующий символу c  SetChild(node, c, child) – устанавливает указатель, соответствующий символу c, в значение child 16 Вставка элемента в префиксное дерево (Trie) function TrieInsert(root, key, value) node = root for i = 1 to Length(key) do child = GetChild(node, key[i]) if child = NULL then child = TrieCreateNode() SetChild(node, key[i], child) end if node = child end for node.value = value TInsert = O(m(TGetChild end function + TSetChild))  GetChild(node, c) – возвращает указатель на дочерний узел, соответствующий символу c  SetChild(node, c, child) – устанавливает указатель, соответствующий символу c, в значение child 17 Поиск элемента в префиксном дереве (Trie) function TrieLookup(root, key) node = root for i = 1 to Length(key) do child = GetChild(node, key[i]) if child = NULL then return NULL end if node = child end for return node end function  GetChild(node, c) – возвращает указатель на дочерний узел, соответствующий символу c  SetChild(node, c, child) – устанавливает указатель, соответствующий символу c, в значение child 18 Поиск элемента в префиксном дереве (Trie) function TrieLookup(root, key) node = root for i = 1 to Length(key) do child = GetChild(node, key[i]) if child = NULL then return NULL end if node = child end for return node TLookup end function = O(mTGetChild)  GetChild(node, c) – возвращает указатель на дочерний узел, соответствующий символу c  SetChild(node, c, child) – устанавливает указатель, соответствующий символу c, в значение child 19 Удаление элемента из префиксного дерева I. Отыскиваем лист, содержащий искомый ключ key Т II. Делаем текущим родительский узел найденного листа III. Поднимаемся вверх по дереву и удаляем узлы 1. Если текущий узел не имеет дочерних узлов, удаляем его 2. Делаем текущим родительский узел и переходим к пункту 2 И A Г П Р И $ Р 180 $ 300 20 Узел префиксного дерева (Trie) Как хранить указатели c1, c2, …, cd на дочерние узлы? Value c1 c2 … cd  Массив указателей (индекс – номер символа) struct trie *child[33]; node->child[char_index(‘Г’)] Сложность GetChild/SetChild O(1)  Связный список указателей на дочерние узлы struct trie *child; linkedlist_lookup(child, ‘Г’) Сложность GetChild/SetChild O(d) 21 Узел префиксного дерева (Trie) Как хранить указатели c1, c2, …, cd на дочерние узлы? Value c1 c2 … cd  Сбалансированное дерево поиска (Red black/AVL tree) struct rbtree *child; rbtree_lookup(child, ‘Г’) Сложность GetChild/SetChild O(logd) 22 Представление узла Trie struct trie { char *value; char ch; struct trie *sibling; struct trie *child; }; root value ch: К Сложность GetChild/SetChild: O(d) /* Sibling node */ /* First child node */ Неупорядоченное дерево поиска (unordered search tree) К И value value ch: И ch: О value value value ch: Т ch: Т ch: М Т О Т М 23 Создание пустого узла Trie struct trie *trie_create() { struct trie *node; if ( (node = malloc(sizeof(*node))) == NULL) return NULL; node->ch = '\0'; node->value = NULL; node->sibling = NULL; node->child = NULL; return node; } TCreate = O(1) 24 Поиск узла в Trie по ключу char *trie_lookup(struct trie *root, char *key) { struct trie *node, *list; for (list = root; *key != '\0'; key++) { for (node = list; node != NULL; node = node->sibling) { if (node->ch == *key) break; } if (node != NULL) list = node->child; else return NULL; } /* Check: Node must be a leaf node! */ return node->value; } TLookup = O(md) 25 Вставка узла в Trie struct trie *trie_insert(struct trie *root, char *key, char *value) { struct trie *node, *parent, *list; parent = NULL; list = root; for (; *key != '\0'; key++) { /* Lookup sibling node */ for (node = list; node != NULL; node = node->sibling) { if (node->ch == *key) break; } 26 Вставка узла в Trie if (node == NULL) { /* Node not found. Add new node */ node = trie_create(); node->ch = *key; node->sibling = list; if (parent != NULL) parent->child = node; else root = node; list = NULL; } else { /* Node found. Move to next level */ list = node->child; } parent = node; } /* Update value in leaf */ if (node->value != NULL) free(node->value); node->value = strdup(value); return root; } TInsert = O(md) 27 Удаление узла из Trie struct trie *trie_delete(struct trie *root, char *key) { int found; return trie_delete_dfs(root, NULL, key, &found); } 28 Удаление узла из Trie struct trie *trie_delete_dfs(struct trie *root, struct trie *parent, char *key, int *found) { struct trie *node, *prev = NULL; *found = (*key == '\0' && root == NULL) ? 1 : 0; if (root == NULL || *key == '\0') return root; for (node = root; node != NULL; node = node->sibling) { if (node->ch == *key) break; prev = node; } if (node == NULL) return root; 29 Удаление узла из Trie trie_delete_dfs(node->child, node, key + 1, found); if (*found > 0 && node->child == NULL) { /* Delete node */ if (prev != NULL) prev->sibling = node->sibling; else { if (parent != NULL) parent->child = node->sibling; else root = node->sibling; } free(node->value); free(node); } return root; } TDelete = TLookup + m = O(md + m) = O(md) 30 Вывод на экран элементов Trie void trie_print(struct trie *root, int level) { struct trie *node; int i; for (node = root; node != NULL; node = node->sibling) { for (i = 0; i < level; i++) printf(" "); if (node->value != NULL) printf("%c (%s)\n", node->ch, node->value); else printf("%c \n", node->ch); if (node->child != NULL) trie_print(node->child, level + 1); } } 31 Пример работы с Trie int main() { struct trie *root; root = trie_insert(NULL, root = trie_insert(root, root = trie_insert(root, root = trie_insert(root, root = trie_insert(root, trie_print(root, 0); "bars", "60"); "baribal", "100"); "kit", "3000"); "lev", "500"); "bars", "70"); printf("Lookup 'bars': %s\n", trie_lookup(root, "bars")); root = trie_delete(root, "bars"); trie_print(root, 0); return 0; } 32 Вычислительная сложность операций Trie Способ работы c указателями c1, c2, …, cd Операция Связный список Массив Self-balanced search tree (Red black/AVL tree) Lookup O(md) O(m) O(mlogd) Insert O(md) O(m) O(mlogd) Delete O(md) O(m) O(mlogd) Min O(hd) O(hd) O(hlogd) Max O(hd) O(hd) O(hlogd)  h – высота дерева (количество символов в самом длинном ключе) 33 Преимущества префиксных деревьев  Время поиска не зависит от количества n элементов в словаре (зависит от длины ключа)  Для хранения ключей на используется дополнительной памяти (ключи не хранятся в узлах)  В отличии от хеш-таблиц поддерживает обход в упорядоченном порядке (от меньших к большим и наоборот, реализует ordered map) – зависит от реализации SetChild/GetChild  В отличии от хеш-таблиц не возникает коллизий 34 Производительность строковых словарей Операция     Trie Self-balanced search tree (linked list) (Red black/AVL tree) Hash table Lookup O(md) O(mlogn) O(m + n) Insert O(md) O(mlogn) O(m) Delete O(md) O(mlogn) O(m + n) Min O(hd) O(logn) O(H + n) Max O(hd) O(logn) O(H + n) m – длина ключа d – количество символов в алфавите (константа) n – количество элементов в словаре H – размер хеш-таблицы 35 Bitwise tree  Bitwise trie – префиксное дерево (trie), в котором ключи рассматривается как последовательность битов  Bitwise trie – это бинарное дерево 36 Radix tree (patricia trie)  Radix tree (radix trie, patricia trie, compact prefix tree) – префиксное дерево (trie), в котором узел содержащий один дочерний элемент объединяется с ним для экономии памяти PATRICIA trie:  D. R. Morrison. PATRICIA – Practical Algorithm to Retrieve Information Coded in Alphanumeric. Jrnl. of the ACM, 15(4). pp. 514-534, Oct 1968.  Gwehenberger G. Anwendung einer binären Verweiskettenmethode beim Aufbau von Listen. Elektronische Rechenanlagen 10 (1968), pp. 223–226 37 Radix tree (patricia trie) http://en.wikipedia.org/wiki/Radix_tree 38 Suffix tree  Suffix tree (PAT tree, position tree) – префиксное дерево (trie), содержащее все суффиксы заданного текста (ключи) и их начальные позиции в тексте (values)  Суффиксное дерево для текста BANANA Суффиксы: A$, NA$, ANA$, NANA$, ANANA$, BANANA$  Применение: o o o o o  Поиск подстроки в строке O(m) Поиск наибольшей повторяющейся подстроки Поиск наибольшей общей подстроки Поиск наибольшей подстроки-палиндрома Алгоритм LZW сжатия информации Автор: Weiner P. Linear pattern matching algorithms // 14th Annual IEEE Symposium on Switching and Automata Theory, 1973, pp. 1-11 39 Литература  Ахо А.В., Хопкрофт Д., Ульман Д.Д. Структуры данных и алгоритмы. – М.: Вильямс, 2001. – 384 с.  Гасфилд Д. Строки, деревья и последовательности в алгоритмах. Информатика и вычислительная биология. – Санкт-Петербург: Невский Диалект, БХВ-Петербург, 2003. – 656 с.  Билл Смит. Методы и алгоритмы вычислений на строках. Теоретические основы регулярных вычислений. – М.: Вильямс, 2006. – 496 с. 40