在写入编码的过程中,宏观的过程是:以字节形式读取原文件,然后找到
该字节的编码,进而以字节形式写到压缩文件中去。不停的字节读写会给
cpu 带来频繁的中断并且硬盘的磁头来回在磁道扇区中移动,减慢了速度。
而如果以数据块的形式读写则可以有效地利用到 DMA 通讯
1
,减少了 cpu 中
断,并使硬盘磁头连续移动,显著加快了速度。而 c++语言的 iofstream 类的
read()与 write()成员函数为此思想的实现提供了可能。
所以,可以开辟一个 1024K 的缓冲区,先将文件前 1024K 的字节读入内存
缓冲区中(在本设计中,这称为二级缓冲器),编码后的字节也不急于写入
文件中,而是先写到另一个二级缓冲区中,当其足够 1024K 时再以数据块的
形式写到压缩文件中。然后清空缓冲区,继续做下一个 1024K 的编码写入。
而 缓 冲 区 本 身 , 其 实 就 是 二 个 整 形 数 组 , read_buffer[1048576] 和
write_buffer[1048576]。不过这样的数组声明已经太大了,可以用 STL 的
vector 向量类来代替这个数组(vector 结构实际也就是一个封装了的加强型
数组)。
一级缓冲器在微观上解决了写编码速度的问题,而二级缓冲器则在宏观上
改善了写编码的问题,两者关系的嵌套的关系,实际的程序主结构也就是一
个二重循环,外层控制二级缓冲器,内层控制一级缓冲器。
G 一些细节问题
采用以单字节为单位构造哈夫曼树,这样数的规模不会太过庞大,构造
的时间比较快,并且有比较良好的压缩率(详细的压缩报告见附录二)。如
果以双字节构造,则可能出现叶子数为 65536 的哈夫曼树,虽然压缩率可以
得到相对提高,但已经提升不明显,而整个的压缩过程将变的缓慢。如果进
行智能识别频率采样,一方面采样过程又要花费一定的时间,另一方面,哈
夫曼树本身的结构也决定了这样做并不划算,也给解压缩和写入索引带来了
许多麻烦。
用 left[]和 right[]数组来描述一颗二叉树而没有用指针,是为了避免指针
可能带来的由叶子到根的反向建树的麻烦;另一方面,树的节点和叶子数目
基本确定,没太多必要使用灵活的指针和相关的内存分配语句。
编码写出后,内层缓冲器可能剩几个 bit,没有达到 8bit,此时应补‘0’或‘1’
以凑齐 8 位再写出。
文件的大小也不大可能正好被 1024K 整除,要考虑到最后的剩余部分字
节的编码,即要计算好最后的实际字节 读取个数, fstream 的成员函数
gcount()
2
能解决这个问题。
如果把整个压缩过程作为一个函数的话,二级缓冲区的定义最好在函数
外作为全局量定义,否则可能栈溢出。
2.解压缩算法部分
1
戴梅萼 史嘉权《微型计算机技术及应用》第二版 199-201 页
2
王浩 《面向对象程序设计》 第 245 页