## Arithmetic Coding Back

### Arithmetic Coding

• Arithmetic編碼: 是一種比Huffman編碼還要有效的現代編碼
• 浮點數精度需要考慮
• 用比例縮放來解決溢出問題
• 廣泛應用於圖像數據編碼

#### 數據結構

``````weight[4];    //weight[0] for "00", weight[1] for "01"
//weight[2] for "10", weight[3] for "11"
``````

#### 算法實現

``````/* Code */
long double ARITHMETIC_CODING(char* input)
{
long double start = 0;
long double end = 1;
char extract[3];
if (strlen(input) % 2 != 0)
return -1.0;
else
{
char* ch = input;
while (*ch != '\0')
{
extract[0] = *ch++;
extract[1] = *ch++;
extract[2] = '\0';
char* extract_string = extract;
if (!strcmp(extract_string, "11"))
{
start = end - (end - start) * weight[3];
}
else if (!strcmp(extract_string, "10"))
{
long double e = end - (end - start) * weight[3];
long double s = end - (end - start) * (weight[3] + weight[2]);
end = e;
start = s;
}
else if (!strcmp(extract_string, "01"))
{
long double e = end - (end - start) * (weight[3] + weight[2]);
long double s = start + (end - start) * (weight[0]);
end = e;
start = s;
}
else
{    //"00"
end = start + (end - start) * (weight[0]);
}
cout.precision(20);                                        //设置精度，防止损失
printf("start: %.12lf, end: %.12lf\n", start, end);
}
return (start + end) / 2;
}
}
``````