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

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

Історія, етимологія Вперше концепцію префіксного дерева використав 1912 року Аксель Туе для подання множини, в якій кожен елемент є рядком Процитовано за Кнутом.. В інформатиці вперше префіксні дерева описав 1959 року Рене де ла Бриндаіс Процитовано за Брассом і Кнутом.. Також 1960 року незалежно цю концепцію описав Едвард Фредкін, який запропонував використовувати слово trie. Вимовляти треба було (так само як і англійське слово «дерево» — «tree»). Однак, інші автори пропонують вимовляти це (так само як і англійське слово «try») для того, щоб відрізніти від «tree».

Операції над префіксним деревом Префіксні дерева підтримують тіж самі операції, котрі можна знайти в асоціативному масиві — це операції додавання пари, а також пошуку та видалення пари за ключем:

вставити (ключ, значення) шукати (ключ) вилучити (ключ)

Кожна з цих операцій реалізується за допомогою спуску деревом від кореня, але ефективність такої операції залежить від організації навігації вузлами. Для подальшого аналізу різних підходів до цієї проблеми позначимо через довжину рядка, який запитують / видаляють / вставляють, а через позначимо розмір алфавіту, тобто кількість різних символів на ребрах цього префіксного дерева. Нехай певний вузол має дітей (при цьому ). Позначимо через посилання на цих дітей, а через  — символи, якими позначено ребра, що з'єднують із відповідними дітьми.

Найпростіший спосіб організувати навігацію в  — зберігати динамічний масив пар . За такого підходу всі три операції виконуються за . Якщо ж вставлення і видалення не використовуються, то краще відсортувати пари за ключем і тоді операцію перевірки наявності ключа в префіксному дереві можна буде виконувати за за допомогою двійкового пошуку у вузлах. Можна досягти часу виконання для всіх трьох операцій, якщо зберігати пари відсортованими за ключем в будь-якому збалансованому двійковому дереві пошуку, наприклад, у червоно-чорному дереві або АВЛ-дереві. У більшості мов програмування реалізація якогось збалансованого дерева пошуку входить до стандартної бібліотеки у вигляді асоціативного масиву. Інший популярний спосіб організації навігації в  — зберігати пари за ключем в геш-таблиці. За такого підходу всі три операції виконуються за очікуваний час (тоді як два попередні варіанти мають гарантований час виконання). У багатьох мовах програмування геш-таблиці входять до стандартної бібліотеки. Можна ще поліпшити часові гарантії, замінивши геш-таблицю гешуванням зозулі або іншою аналогічною структурою: такий геш дає змогу виконувати запит і видалення ключів за гарантований час і лише вставлення виконується за очікуваний час .

Компактне префіксне дерево Розглянемо префіксне дерево, яке містить усі суфікси рядка , що має довжину . Це дерево має не менше вузлів і, отже, займає пам'яті. У цьому прикладі таке марнотратне споживання пам'яті викликане наявністю багатьох вузлів, що мають лише одну дитину. Для подолання цієї проблеми Дональд Моррісон розробив модифікацію префіксного дерева, звану компактним префіксним деревом (також зустрічаються варіанти стиснуте префіксне дерево, базисне дерево, стислий бір, компактний бір, стислий промінь, стиснуте навантажене дерево; сам Моррісон називав свою структуру «PATRICIA tree» і ця назва досі іноді зустрічається).

Визначення та способи зберігання

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

Компактне префіксне дерево будують зі звичайного префіксного дерева, яке містить ключі , послідовно видаляючи кожен вузол (крім кореня), який має лише одну дитину і не є виділеним, при цьому батька й дитину видаленого вузла з'єднують і утворене ребро позначають рядком, отриманим з'єднанням позначок на ребрах батько-вузол і вузол-дитина (хоча такий метод побудови компактного префіксного дерева не рекомендується).

Ефективність компактного префіксного дерева походить від способу подання позначок на ребрах. Оскільки кожна позначка є підрядком якогось рядка , можна подати за допомогою трійки чисел , де (тут позначає підрядок рядка , що починається в позиції та закінчується в позиції ). Якщо всі рядки є підрядками якогось одного заданого рядка , то позначки можна подавати парами чисел , відповідними підрядкам . Навігація у вузлах організовується тими ж способами, що й у звичайному префіксному дереві, але символами-посиланнями слугують перші символи в позначках на ребрах вузол-дитина: наприклад, у компактному префіксному дереві на малюнку вузол, відповідний рядку «Pe», має трьох дітей і символами-посиланнями в цьому вузлі слугують «t», «c», «p», які є першими символами в позначках «ter», «ck», «ppers» на ребрах вузол-дитина. Можна показати, що компактне префіксне дерево для набору рядків має всього не більше вузлів і, отже, займає пам'яті, якщо не брати до уваги пам'ять необхідну для зберігання самих рядків .

Операції над компактним префіксним деревом Операції запиту, видалення та вставлення в компактному префіксному дереві можна виконувати так само, як і у звичайному префіксному дереві, за допомогою спуску від кореня. При цьому алгоритм стає дещо складнішим через необхідність під час спуску ребрами, позначеними рядками довжини два і більше, читати вміст позначки з відповідного підрядка одного з рядків . Теоретично час роботи такого алгоритму можна оцінити так, як і для звичайного префіксного дерева (тобто як , , , залежно від організації навігації у вузлах), але на практиці операції над компактним префіксним деревом нерідко виявляються швидшими через те, що більшість шляху від кореня до вузла проходить ребрами і немає потреби часто звертатися до структур даних у вузлах.

Якщо довжини всіх рядків порівняно невеликі (наприклад, у межах довжини однієї кеш-лінії, яка на багатьох сучасних процесорах становить 64 байти), то промахів кешу, викликаних частими перескоками між різними позначками, можна уникнути за допомогою іншого методу спуску деревом (якраз цей метод описано в статті Моррісона). Наприклад, розглянемо алгоритм пошуку найдовшого префікса заданого рядка , який можна прочитати, рузаючись від кореня до якогось вузла в заданому компактному префіксному дереві; інші операції можна реалізувати за аналогією.

Алгоритм полягає в тому, щоб першим проходом опитати тільки вузли дерева, пропускаючи ребра, і, отже, спустившись якнайнижче в дереві, знайти рядок зі множини , що має найдовший спільний префікс із рядком . Потім потрібно вирахувати спільний префікс і звичайним наївним алгоритмом та повернути результат. У наведеному нижче C-подібному псевдокоді s[i] позначає рядок , root позначає корінь дерева, і кожен вузол містить такі поля / методи: x->len — довжина позначки на ребрі від x до батька x; x->child(c) — посилання на дитину вузла x, з'єднану з x ребром з позначкою, яка починається символом c, або nullptr, якщо такої дитини немає; x->src — число, таке, що рядок на шляху від кореня до x є префіксом рядка .size_t find_longest_prefix(string t) { struct node_t *x = root; for (size_t i = 0; i < t.length(); i += x->len) if (x->child(t[i]) != nullptr) x = x->child(t[i]); else break; return довжина спільного префіксу t и s[x->src]; }

Застосування Структура широко застосовується в алгоритмах пошуку та інших місцях.

Префіксне дерево використовується в алгоритмі Ахо — Корасік для пошуку кількох рядків у заданому рядку. Також префіксне дерево використовується в алгоритмі Лемпеля — Зіва — Велча. Компактне префіксне дерево, що містить усі суфікси заданого рядка, називається суфіксним деревом і відіграє важливу роль в алгоритмах пошуку. Компактне префіксне дерево використовується, зокрема, для морфологічного аналізу природних мов.Pymorphy 2 https://habrahabr.ru/post/176575/ Компактне префіксне дерево — одна зі структур даних ядра Linux.

Див. також

Алгоритм Ахо — Корасік Суфіксне дерево

Примітки

Література

Посилання

Bentley, Jon; Sedgewick, Robert (1998-04-01). "Ternary Search Trees". Dr. Dobb's Journal (Dr Dobb's). Archived from the original on 2008-06-23. Архівна , by Lloyd Allison, Monash University. Algorithms and Data Structures Research & Reference Material: PATRICIA , Lloyd Allison, Monash University. Patricia Tree , NIST Dictionary of Algorithms and Data Structures. Crit-bit trees , by Daniel J. Bernstein. Radix Tree API in the Linux Kernel , by Jonathan Corbet. Kart (key alteration radix tree) , by Paul Jarc.