Префиксное дерево. Задача о покрытии строки.
Определение
Префиксное дерево (или бор) - это структура данных, используемая для хранения набора строк, которая позволяет эффективно выполнять операции поиска, вставки и удаления строк, а также выполнять операции нахождения всех строк, являющихся префиксами данной строки.
Префиксное дерево состоит из узлов, каждый из которых содержит ссылки на дочерние узлы, представляющие символы алфавита. Путь от корня до узла представляет собой строку, образованную символами, представленными на этом пути.
Префиксное дерево Дерево, которое мы строили в предыдущей задаче (кодирование по Хаффману), уже было префиксным, но оно позволяло кодировать только последовательностями из нулей и единиц, так как каждый узел имел не более двух потомков. Идея о том, что каждая ветка однозначно определяет код, позволяет иногда уменьшить количество данных, требуемых для представления. Не умаляя общности, положим, что из каждого узла всегда выходит ровно три ветви, A, B и C. Каждая из веток приходит либо в узел, либо в вершину, либо в никуда.
Алгоритм построения префиксного дерева оказывается достаточно простым.
- Создаём вершину дерева — узел с пустыми ветвями.
- Для каждого слова исполняем:
- Устанавливаем указатель в вершину дерева.
- Считываем очередную букву.
- Если текущий узел не содержит нужной ветви, создаём эту ветвь и пустой узел на ней.
- Переходим в нужную ветвь.
- Если узел уже серый или не пустой, завершаем алгоритм с неудачей.
- Если слово закончилось, то помечаем узел серым цветом.
- Считываем очередную букву....
- Завершаем алгоритм с успехом.
Задача
Задача о покрытии строки: имеется набор слов, и ни одно из них не начинается с другого, то есть они образуют префиксный код. Имеется строка p - предложение. Требуется определить можно ли составить предложение из набора слов. Цель - найти оптимальное решение.
Не оптимальный алгоритм Решение с использованием жадных алгоритмов:
- начинаем с первого символа строки
- ищем слова которые начинаются с этого символа
- если таких нет, то ответ “нет”, иначе сдвигаем указатель строки и дальше сравниваем символы с найденными подстроками
- последовательно доходим до конца подстроки, возвращаемся к п.2 сложность O(n*m), где n-длина предложения, m-сумма длин всех слов.
Оптимальный алгоритм заключается в построении префиксного дерева.
- Начинаем от корня, берём все уникальные символы с которых начинаются наши слова и соединяем с корнем(построили 1 уровень дерева).
- Последовательно проходимся по словам и дереву и добавляем необходимые вершины.
- Если доходим до конца слова, помечаем вершину серой.
Поиск по такому дереву стал элементарным:
- Считываем первый символ, идем в соответствующую вершину из корня, если такой нет, то возвращаем “нет”
- Повторяем п.1, пока не доходим до серой вершины (указатель на конец слова)
- Вновь поднимаемся в корень и повторяем п.1 и п.2
Общая сложность этого алгоритма O(n + m)