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