第 59 页KWIC 的后缀排序解决方案预处理对文本进行后缀排序。查询二分查找查询词然后扫描直到不匹配。图示在排序后的后缀数组中二分查找 search找到一片连续区域。物理含义预处理阶段构建后缀数组O(N log N) 或更好。查询阶段在排序后的后缀数组上做二分查找定位查询词可能出现的区间。二分查找每次比较查询词和后缀的前缀比较代价与查询词长度成正比。找到起始位置后向后扫描直到后缀不再以查询词开头。扫描的每个后缀都对应文本中一次出现。查询时间O(查询词长度 × log N 匹配次数 × 查询词长度) 或更优。物理上所有以查询词开头的后缀在排序后是连续的所以二分查找可以定位到这个区间的左边界。第 60 页最长重复子串问题给定长度为 N 的字符串找到最长的重复子串。应用生物信息学、密码分析、数据压缩。物理含义最长重复子串是字符串中至少出现两次的最长子串。在基因组中重复序列可能有生物学意义。在数据压缩中重复子串是压缩的机会。暴力算法是检查所有索引对计算最长公共前缀O(N²) 或更差。利用后缀数组可以更高效地解决。第 61 页最长重复子串的音乐应用展示一个可视化把音乐中的重复片段用弧线连接。Mary Had a Little Lamb 和 Bach 的 Goldberg Variations。物理含义音乐可以表示为字符串音符序列。最长重复子串对应音乐中重复出现的主题或动机。这是一个直观的应用示例说明字符串算法可以用于分析序列数据中的重复结构。第 62 页最长重复子串的暴力算法尝试所有可能的起始索引 i 和 j。对每一对计算最长公共前缀LCP。分析运行时间 ≤ D N²其中 D 是最长匹配的长度。物理含义双重循环遍历所有索引对对每一对调用 lcp 函数。lcp 最多比较 D 个字符。最坏情况下 O(N² D)对于长文本不可接受。第 63 页最长重复子串的排序解决方案形成所有后缀。排序后缀把重复子串带到一起。计算相邻后缀之间的最长公共前缀LCP。图示输入字符串aacaaagtttacaagc形成后缀排序然后计算相邻后缀的 LCP。物理含义最长重复子串一定是某两个后缀的最长公共前缀。如果两个后缀共享一个长度为 L 的前缀那么这个前缀在文本中至少出现了两次。在所有后缀对中最长公共前缀最大的那一对其 LCP 就是最长重复子串。关键观察不需要检查所有后缀对。排序后最长公共前缀最大的两个后缀一定在排序后相邻或至少可以通过相邻后缀的 LCP 找到。因为排序把相似的后缀放在一起。所以算法排序后缀数组然后扫描相邻后缀计算它们的 LCP记录最大值。第 64 页最长重复子串的 Java 实现javapublic String lrs(String s) { int N s.length(); String[] suffixes new String[N]; for (int i 0; i N; i) suffixes[i] s.substring(i, N); Arrays.sort(suffixes); String lrs ; for (int i 0; i N-1; i) { int len lcp(suffixes[i], suffixes[i1]); if (len lrs.length()) lrs suffixes[i].substring(0, len); } return lrs; }物理含义创建后缀数组每个后缀是一个 String 对象共享底层char[]。Arrays.sort(suffixes)使用 Java 的归并排序对对象数组或 TimSort比较后缀字符串的字典序。扫描相邻后缀计算 LCP记录最长的。时间复杂度瓶颈在排序O(N log N) 次字符串比较每次比较可能扫描很长前缀。最坏 O(N² log N)。使用三路基数快速排序可以改善。第 65 页排序挑战五位科学家 A、B、C、D、E 面对 10 亿个核苷酸的基因组寻找最长重复子串。A让研究生手工做。B暴力算法。C后缀排序 插入排序。D后缀排序 LSD 字符串排序。E后缀排序 三路字符串快速排序。问题谁更可能找到治愈癌症的方法物理含义选择正确的后缀排序算法至关重要。插入排序 O(N²) 不可行。LSD 需要固定长度对长基因组不适用。三路字符串快速排序是实际中最优的选择。这强调了算法选择对实际应用的影响。第 66 页最长重复子串的经验分析表格比较暴力算法和后缀排序在不同输入上的运行时间。LRS.java2,162 字符暴力 0.6 秒后缀排序 0.14 秒LRS 长度 73。amendments.txt18,369 字符暴力 37 秒后缀排序 0.25 秒LRS 长度 216。aesop.txt191,945 字符暴力 1.2 小时后缀排序 1.0 秒LRS 长度 58。mobydick.txt1.2M 字符暴力 43 小时后缀排序 7.6 秒LRS 长度 79。chromosome11.txt7.1M 字符暴力 2 个月后缀排序 61 秒LRS 长度 12,567。pi.txt10M 字符暴力 4 个月后缀排序 84 秒LRS 长度 14。pipi.txt20M 字符暴力 forever后缀排序 LRS 长度 10,000,000。物理含义暴力算法随 N² 增长不可扩展。后缀排序在实践中是唯一可行的方案。chromosome11 的 LRS 长度达到 12,567说明基因组中有很长的重复序列。pipi.txt 是两个相同文本的拼接LRS 长度达到 10,000,000即整个文本的一半。这暴露了后缀排序在 LRS 极长时的性能问题LCP 计算需要 O(D) 时间D 很大时总时间 O(N D) 可能变为二次。第 67 页坏输入——最长重复子串很长例子同一个字母重复 N 次两份相同的 Java 代码库。形成后缀排序计算 LCP。LRS 需要至少 1 2 3 ... D 次字符比较其中 D 是最长匹配长度。运行时间O(D²) 或更差。物理含义如果最长重复子串很长比如 D N/2那么计算相邻后缀的 LCP 时每个 LCP 可能比较 D 个字符。总共有 N 个后缀总比较次数可能达到 N D最坏 D N 时是 O(N²)。这是后缀数组方法的一个弱点当重复非常长时LCP 计算成为瓶颈。第 68 页后缀排序的困难问题对任意长度 N 的字符串进行后缀排序。最坏情况运行时间选项二次时间、线性时间、线性时间、没人知道、Manber-Myers 算法、后缀树超出范围。物理含义使用通用的字符串排序算法如三路快排对后缀排序最坏情况可能达到 O(N² log N) 或 O(N²)。Manber-Myers 算法可以在 O(N log N) 时间内完成后缀排序。后缀树可以在线性时间内构建但空间开销大实现复杂。这一页在提示后缀排序本身是一个需要专门算法的问题。第 69 页线性对数后缀排序Manber-Myers MSD 算法概述阶段 0用键索引计数按第一个字符排序。阶段 i给定按前 2^{i-1} 个字符排序的后缀数组创建按前 2^i 个字符排序的数组。最坏运行时间 O(N log N)。在 log N 个阶段后完成。每个阶段可以在线性时间内完成。物理含义这是一个倍增doubling算法。阶段 0按首字符排序得到按 1 个字符排序的后缀。阶段 1利用已经排好的 1 字符顺序把每个后缀的前 2 个字符看作一个二元组当前排名后一个位置的排名然后按这个二元组排序。因为后一个位置的排名已知来自阶段 0所以排序可以在线性时间内通过键索引计数完成。阶段 2用前 2 个字符的排名组合成前 4 个字符的二元组排序。以此类推直到排序键长度超过 N。总共 log N 个阶段每个阶段 O(N)总 O(N log N)。第 70-74 页线性对数后缀排序示例展示babaaaabc...字符串的逐阶段排序过程。阶段 0按首字符排序。阶段 1按前 2 个字符排序。阶段 2按前 4 个字符排序。阶段 3按前 8 个字符排序。最终完成排序。第 74 页展示如何通过 inverse 数组在常数时间内比较两个后缀的前 2^i 个字符。物理含义每一阶段后缀的排序键从长度 2^{i-1} 扩展到 2^i。排序键由两个部分组成前半部分长度 2^{i-1}的排名和后半部分长度 2^{i-1}的排名。这两个排名都来自上一阶段的排序结果。把这两个排名组成一个二元组然后用键索引计数因为排名是 0 到 N-1 的整数在 O(N) 时间内排序。inverse[]数组记录了每个后缀在当前排序中的位置用于快速获取后半部分的排名。经过 log N 个阶段排序键长度达到 N排序完成。第 75 页字符串排序总结我们可以开发线性时间排序键索引计数、LSD。我们可以开发次线性时间排序MSD只检查必要字符。三路字符串快速排序是渐近最优的1.39 N log N 字符比较随机数据。长字符串在实践中很少是随机的。目标通常是学习其结构可能需要专门算法。物理含义字符串排序的核心优势利用字符是整数直接用数组索引绕过比较下界。后缀数组是字符串排序的一个重要应用用于文本索引、重复检测、生物信息学。实际中长字符串如基因组有大量重复和结构通用排序算法可能不够需要专门的后缀排序算法如 Manber-Myers。一、最长重复子串问题Q第64页这里的代码是何意味呢for (int i 0; i N-1; i) { int len lcp(suffixes[i], suffixes[i1]); if (len lrs.length()) lrs suffixes[i].substring(0, len); }计算最长的重复数组可是这里只比较了相邻数组。是基于排序后重复的字符部分会相连的特性吗A是的。这段代码的物理动作是在排序后的后缀数组中只检查相邻的两个后缀找出它们的最长公共前缀LCP并记录全局最长的那个。1. 为什么不用比较所有对假设文本中最长的重复子串是abc它在文本中出现了三次分别对应后缀 A、后缀 B、后缀 C。排序后所有以abc开头的后缀一定会被排在一起形成一个连续的区间。因为字典序比较是从左向右逐个字符比只要前缀相同它们就不会被其他不以abc开头的后缀隔开。2. 相邻对如何捕捉到这个最长前缀在这个连续区间里可能有好几个后缀。我们不需要让 A 和 C 去比它们隔得远但前缀依然相同。我们只需要看相邻的 A 和 B或者 B 和 C。只要它们相邻它们的前缀就必然包含abc。如果在abc之后A 和 B 的下一个字符不同那么lcp(A, B)返回的长度就是 3。这就找到了重复子串abc。如果 A 和 B 在abc之后还有更多相同字符比如abcd那lcp(A, B)会返回 4。你甚至能在相邻对里找到更长的重复。3. 会不会出现“最长的重复子串只出现在不相邻的两个后缀中”绝对不会。假设有两个不相邻的后缀 X 和 Y它们共享一个很长的前缀 S比如长度 10。因为 X 和 Y 不相邻它们中间必然夹着其他后缀 Z。由于排序是按字典序排的Z 必须排在 X 和 Y 之间。这意味着 Z 的前缀也必须是 S或者至少包含 S否则 Z 不可能被夹在中间。既然 Z 也包含 S那么lcp(X, Z)或lcp(Z, Y)的长度必然也至少是 10。所以全局最长的公共前缀一定出现在相邻的两个后缀之间。你不需要去跨越中间后缀去找。4. 代码逐行物理动作javafor (int i 0; i N-1; i) { int len lcp(suffixes[i], suffixes[i1]); if (len lrs.length()) lrs suffixes[i].substring(0, len); }for (int i 0; i N-1; i)按顺序从第一个后缀遍历到倒数第二个后缀。每次拿当前后缀和它紧挨着的下一个后缀。int len lcp(suffixes[i], suffixes[i1]);计算这两个相邻后缀从第 0 个字符开始有多少个字符完全相同。这就是它们共享的重复子串长度。if (len lrs.length())如果这个长度比之前记录的最长重复子串还长。lrs suffixes[i].substring(0, len);更新最长重复子串。截取当前后缀的前len个字符这就是当前找到的最长重复片段。总结这段代码的意思是通过排序把文本中所有重复出现的子串“暴露”在相邻位置。 因此最长重复子串的计算从“寻找所有后缀对的最大公约数”变成了“一次遍历比较相邻元素的公共前缀”。这就是排序解法从 O(DN2) 降到 O(NlogNND)的关键所在。二、小节疑问Qok我看到第66页了。就这样没有了既没有讲查找匹配对比的长度也没有讲后缀的具体建立机制这样就可以了吗就是一个介绍而已吗A1. 这一节的定位是“字符串排序”的应用示例第 5 章的核心是字符串排序5.1后缀数组是这一节末尾的一个应用案例用来说明“字符串排序能用来解决什么问题”。它不是后缀数组的完整教程。PPT 用几页展示了问题定义、核心思路和性能数据然后结束。真正的后缀数组实现细节Manber-Myers 的完整代码、LCP 数组的构建、后缀树的对比被放在了教材的后续章节或专门文献里。PPT 只给了概念和示例。2. 搜索匹配的具体动作没有展开你问“没有讲查找匹配对比的长度”。确实没有。PPT 第 59 页只写了一句话“Query: binary search for query; scan until mismatch.” 它假设你已经在第 3 章学过二分查找在第 5.3 节会学 KMP/Boyer-Moore 等子串搜索算法。这里只是告诉你“后缀数组上的查询 二分查找 扫描”不展开具体比较过程。如果你想追踪一次完整的查询物理动作是在排序后的后缀数组上二分查找查询词。每次比较时逐字符比较查询词和后缀的前缀。找到左边界后向后扫描直到后缀不再以查询词开头。扫描过的每个后缀其起始索引就是一次出现位置。这个动作在第 59 页的 KWIC 输出中隐含了但 PPT 没有画指针图。3. 后缀的具体建立机制只给了 Manber-Myers 的概念第 69 页给出了 Manber-Myers 的概述倍增法第 70-74 页展示了倍增过程。但没有给完整 Java 实现。PPT 的定位是让你理解“倍增”这个思想而不是让你自己写出来。如果你要自己实现需要阶段 0键索引计数按首字符排序。阶段 i用上一轮的排名构造二元组键索引计数排序。终止条件所有后缀的排名互不相同。用inverse[]数组在 O(1) 时间内获取排名。这些在 PPT 里只展示了示例没有给完整代码。4. 这一节的目标它想让你知道后缀数组是什么。它能解决什么问题全文搜索、最长重复子串。它的性能优势预处理 O(N log N)查询快。它的核心难点后缀排序需要专门算法不能直接用通用比较排序。它不要求你手写 Manber-Myers。追踪查询的二分查找指针。实现 LCP 数组的线性时间构建。5. 如果你需要更多PPT 之外教材第 5.1 节末尾和第 6 章有更详细的展开。但作为自学你不需要在第一次遇到时把每个细节都啃透。你现在理解了后缀数组的物理意义和核心思路这已经足够。后续如果遇到需要实现或优化的场景再回来补细节。