文本压缩(数据库)

时间：2022-11-28 20:30:01 | 来源：信息时代

时间：2022-11-28 20:30:01 来源：信息时代

    文本压缩 : 采用某种方法对输入文本进行的一种编码处理,输出压缩文本,以便能用更少的字节数来表示原有文本,达到信息的压缩存储。文本解压缩是与文本压缩相对应的概念,即对压缩文本进行解码处理,输出原有文本。文本压缩在文本数据中发挥着重要的作用,这是因为文本压缩可以减少文本的大小,从而减少数据库的I/O操作,提高数据库性能。目前许多数据库系统(如Oracle、DB2等)一般都支持数据压缩功能。
1. 文本压缩
定义:压缩率=未压缩之前文本的大小÷压缩之后文本的大小。
Shannon曾证明,对给定的一组符号进行编码,每个符号需要的平均位数等于平均信息量:

E是任何压缩算法的理论极限。Shannon还指出,在最优情况下,出现概率为p的符号需要用log₂(1/p)个位来表示。
2. 文本压缩方法
(1)基于词典的压缩方法:最早由Ziv和lempel在20世纪70年代提出的,该压缩方法是基于这样一个朴素的思想: 在前文中已经遇见过的字符串可视为先验知识,在再次遇到它时可以用较短的码字来表示它,从而实现压缩。它不是把单个字符编码成可变长度的码字,而是将可变长度的符号串编码成码字,或称为标记(token)。如果该码字的长度短于字符串的长度,则实现了压缩。LZ系列算法,包括LZW、LZ77、LZ78、LZSS等是目前最常用的通用压缩算法。
(2)基于统计的文本压缩方法:其基本原理是统计文本符号的出现频率,用尽可能少的字节或者位来表示出现频率高的文本符号。基于统计的文本压缩方法可以细分为两个阶段:建模阶段和编码阶段。建模阶段主要是统计符号概率分布模型,也就是每个文本符号的出现概率。编码阶段根据符号概率分布模型,把文本符号转编码成二进制。建模方法可以主要有静态、自适应、半静态三种。静态方法预先估计文本符号的平均概率分布,不管输入文本是什么,静态方法都该分布来指导编码。当输入文本与预先估计的分布相差比较大的时候,静态方法的压缩率很差。自适应方法无需任何先验知识,它们一边扫描压缩输入文本,一边获取概率分布。当输入文本比较大的时候,自适应方法统计的符号概率分布非常接近真实的概率分布。
3.Huffman编码的实现
基于统计的编码方法主要有Huffman编码和算术编码。Huffman编码先构造一个哈夫曼树,之后就可根据哈夫曼树进行编码。
给定字符串abcdafef,根据字符出现概率可以构造一棵如图1所示的Huffman树,使得出现概率越高的字符离根结点越近。

图1 Huffman编码示意图

经哈夫曼树可以得到字符对应的码值,比如字符a用01,b用0000来表示,而字符f用1来表示。字符串abcdafef压缩之后的输出为010000、0001、0010、01、1、0011、1。只要使用同一棵哈夫曼树,就可把编码还原成原来那组字符。显然哈夫曼编码是前缀编码,即任一个字符的编码都不是另一个字符的编码的前缀,这样可以方便解码。
算术编码是压缩能力最强的一种编码方式,它把输入文本表示成一个[0,1)之间的一个数值。算术编码需要预先获得符号的概率,并确定每个符号的编码间隔。算术编码给概率较高的符号分配较大的编码间隔,给出现概率较低的符号赋予较小的编码间隔。
表1的例子说明算术编码的过程。给定三个符号a₁,a₂,a₃,三者出现的概率分别是p₁＝0.4,p₂＝0.5,p₃＝0.1,编码字符串a₂a₂a₂a₃。

表1 算术编码演示

步骤	输入符号	间隔	计算方法
0	初始状态	[0,1)
1	a2	[0.4,0.9)	0+(1-0)×0.4 0+(1-0)×0.9
2	a2	[0.6,0.85)	0.4+(0.9-0.4)×0.4 0.4+(0.9-0.4)×0.9
3	a2	[0.7,0.825)	0.6+(0.85-0.6)×0.4 0.6+(0.85-0.6)×0.9
4	a3	[0.8125,0.8250)	0.7+(0.825-0.7)×0.9 0.7+(0.825-0.7)×1

根据概率分配间隔,给a₁,a₂,a₃分别分配一段间隔[0,0.4),[0.4,0.9),[0.9,1)。
初始间隔是[0,1),第一个输入符号是a₂,它的编码间隔是[0.4,0.9),因此取输入间隔的40%～90%部分,输出[0.4,0.9)。
当前间隔是[0.4,0.9),第二个输入符号还是a₂,因此取[0.4,0.9)的40%～90%,输出[0.6,0.85)。
如此不断分隔,表1描述了算术编码的整个过程,编码的最终的结果是[0.8125,0.8250)。