算术编码的实现

霍夫曼编码

概率越低，码长越长。每个符号的编码长度为整数。缺点：概率不为2^(-n)时，编码不优；需要事先知道概率。

算术编码

现在常用的更优的编码方法，它比霍夫曼编码更接近信息熵。

把整个信源序列表示成0-1内的一个区间，其长度等于该序列的概率，在区间内选择一个最小位数的小数作为编码。序列中每个新增元素会缩短区间，当然就需要更多符号。

这种编码中符号的平均码长可以为小数。

在不考虑精度问题时，这个过程是相当简单的。我们只需要用单个字符来更新区间下限L和区间长度R：

L’ = L + R*(S[i]/S) R’=R*(S[i+1]/S – S[i]/S)

这里S[i]/S即单个符号i所划分区间的起始位置。

规整化和再归一化

规整化

为了在有限精度的机器上实现，需要对编码区间取近似值。例如，当使用8位编码，符号abc等概率时，划分为[0, 82/256), [82/256, 164/256), [164/256, 1)。

但划分几次后，这个过程就不能继续进行了。虽然可以使用高精度计算把划分的区间变得很细，但它的计算效率没有应用的意义。

注意到，当区间收窄时，二进制小数的最高位可以逐步确定。这样可以把高位作为编码结果输出，然后按位左移当前数值，就可以在固定字长的寄存器上计算了。这个过程需要再归一化。

再归一化

然而有时编码的最高位一直难以确定。例如上述输入为bbbbbb时，区间一直包括0.5，这样仍会超出机器精度限制。

为此，我们不得不设置一个阈值，当区间范围R小于阈值时，强行将编码的高位输出。这样做的后果是，如果区间真的在0.5上方，左移之后会大于1，也称为进位。因此，我们需要记录下边界L中连续0.01111111…中1的出现长度，如果出现进位，则全部改用0.10000000…填充。

下面代码使用16位整数作为上限，将连续8位一起处理，以提高效率：

如果在更新阶段，发生L>>8 > 0xff时，说明发生溢出，此时标记z=1，buf++，然后删除溢出位。

然后进行重归一化：当剩余区间长度小于1<<8时，我们把尝试把高8位弹出。当高8位为0xff(11111111B)时，说明暂时不可确定，计数器+1。否则先输出进位前面buffer中的内容，然后根据是否进位输出连续的1或者0。

解码

解码过程就相对简单了，我们用一个V表示当前读到的二进制流。如果V小于区间下界L，则说明此处编码时发生了上溢，要把1<<p加回去。其他部分代码和编码时基本相同。

```
void encode(){
```

	FILE *input=fopen(filename.c_str(),"r");

	check(input, "can't find source file");

```
	auto content=new char[1000000];
```

	content[fread(content,1,1000000,input)]=0;

```
	fclose(input);
```
```
	int len=strlen(content)+10; //padding
```
```
	statRange(content,len);
```
```
 
```
```
	//initial
```
```
    uint L = 0, R = 1ull << P;
```

    byte buf = -1, c = 0, z = 0; bool first=1;

    ofstream out(filename+".bin", ios::binary);

```
 
```
```
	for (int i=0;i<len;i++){
```
```
		int ch=content[i];
```
```
		//update
```
```
	    L = L + R * (double)range[ch];
```

	    R = R * (double)(range[ch+1] - range[ch]);

```
	    uint temp = L >> (P - 8);
```
```
	    if (temp > 0xff){ //overflow?
```
```
	        buf++ ;
```
```
	        L -= (1ull << P);
```
```
	        z = 1;
```
```
	    }
```
```
 
```
```
	    //renormalize
```
```
	    while(R < (1 << (P - 8))){
```
```
			temp = L >> (P - 8);
```
```
			if (temp < 0xff){
```

				if (!first) out.put(buf);   //output previous

				for (;c > 0;c--)   // output 0xff or 0x00

```
					if(z == 1)
```
```
						out.put(0);
```
```
					else
```
```
						out.put(0xff);
```
```
				buf = temp; // current buffer
```
```
				first=0;
```
```
			}
```

			else if (temp == 0xff) // can't judge now

```
				c++;
```
```
			R <<= 8;
```

			L = (L << 8) & ((1ull << P) - 1); // left shift , and cut higher positon

```
			z = 0;
```
```
    	}
```
```
	}
```
```
	//out.put(L >> (P - 8)); //last
```
```
	delete[] content;
```

	cout<<"Encode done in "<<filename+".bin"<<endl;

```
}
```
```
void decode(){
```

	FILE *dict=fopen((filename+".dict").c_str(),"r");

```
	check(dict, "can't find dict file");
```

    ifstream in(filename+".bin", ios::binary);

	check(in.is_open(), "can't find binary file");

```
 
```
```
	int count[128];
```

	for (int i=0;i<128;i++) fscanf(dict, "%d", count+i);

```
	fclose(dict);
```

	for (int i=0;i<128;i++) count[i+1]+=count[i];

	for (int i=0;i<128;i++) range[i+1]=(double)count[i]/count[127];

```
 
```
```
	uint L = 0, R = 1ull << P, V=in.get();
```
```
	V=V<<8 | in.get();
```
```
	V=V<<8 | in.get();
```
```
	V=V<<8 | in.get();
```
```
 
```

    ofstream out(string("out_")+filename);

```
 
```
```
	while (!in.eof()){
```
```
		// get symbol
```
```
		if(V < L) // carry bit 
```
```
			V += 1ull << P;
```
```
    	double T = (double)(V - L) / R;
```
```
		int ch;
```
```
		for (int i=0;i<128;i++) 
```

			if(range[i+1]-range[i]>=1e-8 && T>=range[i] && T<range[i+1]){

```
				ch=i; break;
```
```
			}
```
```
		if (ch==0) break;
```
```
		// update
```
```
		out<<(char)ch;
```
```
	    L = L + R * (double)range[ch];
```
```
	    //cout<<R;
```

	    //cout<<' '<<R * (double)(range[ch+1] - range[ch])<<'\n';

	    R = R * (double)(range[ch+1] - range[ch]);

```
	    while(R < (1 << (P - 8))){
```
```
        	R <<= 8;
```

        	L = (L << 8) & ((1ull << P) - 1);

        	V = (V << 8) & ((1ull << P) - 1);

```
    		V |= in.get();
```
```
		}
```
```
	}
```
```
 
```

	cout<<"Decode done in out_"<<filename<<endl;

```
}
```

写的时候遇到一个小坑，把词频用浮点保存会引起精度误差，代码一长就不对了。上面代码编码和解码的浮点运算必须完全一致结果才能对。最好还是全部改用整数运算。

完整代码在https://github.com/fffasttime/cs_misc/blob/master/digitmedia/ArithmeticCoding.cpp

霍夫曼编码

算术编码

规整化和再归一化

规整化

再归一化

解码

发表评论 取消回复

发表评论取消回复