共有回帖数 0 个
- 压缩算法tutorial]-[chapter-2]-概率预测模型与算术编码器
-
只看楼主
收藏
回复
-
我们给大家讲了压缩算法中预测模型与编码器的概念，同时给大家介绍了一个简单的hello_compressor。虽然hello_compressor中预测模型与编码器都有实现，但是这两个简单的核心部件的压缩效率并不高。今天我会给大家介绍更高效的预测模型和编码器，使我们的算法达到更高的压缩效率。
概率预测模型：
在hello_compressor中我们用到的是一个上下文长度为2字节的模型，每次预测时返回可能性最大的字符。这个模型会有一个很大的缺点：当可能性大的字符不止一个时，这个模型常常会顾此失彼，给出不正确的预测。例如在英文文章中，there和three都是很常见的单词，假设一篇文章中th之后出现e和出现r的概率各占50%，在我们的预测模型处理到th时，预测结果是e还是r呢？显然无论结果是哪一个，都会有相当大的出错概率。
为了解决这个问题，我们将预测模型的功能进行拓展，预测时不是给出概率最大的字符，而是给出所有字符的出现概率，让编码器根据这个概率表来对下一个字符进行编码，这就是所谓的概率预测模型（probability model)。
显然我们的hello_compressor中的编码器是不能利用模型给出的概率表进行编码的，适用这种模型的编码器有我们将要讲到的数字编码，还有哈夫曼编码（很著名的算法，不过我们不打算讲它）、香农-范诺编码等。
算术编码：
（本章讲的是简单的基于bit的算术编码器，现在网上的很多算术编码器都是基于byte的，代码有些不同，但算法思想基本一样）
算术编码算法可能比较抽象，我们先从一个实验讲起。
假设我们有一张纸一支笔和尺子，现在要我们记录一个二进制序列10110，我们可以用这样的方法：首先画一条32mm的线段，然后将线段二等分，处理第一个bit位，如果为0，使用左边的0..16的区间，如果为1则使用右边的16..32区间。对于我们的数据10110，显然使用的是右边的16..32区间。然后将这个区间二等分，用同样的方法处里下一个bit位。对于我们的数据10110，每次的区间依次为：
16..32
16..24
20..24
22..24
22..23
最后我们将22cm到23cm涂成黑色，完成整个编码过程。
解码可以用类似的方法完成，同样将32mm的线段分为二等分，如果黑色区间在等分点左边，我们解码出一个bit位0，然后使用左边区间继续解码；黑色区间在等分点右边，我们解码出一个bit位1，然后使用右边区间。这个过程可以一直进行到最后的区间恰好为涂成黑色的区间，我们会发现正好解出了10110这个序列。
有读者可能会猜到了，只要我们有足够精确的尺子，这个方法实际上可以在很小的纸条上记录任意多的bit位，因为“一尺之棰,日取其半,万世不竭”。实际上也是如此，所以我们也可以说：“给我纸笔尺子，我就能记录整个宇宙的数据！”
现在我们将这个方法用程序实现，一个最大的问题是在计算机中数据都是离散的0和1，即使是浮点类型也会有有限的精度。也就是说在计算机中并不能完成“无限细分”，到最后我们的区间会退化到一个点上，不能再等分下去。
一个解决方法是将数据分段，当区前退化到一个点上时我们就将这个点保存起来，然后重新开辟一个新区间对后面的数据进行处理。这个方法写成代码如下（我们的用区间长度是0..65535）：
void encode()
{
unsigned short hi_val = 65535;
unsigned short lo_val = 0;
int i;
int next_char;
while((next_char = getchar()) != EOF)
{
for(i = 0; i 8; i++)
{
// encode a bit
if(1 & (next_char i))
{
// bit 1
lo_val = lo_val / 2 + hi_val / 2 + 1;
}
else
{
// bit 0
hi_val = lo_val / 2 + hi_val / 2;
}
// the range can no longer split in two, output it and use a new one
if(hi_val == lo_val)
{
putchar(hi_val / 256);
putchar(hi_val % 256);
lo_val = 0;
hi_val = 65535;
}
}
}
// the last range stores the ending few bytes, output it
putchar(hi_val / 256);
putchar(hi_val % 256);
return;
}
这个方法能不能压缩数据呢，通过上一章的知识我们知道，这个算法没有对输入进行任何预测，显然是不能进行压缩的。实际上我们的16位长度的区间在处理16个bit之后就退化成一个点，而保存这个点恰好需要16位。
现在我们开始讲数字编码，在hello_compressor中我们有这样一个做法，对于出现概率高的字符，我们用短的编码来表示它。数字编码的算法和上面提到的方法大体相同，只不过不再是等分区间，而是按0和1出现的概率去划分，例如0和1的概率分别是25%和75%，那么对于0..16这个区间，它个两个字区间分别是0..4和4..16。这样做一个直观的效果是对于概率大的bit，区间划分后得到的还是一个比较大的子区间，使得原本只能处理16个bit的区间现在能够处理更多的bit。
这里给出具体的区间变换公式（假设原区间为a..b，0和1的概率分别为p和1-p）：
左边区间： a..[(b - a) * p]
右边区间： [(b - a) * p + 1]..b
使用这两个公式替换掉上面代码中的等分区间部分，就得到了算术编码的算法，下面我们给出一个完整的算术编码的源代码，里面世包含了一个上下文长度为3字节的0-1概率预测模型：
（为了代码编写方便，我将计算区间的代码放在了预测模型中，也就是说现在的预测模型功能是：输入区间的上下边界，模型根据预测计算出区间的划分点）
#include stdio.h
#include stdlib.h
#include string.h
// # prediction model
// #############################################################################
typedef struct model_type_struct
{
unsigned char* m_count[2];
unsigned int m_context;
} model_type;
void model_init(model_type* model)
{
model-m_count[0] = malloc(sizeof(unsigned char) * (1 24));
model-m_count[1] = malloc(sizeof(unsigned char) * (1 24));
memset(model-m_count[0], 0, sizeof(unsigned char) * (1 24));
memset(model-m_count[1], 0, sizeof(unsigned char) * (1 24));
return;
}
void model_destroy(model_type* model)
{
free(model-m_count[0]);
free(model-m_count[1]);
return;
}
unsigned short model_predict(model_type* model, unsigned short lo_val, unsigned short hi_val)
{
unsigned char count[2] =
{
1 + model-m_count[0][model-m_context % (1 24)],
1 + model-m_count[1][model-m_context % (1 24)],
};
return lo_val + (hi_val - lo_val) * count[0] / (count[0] + count[1]);
}
void model_update(model_type* model, int bit)
{
if((model-m_count[bit][model-m_context % (1 24)] += 1) = 255)
{
// avoid overflow
model-m_count[0][model-m_context % (1 24)] /= 2;
model-m_count[1][model-m_context % (1 24)] /= 2;
}
model-m_context = model-m_context * 2 + bit;
return;
}
// # coder
// #############################################################################
void arithmetic_encode(model_type* model)
{
unsigned short hi_val = 65535;
unsigned short lo_val = 0;
int i;
int next_char;
while((next_char = getchar()) != EOF)
{
for(i = 0; i 8; i++)
{
// encode a bit
if(1 & (next_char i))
{
lo_val = model_predict(model, lo_val, hi_val) + 1;
model_update(model, 1);
}
else
{
hi_val = model_predict(model, lo_val, hi_val);
model_update(model, 0);
}
// the range can no longer split in two, output it and use a new one
if(hi_val == lo_val)
{
putchar(hi_val / 256);
putchar(hi_val % 256);
lo_val = 0;
hi_val = 65535;
}
}
}
// the last range stores the ending few bytes, output it
putchar(hi_val / 256);
putchar(hi_val % 256);
return;
}
void arithmetic_decode(model_type* model)
{
unsigned short hi_val = 0;
unsigned short lo_val = 0;
unsigned short val = 0;
unsigned short mid;
int output_char = 0;
int output_bit_pos = 0;
while(!feof(stdin))
{
// process next range
if(hi_val == lo_val)
{
val = (val * 256) + getchar();
val = (val * 256) + getchar();
lo_val = 0;
hi_val = 65535;
}
// decode a bit
mid = model_predict(model, lo_val, hi_val);
if(val mid)
{
output_char |= (1 (output_bit_pos++));
model_update(model, 1);
lo_val = mid + 1;
}
else
{
output_char &= ~(1 (output_bit_pos++));
model_update(model, 0);
hi_val = mid;
}
if(output_bit_pos == 8)
{
putchar(output_char);
output_bit_pos = 0;
}
}
return;
}
// # main
// #############################################################################
int main(int argc, char** argv)
{
static char stdin_buffer[4096];
static char stdout_buffer[4096];
static model_type model;
setbuffer(stdin, stdin_buffer, sizeof(stdin_buffer));
setbuffer(stdout, stdout_buffer, sizeof(stdout_buffer));
if(argc == 2 && strcmp(argv[1], "encode") == 0)
{
model_init(&model);
arithmetic_encode(&model);
model_destroy(&model);
}
else if(argc == 2 && strcmp(argv[1], "decode") == 0)
{
model_init(&model);
arithmetic_decode(&model);
model_destroy(&model);
}
else
{
fputs("argument: (encode|decode) in.file out.file", stderr);
}
return 0;
}
用这个程序压缩EGE的graphics.cpp文件，可以压缩到65.4KB，压缩率为29.7%，比上一章的hello_compressor提高了不少。
编码器的优化：
上面代码主要还是为了让大家理解算术编码，实际上还有优化的空间。最明显的是在计算划分点时由于整数舍入造成划分的误差，当区间很大时这个误差仅为几万分之一，基本不会对压缩率造成影响，但当区间很小时误差就不能忽略了，一个极端的例子是对于长度为2的区间如1..2，无论输入概率是多少，它的两个子区间都是按50%来算的1..1和2..2。这对压缩效率造成了很大的损失。
现在我给出一个优化过的编码器，它的主要变化是：不再是将一个区间分划至退化为点的时候输出，而是分划到16位的前8位相同时就输出前8位，然后对整个区间进行一个比例扩大的操作。
// # coder
// #############################################################################
void arithmetic_encode(model_type* model)
{
unsigned short hi_val = 65535;
unsigned short lo_val = 0;
int i;
int next_char;
while((next_char = getchar()) != EOF)
{
for(i = 0; i 8; i++)
{
if(1 & (next_char i))
{
lo_val = model_predict(model, lo_val, hi_val) + 1;
model_update(model, 1);
}
else
{
hi_val = model_predict(model, lo_val, hi_val);
model_update(model, 0);
}
while(hi_val / 256 == lo_val / 256)
{
putchar(hi_val / 256);
lo_val = (lo_val * 256);
hi_val = (hi_val * 256) + 255;
}
}
}
putchar(hi_val / 256);
putchar(hi_val % 256);
return;
}
void arithmetic_decode(model_type* model)
{
unsigned short hi_val = 0;
unsigned short lo_val = 0;
unsigned short val = 0;
unsigned short mid;
int output_char = 0;
int output_bit_pos = 0;
while(!feof(stdin))
{
while(hi_val / 256 == lo_val / 256)
{
val = (val * 256) + getchar();
lo_val = (lo_val * 256);
hi_val = (hi_val * 256) + 255;
}
// decode a bit
mid = model_predict(model, lo_val, hi_val);
if(val mid)
{
output_char |= (1 (output_bit_pos++));
model_update(model, 1);
lo_val = mid + 1;
}
else
{
output_char &= ~(1 (output_bit_pos++));
model_update(model, 0);
hi_val = mid;
}
if(output_bit_pos == 8)
{
putchar(output_char);
output_bit_pos = 0;
}
}
return;
}
这个改进算法将EGE的graphics.cpp压缩至60.8KB，压缩率为27.6%。顺便说一下，网络上能找到的0-1算术编码基本上都是这个算法。算术编码算法是有专利权的，不过我认为这个专利权完全无效，因为在算术编码发明之前就已经有一个无专利限制的区间编码，算法思想和算术编码很相似（其实我认为两者是同一个算法的不同叙述方式）。
这里也想说一下，算术编码器已经是一个很成就的算法模型，基本不会有什么大的变动。所以即使你实在看不懂算术编码的代码也没关系，只要知道它大概的思想，会使用这份代码就行了，下一章我们会讲一下预测模型的优化，达到更高的压缩率，到时候就只给出prediction model的代码，这个编码器的代码就不打算再列出来。
PS: 有些朋友提到我的示范代码不能在Windows中编码运行，主要是因为我用到了一个linux下的setbuffer函数，Windows用户将它用setvbuf替换掉即可（参数要改一下）。此外由于Windows的文件打开模式区分为文本模式和二进制模式，所以要用示范代码处理二进制数据，请在代码中加上：
...
#include io.h
int main(...)
{
/* variant definition */
...
_setmode(_fileno(stdin), _O_BINARY);
_setmode(_fileno(stdout), _O_BINARY);
...
}
楼主 2015-11-19 21:04 回复
Copyright © 2010~2015 直线网 版权所有,All Rights Reserved.沪ICP备10039589号
意见反馈 |
关于直线 |
版权声明 |
会员须知
