基數排序用於後綴排序嗎？

我想實現塊排序。這是來自Burrows Wheeler paper。基數排序用於後綴排序嗎？

（在此步驟之前，將創建的S爲V後綴數組）

Q4。 [基數排序]
對V的元素進行排序，使用每個後綴的前兩個字符作爲排序關鍵字。這可以使用基數排序有效地完成。

所以我明白你正在用radix排序後綴。
這應該如何更新數組V？只有在基數排序完成後，我才能知道後綴的排序位置。假設第4個後綴在排序後最終成爲第一個後綴。所以V [0] = i。在這種情況下，我們知道（因爲我告訴過你）i = 4。但是算法如何知道，因爲我們沒有跟蹤他們的位置。我應該創建一個包含後綴和後綴數字的類嗎？

來源

2011-06-15 Erandros

快速閱讀後;我認爲Burrows-Wheeler有一個錯誤，並且打算說使用數組V來排序W的元素以跟蹤和映射W的元素的最終位置。 W不變，V包含索引的排序列表。

本文似乎將V視爲指向W中從這一點開始的元素的指針數組。

檢出http://michael.dipperstein.com/bwt/在頁面底部有一個很好的描述以及算法的源代碼。

來源

2011-06-15 04:09:43 Colin

我不這麼認爲，你實際上必須對後綴進行排序。也許他的意思是說，你實際上排序V和W（肯定是V）。這篇論文如此含糊不清，讓我想要轟炸作者的房屋。 – Erandros 2011-06-15 04:13:40

好的，也許吧。我把它理解爲用W [i]的後綴作爲每行第i行的關鍵字來排序W，並將結果存儲爲V. – Colin 2011-06-15 04:17:08

哈，是的，不完整性在學術論文中很不常見。 – Colin 2011-06-15 04:19:01

基數排序用於後綴排序嗎？

回答

相關問題