algorithm - 后缀排序是用基数排序吗？

Question

我正在尝试实现 block 排序。这是来自 Burrows Wheeler paper .

(在这一步之前，你先创建一个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/页面底部有很好的算法描述和源代码。