3

假设有一种加密字符串的方法：

  • 在字符串的末尾附加字符 $，它是字母表中的第一个字符。
  • 通过不断地将第一个字符移动到字符串的末尾来形成我们得到的所有字符串。
  • 将我们得到的所有字符串按字母顺序排序。
  • 通过将每个字符串的最后一个字符附加到它来形成一个新字符串。

例如，单词 FRUIT 以以下方式加密：

We append the character $ at the end of the word:
FRUIT$

We then form all the strings by moving the first character at the end:
FRUIT$
RUIT$S
UIT$FR
IT$FRU
T$FRUI
$FRUIT

Then we sort the new strings into alphabetical order:
$FRUIT
FRUIT$
IT$FRU
RUIT$F
T$FRUI
UIT$FR

The encrypted string:
T$UFIR

现在我的问题很明显：如何将给定的字符串解密为原始形式。

头疼了半个星期，终于没纸了。

我该怎么办？

我发现了什么：

如果我们有加密的最后一步：

$FRUIT
FRUIT$
IT$FRU
RUIT$F
T$FRUI
UIT$FR

我们可以知道原始字符串的第一个和最后一个字符，因为最右边的列是加密字符串本身，最左边的列总是按字母顺序排列。最后一个字符是加密字符串的第一个字符，因为 $ 在字母表中总是排在第一位，而且它在一个字符串中只存在一次。然后，如果我们从最右边的列中找到 $ 字符，并在最左边的列中查找同一行的字符，我们会得到第一个字符。

所以我们可以知道加密字符串 T$UFIR 是原始字符串是 F***T$，其中 * 是一个未知字符。

我的想法到此结束。现在我必须利用万维网问另一个人：怎么做？

您可以说这是作业，并且熟悉我的导师，我将赌注押在这是一个动态编程问题上。

4

1 回答 1

15

这是 Burrows-Wheeler 变换。

它是一种通常用于辅助压缩算法的算法，因为它倾向于将常见的重复短语组合在一起，并且是可逆的。

要解码您的字符串：

给每个字符编号：

T$UFIR
012345

现在排序，保留编号。如果字符重复，则使用索引作为辅助排序键，以便重复字符的索引保持递增顺序，或者使用保证这一点的排序算法。

$FIRTU
134502

现在我们可以解码了。从'$'开始，并使用关联的索引作为下一个字符输出（'$' = 1，所以下一个字符是'F'。'F'是3，所以下一个字符是'R'，等等...)

结果：

$FRUIT

所以只需删除标记字符，就完成了。

于 2013-01-14T22:01:47.963 回答