algorithm - 我在 Burrows Wheeler 变换中使用什么 EOF 字符？

Question

我正在尝试实现 block 排序。在 Burrows Wheeler Transform 论文中，Block Sorting 需要在原始字符串 S 后追加 k 个 EOF 字符，其中 EOF 没有出现在 S 中。

但由于我将处理二进制文件，可能存在任何可能的位组合，因此我无法提前选择单个 EOF 字符，我保证它不会出现在 S 中。

我该如何解决？

由于该 EOF 字符用于在一个步骤中对后缀进行排序，我了解到您可以在不需要该 EOF 字符的情况下对后缀树进行排序。我应该改用后缀树吗？

Answer 1

您可以使用数据容器的长度或使用单独的 EOF 表来创建“虚拟”EOF，该表跟踪虚拟 EOF 字符的字符位置。

[更新另一个想法]...另一个选项，选择一个 EOF 字符，称之为 0x00 和一个转义字符，称之为 0xFF。扫描您的输入并为所有 0xFF 和 0x00 附加 0xFF。也就是说，简单地逃避它们。写回数据时做相反的操作