[算法理论] 颠覆性后缀集测试技术

在这篇论文中，我们介绍了一种新颖的后缀集（suffixient set）概念，这是一种基于前缀数组（PA）压缩技术。与以往压缩整个数组的方法不同，我们通过对PA进行子采样，仅存储少量条目（实际上是压缩后的条目数量），证明了在文本上提供随机访问的情况下，仍然可以通过二分搜索进行模式匹配。

我们专注于解决以下两个问题：

1. 给定文本位置的子集是否为后缀集？
2. 如何找到最小基数的后缀集？

为此，我们提供了线性时间算法来解决这些问题。以下是算法的核心思路：

// 伪代码示例
function isSuffixientSet(positions) {
    // 检查给定位置是否为后缀集
}

function findMinimumSuffixientSet(text) {
    // 找到最小基数的后缀集
}

这些算法的有效性在于它们能够在不需要完整数组的情况下，依然实现高效的模式匹配。

博主点评： 后缀集的这一新颖定义为文本处理提供了更高效的解决方案，尤其在大规模数据处理时，其线性时间算法的提出值得深入研究。