算术编码

详情请看https://segmentfault.com/a/1190000011561822

简单来说，算术编码就是计算每个可能出现的字符的概率区间，然后根据每次出现的字符计算概率区间的上下限。简单来说，首先判断当前概率区间的长度，这个长度为每次的长度乘当前字符的出现的概率。计算出这个长度后，再加上上一次的概率区间下限以及当前概率区间的长度乘以该字母的概率区间的下限。反复计算最后得到一个数字，这个数字我们取为当前的编码值。

然后解码的话，直接就是将上面的过程反过来。每次先判断当前述职在哪个区间，判断出这个区间所代表的字母，然后用这个数值减去当前字母的概率区间的下限，然后再除以当前概率区间的长度。这个结果就是下一次计算的数值。

#include <iostream>

#include <string>



using namespace std;



long double chances[26] = {0.0788, 0.0156, 0.0268, 0.0389, 0.1268, 0.0256, 0.0187, 0.0573, 0.0707, 0.0010, 0.0060, 0.0394, 0.0244, 0.0706, 0.0776, 0.0186, 0.0009, 0.0594, 0.0634, 0.0978, 0.0280, 0.0102, 0.0214, 0.0016, 0.0202, 0.0006};

//chances of 26 characters.

long double low_band[26] = {0};



int main()

{

    for (int i = 1; i < 26; ++i)

    {

        low_band[i] = low_band[i - 1] + chances[i - 1];

    }

    string letters;



    cout << "please input your letters: ";

    cin >> letters;



    int len = letters.length();

    long double low = 0, l = 1.0003;



    for (int i = 0; i < len; ++i)

    {

        int index = letters[i] - 'a';

        low = low + l * low_band[index];

        l *= chances[index];

    }



    cout << "encoded letters: " << low << endl;



    letters.clear();



    int times = 0;



    while (times++ < len)

    {

        int i = 0;

        while (i < 26 && low_band[++i] <= low)

        {

        };

        letters.push_back('a' + i - 1);

        low = (low - low_band[i - 1]) / chances[i - 1];

    }



    cout << "decoded letters: " << letters << endl;



    return 0;

}

但是现在有个问题，就是我们用来储存我们计算数值的这个变量最长也就是long double，但是这个long double还是精度不够，所以现在最多只能编码解码只有三位的字符串。要是解决这个问题倒是可以用链表实现大数的计算，但是这个目前还没想好咋写，有思路了再说。