python 实现的范式huffman压缩，解压缩

程序仅为自己学习之用。关于范式huffman的介绍http://blog.pfan.cn/lingdlz/36436.html

前面写了huffman压缩，解压缩的程序

http://www.cnblogs.com/rocketfan/archive/2009/09/12/1565610.html

程序改写了一下，加入了范式huffman压缩，解压缩。

实现

在设计上利用compressor.py,decompressor.py定义两个框架类给出压缩，解压缩的框架流程，huffman和范式huffman继承这两个框架，并给出不同的实现，同时范式huffman的压缩会复用一部分huffman压缩的函数实现。

利用list，和索引，实现合并分组，来模拟二叉树的建立，并未实际建立二叉树，来计算每个字符对应的encoding应该有的长度，也即叶子深度(等同与huffman编码的长度)。

具体就是每次在优先对列中选择两个权重最小的节点，然后将两个节点所对应的叶子组里面的所有叶子（字符）的深度加1，再将合并后的节点放入队列（权重相加，同时合并两个叶子分组为一组)。

注意由于建立二叉树的时候选择最小的两个节点时可能会有多个相同的最小节点供选择，所以huffman编码并不唯一。

得到每个字符的encoding的长度后，具体encode的时候从encoding length从小到大排序，进行编码。也即频率大的字符先编码，加入最小的encoding length为3

则第一个编码为000，

和http://blog.pfan.cn/lingdlz/36436.html中介绍的实现唯一的不同是没有记录所有encoding length，对应的第一个encoding而是记录最后一个，这样实现更方便些。如length  

3, 3, 5, 5, 6 ,6 ,6 ,6 分别记录红色位置对应的encoding。

3   000

3   001

5   01000

5   01001

6   010100

6   010101

6   010110

6   010111

这样编码的好处是，从000到010111按照字典序，字符串比较是从小到大的。

同时考虑 000 = 0      001 = 1      01000 =  8       01001 = 9        010100 = 20....  010111 = 23 即编码对应的int值也是从小到大的。

这里一个方案是记录编码信息A（3，1），（5，9），（6，23），注意由于编码可能有比较长的如19位，则不能一个byte存储数值，具体实现的时候还是存储成

B (3, 001), (5, 01001),(6, 010111)，解码的时候在恢复出A的形式。

下面是最基本的一个范式huffman解码方法，每次读1byte判断解码

 1         num = 0
 2         length = -1 #the actual encoding length - 1
 3         while 1:
 4             c = self.infile.read(1) 
 5             if c == '':
 6                break
 7             li = huffman.convert(c)    #'a',asc 97,返回 一个list 内容是97对应的各个二进制数字
 8             for x in li:
 9                 num = (num << 1) + int(x)    #TODO num = (num << 1) & int(x) quick??
                 length += 1
                 if(num <= self.decoder.last_list[length]):
                     index = self.decoder.index_list[length] - (self.decoder.last_list[length] - num)
                     self.outfile.write(self.decoder.key_list[index])  #OK we decode one character
                     num = 0
                     length = -1

正确性

压缩率和huffman压缩一样（显然的：）），无论采用那种压缩，最后解压缩后得到的文本和原文本如有不同，是因为原文本最后有多余的换行符，

python读文件的时候会忽略最后多余的换行符号。

速度

速度上，当前的实现两种压缩差不多。不过都慢的很，呵呵，压缩一个24M的文本，得到13M的文本用时1分多，解压缩要4分多。

TODO1.  对于范式huffman解压缩来说，可以考虑在算法层次上的，解压缩优化，包括查表等方法，可参考http://blog.csdn.net/Goncely/archive/2006/03/09/619725.aspx

TODO2.  具体分析程序速度瓶颈，那些地方影响了速度，是读写文件慢还是其它的地方包括读写后的转换。能否利用将核心地方C预言书实现或者参                     

              考http://syue.com/Programming/Procedures/Python/73952.html提高程序速度。

TODO3.  有无现成的python压缩解压缩程序参考，总觉得输入，输出的处理有些繁琐可能影响速度。

TODO4.  参考学习gzip的实现，LZ..算法的实现。

TODO5.   改用c++实现，看速度差异。

TODO6.   考虑分词，用词word作为编码解码的单元，而不是现在的字符character(byte)，对比速度和压缩率。用词做编码单元会使得要编码的符号数目更多，更能体现

               范式huffman的优点。

当前程序

/Files/rocketfan/glzip.rar

def usage():

    """glzip 1.txt                      #will compress 1.txt to 1.txt.crs using huffman method

        glzip -d 1.txt.crs             #will decompress 1.txt.crs to 1.txt.crs.de 

        glzip -c 1.txt                   #will cocompress 1.txt to 1.txt.crs2  using canonical huffman method

        glzip -d -c  1.txt.crs2      #will decompress 1.txt.crs2 to 1.txt.crs2.de  using canonical huffman method

    """

程序的性能分析：

首先分析采用普通的huffman方法压缩文件，初步判断，IO是程序瓶颈，按照一次读文件一个byte，一次写文件写一个byte的方法，读写大文件极其耗时。

考虑下面的代码，一次读一个byte，读完整个文件，对于一个24M的文件，利用cProfile在我的vmware,ubutu系统运行：

 time python -m cProfile ../glzip.py caesar-polo-esau.txt > 2.log

 def readFile(self):
     self.infile.seek(0)
     while 1:
         c = self.infile.read(1) 
         if c == '':
             break     

ompressing,huffman,encode character(byte)

Compressing caesar-polo-esau.txt result is caesar-polo-esau.txt.crs

         24292439 function calls in 59.029 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)

  1   31.151   31.151   59.018   59.018 compressor.py:16(readFile)

耗时1分钟。

对于完整的huffman压缩程序的其流程如下，调用huffman.Compressor.compress()

   def compress(self):
         self.caculateFrequence()
         self.genEncode()
         self.__writeCompressedFile()        
 
  def __writeCompressedFile(self):
         self.outfile.seek(0)
         self.writeEncodeInfo()
         self.encodeFile()

可以看出，程序的时间几乎全部花费在caculateFrequence()和encodeFile()上，分别对应读文件计算字符使用频率，和编码写文件。

caculateFrequence() 会读一遍输入文件，encodeFile()会再读一遍输入文件，并编码写入输出文件。

$./time python -m cProfile -s time ../glzip.py caesar-polo-esau.txt > 1.log

compressing,huffman,encode character(byte)

Compressing caesar-polo-esau.txt result is caesar-polo-esau.txt.crs

         74845611 function calls (74845219 primitive calls) in 263.437 CPU seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)

        1  117.427  117.427  192.423  192.423 huffman.py:124(encodeFile)

 48584258   59.195    0.000   59.195    0.000 {method 'read' of 'file' objects}

        1   43.486   43.486   70.979   70.979 huffman.py:77(caculateFrequence)

 13127563   28.971    0.000   28.971    0.000 {method 'write' of 'file' objects}

对比下仅仅执行读写相同文件的函数的运行时间，仅仅执行下面的readFile和writeFile，显然99%的时间花在了IO代价上。

 1     def readFile(self):
 2         self.infile.seek(0)
 3         self.byteSum = 0
 4         while 1:
 5             c = self.infile.read(1) 
 6             self.byteSum += 1
 7             if c == '':
 8                 break    
 9     def writeFile(self):
         self.outfile.seek(0)
         c = 'a'
         for i in range(self.byteSum):
             self.outfile.write(c)

compressing,huffman,encode character(byte)

Compressing caesar-polo-esau.txt result is caesar-polo-esau.txt.crs

         48584571 function calls in 150.294 CPU seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)

 24292129   50.546    0.000   50.546    0.000 {method 'write' of 'file' objects}

        1   37.005   37.005   65.026   65.026 compressor.py:16(readFile)

        1   33.557   33.557   85.248   85.248 compressor.py:24(writeFile)

 24292129   28.022    0.000   28.022    0.000 {method 'read' of 'file' objects}

显然第一个需要优化的地方是文件的读写，一次读写1byte会带来大量的read,write，影响效率。

需要加入缓冲机制，先读入缓冲区在处理，在http://blog.csdn.net/dwbclz/archive/2006/04/06/653294.aspx提到1.使用小块的读写缓存，经测试，缓存大小在32K~64K之间效果比较好。

我测试了一下对于读，一次read(100)和一次read(1000)对于同样的24M的文件，耗时分别变为0.326，0.031，显然是线性的。