java - 在 Java 中压缩后缀数组

Question

我使用普林斯顿实现创建了一个后缀数组。但是，我的基本文本文档非常非常大，生成的后缀数组大小超过 500mb。有没有办法压缩后缀数组？

谢谢！

Answer 1

与上一个答案中所说的相反，您不仅可以压缩后缀数组，而且实际上压缩后缀树通常是通过首先使用后缀数组模拟树，然后对其进行压缩来实现的。

我不知道有任何现成的 Java 实现后缀数组压缩，并且现有的各种算法涉及太多，无法在此详细描述。Navarro 和 Mäkinen有一篇论文(DOI 10.1145/1216370.1216372) 提供了详细的描述和比较。

但从广义上讲，有两种通用方法：

方法 A：直接减小数组的大小 （参见论文的第 7.1 节）。这涉及仅存储后缀数组的一些条目，并在需要时插入丢失的条目。插值是使用一个函数（在论文中称为ψ）进行的，该函数本身以大数组（但没有原始后缀数组大）和索引位向量的形式存储。

方法 B：FM 方法（见论文第 9 节）。在这里，后缀数组基本上被替换为一个相对较短的数组C，它表示主要字典桶（即以相同初始字符开头的后缀组）的起始位置（在后缀数组中），结合另一个比较大的数据结构Occ这使得所谓的向后搜索成为可能。具体来说，给定一个搜索模式 p=c ₁ ..c _m，它可以迭代地将字符 c _m的存储桶缩小到字符串 c m-1 cm 的较小存储桶，_{然后进一步}缩小到 c m 的存储_桶-2 ℃_m-1 c _m以此类推，直到找到完整模式 p 的最终范围。实现这一点的数据结构Occ很大，但可以使用各种技术进行压缩，最显着的是小波树。

对搜索性能
的影响 上面引用的论文包含仔细的分析和比较。但从广义上讲，压缩后缀数组将导致搜索长度为 m 的模式（如果仔细实施，在未压缩的后缀数组中可能是 O(m)）被一个取决于（通常是对数）的因素延迟整个文本的长度。此外，任何使用小波树的方法都意味着对字母表大小的额外依赖。

Answer 2

据我所知，你不能压缩后缀数组（也许你可以我只是不知道），但你可以压缩后缀树。因此，您可能会考虑更改数据结构。只是谷歌压缩后缀树。

它们大量用于基因测序和常见的子串问题，因为它们可以存储大量数据。

可以在此处找到解释：http: //bioinformatics.oxfordjournals.org/content/23/5/629.abstract
如果您点击底部的链接，它将带您到此页面，您可以在其中下载压缩后缀的代码树：http ://www.cs.helsinki.fi/group/suds/cst/