符号方法

科技工作者之家 2020-11-17

符号方法是通过估计符号(常常是字符)的概率值来压缩文本,它在同一时间只对一个符号编码,如摩斯码,对最可能出现的符号使用较短的码字。符号方法属于外部压缩方法,即对存储在外部存储器的文本数据进行压缩,来降低数据存储成本。

定义符号方法是一种外部压缩方法,通常基于哈夫曼编码或算术编码,主要的不同之处在于如何估计符号的概率。符号概率值估计越难,压缩效果越好。为了获得更好的压缩效果,概率估计常常要根据符号出现的上下文进行。概率估计的工作叫做建模,而建立一个好的模型对于实现好的压缩效果是至关重要的。把概率转化为比特流以供传输的过程叫做摩斯码。

哈夫曼编码Huffman编码将出现概率高的字符编成较短的码字,而出现概率较低的字符则被编成较长的码字,这样做可使得平均每字符的码长最短。Huffman刚提出来时是以单字符为编码单位的,并且假定字符之间是不相关的。这样得到的码效率还不够高,因此后来出现了以字符串(词)作为编码单位的Huffman算法,这样平均每字符的编码长度变小了,但是同时编码码本的大小也显著变大了。另外,这种做法的通用性也比较弱。Huffman原来是静态的,它要求先对信源字符流进行扫描以确定各个字符(串)的出现频度,用它来估计各个字符(串)的分布概率,并根据它来构造码本。在这一过程完成以后,才进行第二次扫描,用已得到的码本来给各个字符(串)编码。静态Huffman的缺陷除了要进行两次扫描之外,还在于它要在每个编码结果中附上相应的码本,这样解码器才能正确地恢复压缩前的字符流。为了克服以上两个缺陷,自适应Huffman编码被提了出来,它只需要对待编码字符流进行一次扫描,在扫描的过程中对字符(串)的出现概率进行估计,同时自适应地构造、更新码本,并用这个动态变化的码本来对扫描到的字符(串)进行编码。自适应Huffman编码除了复杂度要比静态Huffman要高之外,由于其对字符出现概率估计并不能像静态Huffman那么准确,所以它能达到的编码效率也要低一些。Huffman编码器为每个待编码的符号(串)所分配的码字的位数只能是整数的。这个特点妨碍Huffman编码的平均码长对信源熵的逼近。而以下的算术编码法则较好地解决了这个问顾1。

算术编码算术编码是在世纪年代后期提出,并在20世纪80年代得以流行的一种编码方法。算术编码是一种高效清除字串冗余的算法。它用一个单独的浮点输出数值代替一串输入符号,从而每个符号对于输出代码的贡献可以相当于一个小数位数。这使得编码的平均码长从理论上可以任意逼近于信源的熵,避开了Huffman编码中比特数必须取整的问题。类似于Huffman编码,算术编码也要对待编码数据流进行两次扫描2。第一次扫描统计各个字符的出现频度,估计其出现概率。第二次扫描则按照上述的映射规则来对数据流进行编码。所以算术编码的输出码流中也要附上相应的编码码本以作为解码的依据。

算术编码器也可以采用自适应的方式,这时不需要在编码输出中附加编码码本。但是,自适应算术编码的复杂度较高,不利于实现。实践中,算术编码并不是用浮点数形式来实现的,它的编码和解码都是用整数来实现。由于算法中包含了乘除法,所以对算法的时间性能很不利。常用的做法是采用加法和移位操作来代替乘除法操作。

但是算术编码的实现有两大缺陷:很难在具有固定精度的计算机完成无限精度的算术操作。高度复杂的计算量不利于实际应用。例如,对一个简单的信号源进行观察,得到的统计模型如下:

60%的机会出现符号 中性

20%的机会出现符号 阳性

10%的机会出现符号 阴性

10%的机会出现符号 数据结束符. (出现这个符号的意思是该信号源'内部中止',在进行数据压缩时这样的情况是很常见的。当第一次也是一次看到这个符号时,解码器就知道整个信号流都被解码完成了)。

算术编码可以处理的例子不止是这种只有四种符号的情况,更复杂的情况也可以处理,包括高阶的情况。所谓高阶的情况是指当前符号出现的概率受之前出现符号的影响,这时候之前出现的符号,也被称为上下文。比如在英文文档编码的时候,例如,在字母Q或者q出现之后,字母u出现的概率就大大提高了。这种模型还可以进行自适应的变化,即在某种上下文下出现的概率分布的估计随着每次这种上下文出现时的符号而自适应更新,从而更加匹配实际的概率分布。不管编码器使用怎样的模型,解码器也必须使用同样的模型。

文本压缩文本压缩属于无损压缩,是数据压缩的一个分支。它要求能够由压缩后形成的编码无失真地恢复压缩前的原始数据。对文本压缩的研究己有很久的历史,并且前人己经取得了不少的研究成果,有很多己经得到了实际的应用,其中一些有着优良性能的技术正在被广泛地应用。然而,根据Shannon编码定理以及用各种方法估计出来的文本信源的嫡,现有技术还没有达到编码效率的极限,还有很大的发展空间。而且,现有技术大多是由西方国家科学工作者开发出来的,它们即使应用于西方语言文本时能获得较好的性能,当应用于大字符集的文本(例如中文、日文、韩文以及Unicode文本)时,性能却都会大大地降低。因此很有必要发展适用于大字符集文本的文本压缩技术,特别是既适用于西文文本又适用于大字符集文本的文本压缩技术。在电子技术、计算机技术和网络技术蓬勃发展,各种数据的数字化和网络化的步伐迈得越来越大。越来越多的网上图书馆和网上资料库出现了,通过网络传输的电子文档也越来越多了。因此,改进文本压缩技术,节省存储空间,提高网络带宽的利用率是非常有必要的。

有关术语摩尔斯电码摩尔斯电码(又译为摩斯密码,Morse code)是一种时通时断的信号代码,通过不同的排列顺序来表达不同的英文字母、数字和标点符号。它发明于1837年,发明者有争议,是美国人塞缪尔·莫尔斯或者艾尔菲德·维尔。 摩尔斯电码是一种早期的数字化通信形式,但是它不同于现代只使用零和一两种状态的二进制代码,它的代码包括五种: 点、划、点和划之间的停顿、每个词之间中等的停顿以及句子之间长的停顿。最早的摩尔斯电码是一些表示数字的点和划。数字对应单词,需要查找一本代码表才能知道每个词对应的数。用一个电键可以敲击出点、划以及中间的停顿。虽然摩尔斯发明了电报,但他缺乏相关的专门技术。他与艾尔菲德·维尔签定了一个协议,让他帮自己制造更加实用的设备。艾尔菲德·维尔构思了一个方案,通过点、划和中间的停顿,可以让每个字符和标点符号彼此独立地发送出去。他们达成一致,同意把这种标识不同符号的方案放到摩尔斯的专利中。这就是我们所熟知的美式摩尔斯电码,它被用来传送了世界上第一条电报。

这种代码可以用一种音调平稳时断时续的无线电信号来传送,通常被称做“连续波”(Continuous Wave),缩写为CW。它可以是电报电线里的电子脉冲,也可以是一种机械的或视觉的信号(比如闪光)。

一般来说,任何一种能把书面字符用可变长度的信号表示的编码方式都可以称为摩尔斯电码。但这一术语只用来特指两种表示英语字母和符号的摩尔斯电码:美式摩尔斯电码被使用在有线电报通信系统;还在使用的国际摩尔斯电码则只使用点和划(去掉了停顿)。

概率又称或然率、机会率或几率、可能性,是数学概率论的基本概念,是一个在0到1之间的实数,是对随机事件发生之可能性的度量。

概率常用来量化对于某些不确定命题的想法,命题一般会是以下的形式:“某个特定事件会发生吗?”,对应的想法则是:“我们可以多确定这个事件会发生?”。确定的程度可以用0到1之间的数值来表示,这个数值就是概率。因此若事件发生的概率越高,表示我们越认为这个事件可能发生。像丢铜板就是一个简单的例子,正面朝上及背面朝上的两种结果看来概率相同,每个的概率都是1/2,也就是正面朝上及背面朝上的概率各有50%。

这些概念可以形成概率论中的数学公理(参考概率公理),在像数学、统计学、金融、博弈论、科学(特别是物理)、人工智能/机器学习、计算机科学及哲学等学科中都会用到。概率论也可以描述复杂系统中的内在机制及规律性。

本词条内容贡献者为:

李岳阳 - 副教授 - 江南大学