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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм)
м (rollbackEdits.php mass rollback)
 
(не показаны 92 промежуточные версии 4 участников)
Строка 1: Строка 1:
'''Бор''' (англ. ''trie'', ''луч'', ''нагруженное дерево'') структура данных для хранения набора строк, представляющая из себя [[Дерево, эквивалентные определения | подвешенное дерево]] с символами на [[Основные определения теории графов | рёбрах]]. Строки получаются прохождением из корня по [[Основные определения теории графов | рёбрам]], записывая соответствующие им символы, до терминальной вершины. Размер бора линейно
+
'''Бор''' (англ. ''trie'', ''луч'', ''нагруженное дерево'') {{---}} структура данных для хранения набора строк, представляющая из себя [[Дерево, эквивалентные определения | подвешенное дерево]] с символами на [[Основные определения теории графов | рёбрах]]. Строки получаются последовательной записью всех символов, хранящихся на [[Основные определения теории графов | рёбрах]] между корнем бора и терминальной вершиной. Размер бора линейно
 
зависит от суммы длин всех строк, а поиск в бору занимает время, пропорциональное длине образца.
 
зависит от суммы длин всех строк, а поиск в бору занимает время, пропорциональное длине образца.
  
Строка 9: Строка 9:
 
===Обозначения===
 
===Обозначения===
 
Введем следующие обозначения:
 
Введем следующие обозначения:
*<tex>P = \{P_1,\ldots,P_k\} </tex> набор строк, называемый словарем;
+
*<tex>\Sigma</tex> {{---}} используемый алфавит;
*<tex>n = \sum_{i=1}^{k|P_i|}\limits |P_i|</tex>.
+
*<tex>P = \{P_1,\ldots,P_k\} </tex> {{---}} набор строк над <tex>\Sigma</tex>, называемый словарём;
 +
*<tex>n = \sum_{i=1}^{k}\limits |P_i|</tex> {{---}} сумма длин строк.
 +
 
 +
Бор храним как набор вершин, у каждой из которых есть метка, обозначающая, является ли вершина терминальной и указатели (рёбра) на другие вершины или на ''NULL''.
 +
 
 +
'''struct''' vertex:
 +
    '''vertex''' next[<tex>| \Sigma |</tex>]
 +
    '''bool''' isTerminal
 +
 
 
===Алгоритм===
 
===Алгоритм===
 
Непосредственно построение:
 
Непосредственно построение:
*Начало
+
*Начало.
*'''Шаг 1.''' Начинаем с [[Дерево, эквивалентные определения | дерева]] из одной вершины (корня).
+
*'''Шаг 1.''' Создадим [[Дерево, эквивалентные определения | дерево]] из одной вершины (в нашем случае корня).
*'''Шаг 2.''' Добавляем шаблоны <tex>P_i</tex> один за другим. Следуем из корня по [[Основные определения теории графов | рёбрам]], отмеченным буквами из <tex>P_i</tex>, пока возможно.
+
*'''Шаг 2.''' Добавление элементов в дерево.
*'''Шаг 3.''' Определение дальнейших действий.
+
**Добавляем шаблоны <tex>P_i</tex> один за другим. Следуем из корня по [[Основные определения теории графов | рёбрам]], отмеченным буквами из <tex>P_i</tex>, пока возможно.
 
**Если <tex>P_i</tex> заканчивается в <tex>v</tex>, сохраняем идентификатор <tex>P_i</tex> (например, <tex>i</tex>) в <tex>v</tex> и отмечаем вершину <tex>v</tex> как терминальную.
 
**Если <tex>P_i</tex> заканчивается в <tex>v</tex>, сохраняем идентификатор <tex>P_i</tex> (например, <tex>i</tex>) в <tex>v</tex> и отмечаем вершину <tex>v</tex> как терминальную.
**Если [[Основные определения теории графов | ребра]], отмеченного очередной буквой <tex>P_i</tex> нет, то создаем новые ребра и вершины для всех оставшихся символов <tex>P_i</tex>.
+
**Если [[Основные определения теории графов | ребра]], отмеченного очередной буквой <tex>P_i</tex> нет, то создаем новое ребро и вершину для символа строки <tex>P_i</tex>.
*Конец
+
*Конец.
Это занимает, очевидно, <tex>O(|P_1| + \ldots + |P_k|) = O(n)</tex> времени, так как поиск буквы, по которой нужно переходить, происходит за <tex>O(1)</tex>(в вершине есть указатели на буквы).
+
Построение занимает, очевидно, <tex>O(|P_1| + \ldots + |P_k|) = O(n)</tex> времени, так как поиск буквы, по которой нужно переходить, происходит за <tex>O(1)</tex>.
  
Поскольку на каждую вершину приходится <tex>O(k)</tex> памяти, то использование памяти есть <tex>O(nk)</tex>.
+
Поскольку на каждую вершину приходится <tex>O(| \Sigma |)</tex> памяти, то использование памяти есть <tex>O(n| \Sigma |)</tex>.
  
===Другие модификации===
+
===Суффиксный бор===
Бор позволяет решать задачу поиска подстроки в строке, если построить его на множестве суффиксов исходной строки.<ref>Сжатое суффиксное дерево</ref>
+
{{main|Суффиксный бор}}
 +
Бор позволяет решать задачу [[Наивный алгоритм поиска подстроки в строке | поиска подстроки в строке]], если построить его на множестве суффиксов исходной строки.
  
Существует еще одна модификация бора, называющаяся сжатый бор, отличающаяся от бора следующим улучшением: если у некоторой вершины исходящая степень равна 1, то эту вершину, [[Основные определения теории графов | ребро]], входящее в нее, и [[Основные определения теории графов | ребро]], исходящее из нее, можно объединить в одно
+
===Цифровой бор===
[[Основные определения теории графов | ребро]] с более чем одним символом.
+
{{main|Сверхбыстрый цифровой бор}}
  
==Поиск строки в бору==
+
==Использование бора==
 +
===Поиск строки в бору===
 
{{Задача
 
{{Задача
 
|definition =  
 
|definition =  
Требуется найти слово в словаре.
+
Требуется найти слово <tex>S</tex> в словаре.
 
}}
 
}}
Начинаем в корне, идем по [[Основные определения теории графов | рёбрам]], отмеченным символами <tex>S</tex>, пока возможно.
+
При решении этой задачи, обход бора совершается из его корня по [[Основные определения теории графов | рёбрам]], отмеченным символами строки <tex>S</tex>, пока возможно.
Если с последним символом <tex>S</tex> мы приходим в вершину с сохраненным идентификатором, то <tex>S</tex> — слово из словаря.
+
Если с последним символом <tex>S</tex> мы приходим в терминальную вершину, то <tex>S</tex> — слово из словаря.
 
Если в какой-то момент [[Основные определения теории графов | ребра]], отмеченного нужным символом, не находится, то строки <tex>S</tex> в словаре нет.
 
Если в какой-то момент [[Основные определения теории графов | ребра]], отмеченного нужным символом, не находится, то строки <tex>S</tex> в словаре нет.
 
Ясно, что это занимает <tex>O (|S|)</tex> времени. Таким образом, бор — это эффективный способ хранить словарь и искать в нем слова.
 
Ясно, что это занимает <tex>O (|S|)</tex> времени. Таким образом, бор — это эффективный способ хранить словарь и искать в нем слова.
  
==Использование бора в качестве ассоциативного массива==
+
===Использование бора в качестве ассоциативного массива===
Существует множество реализаций ассоциативного массива, начиная от обычного массива (храним массив в отсортированном состоянии, при добавлении элемента, все элементы с большим значением сдвигаются) и заканчивая хеш-таблицами и деревьями поиска. Ещё одну реализацию можно сделать используя бор или сжатый бор.
+
Благодаря тому, что бор позволяет решать задачу, описанную выше, он может выступать в качестве ассоциативного массива. Обычно, когда требуется такая структура, то используют [[Дерево поиска, наивная реализация | двоичное дерево поиска]] или [[Хеш-таблица | хеш-таблицу]].
Начнём с очевидных минусов:
+
====Достоинства====
# Бор хранит строки или символы, а это значит, что у значения ключа будет ограничение на тип (строки, символы, либо числа, представленные как строки).
+
Бор объединяет некоторые преимущества этих структур данных и позволяет одновременно делать следующие операции, которые каждая из структур не может делать по отдельности.
# Если реализовывать ассоциативный массив на обычном боре, а ключами будут являться строки, то будет использоваться слишком много памяти, а так же будет большая константа
+
 
# Если у нас все строки будут являться префиксами друг друга, то поиск и добавление могут занимать <tex> O(n)</tex> действий в худшем случае (например хранятся слова <tex>"a", "aa", "aaa", "aaaa", ...</tex>), где <tex>n</tex> - количество слов
+
{| class="wikitable" style="width:10cm" border=1
Плюсы:
+
|+
# Достаточно простая реализация.
+
| || '''Бор''' || '''Дерево''' || '''Хеш-таблица'''
# Операции добавления имеют меньшую константу (из-за отсутствия всевозможных операций балансировки), чем у двоичных деревьев поиска, поэтому в среднем данная реализация может работать быстрее.
+
|-
# Сортировка элементов гарантируется уже самим построением бора.
+
|-align="center" bgcolor=#FFFFFF
 +
| ''Добавление элемента''
 +
| align="center" style="background: #ddffdd;" | <tex>O(|S|)</tex>
 +
| align="center" style="background: #ffdddd;" |<tex>O(|S|\log k)</tex>
 +
| align="center" style="background: #ddffdd;" | <tex>O(|S|)</tex>
 +
|-align="center" bgcolor=#FFFFFF
 +
| ''Получение всех ключей в отсортированном порядке''
 +
| align="center" style="background: #ddffdd;" | <tex>O(k)</tex>
 +
| align="center" style="background: #ddffdd;" | <tex>O(k)</tex>
 +
| align="center" style="background: #ffdddd;" | <tex>O(k\log k)</tex>
 +
|}
 +
 
 +
====Недостатки====
 +
Несмотря на данные достоинства у реализации ассоциативного массива в виде бора есть следующие недостатки:
 +
# Бор хранит строки или символы, а это значит, что у значения ключа будет ограничение на тип (строки, символы, либо числа, представленные как строки). Чтобы это исправить, научимся приводить любой тип данных к строке. Тогда сможем хранить любой вид данных в качестве ключа.
 +
#Если реализовывать ассоциативный массив на обычном боре, а ключами будут являться строки, то будет использоваться слишком много памяти (возможен, например, вариант, когда у слов нет пересечений по префиксу, тогда бор будет использовать <tex>O(n| \Sigma |)</tex> памяти).
  
 
==См. также==
 
==См. также==
Строка 56: Строка 81:
 
* [[Сжатое суффиксное дерево]]
 
* [[Сжатое суффиксное дерево]]
 
* [[Алгоритм Ахо-Корасик]]
 
* [[Алгоритм Ахо-Корасик]]
 
  
 
== Источники информации ==
 
== Источники информации ==
Строка 62: Строка 86:
 
*[http://e-maxx.ru/algo/aho_corasick Бор. Построение бора]
 
*[http://e-maxx.ru/algo/aho_corasick Бор. Построение бора]
  
==Ссылки==
+
 
<references/>
 
  
 
[[Категория: Алгоритмы и структуры данных]]  
 
[[Категория: Алгоритмы и структуры данных]]  

Текущая версия на 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
  • Бор. Построение бора