Michael_Bryant最喜欢的G(al)G(ame)

那些悲伤,那些寂寞,那些几乎让自己放弃生活的希望的痛苦的回忆,绝对绝对不要将它们忘记。

Michael_Bryant最喜欢的番剧

抱歉⋯我已经绝对不可能再获得幸福了,因为⋯我发现⋯ 其实我⋯ 早就已经被幸福包围了

Michael_Bryant正在看的番剧

死亡一点也不温柔,只有无尽的黑暗和孤独。 就算联系得再紧密,人也是孤独的。

BWT(Burrows–Wheeler-Transform)算法

什么是BWT算法

BWT算法是通过简单的流程 将一个文本串转化成为另外一个相似的文本串的过程 转换后使得相同的字符位置连续或者相邻
在这之后我们就可以用一些过程把这种转化完毕的文本串进行压缩
比如说Move-to-front transform 和 游程编码

BWT的编码方式

我们需要知道几个专用名词

  • 左旋(Rotated Left):定义左旋一次为将第一个字符放在最后一个字符之后
  • 右旋(Rotated Right):定义右旋一次为将最后一个字符放在第一个字符之前
  • F(first)一个字符串中的第一个字符
  • L(last)一个字符串中的最后一个字母

然后就可以开始编码了
这里举一个小例子 我们要对banana这个单词进行编码
怎么办呢

第一步 处理字符串

非常简单 把它变成'banana#' 就是在后面加上一个'#'
然后你需要画一个表格2333

第二步 进行一系列右旋操作

对于banana#来讲 你进行一系列右旋操作之后的结果大概长成这样
1. banana#
2. #banana
3. a#banan
4. na#bana
5. ana#ban
6. nana#ba
7. anana#b

第三步 进行最后的一系列处理

然后你对于得到的这些串 按照字典序进行排序
这里我们认为你添加的字符字典序小于字母
这样的话我们对于排序之后的字符串记录F和L
得到一个长成这样的表格

我们一般使用L列进行压缩
这样的话我们的压缩结果就是annb#aa

BWT的解码方式

比如说我给你一个BWT编码 annb#aa
通过上面的压缩过程你肯定已经知道了 这个单词在没有处理之前是banana
但是你怎么解码呢

一些性质

1:L列的第一个元素就是原文本最后一个元素

‘#’在首位时最后一位元素即为L列第一个元素。

2:对原文本来说,F列每个元素,都是对应L列元素的下一个元素(除首个元素)

由右移可以观察得出。
知道这两个性质之后 你就可以开始解码了

第一步 你需要用到刚才的表格

第二步 进行解码

首先从第一行进行解码
我们这里转化的过程是F->L这样的一种转化
这样的话你的第一步转化就是#->a
然后你获得了一个啊对吧 利用性质2 你接下来需要到F这一列找到a继续解码
但是有很多a怎么办QwQ
你需要知道的就是你当前这个a在L列是第几个
比如说我们刚刚完成的这个转化 a在L列是第一个
我们就到F列找到第一个a进行转码
所以说我们第二步转化是a->n这一步转化
同样的道理 我们要在F列找到第一个n
下一步就是n->a这一步
然后你当前的a是L列中的第二个a
你就去F列找到第二个a 下一步转化就是a->n(这个是第3行的)
以此类推你得到了如下的过程

(LF列表示转化过程 前面的数字代表了这一步转化是第几行的)

第三步 阅读

从下往上阅读转化结果
这个串我们解码结果为 #banana
去掉#我们发现正好是原串的banana

另外一个例子

这个是我手玩的

例题

就一道貌似
bzoj 2408 混乱的置换
题解的话大概在这里?传送门

One Comment

Add a Comment

电子邮件地址不会被公开。 必填项已用*标注

隐藏