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;
    }
}