4

我正在搜索后缀树库（具有线性时间构造），我发现的只是 PATL，但 PATL 没有文档，我无法找出任何示例。那么是否有一个具有不错文档的 c++ 后缀树库？

PATL 主页： http ://code.google.com/p/patl/

编辑：
动机：我需要处理大量字符串并找到频繁的公共子字符串，并报告是否在 t 秒内发生了 n 次以上的任何子字符串。我实现了一个树（在节点中有计数器，实际上它不是一个计数器，而是一个访问时间的 std::vector，因为就像我说我需要时间一样），但它非常慢。所以我想到了增加（在字符串之间连接一些随机的东西，这样子字符串不会跨越一个以上的字符串）一定数量的消息（比如说 30 秒的数据），然后在那个字符串上构建一个后缀树.

4

3 回答 3

4

看看SeqAn库，它提供各种搜索算法和数据结构的高性能实现以及文档。

例如，后缀数组类可以用作后缀树的替代品。

除此之外，您的问题听起来本质上很复杂，我不确定您可以加快多少速度。概括地说，这是一个多重对齐问题，NP 很难。您可能可以将其转换为更易于处理的内容，因为您只对精确的子匹配感兴趣，但它仍然很复杂。

于 2012-03-13T13:53:28.950 回答
1

您可能想查看为Pizza&Chili 项目所做的实现。它们没有后缀树，而是后缀数组和各种压缩索引。普通（非压缩）后缀数组应该非常适合您的目的，即使它不是后缀树。

（您将在“索引集合”链接下找到可下载的代码。）

于 2012-03-13T13:52:30.790 回答
0

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;
    }
}
于 2018-03-23T15:55:19.350 回答