Ахо-Корасик: различия между версиями
Материал из Algocode wiki
Scheduler (обсуждение | вклад) (Новая страница: «== Бор == Бор — это структура данных для компактного хранения строк. Он устроен в виде дер...») |
Scheduler (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
Он устроен в виде дерева, где на ребрах между вершинами написана символы, а некоторые вершины помечены терминальными. Бор хранит ровно те строки, которые получаются, если выписать подряд все буквы на путях от корня до терминальных вершин. | Он устроен в виде дерева, где на ребрах между вершинами написана символы, а некоторые вершины помечены терминальными. Бор хранит ровно те строки, которые получаются, если выписать подряд все буквы на путях от корня до терминальных вершин. | ||
| + | [[File:https://koenig-media.raywenderlich.com/uploads/2016/10/SwiftAlgClub_TrieData-trie-1.png]] | ||
| + | |||
| + | Бор можно удобно использовать для разных задач: | ||
| + | * Хранение строк — занимает гораздо меньше места, чем массив или сет строк. | ||
| + | * Сортировка строк — по бору можно пройтись dfs-ом и вывести все строки в лексикографическом порядке. | ||
| + | * Сет строк — как мы увидим, в нем легко добавлять и удалять слова, а также проверять, если ли слово в боре. | ||
| + | |||
| + | == Реализация == | ||
| + | Бор состоит из ссылающихся друг на друга вершин. В вершине обычно хранится такая информация: | ||
| + | * терминальная ли вершина, | ||
| + | * ссылки на детей, | ||
| + | * возможно, какая-нибудь дополнительная зависящая от задачи информация о слове, если вершина терминальная. Например, количество таких слов — так можно реализовать мультисет. | ||
== Суффиксные ссылки == | == Суффиксные ссылки == | ||
== Алгоритм Ахо-Корасик == | == Алгоритм Ахо-Корасик == | ||
Версия 19:04, 21 ноября 2019
Бор
Бор — это структура данных для компактного хранения строк.
Он устроен в виде дерева, где на ребрах между вершинами написана символы, а некоторые вершины помечены терминальными. Бор хранит ровно те строки, которые получаются, если выписать подряд все буквы на путях от корня до терминальных вершин. Файл:Https://koenig-media.raywenderlich.com/uploads/2016/10/SwiftAlgClub TrieData-trie-1.png
Бор можно удобно использовать для разных задач:
- Хранение строк — занимает гораздо меньше места, чем массив или сет строк.
- Сортировка строк — по бору можно пройтись dfs-ом и вывести все строки в лексикографическом порядке.
- Сет строк — как мы увидим, в нем легко добавлять и удалять слова, а также проверять, если ли слово в боре.
Реализация
Бор состоит из ссылающихся друг на друга вершин. В вершине обычно хранится такая информация:
- терминальная ли вершина,
- ссылки на детей,
- возможно, какая-нибудь дополнительная зависящая от задачи информация о слове, если вершина терминальная. Например, количество таких слов — так можно реализовать мультисет.