Библиотека суффиксного дерева для c ++ с простыми примерами, как ее использовать

Question

Я ищу библиотеку дерева суффиксов (которая имеет линейное построение по времени), и все, что я нашел, это PATL, но у PATL нет документации, и я не могу разобраться ни в одном из примеров. Так есть ли библиотека дерева суффиксов для c ++ с достойной документацией?

PATL home: http://code.google.com/p/patl/

EDIT:
Мотивация: мне нужно обработать большое количество строк и найти часто встречающиеся подстроки, и сообщить, если в течение t секунд произошло более n вхождений какой-либо подстроки. Я реализовал дерево (со счетчиком в узлах, на самом деле это не счетчик, а std :: vector времени посещения, поскольку, как я уже сказал, мне нужно время), но оно очень медленное. Поэтому я подумал о том, чтобы набрать (конкатенировать с некоторыми случайными вещами между строками, чтобы подстроки не охватывали более одной строки) определенного количества сообщений (скажем, данных за 30 секунд), а затем построить дерево суффиксов для этой строки ,

Answer 1

Взгляните на библиотеку SeqAn , которая предлагает высокопроизводительные реализации различных алгоритмов поиска и структур данных с документацией.

Например, массив суффиксов может использоваться в качестве замены для суффиксных деревьев.

Кроме того, ваша проблема звучит по сути своей сложной, я не уверен, насколько вы можете ускорить ее. В общем, это проблема множественного выравнивания , которая трудна для NP. Вероятно, вы можете превратить это в нечто более удобное для восприятия, поскольку вас интересуют только точные совпадения, но оно все еще сложно.

Answer 2

Возможно, вы захотите взглянуть на реализации, сделанные для проекта Pizza & Chili . У них нет суффиксных деревьев, но есть суффиксные массивы и различные сжатые индексы. Простой (несжатый) суффиксный массив должен идеально подходить для ваших целей, даже если он не является деревом суффиксов.

(Код для скачивания можно найти по ссылке «Коллекция индексов».)

Answer 3

SDSL очень зрелый, с реализациями суффиксного дерева , суффиксного массива , вейвлет-дерева и многих других структур в C ++ .

"Библиотека кратких структур данных (SDSL) - это мощная и гибкая библиотека C ++ 11, реализующая краткие структуры данных. В общей сложности библиотека содержит основные моменты 40 научных публикаций. Краткие структуры данных могут представляет объект (такой как битовый вектор или дерево) в пространстве, близком к теоретико-информационной нижней границе объекта, при этом эффективно поддерживая операции исходного объекта. Теоретическая сложность по времени операции, выполняемой над классической структурой данных и эквивалентной ей сжатая структура данных (в большинстве случаев) идентична. "

Список структур, реализованных в SDSL, можно найти здесь .

Пример средней LCP - поиск самого длинного общего префикса с использованием дерева суффиксов (пример из источников SDSL, файл text-statistics.cpp):

#include <sdsl/suffix_trees.hpp>
#include <iostream>

using namespace std;
using namespace sdsl;

typedef cst_sct3<> cst_t;
typedef cst_t::char_type char_type;

int main(int argc, char* argv[])
{
    if (argc < 2) {
        cout << "Usage: "<< argv[0] << " file" << endl;
        cout << "(1) Generates the CST of file." << endl;
        cout << "(2) Calculates the avg LCP value and the runs in the BWT." << endl;
        return 1;
    }
    cst_t cst;
    construct(cst, argv[1], 1);

    long double runs = 1;
    long double avg_lcp = 0;
    if (cst.csa.size()) {
        char_type prev_bwt = cst.csa.bwt[0];
        for (uint64_t i=1; i<cst.csa.size(); ++i) {
            char_type bwt = cst.csa.bwt[i];
            if (prev_bwt != bwt) {
                runs += 1.0;
            }
            prev_bwt = bwt;
            avg_lcp += cst.lcp[i];
        }
        avg_lcp /= cst.csa.size();
        for (size_t k=0; k<=5; k++) {
            cout << "H_" << k << ": " << Hk(cst,k).first << endl;
        }
        cout << "avg LCP: " << avg_lcp << endl;
        cout << "runs in BWT: " << runs << endl;
    }
}