（计算机应用技术专业论文）矢量地图格式中数据压缩技术的研究与实现.pdf

矢量地图格式中数据压缩技术的研究与实现 摘要 随着g i s 应用技术的同益普及，数字地图逐渐代替了传统的纸质地图成为 存储地理空间数据的主要载体。在网络技术高速发展的今天，一方面，w e b g i s 将交互式的电子地图带到了互联网上，利用i n t e r n e t 技术在w e b 上发布空间数据 供用户浏览和使用是g i s 发展的必然趋势：另一方面，基于无线联网技术的移 动设备大量出现，移动地理信息系统以其特有的便携性已经获得了一定市场份 额，并以惊人的速度在扩大其产业规模。由于互联网带宽的限制和人们对海量地 图数据快速传输、显示要求之间的矛盾，数字地图数据的压缩方法将越来越受到 g i s 研发者所重视。数字地图中由于矢量数据结构具有结构紧凑、冗余度低、利 于网络检索分析等优点，是g i s 最常见的图形数据结构。因此对矢量地图数据 压缩研究的意义可谓深远。 本文的研究正是基于这样的实际背景和需求提出的，并且纳入了2 0 0 8 年度 浙江省科技厅重大攻关项目“面向g i s 应用的通用城市空间数据处理平台开发 与安全研究”研究课题之中。 本文的主要工作有： 1 总结了当前国内外矢量地图的各种压缩方法，对无损压缩编码模型进行 了详细阐述。 2 在l z w 压缩算法基础上，结合了b w t 变换的特点，提出了基于b w t 变换的矢量地图压缩改进算法：根据矢量地图数据存储采用文本文件的 特点，我们将矢量数据中坐标数据提取出来，并进行b w t 变换，使变换 后的数据更有序和更易于压缩，最后再采用l z w 算法进行压缩。 3 根据矢量数据采集过程中顺序性和密集性的特征，提出了“一种新的矢 量地图无损压缩算法”：采用预测模型对坐标数据先进行一轮转换，使原 本需要以d o u b l e 型或f l o a t 型表示的数据用l o n g 型表示，再采用“基于不 规则系数的预测编码 进行编码，最后将转换后的数据进行进一步的压 缩。 4 以“一种新的矢量地图无损压缩算法为基础，设计一个不仅能够进行 地图编解码，而且还能够方便地进行地图查看并具有简单分析功能的软 件，利用该软件作为矢量地图编解码技术的一个实用工具。 5 总结了所做的研究工作，并对矢量地图无损压缩算法的前景提出了自己 的意见。 关键词：矢量地图；无损压缩；b w t 变换；l z w 算法；预测模型 t h er e s e a r c ha n di l e m e n t a t l 0 no fd a t a c o 口r e s s i o ni nv e c t o r 睑p s a bs t r a c t w i t ht h ea p p l i c a t i o no fg i st e c h n o l o g yw i d e l yu s e d ，d i g i t a lm a p s g r a d u a l l yr e p l a c et h et r a d i t i o n a lp a p e rm a p sa n db e c o m et h em a i nc a r t i e r i ng e o s p a t i a ld a t as t o r a g e a sw e l la st h er a p i dd e v e l o p m e n to fn e t w o r k t e c h n o l o g y a n dh i g h - s p e e dw i r e l e s sn e t w o r kt e c h n o l o g y ，w e b g i s t e c h n o l o g ya n dm o b i l eg i st e c h n o l o g yh a v ee m e r g e d t h es i z eo f g e o m e t r i cd a t as e t si nt h e s ea p p l i c a t i o n si sc o n s t a n t l yi n c r e a s i n g s t o r i n g s u r f a c eo rv o l u m em e s h e si ns t a n d a r du n c o m p r e s s e df o r m a t sr e s u l t si n l a r g ef i l e st h a ta r ee x p e n s i v et os t o r ea n ds l o wt ol o a da n dt r a n s m i t t h e h i 曲l ye f f i c i e n tc o m p r e s s i o no fd i g i t a lm a p sh a v eb e c o m et h ek e yt o r e s o l v et h ei s s u e t h ev e c t o rd a t as t r u c t u r ei sc o m p a c t ，l o wr e d u n d a n c y ， a n dc o n d u c i v et on e t w o r ks e a r c h i n g ，s oi tb e c o m e st h em o s tp o p u l a r g r a p h i c sd a t as t r u c t u r e t h e r e f o r et h ev e c t o rm a p s c o m p r e s s i o nr e s e a r c h h a sf a r - r e a c h i n gs i g n i f i c a n c e t h i ss t u d yi sb a s e do nt h er e a lb a c k g r o u n da n dr e q u i r e m e n tm e n t i o n e d a b o v e a n di ti sa l s oi n v o l v e di nt h er e s e a r c ht o p i co ft h ed e v e l o p m e n to f g e n e r a lu r b a ns p a t i a ld a t ap r o c e s s i n gp l a t f o r ma n dr e s e a r c ho n s e c u r i t yf o rg i s sa p p l i c a t i o nw h i c hi sp a r to f2 0 0 8m a j o rp r o j e c to f i i i s c i e n c ea n dt e c h n o l o g yd e p a r t m e n to fz h e ji a n gp r o v i n c e t h em a i nc o n t e n t so ft h i st h e s i sa r ea sf o l l o w s ： 1 g i v eas e to fv a r i o u sm e t h o d so fv e c t o rm a p sc o m p r e s s i o n ，a n d d e s c r i b et h ec o d em o d e lo fl o s s l e s sc o m p r e s s i o ni nd e t a i l 2 b a s eo nt h el z wc o m p r e s s i o na l g o r i t h m ，a n dt h ec h a r a c t e r i s t i c so f t h eb w tt r a n s f o r m ，ao p t i m i z em e t h o do fv e c t o rm a p c o m p r e s s i o n b a s e do nt h eb 、t r a n s f o r mw a sp r o p o s e d a c c o r d i n gt ot h et e x t f i l ew a su s e di ns p a t i a ld a t as t o r a g ei nv e c t o rm a p ，t h ep a p e rw i l l s e p a r a t et h ec o o r d i n a t ed a t a ，a n dt h e nu s et h eb w tt r a n s f o r m ，s o t h a tt h et r a n s f o r m e dd a t aw a sm o r eo r d e r l ya n de a s yt oc o m p r e s s ， a f t e rt h a tw ec a nu s et h el z w c o m p r e s s i o na l g o r i t h ma saf u r t h e r c o m p r e s s i o n 3 t h r o u g ht h ea n a l y s i so ft h ev e c t o rm a pf i l e s ，an e wl o s s l e s s c o m p r e s s i o na l g o r i t h m f o rv e c t o r m a p s i s p r o p o s e d i p t h e a l g o r i t h m ，l o s s l e s st r a n s f o r md i f f e r e n t i a t e st h eg r a p h i c a ld a t ao f v e c t o rm a p si n t ot r a n s f o r m e dc o e f f i c i e n t s ，t h e n ，m a k i n gu s eo ft h e p r i n c i p l e o f r e d u c t i o n ，t h e s et r a n s f o r m e dc o e f f i c i e n t s a r e c o m p r e s s e dr e v e r s i b l y a tt h es a m et i m e ，b w tb l o c k s o r t i n g a l g o r i t h mi sa d o p t e da saf u r t h e rc o m p r e s s i o na l g o r i t h ms oa st o a c h i e v et h ee f f i c i e n tr e s u l t so ft h el o s s l e s sc o m p r e s s i o nf o rv e c t o r m a p s r e s u l t so ft h ee x p e r i m e n t sw i t hp r a c t i c a lm a p ss h o wt h a t ， c o m p a r i n g w i t ht h e e x i s t i n g m e t h o do fn e e d l e s s i v a p p e n d e d c o d e - b o o kd i c t i o n a r y b a s e dc o m p r e s s i o n a n do t h e r c o m m o nl o s s l e s sc o m p r e s s i o nm e t h o d s ，t h ep r o p o s e dm e t h o di s f a i r l yg o o da tc o m p r e s s i o nr a t i o ，a n dt h ea l g o r i t h mi sv e r ys i m p l e 4 w i t ht h ef o u n d a t i o no ft h ea c h i e v e m e n td e s c r i b e da b o v e ，a s o f t w a r ew a sd e s i r e dw h i c hi n c l u d e sal o to ff u n c t i o n ，s u c ha st h e b r o w s e ro ft h ed i g i t a lm a p ，c o m p r e s s i n ga n dd e c o m p r e s s i n gt h e m a p ，a sw e l la sd os o m es i m p l ea n a l y s i s t h es o f t w a r ec a nb eu s e d t ot e s ta n dv e i lf yt h ec o m p r e s s i o nm e t h o d 5 s u m m a r i z et h em a i nc a u s e so fd a t ac o m p r e s s i o na n dg i v es o m e 印p r o v i n gs u g g e s t x o n s k e y w o r d s ：v e c t o rm a p ；l o s s l e s sc o m p r e s s i o n ；b w tt r a n s f o r m ； l z w a l g o r i t h m ；p r e d i c t i o nm o d e l v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含本人为获得浙江工商大学或其 它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中作了明确的说明并表示谢意。 签名：黛兽骧嗍劢9 5 7 年弓月够日 关于论文使用授权的说明 本学位论文作者完全了解浙江工商大学有关保留、使用学位论文 的规定：浙江工商大学有权保留并向国家有关部门或机构送交论文的 复印件和磁盘，允许论文被查阅和借阅，可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制 手段保存、汇编学位论文，并且本人电子文档的内容和纸质论文的内 容相一致。 保密的学位论文在解密后也遵守此规定。 签名：毒慨导师签名：砬 日期：如9 尸年乡月k 日 5 9 第1 章绪论 1 1 g i s 技术及其发展现状 随着现代信息社会的发展，每时每刻都有大量来源不同的地理空间数据产 生，大量的地理信息数据无法通过人工方式处理，需要借助专门的软件，运用计 算机处理才能从中获取有用的信息。地理信息系统( g e o g r a p h i ci n f o r m a t i o n s y s t e m ，简称g i s ) 是人类在生产实践中，为描述和处理相关地理信息而逐渐产 生的软件系统【1 2 列。它以计算机为手段，对具有地理特征的空间数据进行处理， 以空间信息为主线，将与其有关的空间位置信息按某种处理方式结合在一起。 g i s 的诞生改变了传统的信息处理方式，使信息处理由数值领域步入空间领域。 地理信息系统作为一种采集、存储、分析处理、显示，并在不同系统、不同地点 和不同用户之间传输数字化空间数据与信息的计算机应用系统，已经逐步地成为 空间信息管理与应用的主要平刽4 5 6 】。 与地理信息产业的建立和数字化信息产品在全世界的普及相呼应【7 , 8 , 9 , 1 0 , 1 1 】， g i s 已经在如区域与城市规划、农业土地与水资源规划、林业管理、自然资源调 查、环境保护、大型工程项目的前期准备和实施控制、公用事业管理、地籍与房 产管理、交通运输规划与管理、国防与军事、地质矿产调查等方面得到较好的推 广应用。另外，g i s 在金融业、保险业、建筑业、制造业、零售业、公用设施 业以及通讯业等也得到广泛应用。g i s 信息作为信息社会中一种重要的基础信 息，既是社会公益性产品，又具有重要的市场价值。 数字地图是是g i s 系统的操作对象。地图数字化就是利用飞速发展的计算 机科学作为载体，把传统的地图使用计算机进行保存，称为数字地图。随着g i s 应用技术的日益普及，数字地图逐渐代替了传统的纸质地图成为存储地理空间数 据的主要载体1 2 , 1 3 , 1 4 。 网络技术高速发展的今天，一方面，w e b g i s 将交互式的数字地图带到了互 联网上，利用i n t e m e t 技术在w c b 上发布空间数据供用户浏览和使用是g i s 发 展的必然趋势1 5 , 1 6 , 17 】；另一方面，基于无线联网技术的移动设备大量出现，移动 地理信息系统以其特有的便携性已经获得了一定市场份额，并以惊人的速度在扩 大其产业规模。由于互联网带宽的限制和人们对海量地图数据快速传输、显示要 求之间的矛盾，数字地图数据的压缩方法将越来越受到g i s 研发者所重视。 1 2 矢量地图压缩定义 数字地图包括两种【l8 】：光栅地图和矢量地图。光栅地图也称点阵地图，就 是把纸媒质的地图使用扫描仪进行数字量化，转化为数字图像并进行保存。而矢 量地图就是用点、线、面等数掘结构来表示地图中的道路，建筑物和区域等各种 地理实体。矢量地图中的矢量数据结构是最常见的图形数据结构，是一种面向目 标的数据组织方式。矢量方法强调离散现象的存在，将线离散为一串采样点的坐 标串，而面状区域则由边界线确定。因此与栅格地图相比，矢量地图具有结构紧 凑、冗余度低、利于网络检索分析等优点，矢量地图也成为g i s 最常见的数字 地图格式。 在表达空间数据时，矢量地图包含了描述空间数据属性特征的属性数据和描 述空间数据空间特征的几何数据以及描述空间数据之间空间关系的关系数据，目 前尚无一种统一的数据结构能够同时存储上述各种类型的数据，而是将不同类型 的空间数据以不同的数据结构存储。通常将矢量地图的属性数据用二维关系表格 形式存储，而几何数据和关系数据则以矢量数据结构存储。一般地，相对于属性 数据，几何数据和关系数据占绝大比例数据量。 ( 1 ) 矢量地图的数据表示 矢量方法将地理现象或事物抽象为点、线、面实体，将他们放在特定空间坐 标系下进行采样记录。矢量地图中，点实体记录点坐标和属性代码，即一个点只 需记录一个x 和一个y 坐标，以及他们的属性代码( 如点的颜色，大小等) ； 线实体记录两个或一系列采样点的坐标以及他们的属性代码；面实体记录边界上 一系列采样点的坐标以及他们的属性代码，由于多边形封闭，边界应为闭合环。 图1 1 的地图数据记录情况见表1 1 。 2 用笛卡尔坐标表示的地图 图1 - 1 矢量地图的数据表示 表1 - 1 矢量数据表示 实体类型编号矢量数据 点实体 6坐标( x y ) + 属性代码 线实体 1 2 坐标( x ly l ，x 2 y 2 ，x 。y n ) + 属性代码 2 3坐标( x iy l ，x 2 y 2 ，x n y 。，闭合环) + 属性代码 面实体 2 4坐标( x ly l ，x 2 y 2 ，x 。y 。，闭合环) + 属性代码 ( 2 ) 矢量地图的数据获取方式 矢量地图的数据获取方式通常有： 1 ) 由外业测量获得，可利用测量仪器自动记录测量结果( 常称为电子手薄) ， 然后转到地理数据库中。 2 ) 由栅格数据转换获得，利用栅格数据矢量化技术，把栅格数据转换为矢 量数据。 3 ) 跟踪数字化，用跟踪数字化的方法，把地图变成离散的矢量数据。 由于栅格数据自动矢量化技术还不成熟，人工跟踪数字化是当前获取矢量数 据的最主要方法。由于实际数字化地图时，根据操作习惯所生成的曲线和多边形 一般有着事实上较为严格的方向性( 如按“从坐到右”，“从上到下 生成) ， 这决定了生成的同一实体坐标点列的值的大小具有单调性或者分段单调性的特 点。 ( 3 ) 矢量地图格式 g i s 经过几十年的发展，在技术和理论上都取得了巨大的进步，其应用领域 3 变得越来越广泛，不同的行业和部门积累了大量的数据资源，加上各种g i s 软 件层出不穷，不同的g i s 软件都有各自不同的数据格式，如a r c l n f o 的e 0 0 格式， e s r i 的s h p 格式，m a p l n f o 的m i f m i d 格式等。虽然在地图格式上有差异，但由 于矢量地图数据结构仍主要以“简单数据结构”和“拓扑数据结构”为主，因此 各种格式之间依然可以相互转换，实现多源数据的共享利用。 ( 4 ) 矢量数据压缩定义 就目前成熟的应用广泛的g i s ( 如：m a p i n f o ，a r c v i e w 等) 中，通常将 矢量地图的图形与拓扑关系信息，即矢量数据，存放在一个结构表中，通称为几 何图形信息，并且将它与属性数据分开存放。属性数据用关系数据库或文件方法 管理，图形数据用文件方法管理，并按地理属性分图层组织文件。一般地，相对 属性数据，图形数据占绝大比例数据量。由于属性数据大多是文本格式，因此对 属性数据的压缩可以采用通用压缩工具进行有效处理，而矢量数据由于其数据的 特殊性，用通用压缩工具或一般压缩算法压缩并不能得到一个非常满意的结果， 因此有必要对矢量数据的压缩进行研究。 矢量数据压缩是从组成曲线的点集合a 中抽取一个子集b ，用这个子集b 在一定的精度范围内尽可能地反映原数据集合a ，而这个子集b 的点数应尽可 能少【1 9 】。对矢量数据能进行压缩其本质的原因在于原始数据存在一定的冗余， 这种数据冗余一方面是数据采样过程中不可避免产生的；另一方面是由于具体应 用变化而产生，比如大比例尺的矢量数据用于小比例尺的应用时，就会存在不必 要的数据冗余，因此应该根据具体应用来选择合适的矢量数据压缩算法。矢量数 据压缩的核心是在不扰乱拓扑关系的前提下对原始采样数据进行合理的删减。 1 3 国内外研究现状 相对于属性数据，几何数据和关系数据( 统称矢量数据) 占绝大比例数据量。 因此对矢量地图的压缩重点便成了如何有效地压缩矢量数据2 0 2 1 2 2 1 。矢量数据压 缩方法根据所压缩的空间对象来讲主要分为曲线数据的压缩和面域数据的压缩。 其实经过特殊的处理，面域数据的压缩可以化归为曲线数据的压缩特殊形式 【2 3 2 4 ，2 5 1 ，因此许多压缩方法仅仅阐述对曲线矢量数据的压缩方法。 目前，曲线矢量数据有损压缩算法主要有：垂距限值法【2 6 】、角度限值澍2 7 1 、 4 光栏法【2 8 】、经典d o u g l a s p e u c k e r 方法【2 9 3 0 ，3 l 】及其改进方法，基于小波技术的压 缩方法【3 2 ，3 3 ，3 4 1 。而无损压缩方面除了通用压缩方法之外，只有李青元和钟尚平【3 5 1 对这方面做了研究。 ( 1 ) 垂距限值法 基本思路是：每次顺序取曲线上的3 个点，计算中间点与其他两点连线的垂 线距离d ，并与限差d 比较，若d a ，则保留第2 点，否则剔除。该算法与垂距限值法很类似，但是算法健壮性好，牺牲了算法简 单的优点。 ( 3 ) 光栅法 基本思路是：定义一个扇形区域，通过判断曲线上的点在扇形外还是扇形 内，确定保留还是舍去。该方法算法复杂度较大，但算法的压缩效率使之有继 续存在的理由。 ( 4 ) 经典d o u g ia s - p e u c k e r 方法 d o u g l a s - - p e u c k e r 方法是由d h d o u g l a s 和t k p e u c h e r 在1 9 7 3 年提出来的， 该方法实际上是垂距限值法的改进，它是在曲线的首尾两点a 、b 之间连接一条 直线段a b ，该直线称为曲线的弦；得到该曲线上离直线段a b 距离最大的点c ， 计算其到a b 的距离d ； 比较d 与给定的限值t ，若d t ， 则用c 将曲线分为两段a c 、b c ，分别对两线段按照以上方法进行处理；所有 曲线处理完毕后，依次连接各分割点形成的折线，得到新的曲线，其中限值t 是 根据实际的精度要求反复试验得到的，如图1 2 ，折线a d c e b 可看成曲线a b 的 相似曲线。 5 a 图卜2d o u g l a s p e u c k e r 方法 ( 5 ) 基于小波技术的压缩方法 基于小波技术对矢量数据进行压缩是一个比较新的方法。小波分析技术对信 号与信息处理、图像处理与编码等方面均产生了重要的影响。在g i s 领域，现 在有不少学者把小波技术引入数据压缩方面并取得了理想的效果。小波、离散小 波、小波变换、多分辨分析等是小波分析技术的基本概念，现有很多专著与文献 均对其做了详细的阐述，在此不再赘述。现在一般用二进制、多进制、b 样条小 波等对矢量数据进行压缩，无论采用哪种小波压缩技术，其压缩模型的思想与方 法都是一样的。根据小波分析理论，可以将空间2 ( 尺) 看成是某地理空间在特定 比例尺下的矢量地图数据模型，厂( z ) 是其上各个图形要素，j i v z , 吃 一可以看 成是基于此比例尺下原始矢量数据的多级压缩模型。根据以上原理，可以认为原 始矢量数据模型l 2 ( r ) = v o ，从y o 出发，应用尺度函数可以表示出 ，f - ，v m 则可以看成是基于小波多尺度分析的原始矢量数据阳 的压缩结果，也就是矢量地图数据在各个层次上的近似表示。运用小波技术对矢 量数据进行压缩的结果对应于原始数据的低频部分，压缩之后丢掉了原始数据的 高频信息。 ( 6 ) 矢量地图的无损压缩算法 矢量地图的无损压缩方面，李青元提出用i n t 甚至s h o r t 型代替d o u b l e 和f l o a t 型来存储空间坐标以取得较高压缩比的方法，钟尚平在此基础上提出了“一类矢 量地图的无损压缩算法”： 该算法利用三维图形数据的几何压缩基本思想，结合平面矢量地图的图形表 示特点，提出平面矢量地图图形的无损几何压缩算法作为第一步算法。另外，对 以文本文件表示的矢量地图，利用其文本特性，以“压缩预处理”加“基于字符的 6 b w t 算法”作为进一步压缩算法；并在这两种压缩算法之间有机应用“无附加码 书”字典压缩编码方法。然后针对平面矢量地图结构表示时线，多边形( 面) 类图 层文件与点类图层文件从几何压缩角度考虑时有较大差别，因此分开讨论这两类 几何压缩算法。该算法的核心思想是“无附加码书”字典压缩编码方法，即对图层 文件进行“偏移量压缩”后，再对变换后的坐标值的分段“+ ”块和“- 块求其 平均数，并以坐标值与平均数的差值代替原值，期望能使大部份坐标值的绝对值 缩小为系统设定的某阈值( 如：3 0 - 5 0 ) 以内，最后进行“无附加码书”字典压缩。在 “无附加码书”字典编码的过程中，对阀值内的数据可以用a s c i i 中的某一段 进行“无附加码书”替换，比如选取a s c i i 为5 8 以后的连续一块字符代替经缩 小后为阀值内的坐标值，而对于那些大于阀值的坐标值则不做单字符替换，而用 间隔符( 如采用a s c i i 码为4 3 ，4 4 的字符) 作间隔处理，也就是说，大于阀值 的坐标值的码量由原来的4 个字节( i n t 型) 变为6 个字节( i n t 型+ 2 个字节的间 隔符) 。可以说，“无附加码书”字典压缩编码方法实现的优劣程度直接对该压缩 方法的压缩比起到了决定性的作用。 前面所提到的矢量地图的有损压缩算法在地图显示逐层放大时发挥了不可 替代的作用，但是对g i s 的研究还不应仅仅满足于显示的要求，我们在研究数 据的存储和传输时，数据量的大小会直接影响到性能，因此我们也需要对矢量地 图的无损压缩做进一步研究。 1 4 论文的主要研究内容和组织结构 在本论文中，研究的是矢量地图无损压缩技术，重点是矢量数据的无损压缩 技术。文章的章节如下： 第一章介绍了g i s 技术及其发展现状，指出了矢量地图压缩在g i s 发展中 的作用，介绍了国内外目前的研究现状，相应的提出了本文的研究目的； 第二章介绍了数据压缩技术的发展和数据压缩理论，回顾了几种经典的编码 算法，尤其详细介绍了字典编码方法； 第三章在分析字典编码的基础上，提出了基于b w t 变换的矢量地图压缩改 进算法，该算法结合了b w t 变换和l z w 算法优点，能得到比l z w 更为优异的 压缩效果； 7 第四章首先介绍了“无附加码书字典编码方法，分析该方法存在的不足， 并在此基础上提出一种新的矢量地图无损压缩算法，该算法适用于所有的矢量地 图坐标系，而且压缩效果与其他方法相比更优异； 第五章在总结第四章研究成果上设计实现了一个压缩软件矢量地图无 损压缩软件； 第六章对全文工作做了总结和对未来工作做了展望。 8 第2 章数据压缩理论 2 1 信息量的定义 数据压缩是信息论的一个应用【3 6 1 。信息论是数学的一个分支，4 0 年代后期 由贝尔实验室的c l a u d es h a n n o n 首创，它涉及各种关于信息的问题，其中包括消 息存储和通讯的各种方式。 数据压缩之所以进入信息论领域，是因为它涉及了冗余问题。一条消息中的 冗余信息要占用额外的位来编码，而且如果去除这些额外信息将减少信息的量。 信息论使用“熵”作为一条信息中多少信息得到编码的量度。消息的熵越高， 所含的信息量就越多。一个符号的熵定义为其概率的对数的负值。对于单个事件 ( 如一个字符) 来说，其熵定义为： h ( i ) = 一l 0 9 2 ( p i ) 该式表示发生的概率为p i 的事件( 字符) i 所具有的信息量。度量信息量大 小的单位是“位”( b i t ) 。其物理含义为表示该事件( 字符) 所需要的最少位数。 对于一个消息队列x ( x = x l ，x 2 ，翮) 的平均信息熵定义为： h ( x ) = 一p ( a o xl o g ：( p ( 口f ) ) 式中的p ( a i ) 表示某一事件a i 发生的概率。由于这个表达式在形式上与物理 学中的热熵的表达式相似，因而借用“熵”这个词表示对信息量的测度。有时为 了区别与热力学熵，又称其为信息熵。一个事件发生的概率越小，其信息熵越高， 所含的信息量越大。 早期的数据压缩之所以成为信息论的一部分，是因为它涉及冗余度的问题。 一条消息中的冗余信息将会产生额外的编码。如果去掉这些冗余信息，就会减少 消息所占的空间。例如“中华人民共和国可以压缩成“中国”。这样能大大节 省存储和传输的开销。 当然，冗余信息在某些情况下是非常有用的。具有一定冗余度的消息能有较 强的抗干扰能力。当消息在传输中受到干扰而出现错误时，这些冗余信息可以帮 助我们根据上下文纠正错误。如果我们接收到“中华人事共幸国”( 其中的“木 表 q 示由于干扰或其他原因造成丢失或无实际意义的字符) ，由上下文可找出丢掉的 两个字。但若收到“木国”，就很难判断丢掉的是什么字，不知到底是“中国”、 “英国”、还是“德国等。 从此可知，不论是文本文件、图形文件、数据文件还是程序文件，其中都有 大量的重复部分。压缩( c o m p r e s s i o n ) 就是设法去掉部分或全部冗余，从而减少 数据或文件所占的存储空间。还原( 或称释放) 就是利用相反的算法使数据或文 件恢复原状。 衡量压缩程度的指标之一是压缩比。到目前为止，关于压缩比的定义尚无统 一的方法。在信息论中，压缩比定义为压缩前后数据的熵之比。这种定义方法基 于对要压缩数据的统计分析结果而提出。而现在所使用的许多压缩技术并不依赖 于数据的统计结果。因此采用这种定义方法有相当的局限。为与实际的概念相一 致，我们采用如下形式定义压缩比： 压缩比= ( 源代码长度压缩后代码长度) 源代码长度10 0 其含义是被压缩掉的数据占源数据的比例。例如，若压缩后的代码长度与源 数据相同，则压缩比为o ；若压缩后的代码长度为0 ，则达到l o o 的压缩比；若 压缩后的代码长度是源数据的3 0 ，则表示被压缩了7 0 ，即其压缩比是7 0 。 数据压缩技术所探讨和研究的各种压缩方法，都是为了提高压缩比。不同的 文件，不同的压缩方法，不同的图像分辨率都将影响到压缩比的大小。从数据压 缩的目的来说，我们希望压缩比越大越好。但实际上，压缩比是有上限的对基 于统计的编码方法而言，这个上限与信息的熵有着密切的关系。如果压缩比超过 了这个上限，还原时将无法恢复原状，出现失真。 2 2 数据压缩技术的发展 s h a n n o n f a n o 编码是第一个对符号进行有效编码的方法，由贝尔实验室的 c l a u d es h a n n o n 和m i t 的r m f a n o 几乎同时提出。它仅仅依赖消息中每个符号 出现的概率进行编码。它所构造的代码的特性有： 不同的代码有不同的位数。 低概率符号的代码有较多的位数，高概率符号的代码有较少的位数。 尽管代码有不同的位长度，但它们能唯一地解码。 1 9 5 2 年，h u f f m a n 第一次发表了关于编码的论文【3 7 1 ，并立即成为信息论中 1 0 引用最多的论文，h u f f m a n 编码产生了很多的小变化，并且直到8 0 年代早期一 直占据着编码世界的主导地位。 到8 0 年代初期，算术编码成了继h u f f m a n 编码后的又一主导编码技术。算 术编码在概念和实现两方面与标准的可变宽度代码相比都略为复杂。它并不为每 个符号在概念和实现两方面与标准的可变宽度代码相比都略为复杂。它并不为每 个符号产生一个单独的代码，而是为整个一条消息产生一个代码。增加到消息中 的每一个符号都大量地修改输出代码。算术编码需要很强的c p u 的支持。算术 编码绕过了用一个特定的代码代替一个输入符号的想法，它用一个单独的浮点输 出数值代替一个流的输入符号，对于较长的复杂消息，输出数值需要更多的位数。 直到1 9 7 7 年，数据压缩的研究工作集中于熵、字符和单词频率以及统计模 型的各个其他方面，为使用h u f f m a n 编码程序寻找新的改进方法。1 9 7 7 年，随 着j a c o bz i v 和a b r a h a ml a m p e i 的论文“au n i v e r s a la l g o r i t h mf o rs e q u e n t i a ld a t a c o m p r e s s i o n 3 8 】的发表，所有一切都改变了，这篇论文以及1 9 7 8 年发表的 “c o m p r e s s i o no f i n d i v i d u a ls e q u e n c e sv i av a r i a b l e r a t ec o d i n g 【3 9 】开辟了字典 压缩的新思路，从此开始了基于字典压缩的研究、算法和程序，这两篇论文所描 述的两个压缩技术也分别被称为l z 7 7 和l z 7 8 。 l z 系列算法的思路并不新鲜，其中既没有高深的理论背景，也没有复杂的 数学公式，它们只是简单地延续了千百年来人们对字典的追崇和喜好，并用一种 极为巧妙的方式将字典技术应用于通用数据压缩领域。通俗地说，当你用字典中 的页码和行号代替文章中每个单词的时候，你实际上已经掌握了l z 系列算法 的真谛。这种基于字典模型的思路在表面上虽然和s h a n n o n 、h u f f m a n 等人 开创的统计学方法大相径庭，但在效果上一样可以逼近信息熵的极限。而且，可 以从理论上证明，l z 系列算法在本质上仍然符合信息熵的基本规律。 l z 7 7 算法的压缩速度相当慢，为了改进l z 7 7 算法的性能，j m a e ss t o r e r 和 t h o m a ss z y m a n s k i 与1 9 8 2 年提出了l z s s 算法m 】，目前应用较广的采用滑动窗 口技术的压缩算法多是l z s s 或其变种。 1 9 8 4 年6 月，t e r r yw e l c h 在“i e e ec o m p u t e r 上发表了题为“at e c h n i q u e f o rh i g h p e r f o r m a n c ed a t ac o m p r e s s i o n ( 高性能数据压缩技术) 的论文【4 ，描 述了他对l z 7 8 算法的实现，该算法被称为l z w ，目前绝大多数的使用压缩软 件，如w i n z i p 、p k z i p 、z l i b 、a r j 等，都是基于l z 7 7 或l z 7 8 算法的。 对各种语言、音频、图片和视频信号的实用的压缩技术，更多地得益于数字 信号处理( d s p ) 、时间序列分析、参数估计、离散变换、模式识别、自适应技 术以及感知生理一心理学的理论进展。图像编码直接借鉴了语音压缩的许多成熟 技术。1 9 6 6 年奥尼尔对比分析了d p c m 和p c m 并提出了用于电视的实验数据， 1 9 6 9 年进行了线性预测编码的实际实验，此后，出现了各种改进的帧内和帧间 线性预测编码方法和自适应预测编码方法。1 9 7 5 年以来，有人通过测量电视图 像中运动物体的位移来进行帧问预测，结果使数据率进一步降低。这一方法不仅 用于电视传输提高了图象质量，也可用于可视电话和会议电视。 为了在全世界范围内促进数据压缩技术的应用，1 9 8 0 年以来，国际标准化 组织( i s o ) 、国际电工委员会( i e c ) 和国际电报电话咨询委员会( c c i t t ) 陆续完成了各种数据压缩与通信的标准与建议。如： 在二值图象、传真机方面，有c c i t tt 4 、t 3 0 、t 8 0 及i s 0 11 5 4 4 ( j b i g ) 标准等。 在语音编码方面，有c c i t rg 7 2 1 、g 7 2 2 、g 7 2 8 标准等。 在文本、图形和曲线方面，有c c i t tt 1 0 1 、t 1 5 0 标准等。 在静止图象方面，有c c i t tt 8 1 及i s 0 1 0 9 1 8 ( j p e g ) 标准等。 在运动图象方面，有c c i t th 2 6 1 及i s o 的m p e g 标准等。 这些标准的建立不仅推进了数据压缩技术的实用化、产业化，同时也进一步 促进了数据压缩领域的研究的开展。 2 3 数据压缩理论 2 3 1 离散无记i z 信源的熵 信息由一系列的随机变量所代表，并往往用随机出现的符号所表示，我们称 输出这些符号的源为信源。由信号源输出的随机符号，如果耿值于某一连续区间， 就称为连续信源；如果取值于某一离散集合，就叫做离散信源；如果随机符号的 一部分取值于连续区间，一部分取值于离散集合，则称为混合信源。一般的，信 源所发出的消息是一个随机过程，它是时间与空间的函数【4 2 1 。如： 语言信号时间函数x ( t ) ； 12 静止平面图像空间函数x ( x ，y ) ； 电视信号时间空间函数x ( x ，y ) ； 电报信号时间离散信号； 文本信号空间上离散的符号序列； 如果用大写字母x 表示随机变量，小写字母t 表示随机变量的一个实现，则 一个离散记忆信源的输出可以用序列集合 x ；t = o ，1 ，2 ，) 来表示，集合中每个字符取自字母表( 有限符号集合) a m = a l ，a 2 ，a 3 ，a 。) 中的一个，字母表的元素叫做字母或字符。若一张表含有m 个不同的字母， 就说该表的大小为m 。 若取t 为有限数n ，则信源可以用n 维随机矢量来表示，即： x = ( x l ，x 2 ，x 。) ，x a ： 这里的a ：l 是a m 中各元素的n 重笛卡尔乘积，总共有m 。中可能的组合。其 中每一个都叫做长为n 的源字。 用p t ( x ) 表示n 维随机变量 x 。= ( x t l ，x 1 2 ，x 恤) x 。a ： 的概率，并记为： t + k ( t l + k ，t 2 + k ，t 。+ k ) 若对于任意整数k 与n ，所有的x a ：都满足 p t + 。( x ) = p 。( k ) 则称此信源为平稳信源，此时上式的下标t 可以省去，若对任意x a ：， 又有关系式 p ( x ) = 兀p ( x 。) x t a m 成立，则此平稳信源又称为离散无记忆信源( 常记做d m s ) 。 对于离散无记忆信源，我们记字符a 出现的概率为 1 3 p ( a j ) 2p j ， j = 1 , 2 ，3 ，m 那么必然有： 0 p ：1 p j = l j = l 则字符a j 出现的自信息量定义为 i ( a j ) = 一l o g ，p j 当对数的底r 取大于1 的整数时，则自信息量单位称为r 进制信息单位，当 r = 2 时，相应的单位为比特，若m = 2 r ，各字符以等概率出现，则有 i ( a j ) = - l 0 9 2 ( 2 求) = r ( b i t ) 此时称为r b i t 长的二进制码字包含有r b i t 的自信息量。 自信息量i ( a j ) 的实际含义是：随机变量x 取值为a j 时所携带信息的度量。 对自信息量的概率取平均值，即随机变量i ( a j ) 的数学期望，叫做信息熵或简称 熵( e n t r o p y ) ，记为 h ( x ) = p j i ( a j ) = 一p j l o g ：p j 单位为b i t