Расскажите, пожалуйста, суть сжатого бора и аспекты реализации.
Расскажите, пожалуйста, суть сжатого бора и аспекты реализации.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | pajenegod | 145 |
http://informatics.mccme.ru/moodle/mod/book/view.php?id=435&chapterid=121
суть в песок. А сжатый бор это экономное по памяти представление обычного бора.
обычный бор для строк {"abcd", "abef"} содержит (вместе с корнем) 7 вершин, и выглядит как-то так:
0-a>1-b>2-c>3-d>4
.............\-e>5-f>6
на каждом ребре мы пишем одну букву
сжатый бор будет выглядеть как-то вот так:
0-ab>1-cd>2
..........\-ef>3
т.е. на каждом ребре мы можем писать несколько букв (вершина есть только если в этом месте бора есть развилка)
Можно про реализацию по-подробнее. С обычным бором знаком.
Ну идешь по бору пока твой префикс совпадает с тем что написано на рёбрах, каждый момент времени у нас есть уже некоторый совавший префикс, текущая вершина соответствующая этому префиксу, и оставшаяся часть нашей добавляемой строки. Каждый раз мы берём то ребро, с которым максимально совпадает префикс оставшейся части, и здесь может быть несколько вариантов.
1) ребро, по которому нам надо идти, меньше либо равно по длине оставшейся части строки и полностью с нами совпадает по всей длине. ну перейдём по этому ребру, отрезав от начала оставшейся части, столько символов сколько в этом ребре
2) оставшаяся часть строки пуста. Ну молодец, нашёл вершину, которая соответсвует этому префиксу, радуйся
3) рёбро совпало с нами не полностью. этот пункт на пальцах, из примера бора чуть выше: есть ребро 0-abcd>1, оставшаяс часть строки что мы добавляем abcef совпало 2 символа, надо это ребро разрезать на два, создать ещё одну вершину и переставить рёбра. после всех манипуляций получаем ту же картинку что и в примере.
Ошибка на ошибке, засыпаю после обеда, ночь не спал :)
Получается же что у нас из каждой вершины может быть больше(намного) 26 ребер?
хз, сплю
гоню.
Не может. Если есть переход, допустим, по ребру "ad", а мы хотим добавить ребро "abc", мы просто расщепим уже существующее ребро, оно теперь станет ребром "a", и у других вершин добавятся переходы "bc" или "d".
Не "вроде бы", а не может. В остальном Вы правы.
Да, точно не может, что-то я не проснулся еще.
В качестве хорошего примера, демонстрирующего суть сжатого бора могу привести суффиксное дерево. В нем мы храним все суффиксы строки, суммарная их длина — O(|s|^2), однако за счет хранения ребер в виде ссылок на отрезки исходной строки нам требуется только O(|s|) памяти.
Вот быдлокодерская реализация в моем исполнении. За качество кода заранее извиняюсь — я не сишник.
UPD. Хотя, конечно, в качестве терминатора строки в боре лучше использовать не доллар, а '\0'.
Это случайно не задача 1414 с Тимуса? С ней и связан мой вопрос:)
Это просто наспех написанная реализация сжатого бора с основными функциями и демонстрацией их использования :).
set за 0.1 заходит там и пишется в 15 строк
Давно спросить хотел, а можно ли как-то на сжатом боре Корасика написать, и нет ли у кого-нибудь примера кода?
Насколько я осведомлен, нельзя, т.к. вычисление переходов, особенно когда мы стоим на середине ребра и/или переходим на середину ребра, в случае сжатого бора — задача явно нетривиальная. Наглядный пример: строки "a(10^5 букв b)c(10^5 букв b)" и "(2 * 10^5 букв b)".
Казалось бы нам нужны суффиксные ссылки и от середин ребер. Если их все посчитать — то их квадрат. А меняться, пока мы идем по ребру, они могут черти как. И как это пересчитывать абсолютно непонятно. Если конечно у нас не суффиксное дерево. Но насколько я понимаю и здесь подсчет этих ссылок и построение за линию — задачи примерно одной сложности.
UPD. Под квадратом имею ввиду суммарную длину. Я привык думать о сжатом боре, только как о суффиксном.
Смотря что имеется ввиду. Если хотите затратить только O(m) памяти, где m — количество слов в боре, то определенно нет. Если бы это было возможно, то мы могли бы реализовать КМП, который тратит O(1) памяти на препроцессинг.
Если просто хочется вместо обычного бора сделать сжатый, то алгоритму Ахо-Корасик не сильно неважно, какими структурами у вас представлен автомат. Но суффиксные ссылки все равно придется хранить полностью.
P.S. Не понимаю, о каком квадрате говорит PavelKunyavskiy.