MTF變換

MTF(move to front)變換是一種可逆變換，也稱為前移編碼

基本介紹

• 中文名：MTF
• 外文名：move to front
• 也稱：前移編碼
• 定義：一種可逆變換

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