后缀排序是否使用基数排序？
我正在尝试实现块排序。这是来自 Burrows Wheeler 论文。
（在此步骤之前，您创建一个 S 的 V 后缀数组）
Q4。 [基数排序]
使用每个后缀的前两个字符作为 V 的元素进行排序 排序键。使用基数排序可以有效地完成此操作。
因此我了解您正在使用基数排序对后缀进行排序。
这应该如何更新数组 V？只有基数排序完成后我才能知道后缀的排序位置。假设第四个后缀最终成为排序后的第一个后缀。所以 V[0] = i。在这种情况下，我们知道（因为我告诉过你）i = 4。但是算法如何知道这一点，因为我们没有跟踪它们的位置。我应该创建一个包含后缀及其后缀号的类吗？
I'm trying to implement block sorting. This is from the Burrows Wheeler paper.
(Before this step, you create a V suffix array of S)
Q4. [radix sort]
Sort the elements of V , using the first two characters of each suffix as the
sort key. This can be done efficiently using radix sort.
So I understand you are sorting the suffixes with radix sort.
How is this supposed to update the array V? Only after the radix sort finished I can know the sorted position of a suffix. Suppose that the 4th suffix end up being the first after sorted. So V[0] = i. In this case, we know (because I told you) that i = 4. But how does the algorithm know that since we are not keeping track of their position. Should I make a Class that contains both the suffix and its suffix number?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
快速阅读后；我认为 Burrows-Wheeler 有一个错误，意思是使用数组 V 对 W 的元素进行排序，以跟踪和映射 W 元素的最终位置。这样 W 不变，V 包含索引的排序列表。
该论文似乎将 V 视为指向 W 中从该点开始的元素的指针数组。
查看 http://michael.dipperstein.com/bwt/ 有很棒的描述以及页面底部的算法源代码。
After a quick read; I think Burrows-Wheeler have an error and meant to say to sort the elements of W using the array V to track and map the final locations of the elements of W. ie. Such that W is unchanged and V contains a sorted list of indices.
The paper appears to treat V as an array of pointers to elements in W from that point forward.
Check out http://michael.dipperstein.com/bwt/ There is a great description as well as source code for the algorithm at the bottom of the page.