技术文章

(SCI) Parallel Algorithm for Wireless Data Compression and Encryption

(SCI) Fast Algorithm of Truncated BWT for Data Compression of Sensors

Dr. Qin Jiancheng

龙之梦助力肇庆教育网云计算

Dr. Zhou Yousheng

Dr. Bai Yuan

龙之梦工作室加盟华南理工学术团队

[软件下载] ComZip超级压缩机免费版下载

继续潜行，龙之梦工作室技术研发又一年

[软件交易] “雅典娜”网页密码锁在线购买

[软件交易] Super Prime超级质数机在线购买

[软件交易] ComZip超级压缩机在线购买

[信息安全] “风语者”高强度加密技术

[信息安全] 多层纵深防御体系结构

[合著] 专利：安全事件检测方法及装置

[合著] 网友交流：关于数据压缩算法

[ 2008-08-10 09:42:31 ]
　　引言/提要：我们网站提到算术压缩编码，我们所做的改进是提高了压缩和解压的速度。另外一个是“雅典娜”网页密码锁软件里面用到了LZSS压缩算法，我们做了针对中文网页的算法优化。

　　关键词：数据压缩，算法优化，核心技术，“雅典娜”网页密码锁，LZSS算法，算术编码

网友（2007-11-6）：
master，您好！
　　我们学校留了个作业，要求：介绍一种新的压缩算法（不限于音频和视频，且不能选择课件中讲过的算法，如huffman等），要求阐述该算法的原理（5分）、工作过程（5分）、应用示例（5分）和个人评价（5分）。我看到您的网站中有，但不详细，您能不能给我提供一份详细的呢？
　　顺致谢意！

　　致
礼！
　

龙之梦工作室（2007-11-7）：
您好，
　　很高兴和您交流。我们网站提到算术压缩编码，我们所做的改进是提高了压缩和解压的速度。另外一个是“雅典娜”网页密码锁软件里面用到了LZSS压缩算法，我们做了针对中文网页的算法优化。
　　算术编码无论是原理上的理解，还是细节上的实现，都比LZSS算法复杂，时间有限，不方便讲，我们简单看看LZSS算法吧。
　　LZSS算法的基本原理您可以在网上搜索到，这里给一个参考链接：http://blog.chinaunix.net/u1/37897/showart_330352.html
　　LZSS的原理比较简单，您理解了之后，可能已经足够完成作业了。如果一定要“新的”压缩算法的话，不妨参考我们在“雅典娜”网页密码锁中的设计：可变长索引、2级缓存（滑动窗口）。

　　采用的LZSS压缩算法变体：2种索引长度(12位、18位)，3种编码形式(字符/12位、0.5K索引/12位、14K索引/18位)。
设置两级缓存，其中1级缓存512字节(0.5K)，2级缓存14336字节(14K)，两级缓存紧密连接，字符流从1级缓存流入2级缓存。
　　索引编码000000000000至011111111111：表示12位索引。
首位为0，第2至10位表示1级缓存内的位移值，后2位表示字串长度，最大表示长度达到15字节。
　　索引编码100000000000至100011111111：表示单个字符。
占用256个编码空间。前4位为1000，后8位表示字符的ASCII码值。
　　索引编码100100000000000000至111111111111111111：表示18位索引。
首位为1，第2至15位表示2级缓存内的位移值，后3位表示字串长度，最大表示长度达到63字节。
　　要点：
　一、1级缓存从当前字符的前面第2个字符开始，因为索引长度值至少为2。向前512字节是1级缓存，紧接着向前14K字节是2级缓存。
　二、首先在1级缓存中进行最大长度匹配，匹配不上再在2级缓存中进行最大长度匹配，再匹配不上才进行单个字符编码。

　　以上是我们最开始的压缩设计，可以有效压缩中文网页的HTML源代码。在“雅典娜”第一个版本出来的时候，具体设计就已经不同了，但设计思路不变，仍然是LZSS的变形。

　　欢迎您就技术上和非技术的问题交流意见。另外，电子邮件的主题最好不要用“求助”之类笼统的标题，很容易被误当作垃圾邮件批量删除的。

网友（2007-11-8）：
Dragon Dream Studio，您好！
　　非常感谢也非常感动您给我的回复。但教师要求不能写课上讲过的算法，其中LZSS（LZ77/LZ78及LZW)已经讲过了，所以要找其它的。：）　anyway thx a lot.　:)

龙之梦工作室（2007-11-8）：
您好，
　　绝对全新的压缩算法，不是说创新就能创造出来的。全世界研究了几十年，出来的新算法也不多。
　　目前世界上无损压缩的算法主要就是两大类：基于统计模型（例如算术编码），基于字典（例如LZSS），其它算法都是在原有算法的基础上改良而成。有损压缩则是根据具体领域和设计思路的不同，牺牲某些认为不太重要的部分，但是在大的方向上，同样是有限的。所以您找“新的”压缩算法，追朔根源几乎肯定会和课上的几种基本算法撞车。
　　所以您的作业要介绍新算法的话，建议您介绍某种改良算法，而不要去找绝对全新的算法。我想老师也不会预期学生做出“举世瞩目”的新算法，应该改良算法就能符合作业要求。
　　您可以自己设计改良，也可以参考我之前提供的“雅典娜”软件压缩算法，那已经是针对网页压缩优化过，不是原本的LZSS算法。至少LZSS不会有分级缓存，不会有变长索引、长度值数组。

（为保护隐私，对网友身份信息作了保密处理。）