12
правок
Изменения
Бор
,Новая страница: «'''Бор''' (trie, луч, нагруженное дерево) — структура данных для хранения набора строк, предста…»
'''Бор''' (trie, луч, нагруженное дерево) — структура данных для хранения набора строк, представляющая из себя подвешенное дерево с символами на ребрах. Строки получаются прохождением из корня по рёбрам, записывая соответствующие им символы, до терминальной вершины. Размер бора линейно
зависит от суммы длин всех строк, а поиск в бору занимает время, пропорциональное длине образца.
==Пример бора==
Бор для набора образцов {he, she, his, hers}:<br />
[[Файл:Aho-corasick1.jpg]]
==Построение бора==
Пусть <tex>P = \{P_1,...,P_k\} </tex> — набор строк, называемый словарем.
Пусть <tex>n = \sum_{i=1}^k|P_i|</tex>.
Начинаем с дерева из одной вершины (корня); добавляем шаблоны <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>P_i</tex> нет, то создаем новые ребра и вершины для всех оставшихся символов <tex>P_i</tex>.
Это занимает, очевидно, <tex>O (|P_1| + ... + |P_k|) = O (n)</tex> времени.
==Поиск строки в бору==
Поиск строки <tex>S</tex> в бору: начинаем в корне, идем по ребрам, отмеченным символами <tex>S</tex>, пока возможно.
Если с последним символом <tex>S</tex> мы приходим в вершину с сохраненным идентификатором, то <tex>S</tex> — слово из словаря.
Если в какой-то момент ребра, отмеченного нужным символом, не находится, то строки S в словаре нет.
Ясно, что это занимает <tex>O (|S|)</tex> времени. Таким образом, бор - это эффективный способ хранить словарь и искать в нем слова.
зависит от суммы длин всех строк, а поиск в бору занимает время, пропорциональное длине образца.
==Пример бора==
Бор для набора образцов {he, she, his, hers}:<br />
[[Файл:Aho-corasick1.jpg]]
==Построение бора==
Пусть <tex>P = \{P_1,...,P_k\} </tex> — набор строк, называемый словарем.
Пусть <tex>n = \sum_{i=1}^k|P_i|</tex>.
Начинаем с дерева из одной вершины (корня); добавляем шаблоны <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>P_i</tex> нет, то создаем новые ребра и вершины для всех оставшихся символов <tex>P_i</tex>.
Это занимает, очевидно, <tex>O (|P_1| + ... + |P_k|) = O (n)</tex> времени.
==Поиск строки в бору==
Поиск строки <tex>S</tex> в бору: начинаем в корне, идем по ребрам, отмеченным символами <tex>S</tex>, пока возможно.
Если с последним символом <tex>S</tex> мы приходим в вершину с сохраненным идентификатором, то <tex>S</tex> — слово из словаря.
Если в какой-то момент ребра, отмеченного нужным символом, не находится, то строки S в словаре нет.
Ясно, что это занимает <tex>O (|S|)</tex> времени. Таким образом, бор - это эффективный способ хранить словарь и искать в нем слова.
