首页 > 代码库 > MTF(Move-to-front transform)数据转换

MTF(Move-to-front transform)数据转换

1.什么是MTF

  MTF(move-to-front)是一种数据编码方式,用于提高数据压缩技术效果。

  在数据压缩算法中,MTF可以作为一个额外的步骤。也就是说 ,可以先进行MTF编码,在进行数据压缩。

2.MTF基本原理

   主要使用的是数据的”空间局部性“,也就是最近出现过的字符很可能在接下来的文本附近再次出现。

  MTF的主要思想是:

    (1)维护一个文本字符集大小的栈,“recently used symbols”(最近访问过的字符),其中每个不同的字符在其中占一个位置,位置从0开始编号。

    (2)扫描需要重新编码的文本数据,对于每个扫描到的字符,使用该字符在“recently used symbols”中的index替换,并将该字符提到“recently used symbols”的栈顶位置(index为0的位置)。

    (3)转到(2),直到文本扫描结束。

  使用MTF,对于许多连续的、相同的字符,将被替换为多个0;最近使用过的字符,会被小的index替换;最近很久没有使用过的字符,会被较大的index替换。MTF完成之后,文本就可以使用一串数字表示,如果文本数据具有较好的空间局部性,这些数字会很小,便于压缩。

3.MTF图解

   (1)先建立字符集大小的栈,“recently used symbols”,这里只考虑26个小写字母a~z。

    recently used symbols:queue=(abcdefghijklmnopqrstuvwxyz)。

  其中字符在栈中的位置表示该字符的index。起初,字符a的index为0,b的index为1,以此类推,z的index为25。

  (2)扫描文本,如”bananaaa“。

    编码如下:

    

  如上,bananaaa经MTF之后变成了list=(1,1,13,1,1,1,0,0)。MTF只可逆的过程,只要记录下转换之前的queue和转换之后的list,就完全可以快速的回复原始文本数据。

  解码如下:

    

4.MTF数据转换的使用

   MTF转换主要是利用空间局部性原理来减少信息熵。因为最近访问的字符总是出现在“recently used symbols”的前面位置,如果字符的空间局部性较好,编码之后就会出现很多小的数字,如”0“或”1“。然而,并不是所有的文本数据,都具有较好的局部相关性。

  一个重要的应用就是基于Burrows–Wheeler transform压缩算法。Burrows-Wheeler transform能将文本转换为局部相关性很好的序列。

  一般压缩可以将文本先使用Burrows–Wheeler transform生成局部相关性很好的序列,再使用MTF减少信息熵,最后再进行压缩。

5.MTF转换代码实例

下面的代码是对文本进行move-to-front数据编码:

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <string>
 4 #include <list>
 5 using namespace std;
 6 
 7 int MTF_transform(const string &text,int* result_MTF,list<char> &mylist){
 8     list<char>::iterator it;
 9     for(int i=0;i<text.size();i++){
10         it=find(mylist.begin(), mylist.end(),text[i]);  ///查找当前字符
11         result_MTF[i]=distance(mylist.begin(),it);  ///保存当前字符在mylist中的索引
12         mylist.erase(it);   ///删除元素
13         mylist.push_front(text[i]); ///把当然元素添加到index为0的位置
14     }
15     return 0;
16 }
17 
18 int main(int argc,char* argv[])
19 {
20     string text = "bananaaa";
21     int *result_MTF = new int[text.size()];
22     list<char> mylist;
23     for(int i=0;i<26;i++){
24         mylist.push_back(a+i);
25     }
26 
27     MTF_transform(text,result_MTF,mylist);
28     for(int i=0;i<text.size();i++){
29         cout<<result_MTF[i]<<" ";
30     }
31     delete [] result_MTF;
32     return  0;
33 }

 

参考:http://en.wikipedia.org/wiki/Move-to-front_transform

额外阅读:http://en.wikipedia.org/wiki/Least_Recently_Used#LRU