后缀数组的定义及实现

后缀数组的定义及实现 1 后缀数组的定义 1.1 后缀数组的相关概念     (1) 文本串的后缀：对于符号 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf Σ上的长度为n的文本串T[1...n]，文字串T的后缀是指从第i个字符开始到T的末尾所形成的子串T[i...n]，1 ≤ i ≤ n。     (2) 子串：在长度为 n的文字串T中，下标从i到j的连续的(j-i+1)个字符所组成的字符序列就是文字串T的一个长度为( j – i + 1)子串，其中1 ≤ i ≤ j ≤ n。     (3) 后缀数组：后缀数组SA是T的所有后缀T0, T1, ... Tn-1的一个字典序排序，即SA[i] = j表示后缀Tj是字符串集合{T0, T1, ... Tn-1}中第i个最小字符串。排序后的后缀数组具有如下性质： TSA[0] < TSA[1] < …< TSA[n - 1] 下图为后缀数组及其名次示例(T = acaaccg$)     此图表示描述了了SA中所需要得到的SA[i]和Rank[i]，其中Rank[i] = j表示T中的第i个后缀在所有后缀的字典排名为j。     SA[i] = j的两种表示理解方式：(1) 表示Tj在字符串集合中排名为i (2) 表示排名为i的后缀的Position。 1.2 后缀数组的相关数组解释     为了理解后缀数组，我们需要理解以下两个数组的含义以及它们之间的相互关系：     SA数组(Pos数组)：SA数组是我们需要直接使用的数组，SA数组是FM-index的基础，后面的bwt正是在SA的基础上进行变化得到文本L。在1.1中提到：SA[i] = j表示后缀Tj是字符串集合{T0, T1, ... Tn-1}中第i个最小字符串。因此SA[i] = j的两种表示理解方式：(1)表示Tj在字符串集合中排名(字典序排名)为i。(2)表示排名为i的后缀的Position。     Rank数组：Rank数组是后缀数组的逆数组SA-1，即若SA[j] = i，则Rank[i] = j，其实质反映了T中的第i个后缀在所有后缀中的字典序排名为j。 2 倍增法后缀数组 2.1 倍增法后缀数组基本概念     倍增法可以在logn步完成后缀数组的构造，n代表字符串A的长度。在倍增过程中，要维护两个整型、大小为N的数组Pos，Rank。Pos [i] 表示排名为i的后缀的Position，即在原字符串中的起始位置。Rank[i]表示在原字符串i处开始的后缀的排名，明显Pos[Rank[i]]=i。在第一阶段，所有后缀按首字母进行桶排序，即：所有首字母相同的后缀位于同一个桶内，且桶与桶之间按字典序排序。 之后，每个阶段按照2倍于上次的字符数参与新一轮的桶排序。明显在k阶段，参与比较的字符数为2K个，用H表示，即所有前H个字符相同的后缀处于同一个桶内。现在假设H阶段已经排序完成，即Pos数组，Rank数组有正确的值，倍增算法的基本思路是：根据H阶段的Pos值，Rank值， 构造2H阶段的Pos值，Rank值。     假设Ai和Aj是H阶段同一个桶内的两个后缀，这意味着：Ai和Aj的前H个字符是相同的，接下来需要比较后续的H个字符，即H+1到2H之间的字符。非常巧的是，这H个需要比较的字符也恰巧是后缀Ai+H，Aj+H的前H个字符，假设我们已经知道Ai+H，Aj+H按≤H的字典序关系（≤H的字典序表示后缀间按前H个字符的大小关系得到的字典序，后续的≤H，≤2H意义相同），则：     从第一个桶的最左边（按≤H字典序最小）的后缀开始扫描，得到第一个后缀Ai，很明显Ai的前H个字符是最小的，考虑后缀Ai-H，其H到2H阶段的H个字符是最小的（Ai的前H个字符是最小的），所以Ai-H 这个后缀应该处在它所在2H阶段的相应桶内的最左端（最小）。所以，算法的整体思路就是：扫描H阶段按≤H有序的桶内的所有后缀，对于每一个后缀Ai，将Ai-H 移动到它的桶内的下一个位置。当H阶段的扫描完成时，所有后缀都已经按≤2H的顺序处于对应的桶内，同一个桶内的所有后缀的前2H个字符都是相同的。在这个过程中，我们也需要维护一个BH数组，用来表示桶的边界，大小为n，初始值为全0，在每个桶的起始位置处为1，所以在BH数组中，假设两个连续的1对应的下标为S，V，则排名在[S,V−1]之间的所有后缀处在同一个桶内。     伴随着H的增大，旧桶破裂，新桶产生，且桶的数目在增大（此过程对应BH数组的变化），在最后一个阶段，桶的数目等于N，BH数组全为1，此时每个桶里只有一个后缀，排序完成。所以算法的大致 流程 快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计 为：     1：所有后缀按首字母桶排序，得到对应的Pos，Rank，BH数组。     2：在已有H阶段Pos，Rank，BH数据的情况下，按≤H的顺序扫描所有桶内的所有后缀Ai，移动Ai-H 到对应位置（实质是修改Rank的值）。最终得到≤2H阶段的Pos，Rank，BH的值。     3：若H > N,排序完成，此时Pos，Rank为最终值，BH全1。否则H=2H，转到2。     按照上述算法，共需扫描log(n)次，每次都需要扫描所有的后缀，所以时间复杂度为O(n log n)。在排序过程中，需要维护Pos，Rank，BH等辅助空间，其大小都为n，所以空间复杂度为O(n)。 2.2 算法 Algorithm 1: Suffix Sorting(A, Pos, n) Input: A, n Output: Pos Variables: Rank[n], Count[n]; BH[n+1], B2H[n+1] /*Assume that you have the right value of Pos、Rank、BH using a radix sorting with compareing the first singal-symbol of all the suffixs, our main point is to explain how compute Pos ,Rank and BH of stage 2H while using the information of stage H */ 1: for H ← 1, 2, 4, 8, …., n−1 do 2:     for each H_Bucket[L, R] do 3:         Count[L] ←0 4:         for c ← L to R do 5:             Rank[Pos[c]] ← L 7:     d ← N−H 8:     e ← Rank[d] 9:     Rank[d] ← e + Count[e] 10:     Count[e] ← Count[e] + 1 11:         B2H[Rank[d]] ← 1 12:        for each H_bucket[L,R] in order ≤ H_order do 13:         for c ← L to R do 14:             d ← Pos[c]−H 15:             if d ≥ 0 then 16:                 Rank[d] ←Rank[d]+Count[Rank[d]] 17:                 Count[Rank[d]] ←Count[Rank[d]] + 1 18:                 B2H[Rank[d]] ←1 19:         for c ← L to R do 20:             d ←Pos[c] − H 21:             if d ≥ 0 then 22:                 if B2H[Rank[d]] then 23:                        e ← min(j : j >Rank[d] and (BH[j] or not B2H[j])) 24:                        for f ← Rank[d] + 1 to e −1 do 25:                            B2H[f] ← 0 26:     for i ← 0 to N−1 do 27:         Pos[Rank[i]] ← i 28:     for i ← 0 to N−1 do 29:            if B2H[i] and not BH[i] then 30:                BH[i] ←B2H[i]     输入参数A表示原文本字符串，n表示原本字符串的长度，Pos数组为最终的返回值。算法第2行表示取每个通的左右边界，第12行意思类似，只是按照桶的≤H字典序进行，即先取“小”桶的边界，再取“大”桶的边界。本算法主要突出由H阶段的Pos值构造2H阶段的Pos值的核心过程。     算法中用到了三个大小为n的整型数组，Pos、Rank和Count和两个大小为n+1的Boolean型数组BH和B2H。     Pos[i]表示名次为i的后缀在原字串中的起始位置，Rank数组是Pos数组的逆，即Rank[Pos[i]]=i，Rank[j]表示从j处开始的后缀的排名。     Count数组是个临时数组，用来保存在扫描过程中，某个桶内已经移动的后缀的个数。在该桶内的后缀都未移动时，所有后缀的排名与最左端后缀的排名相同，则该桶内第Count[Rank[d]]个移动的后缀的排名更新为Rank[d]+Count[Rank[d]]−1，这是算法的核心。     BH数组用来表示每个阶段的桶的开始位置。B2H是BH的临时数组，在某次具体的扫描过程中，B2H标示出那些被移动过的后缀，在扫描的结尾，结合BH和B2H的信息，得到新的桶的开始位置，这是算法的关键。 文档已经阅读完毕，请返回上一页！