|
参考链接：
https://segmentfault.com/a/1190000011561822
https://www.cnblogs.com/xubenben/p/3426646.html
http://www.echojb.com/linux-unix/2016/08/17/187428.html
算数编码是熵编码的一种，是基于数据中字符出现的概率，给不同字符以不同的编码。
编码过程：将字符映射到 [0,1) 的区间的一个数。
直接贴代码：
#include
#include
#include
char inStr[100], chSet[20]; //输入字符串和字符集
float P[20]; //每个字符的概率
float pZone[20]; //概率区间
int strLen; //输入字符串长度
int chNum; //字符集中字符个数
int binary[100];
float infoLen; //信息量大小
void compress(); //编码函数
void uncompress(); //解码函数
int main()
{
int i,j;
printf("input the length of char set:\n");
scanf("%d", &chNum);
getchar();
printf("input the char and its p\n");
for (i=0; i < chNum; i++) {
printf("input char: ");
scanf("%c", &chSet[i]);
getchar();
//printf("sssss%c ", chSet[i]);
printf("\ninput its p: ");
scanf("%f",&P[i]);
getchar();
printf("\n");
}
/*********** test ************
for (i = 0; i < chNum; ++i)
printf("%c%f\n", chSet[i], P[i]);
*/
/************ 计算概率区间 **************/
pZone[0] = 0;
for (i=1; i < chNum; ++i)
pZone[i] = pZone[i-1] + P[i-1];
printf("input the string \n");
gets(inStr);
strLen = strlen(inStr);
/************* test ***************/
printf("the string is: \n");
puts(inStr);
printf("*********** compress **************\n");
compress();
printf("\n*********** uncompress **************\n");
uncompress();
return 0;
}
void compress()
{
float low = 0, high = 1;
float L, H, zlen = 1;
float cp; //输入字符的概率
float result; //结果
int i, j;
for (i=0; i < strLen; i++) {
for (j=0; j < chNum; j++) {
if (inStr[i] == chSet[j]) {
//cp = P[j];
//L = pZone[j];
low = low + zlen * pZone[j];
zlen *= P[j];
break;
}
}
//low = low + zlen * L;
//zlen *= cp;
}
result = low;
printf("the result is %f\n", result);
infoLen = log(1/zlen) / log(2); //计算香农信息量
if(infoLen > (int)infoLen)
infoLen = (int)infoLen + 1;
else
infoLen = (int)infoLen;
/********** 转二进制 *************/
for (i=0; i < infoLen; i++) {
result *= 2;
if (result > 1) {
result = result - 1;
binary[i] = 1;
} else if (result < 1) {
binary[i] = 0;
} else {
break;
}
}
if (i >= infoLen) {
for (j=i; j >= 1; j--) {
binary[j-1] = (binary[j-1]+1)%2;
if (binary[j-1] == 1)
break;
}
}
printf("****************** the compress result*****************\n");
for (j=0; j < i; j++)
printf("%d ", binary[j]);
}
void uncompress()
{
int i,j;
float w = 0.5;
float deResult=0;
float newLow,newLen;
float low=0,zlen=1;
/*************** binary to ten *******************/
for (i=0; i < infoLen; i++) {
deResult += w*binary[i];
w *= 0.5;
}
printf("uncompress to ten:%f\n", deResult);
printf("uncompress result:\n");
for (i=0; i < strLen; i++) {
for (j=chNum; j > 0; j--) {
newLow = low;
newLen = zlen;
newLow += newLen * pZone[j-1];
newLen *= P[j-1];
if (deResult >= newLow) {
low=newLow;
zlen=newLen;
printf("%c ",chSet[j-1]);
break;
}
}
}
}
|