关于DC3算法中R₀与SAR₀生成逻辑的技术问询
2026-6-21
DC3算法论文中R₀与SAR₀的生成逻辑解释
一、R₀的生成逻辑
你误解了步骤：R₀不是对R的后缀排序后生成的，而是对R中的单个三元组按字典序排序并分配排名得到的：
- 先列出R中的所有三元组：
abb, ada, bba, do0, bba, dab, bad, o00 - 对这些三元组按字典序排序，相同三元组共享排名：
abb < ada < bad < bba = bba < dab < do0 < o00 - 给每个三元组分配从1开始的递增排名：
abb→ 1ada→ 2bad→ 3bba→ 4dab→ 5do0→ 6o00→ 7
- 按原R的顺序替换每个三元组为对应排名，就得到示例中的
R₀=(1,2,4,6,4,5,3,7)
二、SAR₀的生成逻辑
SAR₀是**R的所有后缀（含空后缀）**按字典序排序后的原索引序列（0-based，其中8代表空后缀）：
- 列出R的所有后缀（0-based索引，后缀i表示从第i个三元组开始到末尾的子数组）：
- 空后缀（标记为8）：无元素，字典序最小
- 后缀0：
[abb, ada, bba, do0, bba, dab, bad, o00] - 后缀1：
[ada, bba, do0, bba, dab, bad, o00] - 后缀2：
[bba, do0, bba, dab, bad, o00] - 后缀3：
[do0, bba, dab, bad, o00] - 后缀4：
[bba, dab, bad, o00] - 后缀5：
[dab, bad, o00] - 后缀6：
[bad, o00] - 后缀7：
[o00]
- 按字典序排序这些后缀：
排序规则是逐个比较对应位置的三元组，直到分出大小。比如后缀4（[bba, dab,...]）和后缀2（[bba, do0,...]），第一个三元组相同，比较第二个三元组dab < do0，所以后缀4排在后缀2前面。 - 排序后的后缀对应的原索引（含空后缀的标记8）就是：
8,0,1,6,4,2,5,3,7，即示例中的SAR₀。
内容的提问来源于stack exchange，提问作者kolman
相关产品推荐
相关产品推荐
