最近写了一个文件压缩程序，采用的是字典压缩算法中的一种。
首先介绍一下我的字典压缩算法：
字典压缩算法就是用尽可以短(占用的二进制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());
}
}
前缀=输入流[输入流序号]；
}
|
QQ好友和群
QQ空间
腾讯微博
腾讯朋友
收藏
淘帖
顶
踩
