LZW压缩算法简单实现

yinda_peng

def lzw_encode(data):
    # 初始化字典，包含所有可能的单个字符
    dictionary = {chr(i): i for i in range(256)}
    dict_size = 256
    result = []
    # 初始化 P 和 C
    P = ""
    for C in data:
        PC = P + C
        # 如果 PC 在字典中
        if PC in dictionary:
            P = PC
        else:
            # 输出 P 的编码，并将 PC 添加到字典中
            result.append(dictionary[P])
            dictionary[PC] = dict_size
            dict_size += 1
            P = C
    # 输出最后一个 P 的编码
    if P:
        result.append(dictionary[P])
    return result

# 测试编码函数
data = input("请输入字符串:")
if data is "":
    data = "TOBEORNOTTOBEORTOBEORNOT"

encoded_data = lzw_encode(data)
print("字符串LZW压缩后的码如下:")
print(encoded_data)


def lzw_decode(encoded_data):
    # 初始化字典，与编码时相同
    dictionary = {i: chr(i) for i in range(256)}
    dict_size = 256
    result = []
    # 初始化 pW 和 cW
    pW = chr(encoded_data.pop(0))
    result.append(pW)
    for cW in encoded_data:
        # 如果 cW 在字典中
        if cW in dictionary:
            entry = dictionary[cW]
        elif cW == dict_size:
            entry = pW + pW[0]
        else:
            raise ValueError("Bad compressed data")
        # 输出 entry
        result.append(entry)
        # 将 pW+cW[0] 添加到字典中
        dictionary[dict_size] = pW + entry[0]
        dict_size += 1
        # 更新 pW
        pW = entry
    return ''.join(result)

# 测试解码函数
decoded_data = lzw_decode(encoded_data)
print("解码后的字符串与原字符串比较：",decoded_data == data)
print("解码后的字符串如下：")
print(decoded_data)


# 对英文txt文档进行测试
path = "F:/英语/test.txt"
with open(path, 'r', encoding='UTF-8') as f:
    content = f.read()      # 为字符串内容
    encoded_content = lzw_encode(content)
    print("文本LZW压缩后的码如下:")
    print(encoded_content)

    decoded_content = lzw_decode(encoded_content)
    print("解码后的文本与原文本比较：",decoded_content == content)
    print("输出解码后的文本：")
    print(decoded_content)
    f.close()

test文件内容：

Happiness Is Your Own Choice

Most of us compare ourselves with anyone we think is happier -- a relative, someone we know a lot, or someone we hardly know. As a result, what we do remember is anything that makes others happy, anything that makes ourselves unhappy, totally forgetting that there is something happy in our own life.
So the best way to destroy happiness is to look at something and focus on even the smallest flaw. It is the smallest flaw that would make us complain. And it is the complaint that leads to us becoming unhappy.
If one chooses to be happy, he will be blessed; if he chooses to be unhappy, he will be cursed. Happiness is just what you think will make you happy.

参考：file:///F:/%E5%A4%A7%E4%BA%8C%E4%B8%8B/%E4%BF%A1%E6%81%AF%E8%AE%BA/LZW%E5%8E%8B%E7%BC%A9%E7%AE%97%E6%B3%95%E5%8E%9F%E7%90%86%E8%A7%A3%E6%9E%90%20-%20%E4%B8%AA%E4%BA%BA%E6%96%87%E7%AB%A0%20-%20SegmentFault%20%E6%80%9D%E5%90%A6.html

某一个“天”

学习

很cool的阳

很cool的阳