Тайли: Дерево префіксів за лаштунками автозаповнення

Що таке Трай?

Трай (призначення - ‘try’, від retrieval) – це деревоподібна структура даних, спеціально побудована для зберігання рядків. На відміну від бінарного пошукового дерева, де кожен вузол містить весь ключ, вузол у Траї зазвичай містить лише один символ, а повне слово формується шляхом проходження шляху символів від кореня до позначеного вузла. Ключова особливість полягає в тому, що спільні префікси мають однакову структуру: якщо ви вставите обидва слова 'cat' і 'car', корінь розгалужується на дитину для 'c', ця дитина розгалужується на дитину для 'a', і лише після цього спільного шляху 'ca' дерево розділяється на окремі гілки для 't' та 'r'. Будь-яке слово, що починається з 'ca', проходитиме через ці точні ж пари вузлів. Кожен вузол також містить прапорець, який показує, чи є шлях до цього вузла повним словом само по собі, оскільки одне слово може бути префіксом іншого (наприклад, 'car' та 'card'). Це означає, що форма Траю визначається повністю словниковим запасом, і будь-які дві рядки, які мають спільний префікс довжиною k, перекриватимуться точно на k вузлів перед розходженням, незалежно від того, наскільки вони відрізняються після цього.

Вставка: Построение дерева посимвольно

Вставку слова в трие можно представить как простой путь. Начиная с корня, вы смотрите на первый символ слова и проверяете, есть ли у текущего узла уже дочерний элемент для него. Если он есть, просто переходите по этому существующему дочернему элементу; если его нет, создайте новый дочерний узел для этого символа и затем переходите в него. Повторяйте это для каждого символа слова, расширяя путь только там, где его еще не существует. Когда вы потребляете последний символ, отмечайте этот конечный узел как конец допустимого слова. Поскольку существующие общие префиксы используются повторно, а не дублируются, вставка 'cat' после 'car' требует только одного нового узла (для 't'), поскольку узлы 'c' и 'a' уже существуют из предыдущей вставки. Вставка выполняется за время, пропорциональное длине вставляемого слова, а не количеству уже хранящихся слов, что делает трии масштабируемыми как словарь по мере его роста. Этот же посимвольный путь используется почти без изменений для поиска: поиск слова просто проверяет, существуют ли все необходимые дочерние элементы последовательно и отмечает конечный узел как полное слово, немедленно завершаясь, когда отсутствует необходимый символ.

Пошук за префіксами: Чому це швидко

Реальна вигода від триє – це відповіді на запити щодо префіксів, такі як «знайти всі слова, що починаються з pre», без сканування всього словника. Алгоритм проходить по триє, слідуючи за символами префікса, точно як пошук, до тих пір, поки не буде досягнуто вузла, який представляє останній символ префікса. З цього одного вузла всі слова під ним у піддереві починаються з цього префікса, тому збір усіх відповідностей – це просто глибинний перегляд цього піддерева, збір кожного шляху, що закінчується вузлом із позначкою слова.

Розглянемо невелике триє, побудоване з cat, car, card, care та dog. Проходячи «ca», ви потрапляєте на спільний вузол після «c» і «a»; піддерево нижче нього містить гілки для «t» (cat), «r» (car, яке також є повним словом), «rd» (card) та «re» (care) – чотири відповідності знайдено, досліджуючи лише одну цю підгалузь, не торкаючись непов’язаної гілки «dog» взагалі. Вартість пошуку піддерева префікса залежить тільки від довжини префікса, а вартість переліку відповідностей залежить тільки від кількості відповідностей і кількості символів у них, а не від розміру всього словника. Це структурне пояснення того, чому пошук за префіксами здається миттєвим навіть над величезними словниками.

Обмін пам'яттю та стиснуті варіанти

Tries обмінюють пам’ять на швидкість, і для розріджених даних, коли обмін може бути поганим. Простий масив вузлів на символ (наприклад, 26 слотів для малих літер) означає, що кожен вузол резервує місце для всіх можливих наступних символів, навіть якщо лише один або два з них використовуються, тому три може споживати помітно більше пам’яті, ніж просто зберігати ці слова в відсортованому списку або масиві та виконувати бінарний пошук у ньому. Перевищення відбувається через довгі ланцюги з одного дитини: довге слово без братів все ще отримує один повний вузол на символ. Патріархальні дерева (також відомі як Patricia tries) вирішують це, об'єднуючи ланцюжки вузлів з однією дитиною в один край, позначений цілим підрядком замість одного символу, тому унікальний суфікс, такий як 'ardvark', стає одним краєм замість семи окремих вузлів. Це зберігає переваги обміну префіксами для розгалужених областей, одночасно усуваючи непотрібну структуру вздовж рідких нерозгалужених проходів. Інші реалізації замінюють фіксовані масиви дочірніх елементів хеш-мапам або відсортованими малими масивами на вузол, обмінюючи трохи швидкості за виявлення на значно нижчий рівень пам’яті, коли алфавіт великий (наприклад, Unicode) або коли більшість вузлів мають дуже мало дітей, що є поширеним випадком у словниках реального світу.

Практичне застосування

Трійки та їхні стиснені родичі зустрічаються скрізь, де важливе швидке зіставлення префіксів. Автозавершення та системи пропозицій пошуку використовують їх для миттєвого переліку завершень, коли користувач вводить текст, часто зберігаючи дані про частоту або популярність на кожному вузлі слова, щоб ранжувати пропозиції. Перевірка правопису проходить по трійці, щоб підтвердити, чи існує у словнику введений термін, і може пропонувати близькі терміни, досліджуючи гілки, які відрізняються лише на один символ. Маршрутизаційні таблиці IP використовують спеціалізовану трійку над бінарних префіксів адрес для виконання зіставлення за найдовшим префіксом, дозволяючи маршрутизаторам вирішувати, який із багатьох пересічних правил мережі застосовується до адреси призначення пакета, шляхом покрокового обходу дерева та запам'ятовування найглибшого зіставлення. T9 передбачуваний текст, технологія введення тексту за допомогою цифрової телефонної клавіатури, відображав кожен натиск клавіші на набір можливих літер і використовував структури, подібні до трійки, щоб звузити валідні слова з словника, коли вводилися цифри, пропонуючи найбільш ймовірне слово перед завершенням введення. У кожному випадку експлуатується одна й та ж основна властивість: оскільки пов'язані рядки мають структуру, один обхід дерева може відповісти на цілий клас запитань щодо багатьох рядків одночасно.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Tries: The Prefix Tree Behind Autocomplete і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.