Бор — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
Строка 1: Строка 1:
{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
 
|+
 
|-align="center"
 
|'''НЕТ ВОЙНЕ'''
 
|-style="font-size: 16px;"
 
|
 
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
 
 
Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
 
 
Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
 
 
Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
 
 
''Антивоенный комитет России''
 
|-style="font-size: 16px;"
 
|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
 
|-style="font-size: 16px;"
 
|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
 
|}
 
 
 
'''Бор''' (англ. ''trie'', ''луч'', ''нагруженное дерево'') {{---}} структура данных для хранения набора строк, представляющая из себя [[Дерево, эквивалентные определения | подвешенное дерево]] с символами на [[Основные определения теории графов | рёбрах]]. Строки получаются последовательной записью всех символов, хранящихся на [[Основные определения теории графов | рёбрах]] между корнем бора и терминальной вершиной. Размер бора линейно
 
'''Бор''' (англ. ''trie'', ''луч'', ''нагруженное дерево'') {{---}} структура данных для хранения набора строк, представляющая из себя [[Дерево, эквивалентные определения | подвешенное дерево]] с символами на [[Основные определения теории графов | рёбрах]]. Строки получаются последовательной записью всех символов, хранящихся на [[Основные определения теории графов | рёбрах]] между корнем бора и терминальной вершиной. Размер бора линейно
 
зависит от суммы длин всех строк, а поиск в бору занимает время, пропорциональное длине образца.
 
зависит от суммы длин всех строк, а поиск в бору занимает время, пропорциональное длине образца.

Текущая версия на 19:17, 4 сентября 2022

Бор (англ. trie, луч, нагруженное дерево) — структура данных для хранения набора строк, представляющая из себя подвешенное дерево с символами на рёбрах. Строки получаются последовательной записью всех символов, хранящихся на рёбрах между корнем бора и терминальной вершиной. Размер бора линейно зависит от суммы длин всех строк, а поиск в бору занимает время, пропорциональное длине образца.

Пример

Бор для набора образцов [math] \{ \textbf{he}, \textbf{she}, \textbf{his}, \textbf{hers}\} [/math]:
Бор.jpg

Построение

Обозначения

Введем следующие обозначения:

  • [math]\Sigma[/math] — используемый алфавит;
  • [math]P = \{P_1,\ldots,P_k\} [/math] — набор строк над [math]\Sigma[/math], называемый словарём;
  • [math]n = \sum_{i=1}^{k}\limits |P_i|[/math] — сумма длин строк.

Бор храним как набор вершин, у каждой из которых есть метка, обозначающая, является ли вершина терминальной и указатели (рёбра) на другие вершины или на NULL.

struct vertex:
    vertex next[[math]| \Sigma |[/math]] 
    bool isTerminal

Алгоритм

Непосредственно построение:

  • Начало.
  • Шаг 1. Создадим дерево из одной вершины (в нашем случае корня).
  • Шаг 2. Добавление элементов в дерево.
    • Добавляем шаблоны [math]P_i[/math] один за другим. Следуем из корня по рёбрам, отмеченным буквами из [math]P_i[/math], пока возможно.
    • Если [math]P_i[/math] заканчивается в [math]v[/math], сохраняем идентификатор [math]P_i[/math] (например, [math]i[/math]) в [math]v[/math] и отмечаем вершину [math]v[/math] как терминальную.
    • Если ребра, отмеченного очередной буквой [math]P_i[/math] нет, то создаем новое ребро и вершину для символа строки [math]P_i[/math].
  • Конец.

Построение занимает, очевидно, [math]O(|P_1| + \ldots + |P_k|) = O(n)[/math] времени, так как поиск буквы, по которой нужно переходить, происходит за [math]O(1)[/math].

Поскольку на каждую вершину приходится [math]O(| \Sigma |)[/math] памяти, то использование памяти есть [math]O(n| \Sigma |)[/math].

Суффиксный бор

Основная статья: Суффиксный бор

Бор позволяет решать задачу поиска подстроки в строке, если построить его на множестве суффиксов исходной строки.

Цифровой бор

Использование бора

Поиск строки в бору

Задача:
Требуется найти слово [math]S[/math] в словаре.

При решении этой задачи, обход бора совершается из его корня по рёбрам, отмеченным символами строки [math]S[/math], пока возможно. Если с последним символом [math]S[/math] мы приходим в терминальную вершину, то [math]S[/math] — слово из словаря. Если в какой-то момент ребра, отмеченного нужным символом, не находится, то строки [math]S[/math] в словаре нет. Ясно, что это занимает [math]O (|S|)[/math] времени. Таким образом, бор — это эффективный способ хранить словарь и искать в нем слова.

Использование бора в качестве ассоциативного массива

Благодаря тому, что бор позволяет решать задачу, описанную выше, он может выступать в качестве ассоциативного массива. Обычно, когда требуется такая структура, то используют двоичное дерево поиска или хеш-таблицу.

Достоинства

Бор объединяет некоторые преимущества этих структур данных и позволяет одновременно делать следующие операции, которые каждая из структур не может делать по отдельности.

Бор Дерево Хеш-таблица
Добавление элемента [math]O(|S|)[/math] [math]O(|S|\log k)[/math] [math]O(|S|)[/math]
Получение всех ключей в отсортированном порядке [math]O(k)[/math] [math]O(k)[/math] [math]O(k\log k)[/math]

Недостатки

Несмотря на данные достоинства у реализации ассоциативного массива в виде бора есть следующие недостатки:

  1. Бор хранит строки или символы, а это значит, что у значения ключа будет ограничение на тип (строки, символы, либо числа, представленные как строки). Чтобы это исправить, научимся приводить любой тип данных к строке. Тогда сможем хранить любой вид данных в качестве ключа.
  2. Если реализовывать ассоциативный массив на обычном боре, а ключами будут являться строки, то будет использоваться слишком много памяти (возможен, например, вариант, когда у слов нет пересечений по префиксу, тогда бор будет использовать [math]O(n| \Sigma |)[/math] памяти).

См. также

Источники информации

  • Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — ISBN 5-8489-0857-4
  • Бор. Построение бора