重温一下 毕业后写的第一个算法 LZW

LZW压缩算法的基本原理：提取原始文本文件数据中的不同字符，基于这些字符创建一个编译表，然后用编译表中的字符的索引来替代原始文本文件数据中的相应字符，减少原始数据大小
第一次实现的时候是用C# 和js用于数据压缩 ，当时刚毕业，是根据伪码写的，当时挺痛苦的，后来想想还是挺有意思的：）

#encoding = utf-8
import string

def lzw_compress(s="ababcbababaaaaaaa"):
    """
    进行lzw 压缩
    """
    dic = {}
    for i in string.ascii_letters:
        dic[i]=i
    
    result = ''
    key = s[0]
    #进行向后编码的起始值
    dic_index = 129
    for i in range(1,len(s)):
        v = s[i]
        key += v
        if dic.has_key(key):
            continue
        else:
            print key,
            dic[key] = unichr(dic_index)
            dic_index+=1
            result += dic.get(key[0:-1])
            #print key[0:-1],result.encode("utf-8")
            key = v
    return result

r = lzw_compress()
print "result is:" ,r.encode("utf-8")

ab ba abc cb bab baba aa aaa aaaa result is: ab*c*‚…*a**‡ˆ

感兴趣的同学，可以写个解压的算法，有点像破译密码，挺有意思的。注意基于编码表

评论

4 楼 ych516 2011-02-26  

当年我的毕业论文就是写的LZW ~：）

3 楼 acrbb 2011-02-22  

有时间去看看,mark

2 楼 squirrelRao 2011-02-21  

有意思，学习...Mark

1 楼 jackhorner 2011-02-20  

lz 算法家族的核心概念就是字典表和窗口概念，要感谢Abraham Lempel and Jacob Ziv 两位数学家的贡献。