你所能用到的无损压缩编码(二)

     上个月项目荷兰大佬要检查,搞的我想写的东西不断推迟,现在检查完了,我决定继续把我想写的这整个一个系列写完,上一次写的是最简单的无损编码行程编码,这一次我想要写的是算术编码。这种编码的原理就是用一个数来代替一组数,我第一次看这个思想的时候深深的被这些大牛的思维方式所折服,用一个数代替一组数,这其实就是压缩的最基本思想,虽然看起来是那么的遥不可及,但是在这种大的思想的指引下,总能开创出接近于完美的方法,所以我一直觉得一个人敢想,有主意,无论这个主意多么的不靠谱,都是应该的,因为你总能从一定的想法中找到合适的启发,可惜的是,经过这么多年的教育,我经常都感觉自己的思想根本跳不出某一个圈子,很难获得一些个启发。

     言归正传,算术编码的原理简单的说就是利用统计概率将一串数字表现出来,完整的算术编码的实现是很复杂的,基本上可以写一篇初级本科毕业论文,所以这里为了说明原理,我删去了一些实现上的细节部分,但是总体原理是完整保存的下来的,下面是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月我会更新的比较勤快的,也希望各路高手能给我提出意见。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小红豆的数据分析

小蛇学python(17)时间序列的数据处理

不管是在金融学、经济学的社会学科领域,还是生态学、系统神经的自然学科领域,时间序列数据都是一种重要的结构化数据形式。

2135
来自专栏java一日一条

Java 8:HashMap的性能提升

HashMap是一个高效通用的数据结构,它在每一个Java程序中都随处可见。先来介绍些基础知识。你可能也知道,HashMap使用key的hashCode()和e...

822
来自专栏华章科技

令人困惑的TensorFlow!谷歌大脑工程师帮你解决麻烦

导读:虽然对于大多数人来说 TensorFlow 的开发语言是 Python,但它并不是一个标准的 Python 库。这个神经网络框架通过构建「计算图」来运行,...

1753
来自专栏灯塔大数据

解密 | 一文总结学习 Python 的 14 张思维导图

前言 本文主要涵盖了 Python 编程的核心知识(暂不包括标准库及第三方库,后续会发布相应专题的文章)。 首先,按顺序依次展示了以下内容的一系列思维导图:基础...

3597
来自专栏一名叫大蕉的程序员

大数据计数原理1+0=1这你都不会算(二)No.50

上一次我们说完了用 HashSet 来进行计数了。我们可以发现,如果我们估计有N个数,那么我们至少需要N*32bit(按照int在32位操作系统下占用32个bi...

2078
来自专栏owent

PKU POJ 1724 ROADS 解题报告

题目链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=1724

692
来自专栏数据小魔方

IF函数——放松工作,享受生活!

今天跟大家分享一个简单却实用、高效的逻辑函数——IF函数。 ▼ IF函数可以简化很多我们数据处理过程中的重复性操作工作,让我们的工作效率大大提高。今天通过两个例...

3295
来自专栏简书专栏

Python数据科学库-小测验

答:np.arange、np.array、np.ones、np.zeros、np.full

1861
来自专栏潇涧技术专栏

Python Algorithms - C5 Traversal

Traversal就是遍历,主要是对图的遍历,也就是遍历图中的每个节点。对一个节点的遍历有两个阶段,首先是发现(discover),然后是访问(visit)。遍...

981
来自专栏小樱的经验随笔

零基础学并查集算法

并查集是我暑假从高手那里学到的一招,觉得真是太精妙的设计了。以前我无法解决的一类问题竟然可以用如此简单高效的方法搞定。不分享出来真是对不起party了。(pa...

5538

扫码关注云+社区

领取腾讯云代金券