45

哪种结构提供了最好的性能结果；trie（前缀树）、后缀树还是后缀数组？还有其他类似的结构吗？这些结构的良好 Java 实现是什么？

编辑：在这种情况下，我想在大型名称字典和大量自然语言文本之间进行字符串匹配，以便识别文本上字典的名称。

4

7 回答 7

65

trie 是第一个发现的此类数据结构。

后缀树是对 trie 的改进（它具有允许线性错误搜索的后缀链接，后缀树修剪了 trie 的不必要分支，因此它不需要太多空间）。

后缀数组是基于后缀树的精简数据结构（没有后缀链接（慢错误匹配），但模式匹配非常快）。

trie 不适用于现实世界，因为它占用了太多空间。

后缀树比 trie 更轻更快，用于索引 DNA 或优化一些大型网络搜索引擎。

在某些模式搜索中，后缀数组比后缀树慢，但使用的空间更少，并且比后缀树使用更广泛。

在同一系列数据结构中：

还有其他实现，CST 是使用后缀数组和一些附加数据结构来获得后缀树搜索功能的后缀树的实现。

FCST 更进一步，它实现了一个带有后缀数组的采样后缀树。

DFCST 是 FCST 的动态版本。

扩展：

两个重要因素是空间使用和操作执行时间。您可能认为这与现代机器无关，但索引一个人的 DNA 需要 40 GB 的内存（使用未压缩和未优化的后缀树）。在这么多数据上构建其中一个索引可能需要数天时间。想象一下谷歌，它有很多可搜索的数据，他们需要一个包含所有网络数据的大型索引，而且他们不会在每次有人构建网页时都更改它。他们为此提供了某种形式的缓存。然而，主要指数可能是静态的。每隔几周左右，他们就会收集所有新的网站和数据，并建立一个新的索引，在新的完成后替换旧的。我不知道他们使用哪种算法来索引，但它可能是一个在分区数据库上具有后缀树属性的后缀数组。

CST 使用 8 GB，但后缀树操作速度大大降低。

后缀阵列可以在大约 700 兆到 2 兆的情况下执行相同的操作。但是，您不会在带有后缀数组的 DNA 中发现遗传错误（意思是：使用通配符搜索模式要慢得多）。

FCST（完全压缩后缀树）可以创建 800 到 1.5 千兆的后缀树。朝向 CST 的速度下降幅度很小。

DFCST 使用的空间比 FCST 多 20%，并且速度比 FCST 的静态实现慢（但是动态索引非常重要）。

后缀树的可行（空间方面）实现并不多，因为很难使操作速度提升补偿数据结构 RAM 空间成本。

这就是说，后缀树对于带有错误的模式匹配具有非常有趣的搜索结果。aho corasick 没有那么快（尽管对于某些操作来说几乎一样快，而不是错误匹配），而 boyer moore 则被抛在了后面。

于 2011-07-17T10:43:09.193 回答
4

你打算做什么操作？ libdivsufsort曾经是 C 语言中最好的后缀数组实现。

于 2011-03-31T01:01:57.083 回答
2

使用后缀树，您可以在 O(n+m+k) 时间内编写将字典与文本匹配的内容，其中 n 是字典中的字母，m 是文本中的字母，k 是匹配的数量。为此，尝试要慢得多。我不确定什么是后缀数组，所以我不能对此发表评论。

也就是说，编写代码并非易事，而且我碰巧不知道任何提供必要功能的 Java 库。

于 2010-03-21T16:12:22.227 回答
1

编辑：在这种情况下，我想在大型名称字典和大量自然语言文本之间进行字符串匹配，以便识别文本中字典的名称。

这听起来像是Aho-Corasick 算法的一个应用：从字典中构造一个自动机（在线性时间中），然后可以使用它来查找多个文本中任何字典单词的所有出现（也在线性时间中）。

（这些讲义中的描述，链接自维基百科页面的“外部链接”部分，比页面本身的描述更容易阅读。）

于 2010-03-21T17:51:21.260 回答
1

我更喜欢后缀自动机。您可以通过我的网站找到更多详细信息： http ://www.fogsail.net/2019/03/06/20190306/

在此处输入图像描述

首先，如果你使用正常的构造，它将花费 O(n^2) 来遍历所有的后缀

我们使用 radix-sort 按第一个字符对后缀 Array 进行排序。

但是，如果我们对第一个字符进行排序，我们就可以使用这些信息。

细节由图片显示（忽略中文）

我们按照 first-key 对数组进行排序，结果用红色矩形表示

,,....−−>,,....

在此处输入图像描述

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>

using namespace std;
const int maxn = 1001 * 100 + 10;

struct suffixArray {
    int str[maxn], sa[maxn], rank[maxn], lcp[maxn];
    int c[maxn], t1[maxn], t2[maxn];
    int n;

    void init() { n = 0; memset(sa, 0, sizeof(sa)); }

    void buildSa(int Rdx) {
        int i, *x = t1, *y = t2;
        for(i = 0; i < Rdx; i++) c[i] = 0;
        for(i = 0; i < n; i++) c[x[i] = str[i]]++;
        for(i = 1; i < Rdx; i++) c[i] += c[i-1];
        for(i = n-1; i >= 0; i--) sa[--c[x[i]]] = i;

        for(int offset = 1; offset <= n; offset <<= 1) {
            int p = 0;
            for(i = n-offset; i < n; i++) y[p++] = i;
            for(i = 0; i < n; i++) if(sa[i] >= offset) y[p++] = sa[i] - offset;

            // radix sort
            for(i = 0; i < Rdx; i++) c[i] = 0;
            for(i = 0; i < n; i++) c[x[y[i]]]++;
            for(i = 1; i < Rdx; i++) c[i] += c[i-1];
            for(i = n-1; i >= 0; i--) { sa[--c[x[y[i]]]] = y[i]; y[i] = 0; }

            // rebuild x and y
            swap(x, y); x[sa[0]] = 0; p = 1;
            for(i = 1; i < n; i++)
                x[sa[i]] = y[sa[i-1]] == y[sa[i]] && y[sa[i-1]+offset] == y[sa[i]+offset] ? p-1 : p++;
            if(p >= n) break;
            Rdx = p;
        }
    }
于 2019-05-19T09:20:08.687 回答
0

特里树 vs 后缀树

两种数据结构都确保非常快速的查找，搜索时间与查询词的长度成正比，复杂度时间 O(m) 其中 m 是查询词的长度。

这意味着如果我们的查询词有 10 个字符，所以我们最多需要 10 个步骤才能找到它。

Trie：一棵用于存储字符串的树，其中每个公共前缀都有一个节点。字符串存储在额外的叶节点中。

后缀树：与给定字符串的后缀相对应的 trie 的紧凑表示，其中具有一个子节点的所有节点都与其父节点合并。

def 来自：算法和数据结构字典

通常 Trie 用于索引字典单词（lexicon）或任何字符串集 例如 D={abcd, abcdd, bxcdf,.....,zzzz }

用于索引文本的后缀树，在文本的所有后缀上使用相同的数据结构“Trie” T=abcdabcg T = {abcdabcg , abcdabc , abcdab, abcda, abcd, abc , ab, a}

现在它看起来像一组字符串。我们在这组字符串（所有 T 的后缀）上构建一个 Trie。

两种数据结构的构造都是线性的，在时间和空间上都需要 O(n)。

在字典（一组字符串）的情况下：n =所有单词的字符之和。在文本中：n = 文本长度。

后缀数组：是一种表示压缩空间中后缀树的技术，它是一个字符串后缀的所有起始位置的数组。

它在搜索时间上比后缀树慢。

有关更多信息，请访问 wikipedia，有一篇关于此主题的好文章。

于 2014-03-17T13:55:37.017 回答
0

这种诱导排序算法（称为 sais）的实现有一个用于构造后缀数组的 Java 版本。

于 2011-07-15T20:56:45.473 回答