有熟悉算术编码的朋友吗?(300分)

H

hopfield

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-09-17

• #1

最近忙着用Huffman算法做数据压缩,效果不错,压缩比可以到1/6---1/7,压缩/解压缩的
速度也挺好. 可是由于数据量比较大,每天的数据压下来还有4M左右,这样一年下来会有
接近1G. 记得以前看过资料,算术编码的压缩比更高,而且今天还看到一个新名词叫:
"二阶自适应算术编码",有哪位朋友熟悉算术编码吗? 请给我一些资料或谈谈你们的感受.

 

H

htw

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-09-17

• #2

Huffman编码应该是最优化的无损压缩编码了。
既然压缩速度也不错, 何必没有事找事做呢

 

H

hopfield

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-09-17

• #3

从信息熵的角度来讲,Huffman只是bit级的最优编码,而根据Shannon公式算出来的
最小的信息表示长度可能只要零点几个bit,那这种情况下,Huffman就不是最有的了,
算术编码的特点就是可以突破bit的限制

 

C

Chenlili

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-09-17

• #4

那你可以trytry LZW等其他算法，LZW我搞过，由于压缩字典是动态生成的，所以速度比较快
你还可以去http://compsci.home.chinaren.com/compress/article.htm

 

H

hopfield

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-09-17

• #5

To Chenlili:
thanks! 我这就去看看. 不过LZW你做过,我就问问关于LZW的问题吧:
1.LZW和HuffMan有什么区别? 对于给定的概率分布,在bit级上,Huffman可以
说是最优的,LZW有什么优势吗? 我的感觉是: LZW事先对概率分布一无所知,
压缩字典动态生成,在这点上,LZW弥补了静态Huffman的不足,不知道我的猜测
对不对? 如果是这样,LZW相对动态Huffman呢? 当然,动态Huffman太难了,我没
兴趣实现它
2.LZW能突破bit级的限制吗?

 

旧

旧雨

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-09-18

• #6

听听！

 

O

oldppp

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-09-18

• #7

静态的算术编码的源码以前有，不过弄丢了。:-((
但是好象并不难.动态的没做过,如果你作出来,请给我一份,谢谢

 

J

JJams_King

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-09-19

• #8

http://www.cs.mu.oz.au/~alistair/arith_coder/arith_coder-3.tar.gz

 

J

JJams_King

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-09-19

• #9

http://www.cs.mu.oz.au/~alistair/abstracts/mnw98:acmtois.html

 

J

JJams_King

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-09-19

• #10

原理
http://dogma.net/markn/articles/arith/part1.htm

 

J

JJams_King

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-09-19

• #11

原理很简单，按概率把symbol分配到0--1之间，每个symbol一个间隔
然后对symbol，找它对应的间隔并按概率细分这个间隔，一直到symbol
流结束。得到一个小数，这个小数就是code了。

 

J

JJams_King

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-09-19

• #12

伪码 (From:http://dogma.net/markn/articles/arith/part1.htm)
Set low to 0.0
Set high to 1.0
While there are still input symbolsdo
get an input symbol
code_range = high - low.
high = low + range*high_range(symbol)
low = low + range*low_range(symbol)
End of While
output low

 

H

hopfield

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-09-20

• #13

To JJams_King:
Thanks a lot! 谢谢你提供的资料,算术编码的资料我以前看过一些,原理就像你前面所
讲的. 不知道你是否具体做过算术编码,能谈谈它压缩/解压缩的速度吗? 另外,相对于
Huffman算法,它压缩比会有多大提高?
不过前面的伪码有问题吧,如果symbols很长,编码出来的小数位数会很长,而float
型数据在计算机里面的表示精度是有限的,那这个矛盾如何解决? 当然,前面的代码可能
只是说明大致的原理,并不是实际用的代码.

 

张

张剑波

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-10-12

• #14

请[^]提前或结束

 

J

JJams_King

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-10-12

• #15

to hopfield:
我没有做过程序，不过看过一个。实际上压缩的时候并不是用float的，而是用一个
整数，并且不断把已经不会改变的bit从整数中移掉。

 

张

张剑波

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-10-19

• #16

多人接受答案了。