1. 算法描述

功能：

  给定概率字典以及待编码字符串，求出该字符串算术编码的结果（最短二进制串），并能根据算数编码结果进行解码，得到原字符串。

2.算法流程：

算术编码流程：

  (1) 首先，初始化概率区间上下界分别为1和0。读入第一个字符，并根据该字符的概率区间更新当前区间，具体方法为：
$$\begin{gathered} upper\_bound=lower\_bound+intervalLength\ast probDict[chr][1] \\ lower\_bound=lower\_bound+intervalLength\ast probDict[chr][0] \end{gathered}$$
其中$intervalLength$表示当前区间长度，$probDict[chr][1],probDict[chr][0]$分别表示当前字符的概率区间上下界。

  (2) 然后，继续读入下一字符并不断更新当前概率区间，直到最后一个字符处理完毕后退出循环，得到最终的概率区间。

  (3) 根据最终概率区间求出该区间内的最短二进制串，方法如下：从第一个二进制位开始，若当前位置1得到的数大于区间上界，则将该位置0；若当前位置1得到的数恰好在区间内（即恰好大于下界），则该位置1不变，然后直接出循环，无需生成后续的位数；若当前位置1得到的数小于下界，则该位置1。如此可保证求出的二进制串必为该区间内的最短二进制串。

算术解码流程：

  (1) 将编码得到的二进制串转为十进制小数，记作$encodedDec$。

  (2) 先看$encodedDec$落在哪个字符的概率区间内，若它落在字符$c$的概率区间内，则解码出的第一个字符即为$c$。

  (3) 接下来，继续对当前区间进行划分，得到概率字典中各字符的新概率区间，再看现在$encodedDec$落在哪个字符对应的区间内，则第二个解码出的字符就是该字符。

  (4) 重复步骤(3)直到循环次数达到字符串长度，完成解码过程。

求区间内的最短二进制串流程：

  从小数点后第一位开始往后：若该位置1得到的数大于区间上界，则将该位置0；若当前位置1得到的数恰好在区间内（即恰好大于下界），则该位置1不变，然后直接出循环，无需生成后续的位数；若当前位置1得到的数小于下界，则该位置1。

3. 核心代码

# 算术编码函数：输入为字符串和概率字典，返回最终区间的上下界
def arithEncode(string, probDict):
    lower_bound = Decimal('0.0')
    upper_bound = Decimal('1.0')
    for chr in string:
        intervalLength = upper_bound - lower_bound  # 区间长度
        # 不断更新区间上下界，注意必须先更新上界，否则会导致上界更新错误（因为上界的计算用的是上一次的下界）
        upper_bound = lower_bound + intervalLength * probDict[chr][1]
        lower_bound = lower_bound + intervalLength * probDict[chr][0]
        print(lower_bound, upper_bound)
    # 返回最终区间的上下界
    return lower_bound, upper_bound
 
# 求出最终区间内的最短二进制串
def dec2Bin(lower_bound, upper_bound):
    binStr = ''
    # 初始化01串转为的二进制数为0.0
    temp = Decimal(0.0)  
    i = 1  # 初始化幂为1
    while(1):
        bit = 1
        # 若当前位 置1 得到的数大于区间上界，则将该位 置0，temp不变
        if((temp + Decimal(1 / (2 ** i) * bit)) > upper_bound):
            bit = 0
            binStr += '0'
        # 若当前位 置1 得到的数恰好在区间内（即恰好大于下界），则该位 置1 不变，然后直接出循环，无需生成后续的位数
        else:
            if((temp + Decimal(1 / (2 ** i) * bit)) > lower_bound):
                binStr += '1'
                break
            # 若当前位 置1 得到的数小于下界，则该位 置1 
            else:
                binStr += '1'
        # 更新temp
        temp += Decimal(1 / (2 ** i) * bit)
        # 阶数自增1，下一轮循环时用
        i += 1
    return binStr

# 二进制串转十进制小数（乘二取整）
def bin2Dec(bin):
    dec = Decimal(0.0)
    for i in range(len(bin)):
        if(bin[i] == '1'):
            dec += Decimal(1 / (2 ** (i + 1)))
    # 这里返回的数据类型一定要是Decimal
    return dec

# 算术解码函数：输入为已编码二进制串、概率字典、字符串长度，返回解码后的字母串
def arithDecode(encodedBin, probDict, strLength):
    decodedStr = ''
    # probDict_copy存放原始的概率字典
    probDict_copy = deepcopy(probDict)
    # 二进制串转十进制小数
    encodedDec = bin2Dec(encodedBin)
    # 因为要解码出strLength个字符，所以共循环strLength次
    for _ in range(strLength):
        # 如果编码数字落在某个字符的概率区间内，则在结果中加入该字符
        for chr, interval in probDict.items():
            if((encodedDec >= interval[0]) & (encodedDec < interval[1])):
                decodedStr += chr
                # 继续对当前区间划分，看编码数字落在哪个字符对应的区间内
                # 更新字典中各字符的概率区间
                temp_lower_bound = interval[0]    # 记录当前区间下界和区间长度
                intervalLength = interval[1] - interval[0]
                for chr in probDict.keys():
                    probDict[chr][0] = temp_lower_bound + intervalLength * probDict_copy[chr][0]
                    probDict[chr][1] = temp_lower_bound + intervalLength * probDict_copy[chr][1]
                break
    return decodedStr

4. 实验结果

  结果分析：用户输入待编码各字符、各字符的概率以及需要编码的字符串，程序会先构造出概率字典，然后输出算数编码的最终结果，即最短二进制串和对应的十进制浮点数。在编码成功后，程序对编码得到的二进制串解码，最终的解码结果与原字符串一致，说明解码准确率为100%。从程序运行的结果可以看到，本实验成功实现了对给定概率字典的字符串的无损算术编码及解码。

5. 分析与总结

 1. 通过本次实验，我掌握了算术编码及解码的基本算法思想，并通过编程实现了算数编码及解码的过程，提高了自己的动手实践能力，对于Python语言中的float、Decimal等数据类型的概念和用途有了更深的理解。

  2. 题目要求我们求出在最终概率区间内的最短二进制串作为算术编码结果，但我一开始没有想到最短二进制串的求法，于是我在草稿纸上从小数位第一位开始逐位向后推算，看每一位上1和上0后得到的十进制数在不在概率区间内，最后推出了求最短二进制串的算法。其实我们在碰到看起来不会解决的问题时，不妨先静下心来拿出纸笔演算几步，说不定就能得出解法，而不是对着电脑在大脑里思考，这样做效率是很低下的。

  3. 在写算术编码函数的时候，按照算法流程，我们需要反复更新概率区间的上下界，在这个过程中我们是利用上一次的概率区间下界以及当前字符的概率区间上下界去更新的。我一开始在写这个函数的时候，没注意到必须要先更新upper_bound再更新lower_bound，而是先更新了lower_bound。这么做会导致新的区间上界是用新的区间下界更新的，而不是用上一次的下界更新的，后来我调试的时候发现了这一错误并且改正了。

  4. 关于数据类型的收获：Python中的float类型无法在任意指定的小数位上保持精确，因此在实验过程中所有的数值均转化为了Decimal类型，以保证精确计算（Decimal的精度默认是28位）。在对于运行效率要求不是很高而对于精度要求很高时，可以使用Decimal保精度，若对于运行效率的要求较高而不怎么在意精度，则使用float类型也无妨。