标题: 字典算法 [打印本页]

---

作者: 51黑tt    时间: 2016-3-5 17:36
标题: 字典算法
最近写了一个文件压缩程序，采用的是字典压缩算法中的一种。
首先介绍一下我的字典压缩算法：
    字典压缩算法就是用尽可以短(占用的二进制bit 位)的标记数据，代替尽可能长的 原始文件数据,从而达到压缩的效果。
总的来说,字典压缩算法 可以理解为 一个压缩机。 一头输入(从源文件中读取数据）要压缩的数据，另一头输出(输入到压缩文件)或不输出。
与赫夫曼算法比较可知采用服 这种算法 内存中不须要滞留 太多原始数据，这里说的不须要滞留原始数据指的是不须要 先将要压缩的全部数据读入内存。因为这种算法不须要对整个文件数据进行统计。
当然完全不要滞留是不可能的。这里要滞留的仅仅是字典。

首先我们明白    字典里装的是什么     prefix (前缀)   和  suffix (后缀) .    例如:  index :1  content:  preffix : a   suffix : b  ;   
前缀可以是原始数据也可以是原始数据的标记,我们知道对于任可数据都是由二进制0或1组成的。所有我们在一次读一个byte后得到的原始数据的范围在0到255之间。 之所以能够达到压缩的效果是因为
我们可以用0到255范围外的数来代替很多个原始byte 原始数据重复数据越多压缩效果就越好。这很好理解，然而关键就是怎么才能做到用0到255范围外的数据代替原来的数据呢。所以这里我们就要扩展
数据位了。也就是说原来8个bit表示的数据现在我们要用9个bit来表示.最高位我们让他为0，因为9位能表示的范围达到了0到511。当然我们也可能要扩展到十二位来表示一个数据单元.这就取决于我们
的字典造多大。按理来说字典构造得越大达到的压缩效果是越好。但是这样程序的复杂度也将增加。我采用的字典最大index 为4095,达到最大index后重新构造字典 也就是十二个bit所能表示的范围。
然而还有一个关键的问题就是我们解压的时候怎么知道我们现在一次要读多少个bit位，字典index 达到最大值后，怎么知道要重构字典呢。所以我们还得加上6个数据扩展标记位(bit位有变时标记)，和一个字典重构标记。
达到扩展数据位的方法就是位运算。所以字典压缩和 解压程序整个就是位运算.
下面就说压缩算法:
先来一个例子，便于理解算法

input   index    prefix   suffix    string    outPut
A                      A     
B       263         A        B              AB         A

A       264         B        A             BA         B
B                 
A       265        263       A           ABA        263
B      
A            
B       266        265      B            ABAB       265
B       267         B        B             BB         B
B      
A       268      267       A             BBA         267
B      
A
B
A      269       266      A          ABABA       266
A      270       A          A            AA           A
C      271       A          C            AC           A
D      272       C          D            CD           C
A      273       D          A            DA           D
C
D      274      271       D          ACD          271
A
D      275      273       D          DAD          273   
C      276       D          C          DC            D
A      277       C           A          CA            C
B
A
A     278      265       A          ABAA          265
A
B     279      270       B          AAB            270
A
B     280      264       B          BAB            264
                                                               B
原始数据占用bit位数:
32*8=256      
压缩后数据占用bit位数:
18*9=162
显然 162<256 原始数据被压缩了。
以C语言为例 字典数据结构为：
struct 标号｛
               word       前缀；
               word      后缀；
｝;
结构数组为：
标号标号组[4095]；
压缩算法如下：

int   当前最大标号＝263；
word 前缀，后缀；
char输入流［x］；
int 输入序号＝0
然后，我们读入第一个字符 A和第二个字符B 。
前缀＝输入流［输入序号］；
输入序号＋＋；
从这里开始，我们开始压缩过程，直到把数据处理玩：
int I=263;
for(输入序号 ; 输入序号<X ; 输入序号++){
              后缀＝输入流［输入序号］；
              //查找当前串在表中的位置
              bool found=false;
              while ( I<当前最大标号 ) {
                     if ( 前缀 != 标号组［I］。前缀) ｛I＋＋；continue;｝
                     if( 后缀 != 标号组［I］。后缀 ) ｛I＋＋；continue;｝
                  
                    //找到了，就是这个串
                     found=true;
                     前缀＝I；      //把当前串规约到标号
                     I＋＋；
                     break;
              ｝
              if ( ! found ) {                     //没找到，把这个串加到标号组中
                     标号组［当前最大标号］。前缀＝前缀；
                     标号组［当前最大标号］。后缀＝后缀；
                     当前最大标号＋＋；
                     
                     输出 前缀
                    
                     前缀＝后缀；
                     if （当前最大标号> 4095）{           //已经超过了最大的长度
                            当前最大标号＝263；
                           
                       输出字典重构 标志；
                           
                     ｝
                     I=263;
              ｝
｝



解压是压缩的逆过程:
如图

input   index    prefix   suffix    stack    outPut
A                       A
B       263          A         B                         A
  
263    264       B          A                          B

265    265       263      A           AB           AB
B        266       265      B           ABA         ABA
267    267       B          B                           B
266    268      267      A            BB           BB
A        269        266     A           ABAB       ABAB
A        270        A         A                          A
C        271        A         C                          A
D        272        C        D                           C
271    273      D          A                           D  
273    274      271      D           AC            AC
D       275        273      D          DA            DA

C        276        D        C                           D
265    277      C          A                           C
270    278      265      A            ABA          ABA      
264    279      270      B            AA            AA
B        280        264     B           BA            BA   
                                                
                                                                B

解压算法如下：
int   当前标号＝263；
栈 stack;
int  前缀，后缀；
int 输入流［x］；
int 输入序号＝0
前缀＝输入流［输入序号］；
输入流序号++；

for(输入序号 ; 输入序号<X ; 输入序号++){
  
   
标号组[当前标号]。前缀=前缀；
   
   后缀=输入流[输入流序号]；
   
  //确定当前后缀
   if(当前后缀<256){
标号组[当前标号]。后缀=后缀；
   当前标号++；
}else {

后缀=标号组[后缀]。前缀；

while(后缀>255){

后缀=标号组[后缀]。前缀；
}
//在字典中找到了原始数据前缀
   标号组[当前标号]。后缀=后缀；
    当前标号++；
}
//确定前缀并输出
   if(前缀<256){
   
    输出 (char)前缀；
} else{ /*前缀不是原始数据*/

              push(标号组[前缀].后缀);//字典中序号为当前前缀的，结构体后缀入栈
               if((标号组[前缀].前缀)<256){ //字典中序号为当前前缀的，结构体前缀为原始数据,则入栈
               push(标号[前缀].前缀);   // 入栈

               }else{
                       前缀=标号组[前缀].前缀;
                      while(前缀>256){/*字典中序号为当前前缀的，结构体前缀为原始数据的标记*/
                          push(标号组[前缀].后缀）;//后缀入栈
                           前缀=标号组[前缀].前缀;改变当前前缀

                       }

                       
               //字典中找到了序号为当前前缀的，结构体前缀为原始数据
                       push(前缀)//前缀入栈
                while(stack不空){
                  
                  输出(pop());
                  }
               }
  
           前缀=输入流[输入流序号]；
}

---

欢迎光临 (http://www.51hei.com/bbs/)

Powered by Discuz! X3.1