你所能用到的无损压缩编码(二）
你所能用到的无损压缩编码(二）
上个月项目荷兰大佬要检查，搞的我想写的东西不断推迟，现在检查完了，我决定继续把我想写的这整个一个系列写完，上一次写的是最简单的无损编码行程编码，这一次我想要写的是算术编码。这种编码的原理就是用一个数来代替一组数，我第一次看这个思想的时候深深的被这些大牛的思维方式所折服，用一个数代替一组数，这其实就是压缩的最基本思想，虽然看起来是那么的遥不可及，但是在这种大的思想的指引下，总能开创出接近于完美的方法，所以我一直觉得一个人敢想，有主意，无论这个主意多么的不靠谱，都是应该的，因为你总能从一定的想法中找到合适的启发，可惜的是，经过这么多年的教育，我经常都感觉自己的思想根本跳不出某一个圈子，很难获得一些个启发。
言归正传，算术编码的原理简单的说就是利用统计概率将一串数字表现出来，完整的算术编码的实现是很复杂的，基本上可以写一篇初级本科毕业论文，所以这里为了说明原理，我删去了一些实现上的细节部分，但是总体原理是完整保存的下来的，下面是wiki连接介绍算术编码的基本原理，太长了，复制了太占篇幅：
http://zh.wikipedia.org/wiki/%E7%AE%97%E6%9C%AF%E7%BC%96%E7%A0%81
简单的说就是所有待压缩的数字根据自己的出线概率在有限长度的数轴上按比例划出自己的地盘，最后得出一个精确值，看看这个值在位于哪两个坐标之间，就说明待压缩的原始数值是几。比如现在待压缩的数值有三个001，那么0出现的概率是0.67,1是0.33，于是在一个长度为1的数轴上分成两个部分，一个是0到0.67，这个部分是0的管辖范围，0.67到1是1的管辖范围。那么在压缩的过程中，依次读入三个数，读到第一个数，是0，应该在0管辖的地盘上选取一个数（如果你只压缩一个数的时候），或者我们将目光投向0的地盘[0,0.67),继续将这个地盘按照0.67:0.33的比例划分成两个部分，依次这样，直到没有要压缩的数，最后一定会得到一个区间，在这区间内选取一个数，这就是无损压缩后的结果。
如果你对计算机编程有初步深入的认识的话，这里你应该意识到一个问题，计算机保存的浮点数精度是有限的，如果大型数据的话，那么最后压缩出来的小数一定要求精度非常高，这个时候计算机本身的浮点数无法表示，这样会导致无损变有损，这时候就需要你自己开发高精度的浮点表示方式，因为这次我只是为了说明算术编码的原理和实现，我用的压缩数据并不大，所以这个细节这次我并没有做。但是这些算法和数据结构和东西我将在下一个系列中说明。
原理差不多了，下面就是实现的部分。算术编码除了压缩，还需要一个统计概率的预处理过程，这里我使用c++ stl库的map来完成这个使命的。代码如下：
1 map<char,double> GetProbability(string fileName)
2 {
3 ifstream fin(fileName.c_str());
4 char input;
5 //vector<int> result;
6 map<char,int> tmp;
7 map <char, int>::iterator iter;
8
9 map <char, double> result;
10
11 int count=0;
12
13 while(!fin.eof())
14 {
15 fin>>input;
16 if(fin.fail())
17 break;
18 count++;
19 iter=tmp.find(input);
20 if(iter==tmp.end()){
21 tmp.insert(map <char,int>::value_type(input,1));
22 }
23 else{
24 ++iter->second;
25 }
26
27 }
28
29
30
31
32 for (iter = tmp.begin(); iter != tmp.end(); iter++ )
33 {
34 //count+=iter->second;
35 result.insert(map <char,double>::value_type(iter->first,iter->second/(double)count));
36 }
37
38
39 fin.close();
40
41 return result;
42 }这里我觉得需要注意的一个小细节就是在文件流这一块,在这个循环之中除了判断文件流有没有读到最后一个字符（fin.eof())之外还加了一个fin.fail(),这是一个很容易被忽略的地方，因为eof（）返回true时是读到文件结束符0xFF，而文件结束符是最后一个字符的下一个字符。所以会造成一个现象是最后一个字符读了两次，这样就导致最后计算出来的概率是不对的。当然这个问题有很多解决办法，比如用file.peek()==EOF,这里采用的是看是否读文件失败，如果失败直接退出。
统计出概率，下面要做的就是算术编码压缩了，其实现代码如下:
1 1 double compress(map<char,double> m,string fileName)
2 2 {
3 3 double result=1.0;
4 4 vector<double> freqs;
5 5 ifstream fin(fileName.c_str());
6 6 char input;
7 7 map <char, double>::iterator iter;
8 8 double pre=0.0;
9 9 freqs.push_back(pre);
10 10
11 11 double w=0.0,begin=0.0,end=1.0,length;
12 12 while(!fin.eof())
13 13 {
14 14 fin>>input;
15 15 if(fin.fail())
16 16 break;
17 17 int value=input-'0';
18 18 w=0;
19 19 int k=0;
20 20 iter=m.begin();
21 21 while (k<value)
22 22 {
23 23 w+=iter->second;
24 24 iter++;
25 25 k++;
26 26 }
27 27 length=end-begin;
28 28 end=begin+length*(w+iter->second);
29 29 begin+=length*w;
30 30
31 31 }
32 32 result=begin*0.01+end*0.99;
33 33 fin.close();
34 34 return result;
35 35
36 36 }原理很简单，就是按照待压缩符号的概率，不停地计算新的区间，最后保存为一个浮点数，再次说明的一点是，如果你需要开发完全的应用，你需要自己写一个数据结构保存该浮点值。
解压缩的原理就是和压缩的代码相反，不停地缩小区间，每次缩小区间都计算出相应的区间的两个端点，然后判断出是哪个信源符号（这里只有两个信源，多个信源可以类推），代码如下：
1 double tmpEnd=1.0;
2 void decompress(int length,double result,map<char,double> m)
3 {
4 double begin=0.0,end=1.0,tmp=0.0;
5 int n=0;
6 double valueLength;
7 map <char, double>::iterator iter;
8 vector<double> probs;
9
10 for (iter = m.begin(); iter != m.end(); iter++ )
11 {
12 //count+=iter->second;
13 probs.push_back(iter->second);
14 // result.insert(map <char,double>::value_type(iter->first,iter->second/(double)count));
15 }
16
17 for(int i=0;i<length;i++)
18 {
19
20 n=0;
21 tmp=0.0;
22 valueLength=end-begin;
23 while(result-begin>tmp*valueLength)
24 {
25 tmp+=probs[n++];
26
27 }
28
29
30 n--;
31 end=begin+tmp*valueLength;
32 if(end==tmpEnd)
33 begin=end-probs[n]*valueLength;
34 // begin=end-probs[n]*valueLength);
35 //cout<<begin<<" "<<end<<endl;
36 tmpEnd=end;
37 cout<<n<<" ";
38 }
39 cout<<endl;
40
41 }我使用的测试文件如下：
里面有15个信源符号，执行程序，得出的结果如下:
第一行是0出现的概率，第二行是1出现的概率，第三行是验证它们加起来等于，第四行是压缩得到的浮点数结果，第五行是解压缩后的数值，可以看到是无损的。
最后，附上测试代码：
1 int _tmain(int argc, _TCHAR* argv[])
2 {
3 string fileName="input.txt";
4 map <char, double>::iterator iter;
5 map<char,double> result=GetProbability(fileName);
6 double sum=0.0;
7 for (iter = result.begin(); iter != result.end(); iter++ )
8 {
9 cout<<iter->first<<" "<<iter->second<<endl;
10 sum+=iter->second;
11 }
12 cout<<sum<<endl;
13 cout<<(sum=compress(result,fileName))<<endl;
14
15 decompress(15,sum,result);//第一个参数待压缩集合长度，第二个参数压缩后的浮点值，第三个参数概率集合
16 int i;
17 cin>>i;
18 return 0;
19 }好了，算术编码写完了，在我的计划中，下一步是要写霍夫曼编码，但是由于要设计的树的结构，我写这全部的文章的目的是让初学者可以通过程序实际实现各种看似枯燥的算法，既然要用到树等数据结构，所以我决定我下一步先把你所能用到的数据结构写完，9，10月我会更新的比较勤快的，也希望各路高手能给我提出意见。