MTF变换

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(字符集大小)*串长)