无损数据压缩

互联网领域术语

无损数据压缩（Lossless Data Compression）是指使用压缩后的数据进行重构（或者叫做还原、解压缩），重构后的数据与原来的数据完全相同，但通常压缩比小于有损数据压缩的压缩比

定义与特点

无损压缩用于要求重构的信号与原始信号完全一致的场合。也就是说数据经过压缩后信息不受损失，还能完全恢复到压缩前的原样。它和有损数据压缩相对。这种压缩通常压缩比小于有损数据压缩的压缩比。

一个很常见的例子是磁盘文件的压缩。根据技术水平，无损压缩算法一般可以把普通文件的数据压缩到原来的1/2～1/4。一些常用的无损压缩算法有霍夫曼（Huffman）算法和LZW(Lenpel-Ziv & Welch）压缩算法。

编码技术

香农-范诺编码

最早阐述和实现这种编码的是Shannon（1948年）和Fano（1949年），因此被称为香农-范诺（Shannon-Fano）算法。

这种方法采用从上到下的方法进行编码。首先按照符号出现的频度或概率排序，例如，A、B、C、D和E，如表1所示。然后使用递归方法分成两个部分，每一部分具有近似相同的次数。按照这种方法进行编码得到的总位数为91。压缩比约为1.3 : 1。

表1 Shannon-Fano算法举例表

霍夫曼编码

霍夫曼（Huffman）在1952年提出了另一种编码方法，即从下到上的编码方法。现仍以一个具体的例子说明它的编码步骤：

霍夫曼码的码长虽然是可变的，但却不需要另外附加同步代码。例如，码串中的第1位为0，那肯定是符号A，因为表示其他符号的代码没有一个是以0开始的，因此下一位就表示下一个符号代码的第1位。同样，如果出现“110”，那么它就代表符号D。如果事先编写出一本解释各种代码意义的“词典”，即码簿，那么就可以根据码簿逐个码进行译码。

算术编码

算术编码在图像数据压缩标准（如JPEG、JBIG）中扮演了重要的角色。在算术编码中，消息用0到1之间的实数进行编码，算术编码用到两个基本的参数：符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在0到1之间。编码过程中的间隔决定了符号压缩后的输出。

RLE编码

现实中有许多这样的图像，在一幅图像中具有许多颜色相同的图块。在这些图块中，许多行上都具有相同的颜色，或者在一行上有许多连续的象素都具有相同的颜色值。在这种情况下就不需要存储每一个象素的颜色值，而仅仅存储一个象素的颜色值，以及具有相同颜色的象素数目就可以，或者存储一个象素的颜色值，以及具有相同颜色值的行数。这种压缩编码称为行程编码，常用（run length encoding，RLE）表示，具有相同颜色并且是连续的象素数目称为行程长度。

词典编码

词典编码（dictionary encoding）的根据是数据本身包含有重复代码这个特性。例如文本文件和光栅图像就具有这种特性。词典编码法的种类很多，归纳起来大致有两类。

第一类词典法的想法是企图查找正在压缩的字符序列是否在以前输入的数据中出现过，然后用已经出现过的字符串替代重复的部分，它的输出仅仅是指向早期出现过的字符串的“指针”。这里所指的“词典”是指用以前处理过的数据来表示编码过程中遇到的重复部分。这类编码中的所有算法都是以Abraham Lempel和Jakob Ziv在1977年开发和发表的称为LZ77算法为基础的，例如1982年由Storer和Szymanski改进的称为LZSS算法就是属于这种情况。

第二类算法的想法是企图从输入的数据中创建一个“短语词典（dictionary of the phrases）”，这种短语不一定是像“严谨勤奋求实创新”和“国泰民安是坐稳总统宝座的根本”这类具有具体含义的短语，它可以是任意字符的组合。编码数据过程中当遇到已经在词典中出现的“短语”时，编码器就输出这个词典中的短语的“索引号”，而不是短语本身。

常见格式

图片格式

音频格式

视频格式

全国各地天气预报查询

上海市

市辖区

云南省

临沧市

云南省

丽江市

云南省