寻找长Token序列中所有重复子序列的高效CPU算法

问题描述 #

给定一个包含10^6个Token的超长序列（Token为空格分隔的单词，可拆分为列表），需找出所有重复的Token子序列及其在原序列中的起始位置。示例如下：

this[0] string[1] is[2] test[3] to[4] check[5] duplication[6]
test[7] to[8] check[9] duplication[10] this[11] string[12]

==> at 0,11 - 2 tokens duplication
==> at 3,7 - 4 tokens duplication

此前尝试的方案均存在性能瓶颈：

• 基于字典记录Token索引列表匹配：即便用Numpy优化，速度仍无法满足需求
• 后缀树：现有工具多针对字符场景，适配Token后仅能处理小序列，百万级Token会导致树结构过度膨胀，无法高效运行

需求明确：优先追求CPU性能，RAM资源优先级较低。

最优CPU性能方案：Token级后缀数组+LCP数组 #

核心逻辑 #

后缀数组（Suffix Array）是处理重复子串问题的经典高效结构，适配Token序列后，结合最长公共前缀（LCP）数组，可实现接近O(n log n)的时间复杂度，完美适配百万级规模的Token序列。

执行步骤 #

1. Token整数映射：将所有唯一Token映射为整数ID（比如用字典给每个Token分配唯一整数），把原Token序列转化为整数数组——整数运算比字符串操作快得多，能大幅降低CPU消耗。
2. 构建后缀数组：使用SA-IS算法（线性时间复杂度）对整数数组构建后缀数组。后缀数组是原序列所有后缀的起始索引按字典序排序后的数组，SA-IS是目前最快的后缀数组构建算法之一，CPU效率极高。
3. 构建LCP数组：用Kasai算法在O(n)时间内生成LCP数组，该数组存储后缀数组中相邻两个后缀的最长公共前缀长度（以Token为单位）。只要LCP数组中存在连续数值≥k，对应的后缀起始位置就是长度≥k的重复子序列的起始点。
4. 提取重复信息：遍历LCP数组，定位所有连续高值区间，区间内的后缀起始位置对应的子序列，其公共前缀部分即为重复子序列，记录这些起始位置和子序列长度即可。

性能优势 #

• SA-IS算法线性构建后缀数组，处理百万级Token无压力；
• LCP数组构建同样是线性时间，进一步压缩CPU开销；
• 完全避免后缀树的内存膨胀问题，同时比字典暴力匹配效率提升数个数量级。

实现注意事项 #

• 优先调用C/C++实现的SA-IS扩展库（比如Python中的pysais），纯Python实现的SA算法会大幅降低CPU性能；
• Token映射时用collections.defaultdict配合计数器快速完成，避免冗余操作；
• 可设置最小重复长度阈值（比如示例中的2个Token），过滤短重复子序列，减少无效计算。

备选方案：滚动哈希（Rabin-Karp）分治处理 #

若SA-IS实现成本较高，可考虑滚动哈希结合分治的方案：

• 长序列优先检测：先从长度较大的子序列（比如100个Token）开始，用滚动哈希计算每个窗口的哈希值，存入字典记录起始位置，找到重复哈希后再验证子序列的真实性；
• 逐步缩小范围：处理完长重复子序列后，再处理较短的，利用长重复序列的信息剪枝，减少计算量；
• 该方案CPU性能略逊于后缀数组，但实现更简单，适合快速落地。

内容的提问来源于stack exchange，提问作者Izik