后缀数组实现技术问询：算法正确性与变量含义等问题

代码实现 #

import math
import dataclasses

def suffix_array(text: str) -> list[int]:
    @dataclasses.dataclass(order=True)
    class Entry:
        prefix: list[int] = dataclasses.field(default_factory=lambda: [0, 0])
        start: int = dataclasses.field(default_factory=int, compare=False)

    n = len(text)
    m = math.ceil(math.log2(n)) + 2
    pos = [ord(x) for x in text]
    suffixes = [Entry() for _ in range(n)]
    for step in range(1, m):
        cnt = 2 ** (step - 1)
        for i in range(n):
            suffixes[i].prefix[0] = pos[i]
            suffixes[i].prefix[1] = pos[j] if (j := i + cnt) < n else -1
            suffixes[i].start = i
        suffixes.sort()
        for i in range(n):
            if i > 0 and suffixes[i] == suffixes[i - 1]:
                pos[suffixes[i].start] = pos[suffixes[i - 1].start]
            else:
                pos[suffixes[i].start] = i

    return [i.start for i in suffixes]

技术问答 #

1. 该算法的正确性如何证明？为何排序前缀的相对位置就能保证前缀本身有序？ #

这个算法是基于倍增法的后缀数组实现，正确性可通过数学归纳法证明：

• 归纳基础：step=1时，cnt=1，每个Entry.prefix存储后缀起始位i的字符编码，以及i+1位的编码（超出文本则为-1）。此时排序Entry，本质是按后缀前2个字符的字典序排序，结果是正确的。
• 归纳假设：假设step=k时，已能正确按后缀前2^k个字符的字典序排序所有后缀，且pos数组存储了每个后缀前2^k个字符的排名。
• 归纳步骤：step=k+1时，cnt=2^k，Entry.prefix存储后缀i前2^k个字符的排名，以及后缀i+2^k前2^k个字符的排名（超出则为-1）。这相当于把后缀i的前2^(k+1)个字符拆成两个长度为2^k的子串，两个子串的排名组合，完全等价于原前缀的字典序。排序这些组合键，就能得到按前2^(k+1)个字符排序的后缀序列。由于m取到ceil(log2(n))+2，当2^m >=n时，前2^m个字符覆盖整个后缀，此时排序结果就是完整的后缀数组。

排序前缀的相对位置等价于前缀本身有序的核心：两个长度为2^s的前缀的字典序，完全由拆分后的两个长度为2^(s-1)的子前缀的排名组合决定——若A的前半部分排名小于B，A整体更小；若前半部分排名相等，则比较后半部分排名，这和直接比较前缀字典序的逻辑完全一致。

2. 上述代码中的suffixes、pos、Entry.prefix三个变量分别承担什么作用？ #

• suffixes：存储每个后缀的排序键与起始位置的列表。每次迭代会为每个后缀生成对应的排序键（prefix），对该列表排序后，就能得到当前步长下后缀的有序序列。
• pos：存储每个后缀当前的排名值。初始时是字符的ASCII编码（单个字符的排名）；每次迭代后，更新为当前步长下后缀的排名——若两个后缀的排序键相同，排名也相同，否则按排序后的顺序分配递增排名。这个数组是实现倍增的核心，把长前缀的比较转化为短前缀排名的比较。
• Entry.prefix：作为排序的核心键，每次迭代存储当前后缀对应的两个子前缀的排名组合。比如step=s时，它存储后缀i前2^(s-1)个字符的排名，以及后缀i+2^(s-1)前2^(s-1)个字符的排名（超出文本则为-1）。通过比较这个组合键，就能等价比较后缀前2^s个字符的字典序。

3. 首次迭代（step=1）时suffixes[i].prefix是长度为2的前缀首尾值，二次迭代（step=2）时它基于pos值生成，此时它的具体含义是什么？ #

• step=1时，cnt=1，prefix第一个元素是pos[i]（即text[i]的ASCII编码），第二个元素是pos[i+1]（即text[i+1]的ASCII编码，超出则为-1），对应后缀i的前2个字符原始值，用来按前2个字符排序后缀。
• step=2时，cnt=2，prefix第一个元素是step=1迭代后更新的pos[i]——代表后缀i前2个字符的排名；第二个元素是pos[i+2]（超出则为-1），代表后缀i+2前2个字符的排名。此时这个组合键的含义是：后缀i前4个字符的字典序，等价于（后缀i前2个字符的排名，后缀i+2前2个字符的排名）的组合序。因为后缀i的前4个字符可拆分为text[i..i+1]和text[i+2..i+3]，这两部分的排名组合能唯一确定这4个字符的字典序。

4. 论文称后缀数组位于矩阵P的最后一行，但实际来自suffixes的start值，该表述矛盾如何解释？ #

这里的“矩阵P”是倍增法定义的排名矩阵：矩阵第k行存储每个后缀前2^k个字符的排名。代码中的pos数组，其实就是矩阵P当前迭代步对应的行（每次迭代更新一次pos，对应矩阵的一行）。

论文的表述是简化说法，准确逻辑是：当迭代到2^k >=n时，矩阵最后一行的排名已能唯一区分所有后缀（因为后缀最长为n），此时按最后一行的排名对后缀排序，得到的起始位置序列就是后缀数组。而代码中，每次迭代都会对suffixes列表排序，最后一次排序后的suffixes的start字段，就是按最终排名排序后的后缀起始位置，也就是后缀数组。两者本质等价，并不矛盾——矩阵最后一行的排名决定了后缀顺序，suffixes排序后的start是这个顺序的直接体现。

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