.
Вернулся я к этому проекту после двухлетнего перерыва. Что получилось в результате можно посмотреть на SVN проекта.
Описание сделанных изменений и новых возможностей предоставлю позже. И, конечно, это далеко не окончательный вариант
RK>Привет всем!
RK>Описание сделанных изменений и новых возможностей предоставлю позже.
В библиотеке шаблонов PATL реализованы следующие контейнеры:
Ассоциативные /patl::impl::assoc_generic/. Это базовый класс для контейнерных классов, основанных на алгоритме PATRICIA. В нем реализованы возможности: получения границ различных итераторов ((preorder_|postorder_|r)(begin|end)), итераторов частичного совпадения (partimator); стандартные функции для ассоциативных контейнеров (find, (lower_|upper_)bound, equal_range, count, empty); некоторые специфические для моих контейнеров функции (change_root, root, bit_comp).
От assoc_generic наследуются:
Деревья цифрового поиска /patl::impl::trie_generic/. Является базовым классом для контейнеров, предназначенных для хранения данных с ключами, имеющими не-скалярную природу (строки, массивы, данные произвольно сложной структуры). Возможности этого класса: конструкторы, стандартные для ассоциативных контейнеров, функции (swap, clear, size, max_size, get_allocator, insert). Функция erase расширена возможностью за один вызов удалить целое поддерево узлов, ключи которых имеют определенный префикс заданной длины. Также доступна функция merge, позволяющая максимально эффективно объединить два контейнера.
Онлайновые суффиксные деревья с линейным временем построения, не зависящим от алфавита, с затратами RAM по 16 байт на символ /patl::impl::suffix_generic/. Это базовый класс для индексирования последовательности символов (размеры последовательности ограничиваются только доступной RAM, необходимой для суффиксного дерева, размер каждого символа в принципе не ограничен). В рамках класса реализованы следующие функции: стандартные (size, capacity, pop_front, pop_back, clear, reserve) и специфические (keys, rebind, index_of, prefix_by, endpoint, integrity). Также содержит итератор совпадения (match_iterator), обеспечивающий функцию поиска совпадений с другой последовательностью.
От trie_generic и suffix_generic наследуются соответственно patl::trie_(set|map) и patl::suffix_(set|map), представляющие собой упорядоченное множество ключей (set) и упорядоченное множество ключей с ассоциированными с ними произвольными данными (map).
Онлайновость суффиксного дерева обеспечивают функции (push_back, pop_back, pop_front, count_reindex, pop_reindex, push_reindex). Пример использования см. demos/lz77.
В качестве итераторов по дереву любого из вышеописанных контейнеров используется класс patl::some_cont::vertex. Хотя это и не итератор в смысле STL, но с его помощью можно обойти дерево в прямом (функции preorder_*) и в обратном (функции postorder_*) порядке. Класс patl::impl::vertex_generic, от которого специализируются внутренние vertex контейнеров, позволяет пользователю получить исчерпывающую информацию об указываемом узле, но не позволяет модифицировать структуру дерева. Через vertex описываются итераторы контейнеров, а также партиматоры (еще не реализованы, временно работают через внутренний класс algorithm).
Также в ассоциативных контейнерах имеется класс patl::some_cont::prefix, представляющий собой урезанную версию vertex. Класс prefix служит целям итерации по дереву, когда пользователя не интересуют отдельные узлы, но префиксы, хранящиеся в дереве. Узел дополнительно к префиксу содержит бит различия (0 или 1). Получается, что на два узла приходится один префикс. Через prefix реализованы два полезных класса: patl::maxrep_iterator и patl::super_maxrep_iterator, представляющие итераторы по максимальным и супермаксимальным повторам соответственно.
И, наконец, жемчужина коллекции: класс patl::lca_oracle. В этом классе реализован константный алгоритм Lowest Common Ancestor с линейным временем препроцессинга и линейной же дополнительной памятью. Обычно используется совместно с классом patl::leaf_oracle, после линейного препроцессинга возвращающий vertex, указывающий на лист, соответствующий данному префиксу в суффиксном дереве.
Про алгоритмы (Super)Maximal Repeats и Lowest Common Ancestor см. книгу Д. Гасфилда "Строки, деревья и подпоследовательности в алгоритмах", а также примеры использования demos/ insider, maxpals, word_suffix.
Здравствуйте, Ka3a4oK, Вы писали:
KK>Применение было? Или это (пока) "академический" проект?
Применение дальше demos не заходило ) Но проект имеет практическое значение, как следует из названия. Плюс к тому, он вполне способен развиваться и обрастать дополнительными возможностями.
Если есть какие-то замечания или предложения, прошу писать их здесь или на gmail.com->uxnuxn
You aren't expected to absorb this
Re: [C++] Practical Algorithm Template Library. Жизнь вторая
Здравствуйте, CreatorCray, Вы писали:
CC>Здравствуйте, nen777w, Вы писали:
N>>Рекомендуете ли вы использовать uxn::patl::trie_map<> вместо std::map<> ? CC>Вместо std::map<std:(w)string, T> — да.
Да, изначально он для этого и создавался. Но следует помнить некоторые отличия от std::map/set:
1. Функтор сравнения изменяется с std::less/greater на patl::bit_comparator/reverse_bit_comparator.
2. Надо следить за тем, чтобы bit_comparator не вышел за границы сравниваемых последовательностей. Для std::basic_string<T> это выполняется в специализации patl::bit_comparator, см. bit_comp.hpp. В случае с patl::suffix_set/map требуемое поведение достигается введением стоп-символов в конец индексируемой строки, см. stopBytes в demos/lz77. В простых случаях можно использовать '\0'.
3. После каждой операции вставки/удаления стандартные итераторы становятся недействительными, в случае с vertex/prefix надо смотреть по ситуации.
