哪一种压缩算法速度最快？
Huffman
LZ77
LZ78
LZSS
LZW
算术编码
哪一种编码速度最快？
问题点数：20、回复次数：14Top
1 楼angel_sino（东方天使）回复于 2006-11-27 22:27:25 得分 0
学习。。。Top
2 楼dengsf（drklnk@Radical_Dreamer）回复于 2006-11-28 08:30:55 得分 0
论编码速度自然是LZSS、LZW了，
它们分别是LZ77、LZ78的改进版。
但论解压最快还是LZSS。
Top
3 楼zhouhong0801（小六子）回复于 2006-11-28 09:19:54 得分 0
哈夫慢编码吧？？？Top
4 楼kimryo（God is on my side）回复于 2006-11-28 09:57:11 得分 0
还有压缩和解压的区别~要说这里面最快当然是huffman...因为LZ开头的最后都会用到huffman。。。Top
5 楼wood87654321（wood87654321）回复于 2006-11-28 11:03:53 得分 20
LZ开头的最后都会用到huffman？这可头一次听说，九泉之下，老哈得乐死，而那两个以色列人得气死。
LZ系列是字典压缩法，简单形容，就是用缩写串替代完整串；算术编码、huffman是统计压缩法，目标在于用最少的总bit数表示同样多的字符（相对标准的1字符8bit而言）。所以两类方法走的是根本不同的两条路。
这两类压缩算法之间不存在谁“速度最快”一说，即使限定了压缩比条件也不行，因为还要看源数据结构，即有的文件使用字典压缩法快，也有的使用统计压缩法更快。
在同一类压缩算法中也很难有绝对的“速度最快”之说，如dengsf所说LZSS、LZW是LZ77、LZ78的改进版，那么从理论上认定LZSS、LZW比LZ77、LZ78“效率更高”还是可以的，但是仍不绝对地说“速度更快”，如流行的LZW算法，算法理论上绝对比LZ77、78优秀，但是由于其字典指针至少占2字节，在实际应用中并不能保证压缩任何文件都比LZ78更快或是压缩比更高。
当然也有速度差距一目了然的，比如RLE肯定比huffman压缩、解压缩都快，因为它只有一遍源数据遍历，而不存在后者的建树编码。但是RLE适合用于你的源数据吗？
压缩算法的美妙之处往往在于速度、效率和适用对象之间存在一种有趣的平衡，而真正的应用往往是几种基础压缩算法的组合。
Top
6 楼kimryo（God is on my side）回复于 2006-11-28 11:14:21 得分 0
晕，说错了，都用了huffman的是Deflate和Implode这一系列的算法，目前来看压缩率综合最高的应该是LZMA,不过压缩速度偏慢~Top
7 楼z02321453（ALUCARD）回复于 2006-11-28 16:12:18 得分 0
自适应变长编码(CAVLC)
统一的变长编码(UVLC)
Huffman + 游程
统计二进制算术编码（快速无乘算法）
这些是我这几天的新发现，我现在已经有点头晕了，不知道因该选择哪一种。我要压缩的数据是视频流，要求编码的速度尽可能快（需要实时处理数据）。现在确定的是，单纯"Huffman"或者"游程"已经排除掉了，因为它们压不了多少。然后剩下的几种编码它们的区别对我来说只是速度上的差异，因为它们的效率都很高，基本上都在信息熵的90%以上。楼上几位说LZSS、LZW比较快，我开始也这么认为。LZ系列的算法复杂度大部分集中在符号串的比较上，算术编码的算法复杂度则大部分集中在浮点乘除的运算操作上。这两天我看到有文章介绍“统计二进制算术编码（快速无乘算法）”，新的算术编码去掉了耗费时间的浮点乘除运算，我不能确定它是不是比LZ系列Huffman等更快。
Top
8 楼kimryo（God is on my side）回复于 2006-11-28 16:14:46 得分 0
FT~视频现在最小的是Real的哈，不过要pay~WMV也不错~Top
9 楼wood87654321（wood87654321）回复于 2006-11-29 10:46:14 得分 0
坦率讲，如果是实时视频压缩，我觉得你那些方法都很困难，因为几乎都是无损压缩算法，这要是想真正实现高度压缩，快速根本无从谈起。
当前流行的DivX、Xvid等MPEG4方法才是首选，如果你非要自己实现一种算法，更值得参考的也应是基于DC、小波等数学变换的方法，如JPEGTop
10 楼iohui（小雄）回复于 2006-11-29 20:44:47 得分 0
楼上说的不错，要得到高压缩比就应当考虑使用有损压缩算法。可以考虑MPEG-1，MPEG-2，MPEG-4等算法，这些技术都已经相当成熟而且效果不错Top
11 楼z02321453（ALUCARD）回复于 2006-12-08 17:02:50 得分 0
楼上几位似乎偏题了，我是想问自适应变长编码(CAVLC)，统一的变长编码(UVLC)，Huffman+游程，统计二进制算术编码（快速无乘算法），这些算法里面该选哪个。这些都是DivX、Xvid、MPEG4、jpeg、jpeg2000、gif、rmvb、h.263等等各种编码器的基础核心算法。楼上的说“当前流行的DivX、Xvid等MPEG4方法才是首选”，你要知道这些流行的压缩方法都包含了无损算法，你可以去查一下这些流行的编解码器的结构图，可以清晰地看到最后一个步骤都是无损压缩算法。如果无损压缩算法都“快速根本无从谈起”那么当前流行的DivX、Xvid等MPEG4方法更加“快速根本无从谈起”。Top
12 楼z02321453（ALUCARD）回复于 2006-12-08 17:15:01 得分 0
高压缩比当然使用有损压缩算法，只不过最后一步都是归依为无损压缩算法。我这里只是讨论最后一步应该选择哪一种无损算法。在这里不妨告诉大家，我是用的有损算法就是小波分解，在量化过程中可以无限提高压缩比（当然质量会相对下降）。传统的小波分解速度很慢，我是用了特殊方法使得分解速度达到理论最高速度，但是总体的编码速度都被无损压缩算法拖下来了，所以我在这里想请教大家该选择哪一种无损压缩算法来配合我的小波分解。
总体速度(10)=算术编码(9.9)+小波分解(0.1)
如果选择的无损压缩算法压缩率过低，则显示不出小波分解的效果。如果选择的无损压缩算法速度太慢，则无法实现实时处理。Top
13 楼wood87654321（wood87654321）回复于 2006-12-11 09:13:01 得分 0
如果你只强调最后一步，并且对速度的要求甚于质量的话，那么当然是纯粹的游程编码最快啦！（开个玩笑）
不妨考虑一下差分无损压缩算法Top
14 楼z02321453（ALUCARD）回复于 2006-12-11 15:24:05 得分 0
我决定了，使用“静态概率统计Huffman + 固定游程”。Top
