压缩算法之算术编码

    前几天，我们在课堂上学习数字媒体技术的时候，学习了音频压缩算法。针对音频我们有无损和有损

    今天我们来研究一下无损压缩，一般来说，采取的无损压缩算法都是熵编码算法（即在编码过程中按熵原理不丢失任何信息的编码），主要的无损压缩编码有以下几种：

• 香农范诺（Shannon）编码
• 霍夫曼（Huffman）编码
• 算术编码（arithmeticcoding)

    以上的三种算法中，前两种我先找机会说（老师在课上给我们讲过原理，没讲过代码实现，但是把第三种作为作业，，，尴尬），今天我们主要目光是聚焦在第三种上，即算术编码的原理及其代码实现

    好，那么我们言归正传，来将这个算术编码一探究竟——

一、算术编码的历史

    （以下的这一段落copy自csdn）

    早在1948年，香农就提出将信源符号依其出现的概率降序排序，用符号序列累计概率的二进值作为对芯源的编码，并从理论上论证了它的优越性。1960年， Peter Elias发现无需排序，只要编、解码端使用相同的符号顺序即可，提出了算术编码的概念。Elias没有公布他的发现，因为他知道算术编码在数学上虽然成 立，但不可能在实际中实现。1976年，R. Pasco和J. Rissanen分别用定长的寄存器实现了有限精度的算术编码。1979年Rissanen和G. G. Langdon一起将算术编码系统化，并于1981年实现了二进制编码。1987年Witten等人发表了一个实用的算术编码程序，即CACM87（后用 于ITU-T的H.263视频压缩标准）。同期，IBM公司发表了著名的Q-编码器（后用于JPEG和JBIG图像压缩标准）。从此，算术编码迅速得到了广泛的注意。

二、算术编码的原理

  A、编码

    算术编码的基本原理是将编码的消息表示成实数0和1之间的一个间隔（Interval），消息越长，编码表示它的间隔就越小，表示这一间隔所需的二进制位就越多。

    （一）步骤

    这样说起来可能有点抽象，说的好理解一点实际上就是

1. 首先的准备工作——按照各信源信号好出现的频率，将[0, 1)这个区间分成若干段，那么每个信号源就会有自己对应的区间了；
2. 将[0, 1)这个区间设置为初始间隔；
3. 然后编码过程就是，按照待处理的信号，一个一个信号源读入，每读入一个信号，就将该信号源在[0, 1)上的范围等比例的缩小到最新得到的间隔中。
4. 然后依次迭代，不断重复进行步骤3，直到最后信号中的信源信号全部读完为止；
   
   

    （二）伪代码

    该过程编码的伪代码如下：

    set lowLevel = 0
    set highLevel = 1
    input symbol 
    do 
        delta = highLevel - lowLevel
        lowLevel = lowLevel + delta * symbol[i].lowLevel
        highLevel = highLevl + delta * symbol[i].highLevel
    while symbol traversed
    output lowLevel

   （三）例题

    可能还是会有点抽象，有点不好理解，那么我们看一个实例（实例同样来自csdn），通过实例来对这个算法进行理解：

    假设信源信号有{A, B, C, D}四个，他们的概率分别为{0.1， 0.4， 0.2， 0.3}，如果我们要对CADACDB这个信号进行编码，那么应该怎样进行呢？

    解：首先，我们做好准备工作，按照信源信号的频率为将[0, 1)分解成为若干区间。那么这一步骤完成之后，我们得到以下的表格：

    准备工作完成之后，我们便可以开始进行编码了。

    那么我们首先读入信号：C——因为C在最初始的间隔中是[0.5, 0.7)，所以读入C之后我们的编码间隔就变成[0.5, 0.7)了；

    紧接着，我们读入的是A，A在初始区间内是占整个区间的前10%，因此对应这个上来也是需要占这个编码间隔的前10%，因此编码区间变为：[0.5, 0.52)了；

    再然后是D，因为D占整个区间的70% ~ 100%，所以也是占用这个编码区间的70% ~ 100%，操作后的编码区间为[0.514, 0.52)

    ……

    直到最后将信号量全部读出。

    最后，我们将这个操作过程绘制成为一张表：

  B、解码

    解码的过程其实和编码的过程恰恰相反，解码是给定一个[0, 1)中的浮点数，通过解码操作之后就能完全获得原始的信号串。

    （一）步骤

1. 待解码的数据，首先我们仍然需要在编码时候的那项准备工作，即获取创建一个编码解码表，但是由于我们是在同一个类中完成的，那么我们把该对应表作为类的一个属性就可以实现获取表了；
2. 准备工作完成之后，我们就可以开始正式的解码工作了，首先判断待解码的数据在哪个范围内，将该范围对应的信源信号输出即可；
3. 重复步骤2，按理说，按照这样的方法，解码会一直进行下去，无穷不尽，直到达到计算机的精度为止，那么为了正确的进行解码，我们需要对解码的次数进行限定，即我们首先需要事先知道，解码后的信源信号的长度，然后在进行解码，这样才能比较完美的进行解码。

    （二）伪代码

    解码过程可以由以下的伪代码实现：

    input code
    do 
        find the Interval which contains the code
        set range = highLevel - lowLevel
        set code = (code - lowLevel) / range
    while times out

   （三）例题

    我们以上述的那个题目为例：

    假设信源信号有{A, B, C, D}四个，他们的概率分别为{0.1， 0.4， 0.2， 0.3}，当我们得到的编码是0.5143876的时候，问原始的信号串（7位）是怎样的？

    解：首先，我们做好准备工作，按照信源信号的频率为将[0, 1)分解成为若干区间。那么这一步骤完成之后，我们得到以下的表格：

    准备工作完成之后，我们现在开始解码：

    我们发现，待解码的数据0.5143876在[0.5, 0.7)内，因此，我们解出的第一个码值为C

    同理，我们继续计算0.5143876处于[0.5, 0.7)的第一个10%内因此解出的第二个码值为A

    ……

    这个过程持续直到执行七次全部执行完为止。

    那么以上的过程我们同样可以列表表示：

三、编码实现

    那么，我们现在算是理解这个算法了，那么应当怎样通过代码来实现这一算法呢？

    我们先将这个算法的类抽象出来：

/**
* @author Mica_Dai
* @Date Sept 13 2017
*/

// 算术编码类
class Arithmeticcoding
{
public:
    Arithmeticcoding(){
        length = 0;
    }
    ~Arithmeticcoding(){}

    // 获取编码，实际上就是创建对应表
    void requirecode();
    double encode(string str);
    string decode(double value);
    int getLength();

private:
    // 这个length是字符串的长度
    int length;
    std::map<char, Range> map;
};

    主要的问题有以下几点：

• 按照步骤，我们首先应当输入信源信号以及其对应的频率，相当于建立了一个对应的编码解码库；
• 怎样进行这个算法的操作
  
  

    对于第一个问题，我采取的是使用C++的关联容器类map来创建这个编码解码库，map翻译成中文就是映射，相当于就是我们创建一个信源信号与对应频率之间的映射，这样我们在获取信源信号的时候就能够直接获取该信源信号对应的概率了。但是考虑到在算法进行的过程中，参与计算的并不是该信源信号的概率，而是该信源信号的区间上下界；因此，我索性创建一个类用于存放区间上下界，从而创建一个从信源信号到区间上下界类的映射。这样在编码过程之中就能相当方便的寻找到对应的上下界，并参与运算了。

    对于第二个问题，我们在上面的伪代码中其实已经完成了这一步，在这里我就不再啰嗦了；

    好啦，解决了以上的两个问题，废话不多说，我就直接上代码了：

/**
* @author Mica_Dai
* @Date Sept 13 2017
*/

// 区间类，主要的就是用来存放上下界
class Range
{
public:
    Range(){
        low = 0.0;
        high = 1.0;
        deltaLevel = 1.0;
    }
    ~Range(){}
    double getLow(){
        return this -> low;
    }

    double getHigh(){
        return this -> high;
    }

    void setLow(double low){
        this -> low = low;
    }

    void setHigh(double high){
        this -> high = high;
    }

    void setDelta(double delta){
        this -> deltaLevel = delta;
    }
private:
    double low;
    double high;
    double deltaLevel;
};

    再来看看我们首先创建编码解码表，需要输入，因此我们直接通过一个类方法为类属性map赋值：

/**
* @author Mica_Dai
* @Date Sept 13 2017
*/

void Arithmeticcoding::requirecode(){
    char ch;
    double lowLevel = 0.0;
    double highLevel = 0.0;
    double probability;
    while(1){
        // cout << "youyouyio" << ch << endl;
        // cin >> lowLevel >> highLevel;
        cin >> ch;
        if (ch == '#'){
            break;
        }else{
            cin >> probability;
            // cin >> lowLevel;
            // cin >> highLevel;
            lowLevel = highLevel;
            highLevel = lowLevel + probability;
            Range range;
            range.setLow(lowLevel);
            range.setHigh(highLevel);
            range.setDelta(probability);
            map.insert(std::pair<char, Range>(ch, range));
        }
    }
}

    以下是编码函数的实现：

/**
* @author Mica_Dai
* @Date Sept 13 2017
*/

double Arithmeticcoding::encode(string str){
    /* encode code */
    double lowRange = 0.0, highRange = 1.0;
    for (auto i = str.begin(); i != str.end(); ++ i){
        // 使用map来通过字符完成概率的查找
        // map[*i]表示的就是对应的字符的出现概率
        double delta = highRange - lowRange;
        highRange = lowRange + delta * map[*i].getHigh();
        lowRange = lowRange + delta * map[*i].getLow();

        ++ length;
    }

    return lowRange;
}

    以下是解码过程：

/**
* @author Mica_Dai
* @Date Sept 13 2017
*/

string  Arithmeticcoding::decode(double value){
    double lowInterval;
    double highInterval;
    string symbol = "";

    // 译出第一个编码
    for (auto i = map.begin(); i != map.end(); ++ i){
        if ((i -> second).getLow() < value && (i -> second).getHigh() > value){
            lowInterval = (i -> second).getLow();
            highInterval = (i -> second).getHigh();
            symbol += (i -> first);
            break;
        }
    }

    for (int i = 0; i < length - 1; ++i){
        /* decode code */
        double deltaInterval;
        deltaInterval = highInterval - lowInterval;
        value -= lowInterval;
        value /= deltaInterval;

        for (auto i = map.begin(); i != map.end(); ++ i){
        if ((i -> second).getLow() < value && (i -> second).getHigh() > value){
            lowInterval = (i -> second).getLow();
            highInterval = (i -> second).getHigh();
            symbol += (i -> first);
            break;
            }
        }
    }

    return symbol;
}

    最后贴一下运行过程：

C:\Users\50口口\Desktop>arithmeticcoding.exe
A
0.1
B
0.4
C
0.2
D
0.3
#
CADACDB
0.514388
CADACDB

    以上。