Question

数据无损压缩算法

Answer 1

所谓无损压缩格式，顾名思义，就是毫无损失地将声音信号进行压缩的音频格式。常见的像MP3、WMA等格式都是有损压缩格式，相比于作为源的WAV文件，它们都有相当大程度的信号丢失，这也是它们能达到10%的压缩率的根本原因。而无损压缩格式，就好比用Zip或RAR这样的压缩软件去压缩音频信号，得到的压缩格式还原成WAV文件，和作为源的WAV文件是一模一样的！但是如果用Zip或RAR来压缩WAV文件的话，必须将压缩包解压后才能播放。而无损压缩格式则能直接通过播放软件实现实时播放，使用起来和MP3等有损格式一模一样。总而言之，无损压缩格式就是能在不牺牲任何音频信号的前提下，减少WAV文件体积的格式。

　　经常使用的无损压缩算法有 Shannon-Fano 编码，Huffman 编码，行程（Run-length）编码，LZW（Lempel-Ziv-Welch）编码和算术编码等。

　　Huffman 编码
　　该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码。它是统计独立信源能达到最小平均码长的编码方法。编码效率高 。

　　基本原理：

　　依据信源字符出现的概率大小来构造代码，对出现概率较大的信源字符，给予较短码长，而对于出现概率较小的信源字符，给予较长的码长，最后使得编码的平均码字最短。

　　编码步骤：

　　（1）初始化，根据符号概率的大小按由大到小顺序对符号进行排序。

　　（2）把概率最小的两个符号组成一个节点。

　　（3）重复步骤2。

　　（4）从根节点开始到相应于每个符号的“树叶”，从上到下标上“0”（上枝）或者“1”（下枝）至于哪个为“1”哪个为“0”则无关紧要，最后的结果仅仅是分配的代码不同，而代码的平均长度是相同的。

　　（5）从根节点开始顺着树枝到每个叶子分别写出每个符号的代码。

无损压缩算法有哪些

　　Huffman编码的注意点：

　　Huffman编码没有错误保护功能，如果码中有错误，则可能引起接下来的一连串译码错误。

　　Huffman编码是可变长编码，因此很难随意查找或调用中的文件内容。

　　Huffman依赖于信源的统计特性。 Huffman编码的每个码字都是整数：因此实际上平均码长很难达到信息熵的大小。

　　Huffman编码解码必须要有码表，如果消息数目很多，那么