算术编码Python

算术编码是一种无损数据压缩算法，它根据输入数据的概率分布来生成一个紧凑的编码。下面是一个用Python实现算术编码的例子：

from fractions import Fraction

def arithmetic_encode(data, probabilities):
    low = 0.0
    high = 1.0
    result = ''
    for symbol in data:
        range_size = high - low
        high = low + range_size * probabilities[symbol][1]
        low = low + range_size * probabilities[symbol][0]
        while True:
            if high < 0.5:
                result += '0'
                low *= 2
                high *= 2
            elif low >= 0.5:
                result += '1'
                low = (low - 0.5) * 2
                high = (high - 0.5) * 2
            elif low >= 0.25 and high < 0.75:
                result += '5'
                low = (low - 0.25) * 2
                high = (high - 0.25) * 2
            else:
                break
    return result

def arithmetic_decode(encoded_data, probabilities, length):
    low = 0.0
    high = 1.0
    result = ''
    code = Fraction(encoded_data, 2**length)
    for _ in range(length):
        range_size = high - low
        value = (code - low) / range_size
        for symbol, (symbol_low, symbol_high) in probabilities.items():
            if symbol_low <= value < symbol_high:
                result += symbol
                high = low + range_size * symbol_high
                low = low + range_size * symbol_low
                break
    return result

# 示例用法
data = 'abacabadabacaba'
probabilities = {'a': (0.0, 0.5), 'b': (0.5, 0.75), 'c': (0.75, 0.875), 'd': (0.875, 1.0)}
encoded_data = arithmetic_encode(data, probabilities)
decoded_data = arithmetic_decode(encoded_data, probabilities, len(data))
print('Encoded data:', encoded_data)
print('Decoded data:', decoded_data)

这个例子中，我们定义了一个`arithmetic_encode`函数和一个`arithmetic_decode`函数来进行算术编码和解码。`arithmetic_encode`函数接受输入数据和概率分布作为参数，并返回编码后的数据。`arithmetic_decode`函数接受编码后的数据、概率分布和数据长度作为参数，并返回解码后的数据。