algorithm - 基数排序是否用于后缀排序？

Question

我正在尝试实现块排序。这是来自 Burrows Wheeler 的论文。

（在此步骤之前，您创建一个 S 的 V 后缀数组）

Q4。[基数排序]
对 V 的元素进行排序，使用每个后缀的前两个字符作为排序键。这可以使用基数排序有效地完成。

所以我知道您正在使用基数排序对后缀进行排序。
这应该如何更新数组 V？只有在基数排序完成后，我才能知道后缀的排序位置。假设第 4 个后缀最终成为排序后的第一个。所以 V[0] = i。在这种情况下，我们知道（因为我告诉过你）i = 4。但是算法如何知道这一点，因为我们没有跟踪它们的位置。我应该创建一个包含后缀及其后缀编号的类吗？

Answer 1

快速阅读后；我认为 Burrows-Wheeler 有一个错误，意思是说使用数组 V 对 W 的元素进行排序，以跟踪和映射 W 元素的最终位置。即。这样 W 不变并且 V 包含一个排序的索引列表。

该论文似乎将 V 视为从该点向前指向 W 中元素的指针数组。

查看http://michael.dipperstein.com/bwt/ 在页面底部有一个很好的描述以及算法的源代码。