MTF变换MTF(move to front)变换是一种可逆变换
也称为前移编码
常用在BWT变换后
其维护一张"索引->数值"的表
以BYTE数据为例,假设对一字串S[1]S[2]...S[n]进行前移编码
开始初始化表
索引
0
1
2
3
...
252
253
254
255
数值
0
1
2
3
...
252
253
254
255
逐个地进行如下步骤:
1.找到数值S[i]在表中对应的索引进行输出(作为S'[i])
索引
0
1
2
3
...
S'[i]
...
254
255
数值
0
1
2
3
...
S[i]
...
254
255
2.将数值S[i]移动到表的开头(索引行不变动)
索引
0
1
2
3
...
S'[i]
...
254
255
数值
S[i]
0
1
2
...
S[i]-1
...
254
255
拼接所有输出的字符可得转换后的串S'
解码字串S'[1]S'[2]...S'[n]时同样初始化表
索引
0
1
2
3
...
252
253
254
255
数值
0
1
2
3
...
252
253
254
255
逐个地进行如下步骤:
1.找到索引S'[i]在表中对应的数值进行输出(作为S[i])
索引
0
1
2
3
...
S'[i]
...
254
255
数值
0
1
2
3
...
S[i]
...
254
255
2.将数值S[i]移动到表的开头(索引行不变动)
索引
0
1
2
3
...
S'[i]
...
254
255
数值
S[i]
0
1
2
...
S[i]-1
...
254
255
拼接所有输出的字符可得转换后的串S
显然正变换和逆变换是对称的
同时可以发现,变换前后的字符集是一样的,但是字符的数值会"前移"(向0值移动)
此变换很适合处理连续的相同字符组成的串(比如AAAAAAABBBBBBBCCCCCCC)
而BWT变换后的正是这种串
关于优化从上面的介绍可以发现
MTF变换的速度和字符集大小以及串长有关(实际过程中则受串内容影响较大)
不加任何优化的计算,其最坏情况为O(字符集大小*串长)
如果采用BIT或跳跃表等高效数据结构进行优化,可达O(log(字符集大小)*串长)
