我在Burrows Wheeler轉換中使用了什麼EOF字符？

我試圖實現塊排序。在Burrows惠勒變換中，塊排序需要將EK字符的數量附加到原始字符串S，其中EOF不出現在S.我在Burrows Wheeler轉換中使用了什麼EOF字符？

但是由於我將處理二進制文件，因此可能會有任何可能的組合位，所以我不能提前選擇一個單一的EOF字符，我保證它不會在S.

我該如何解決這個問題？

由於該EOF字符用於在一個步驟中對後綴進行排序，因此我讀過您可以在不需要該EOF字符的情況下對後綴樹進行排序。我應該使用後綴樹嗎？

2011-06-13 Erandros

您可以使用數據容器的長度或通過使用單獨的EOF表來跟蹤虛擬EOF字符的字符位置來創建「虛擬」EOF。

[更新另一個想法] ... 另一個選項，選擇了一個EOF字符，將其稱爲0x00和一個轉義字符，將其稱爲0xFF。掃描您的輸入，併爲所有0xFF和0x00使用0xFF。那就是，簡單地逃避它們。將數據寫回去時做相反的操作

2011-06-13 22:56:47

我知道你的意思，但這是不同的。在S字符串附加了k個EOF字符後，它的後綴被排序（是的，包括EOF字符）。 – Erandros 2011-06-13 23:02:26

查看更新的答案;創建一個EOF字符並將其轉義，就像在C字符串中使用特殊字符一樣。 – 2011-06-13 23:07:19

你說得對。使用轉義序列是必要的，可以使用後綴數組或後綴樹。 – Erandros 2011-06-13 23:21:44

回答