複製鏈接
請複製以下鏈接發送給好友
https://baike.baidu.hk/item/MTF變換/10663891
複製
複製成功

MTF變換

鎖定
MTF(move to front)變換是一種可逆變換，也稱為前移編碼
中文名
MTF
外文名
move to front
別    名
前移編碼
定    義
一種可逆變換

目錄

  1. 1 釋義
  2. 2 關於優化

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變換關於優化

從上面的介紹可以發現
MTF變換的速度和字符集大小以及串長有關(實際過程中則受串內容影響較大)
不加任何優化的計算,其最壞情況為O(字符集大小*串長)
如果採用BIT或跳躍表等高效數據結構進行優化,可達O(log(字符集大小)*串長)