（电路与系统专业论文）基于PDA的电能表现场校验系统中数据压缩与区域划分算法的研究[电路与系统专业优秀论文].pdf

浙江大学硕士学位论文 y 8 3 417 3 摘要 电能表现场校验是对用电点现场的电能表进行检定以保证其正常运行而进 行的工作，集现场校验与内部管理于体，是电力计量部门最重要的任务之一。 随着现代通信技术和信息管理技术的飞速发展，尤其是无线通信技术的发展- 原有的手工校验方式亟待变革，需要向自动化、规范化方向发展。 本文设计了基于p d a 的以无线通信技术为依托的电能表现场校验系统，并 对系统中使用的关键算法进行了研究与改进。 首先，本文通过分析数据压缩的原理，针对校验数据帧的实际特征，选择 了以动态哈夫曼编码为基础的压缩方式，结合l z w 算法的思想，对压缩算法 进行了改进，使其更适合于短数据的压缩，把其应用在现场校验的g p r s 数据 传输中。 其次，本文研究并提出了一种简单实用的区域划分算法，把它应用于计划 制定过程中，并取得了良好效果。 另外，本文设计实现了蓝牙与红外转换采集接口，充分利用了p d a 的无线 特性，使得现场数据采集更加方便快捷，并克服了p d a 底座经过长期插拔容易 损坏的缺点。 最后，本文对整个系统的软硬件设计与实现进行了详细的介绍，并对系统 性能进行了测试分析，系统性能良好。该系统利用了现代的信息管理技术，可 以作为计量信息管理系统的一个雏型。 关键词；p d a ，g p r s ，数据压缩，区域划分，蓝牙 浙江大学硕士学位论文 a b s t r a c t e l e c t r i c - p o w e r m e t e ff i e l d - c h e c k o u ti sa t a s ko fc h e c k i n ge l e c t r i c p o w e r - m e t e r r u n n i n go nt h ep o w e rf i e l dt oa s s u r ei tw o r k i n gw e l l ，w h i c hi n c l u d e sf i e l d c h e c k i n g a n di n t e r n a lm a n a g e m e n t 。i t so n eo ft h em o s ti m p o r t a n tt a s k so fe l e c t r i cp o w e r m e a s u r e m e n td e p a r t m e n t w i t ht h ed e v e l o p m e n to f t h em o d e mc o m m u n i c a t i o na n d i n f o r m a t i o nm a n a g e m e n tt e c h n o l o g y ，e s p e c i a l l yw i t ht h ew i r e l e s sc o m m u n i c a t i o n t e c h n o l o g y ，o l dw a y so fe l e c t r i c - p o w e r - m e t e rf i e l d - c h e c k o u tm u s tb ei n n o v a t e df o r m o r ea u t o m a t i ca n dn o r m a t i v e t h i st h e w sh a sd e s i g n e da l le l e c t r i c p o w e r - m e t e rf i e l d - c h e c k o u ts y s t e mb a s e d o np d aa n dw i r e l e s sc o m m u n i c a t i o nt e c h n o l o g y ，a n ds t u d i e dt h ek e ya l g o r i t h m s u s e di nt h i ss y s t e m ，a n dt h e np r o p o s e di m p r o v e ds c h e m e s f i r s t ，t h i st h e s i sa n a l y s e st h ep r i n c i p l e so fd a t ac o m p r e s s i o na n dp r o p o s e san e w d a t ac o m p r e s s i o na l g o r i t h m ，w h i c ht a k e sp r a c t i c a lc h a r a c t e r i s t i c so fd a t af r a m ei n t o a c c o u n ta n dc o m b i n ed y n a m i ch u f f m a nc o m p r e s s i o nc o d ew i t l ll z w , a n da c q u i r e s b e t t e rp e r f o r m a n c ef o rs h o r td a t a 矗 a m ec o m p r e s s i o n t h i sa l g o r i t h mh a sb e e n a p p l i e di n t ot h eg p r sd a t ac o m m u n i c a t i o ni nt h ef i e l d - c h e c k o u t s e c o n d ，t h i st h e s i sp r o p o s e sas i m p l eb u te f f i c i e n td o m a i nd e c o m p o s i t i o n a l g o r i t h ma n dp u t si ti n t ou s e i nc h e c k o u tt a s k sa r r a n g e m e n tp r o c e s s t h i r d ，t h i st h e s i sd e s i g n sab h i e t o o t h i r d ac o n v e r s i o ne q u i p m e n t , w h i c h t a k e s f u l la d v a n t a g eo fw i r e l e s sc h a r a c t e r i s t i c so fp d aa n dm a k e sf i e l dd a t ac o l l e c t i o n m o r ec o n v e n i e n t m e a n w h i l e ，i to v e r c o m e sp d a ss h o r t c o m i n go fb e i n gp r o n et o d a m a g ea f t e rf r e q u e n ti n s e r t i n g - a n d d r a w i n g l a s t ，t h es o r w a r ea n dh a r d w a r ed e s i g na n di m p l e m e n t a t i o no ft h es y s t e mi s i n t r o d u c e di nd e t a i l ，a n dt h es y s t e mp e r f o r m a n c eh a sb e e nt e s t e d , a n dt h er e s u l t s h a v es h o w nt h a ti tp e r f o r m sv e r yw e l l t h i ss y s t e ma d o p t sm o d e mi n f o r m a t i o n m a n a g e m e n tt e c h n o l o g y , a n d t h e nc a nb ear u d i m e n to ft h e m e a s u r e m e n t i n f o r m a t i o nm a n a g e m e n ts y s t e m k e y w o r d s ：p d a ，g p r s ，d a t ac o m p r e s s i o n ，d o m a i nd e c o m p o s i t i o n ，b l u e t o o t h 2 浙江大学硕士学位论文 1 1 课题背景 第一章绪论 电能表是专门用来测量电能累积值的一种表计，广泛地分布在电力系统发、 供、用电的各个环节中，为合理计收电费及经济核算提供了最有力的依据。鉴于 电能表的特殊性及重要性，对运行中的电能表，特别是用于大电力用户和关口计 量的电能表，必须定期进行现场监督校验，并且对新装和拆换的电能表进行现场 复核校验。这是中国电力部门一直严格贯彻执行的制度，也是国家规定的强制检 定项目。 长期以来，电力系统电能表现场校验工作一直沿用手工帐簿式校验方式， 所有需要校验的用户和电能表的信息用手工记录在记录本中，并在现场手工把 校验数据抄送回来，由于现场校验仪的精密度高，操作复杂，不但导致数据抄 送错误经常发生，而且导致现场校验仪由于错误操作等寿命减短甚至损坏。另 外，造成查阅繁琐，统计困难，一些细节的统计结果根本无法得出。这种手工 式电能表现场校验方式大大浪费了人力物力，效率低下，革新现场校验工作的 方式，充分利用现有的各类新技术，实现现场工作的自动化、无纸化操作，统 计工作的简单化、直观化，把工作人员从复杂的统计报表中解脱出来成为亟待 解决的问题。 再者，现场校验人员在校验现场采集完数据后，如果要判断电能表是否有 接线错误或电能表是否故障，只能根据以往的人工经验进行判断，尝试解决。 这样的工作模式不但浪费时间和精力，而且往往不能彻底解决问题，只能等回 去后查找各种资料找到解决方案后再返回现场，大大的增加了现场校验人员的 工作强度和工作量。因此，在现场能够快速而准确的对故障进行诊断，得到正 确的解决方案也是非常有必要的。 另外，由于校验点的档案信息( 包括校验点的位置信息等) 都是以纸质文件 保存，在制定年校验计划时的不能很好兼顾全局，基本上只能靠以往的经验，位 置相近的一些用户往往可能会被安排到不同的时间去校验。这样，同一地区的用 户可能需要校表人员重复去多次才能全部校验，无形的增加了校表人员的工作强 浙江大学硕士学位论文 度。所以校表人员希望能在保证每天工作量一定的前提下，把位置靠近的用电点 尽量安排在同一天，避免了同一区域的用电点多次盲目的校验，尤其是对于交通 不方便的偏远地区和山上的校验点，更加有必要。这样不但节省了交通费用，而 且能够大大提高校表效率和减少校表人员的工作量，也利于对校表结果的管理。 1 2 国内外的研究现状 电能表现场校验系统中的主要问题之一是设计出适合现场无线数据传输的 数据压缩算法和适合任务制定的区域划分算法。而目前国内外市场上还没有厂 家提供电能表现场校验的系统解决方案，其架构的设计及系统难点的分析都是 一个崭新的课题。因此，只能通过研究分析校验数据的特征和任务制定的具体 流程，结合现在通用的算法，对其进行改进，以期符合我们的要求。 数据压缩算法经历了哈夫曼编码、算术编码到l z 7 7 、l z w 的演变“3 ，现代流 行的通用软件如g z i p 等是首先使用l z 7 7 算法进行压缩，对得到的结果再使用 h u f f m a n 编码的方法进行压缩，而j p e g 、m p e g 的实现中利用了哈夫曼编码和游 程编码。3 。可见，对于不同的应用场合，需要采取不同的压缩方案。而目前数 据压缩算法的研究一般集中在通用数据压缩领域，针对性不强，因此，要想在 某一特殊应用领域取得大的压缩率，就应该充分考虑数据格式的特征，综合各 种因素来采用最适合的压缩算法。 通常区域划分主要有空间聚类算法和有限元区域划分算法等。比较有代表性 的有k n n 算法( k - n e a r e s tn e i g h b o ra l g o r i t h m ) 、贪婪算法( g r e e d ya l g o r i t h m ) 、 a n p ( a i - n a s r aa n dn g u y e n sp a r t i t i o n i n g ) 算法o3 。这些算法实现困难，时间 复杂度高，而且实际应用中多有限制。因此需要设计特殊的适合实际情况的区域 划分算法。 1 3 本文的主要研究内容 本文通过系统分析和研究电能表现场校验的业务流程和需求，结合通信技 术和信息管理技术，提出了现场校验的系统架构，研究设计了适合校验数据特 征的数据压缩算法，用于g p r s 传输，提出了适合实际应用的区域划分算法，应 用于任务制定。最后对整个系统进行了实现。 浙江大学硕士学位论文 现场校验过程中，当需要错误接线诊断时或者需要现场下载任务、上传校 验结果时，需要利用g p r s 进行传输。由于下载和上传的数据帧有几k 的大小， 如果长久使用后，通信费用也是比较可观的。为了减少通信费用，我们结合数 据压缩算法和数据帧的特征，提出了一种适合短数据帧的数据压缩算法。实践 证明，这种算法在通用数据压缩方面与l z w ，f g k 等算法相比毫不逊色。对于本 系统使用的特殊数据帧更是有很好的压缩效果，是l z w 等算法不能相比的。 为了提高校验人员的单位时间的工作效率，提出了一种区域划分算法，把 它应用于校验计划的生成和分派，在保证每天工作量一定的前提下，把位置靠 近的用电点的校表任务尽量安排在同一天，使总体工作量明显下降。 为了采集数据的方便，我们设计了一个远红外串口与蓝牙采集转换接口。 在现场校验的过程中，现场的数据采集和处理保存和通信等通过p d a 来进行。 其中校验仪的数据可以通过串口采集，而电能表的数据必须通过红外进行采集。 因为p d a 上的红外是近红外波段，而电能表的红外是远红外波段，所以二者不 能直接通信。如果在p d a 端加上一个近红外转换成远红外的模块，就必须做到 模块的外形和大小等必须和p d a 的大小相匹配，这样的话，对不同型号和大小 的p d a 必须设计不同的外形模板，不能做到通用，所以最后考虑利用蓝牙技术。 采集电能表数据时只须把采集转换接口挂在电能表上，就能实现与p d a 方便的 通信，不用像掌机抄电表数据那样保证两端红外对牢；采集校验仪数据时，只 须把采集转换接口的串口与校验仪相接，p d a 端就能方便的采集到数据。这样 不但操作简单，而且能做到通用化。再者，p d a 一般经过串口从工作站下载校 验任务，因为p d a 的底座接口不是非常牢固，经过长时间的插拔使用之后，底 座就会损坏。当设计好蓝牙与串口转换模块之后，只须把转换模块插到p c 的串 口上，p d a 完全采用无线进行通信，延长了p d a 的使用寿命，节约了成本。 1 4 本文的组织结构 第二章介绍了数据压缩技术和区域划分的基本概念。 第三章提如了一种改进的数据压缩算法，对其进行了理论分析和试验验证， 适合短数据的压缩。并提出了一种区域划分算法，对其进行了试验验证。 第四章介绍了电能表现场校验系统的设计框架，并介绍了在数据通信、现 浙江大学硕士学位论文 场校验中的关键模块设计。 第五章介绍了电能表现场校验系统主要功能模块的具体实现，以及对系统 的调试和运行结果的测试。 第六章对本文研究内容进行了总结与展望。 4 新江大学硕士学位论文 第二章数据压缩与区域划分的基本概念 2 1 数据压缩技术 2 1 1 数据压缩简史 现实中大多数信息的表达都存在着一定的冗余度，通过采用一定的模型和 编码方法，可以降低这种冗余度。s h a n n o n 提出了最早的对符号进行有效编码 从而实现数据压缩的s h a n n o n - f a n o 编码方法。 数据压缩在商业程序中实现并被应用在技术领域足从h u f f m a n 于1 9 5 2 年 发表的论文“最小冗余度代码的构造方法”( am e t h o df o rt h ec o n s t r u c t i o n o f m i n i m u m r e d u n d a n c yc o d e s ) 开始的。u n i x 系统上一个压缩程序c o m p a c t 就 是h u f f m a n0 阶自适应编码的具体实现。8 0 年代咀前，数据压缩领域几乎一 直被h u f f m a n 编码及其分支所垄断。 8 0 年代，数学家们从新的角度入手，遵循h u f f m a n 编码的主导思想，设 计出另一种更能接近信息论中“熵”极限的编码方法算术编码。可以证明， 算术编码得到的压缩效果可以最大地减小信息的冗余度，用最少量的符号精确 表达原始信息内容。但是要实现和运行算术编码，需要更为艰苦的编程劳动和 更加快速的计算机系统。在同样的计算机系统上，算术编码虽然可以得到很好 的压缩效果，但却要消耗也许几十倍的计算时间。因此算术编码不能够应用于 实际。 j a c o bz i v 和a b r a h a ml e m p e l 发表的论文“顺序数据压缩的一个通用算 法”( au n i v e r s a lm o g r i t h e mf o rs e q u e n t i a ld a t ac o m p r e s s i o n ) 和“通过 可变比率编码的独立序列的压缩”( c o m p r e s s i o no fi n d i v i d u a ls e q u e n c e sv i a v a r i a b l er a t ec o d i n g ) 中提出了一种新的压缩技术一一l z 7 7 和l z 7 8 。这种 压缩方法的思路完全不同于从s h a n n o n 到h u f f m a n 到算术压缩的传统思路， 基于这一思路的编码方法称作“字典”式编码。字典编码对于好的实现，其压 缩和解压缩的速度异常惊人。兑后，t e r r yg e l c h 发表了名为“高性能数据压 缩技术”( at e c h n i q u ef 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 ) 的论文，提 缩技术”( at e c h n i q u ef o rh i g hp e r f o r m a n c ed a t ac o m p r e s s i o n ) 的论文，提 浙江大学硕士学位论文 第二章数据压缩与区域划分的基本概念 2 。1 数据压缩技术 2 1 1 数据压缩简史 现实中大多数信息的表达都存在着一定的冗余度，通过采用一定的模型和 编码方法，可以降低这种冗余度。s h a n n o n 提出了最早的对符号进行有效编码 从而实现数据压缩的s h a n n o n - f a n o 编码方法。 数据压缩在商业程序中实现并被应用在技术领域是从h u f f m a n 于1 9 5 2 年 发表的论文“最小冗余度代码的构造方法”( am e t h o df o rt h ec o n s t r u c t i o n o fm i n i m u mr e d u n d a n c yc o d e s ) 开始的。u n i x 系统上一个压缩程序c o m p a c t 就 是h u f f m a n0 阶自适应编码的具体实现。8 0 年代以前，数据压缩领域几乎一 直被h u f f m a n 编码及其分支所垄断。 8 0 年代，数学家们从新的角度入手，遵循h u f f m a n 编码的主导思想，设 计出另一种更能接近信息论中“熵”极限的编码方法算术编码。可以证明， 算术编码得到的压缩效果可以最大地减小信息的冗余度，用最少量的符号精确 表达原始信息内容。但是要实现和运行算术编码，需要更为艰苦的编程劳动和 更加快速的计算机系统。在同样的计算机系统上，算术编码虽然可以得到很好 的压缩效果，但却要消耗也许几十倍的计算时间。因此算术编码不能够应用于 实际。 j a c o bz i v 和a b r a h a ml e m p e l 发表的论文“顺序数据压缩的一个通用算 法”( au n i v e r s a la l o g r i t h e mf o rs e q u e n t i a ld a t ac o m p r e s s i o n ) 和“通过 可变比率编码的独立序列的压缩”( c o m p r e s s i o no fi n d i v i d u a ls e q u e n c e sv i a v a r i a b l er a t ec o d i n g ) 中提出了一种新的压缩技术一一l z 7 7 和l z 7 8 。这种 压缩方法的思路完全不同于从s h a n n o n 到h u f f m a n 到算术压缩的传统思路， 基于这一思路的编码方法称作“字典”式编码。字典编码对于好的实现，其压 缩和解压缩的速度异常惊人。其后，t e r r yw e l c h 发表了名为“高性能数据压 缩技术，( at e c h n i q u ef 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 ) 的论文，提 浙江大学硕士学位论文 出了l z w 算法。l z w 继承了l z 7 7 和l z 7 8 压缩效果好、速度快的优点，而且 在算法描述上更容易被人们接受，实现也比较简单。u n i x 上c o m p r e s s 程序就 是使用l z w 算法的。该程序性能优良，很快成为了u n i x 世界的压缩程序标准。 目前，基于字典方式的压缩已经有了一个被广泛认可的标准，z i p 格式成为了 事实上的标准。 对声音、图像、视频等多媒体信息的压缩有两条思路，要么采用成熟的通 用数据压缩技术进行压缩，要么根据媒体信息的特性设计新的压缩方法。事实 上，人们在两条道路上都作了卓有成效的探索。 比较有代表性的是g i f 格式。它可以把原始图形文件以非常小数据量存储， 可以在同一个文件中存储多幅图像从而实现动画效果。g i f 中的图像也是使用 l z w 方法压缩的。g i f 是使用通用压缩技术压缩图像信息的最成功的例子，当然， g i f 文件中除了经过l z w 压缩的像素信息以外，还保存有图像的各种属性信息 以及图像所使用的调色板信息等。g i f 精确地保窝了原始图像的每一个像素信 息，是无损图像压缩的代表。 8 0 年代初，人们逐渐意识到，对于图像和声音文件，没有必要忠实地保留 其所有信息，在允许一定的精度损失的情况下，可以实现更为有效的压缩方法。 国际标准化组织( i s o ) 和c c i t t 联合组成了两个委员会：静态图像联合专家 小组( 3 p e g ) 和动态图像联合专家小组( m p e g ) 。j p e g 的压缩目标是静止图像 ( 灰度的和彩色的) ，m p e g 的目标则是声音和视频。但他们的基本思路是完全 一样的，即保留媒体信息中最有规律、最能体现信息主要特征的数据，而略去 其他不重要的数据。他们都取得了令人赞叹的成就。 2 1 2 数据压缩的概念与应用 随着计算机和通信技术的发展，数据压缩的研究受到人们越来越多的关注。 尤其是多媒体技术的兴起，更加促进了有关理论和技术的研究与开发，并使之应 用于工程实践。多媒体计算机技术的关键问题之一是实时地处理语音、图像和文 本等有关数据。需要解决的一个重要的问题是大量数据的存储、处理和传输。数 据压缩技术就能比较有效地解决这个问题。 数据压缩最初是作为信息论研究中的一个重要课题，在信息论中被称为信源 浙江大学硕士学位论文 编码。它主要研究数据的表示、传输和转换的方法，目的是减少数据所占据的存 储空间和传输时所需用的时间。例如，在通讯系统中为了能在存储设备容量、信 道带宽、或通讯链路容量等资源有限的情况下，通过采用适当的编码技术，可以 大大减少数据所占的存储空间，从而可以达到降低成本、提高工作效率的目的。 数据压缩的原始数据经过压缩处理后输出就是被压缩的数据。当这些数据所 占的存储空间和传输中所用时间的开销小于原始数据时，即实现了数据压缩。在 需要使用这些数据时，只要经过解压缩处理即可。这种数据压缩解压缩模块可 以通过软件方式来实现，也可以使用综合了一种或多种压缩技术的专用硬件设备 来实现。数据压缩的应用很广泛，如文本压缩、图像压缩、数据库压缩、电视信 号的压缩以及传输信号的压缩等。 2 1 3 数据压缩的分类 根据不同的编码对原始文件数据产生不同的损失效果，可把压缩技术分为有 损压缩和无损压缩两大类”。 在有损压缩( 熵压缩) 的过程中，会损失掉一部分信息( 即损失了信息熵) 。这 样在还原压缩文件时就无法做到无失真地再现被压缩的数据。它的压缩率比较 高，代价是丢失了部分信息，引起了信号的失真。当然，为确保还原后的数据能 基本保持原数据的特征，这种失真应被限制在某个规定的范围内。熵压缩主要用 于图像和语音数据的压缩。 无损压缩的原理是尽量除去数据中重复和冗余的部分，而不丢失其中的任何 信息，从而确保压缩了的数据还原后与压缩前完全一致。因此可逆压缩又称为无 失真编码( n o i s e l e s sc o d i n g ) 。这种压缩方法主要用于文本、程序文件等不允许 出现任何数据失真的场合。 熵压缩在采用失真压缩处理之后，最后又常常归结到采用无损压缩编码技 术，所以本文主要是对无损压缩模式下的算法进行研究，即我们通常所谓的文本 压缩。 无损压缩又可分为：基于统计模型的压缩和基于字典模型的压缩。 统计模型的工作原理是：首先对数据整体所采用的符号作统计，再将出现次 数高即重复性大的符号用短码表示，重复性小的用长码表示。最典型的代表是 7 浙江大学硕士学位论文 h u f f m a n 编码和算术编码。 一无损压缩 卜 ：统计压缩i ，磊磊磊蟊1 l ：。：l p l 游植犏码i l 三_ 二1 。l ，| j 纛丽习 l _ ：_ _ 量三兰翌型 卜， 一 | ：； 善嫡压缩l 舡| | i 弭测编码i l 二_ _ 二二一l _ _ 二_ 二二_ 厂 争 变换编码l 图2 - 1 数据压缩的分类 字典式模型的工作原理是：从一个空的符号串表出发，然后在编、解码过程 中逐步生成表中内容，我们称之为自适应压缩模式。这种编码模型只需扫描一次 数据，无需有关数据统计量的先验信息，运算时间正比消息的长度。其典型算法 为l z 系列算法。 2 1 4 几种数据压缩的原理 由于本文的应用是针对与数据的无损压缩，所以只介绍无损压缩的常用算 法。 统计编码主要包括哈夫曼编码( h u f f m a nc o d i n g ) 、游程编码( r u n l e n g t h c o d i n g ) 、算术编码( a r i t h m e t i cc o d i n g ) 等。 2 i 4 1 哈夫曼编码( h u f f m a n ) 哈夫曼( d a h u f m a n ) 于1 9 5 2 年提出一种编码方法，它完全依据字符出现的 概率来构造平均长度的最短的异字头码字，有时被称为最佳编码。其主要方法是 8 浙江大学硕士学位论文 对于出现次数高即概率大的符号用较少的位数来表示，而对于出现概率小的符号 用较多的位数来表示。其编码效率主要取决于需编码的符号出现的概率分布，分 布越集中则压缩比越高。 h u f f m a n 编码步骤如下“”： ( 1 ) 将各个符号及其出现频率分别作为不同的小二叉树( 目前每棵树只有根 节点) 。 ( 2 ) 在( 1 ) 中得到的树林里找出频率值最小的两棵树( 即两个节点) ，其根 节点权值为频率值。将他们分别作为左、右子树连成一棵大一些的二叉树。该二 叉树根节点的权值为两棵子树权值之和。我们得到一个新的树林； ( 3 ) 对上面得到的树林重复( 2 ) 的做法，直到所有字符都连入树中为止。 这步完成后，就得到了一颗哈夫曼树； ( 4 ) 生成哈夫曼树之后，从树根遍历到每个叶子节点，树的左右分枝上赋值 o s n l ，得到的一个二进制序列即哈夫曼编码； 译码的过程是，分解原文中字符串，从根结点出发，按字符0 或1 确 定访问子结点的路径，直至叶结点，便求得该子串相对应的字符。 上述的h u f f m a n 编码称为静态h u f f m a n 算法，它利用压缩对象中字符出现频率 的概率进行编码，是一种常用的无损数据压缩方法。不论从算法的复杂度还是在 实现的难度以及对数据压缩的效果来看，h u f f m a n 编码都不失为一种较好的数据 压缩算法。但是静态h u f f m a n 编码压缩方法存在明显不足，即需要对原文件进行 两遍扫描：第一遍扫描对文件字符出现的频率进行统计，利用得到的频率值构造 h u f f m a n 树并保存树的结构信息。这个树的结构信息要在解压缩时使用；第二遍 扫描根据前面得到的h u f f m a n 树对原始数据进行编码，并保存编码信息。这种重 复扫描的方式明显影响了压缩编码的效率，特别是在网络传输中将引起较大的延 迟，破坏网络传输的同步性。对于大文件的压缩，重复扫描引起的额外的磁盘访 问将严重降低该算法的执行速度。另外，它需要将h u f f m a n 树的结构信息随压缩 数据传输，对短数据压缩很不利：所以提出了动态h u f f m a n 算法，它可以解决静 态哈夫曼编码速度慢和必须传输h u f f m a n 树的缺点。 动态h u f f m a n 算法的基本思想是 9 1 ，用前面n 个字符的频率来编码第n + 1 个出 现的字符。由于第n 个字符编码之后，第n + 1 个字符对应的字母频率改变了，因此必 浙江大学硕士学位论文 须调整h u f f m a n 树才能使之符合哈夫曼树的定义。h u f f m a n 树的调整分为两种情 况： ( i ) 第n + 1 个字符的字母在啥夫曼树中还没有出现； ( i i ) 第n + 1 个字符的字母已出现在哈夫曼树中。 根据啥夫曼树的定义，一个具有p 个叶子节点的二叉树是哈夫曼树的充要条 件慰1 4 】： ( 1 ) 每个叶子节点有非负的重量w ，w 2 w r ，每个内部节点的重量是其孩 子重量之和； ( 2 ) 节点按非负的重量的大小顺序来编号所以对于l j p i ，节点2 j 一1 和 2 j 是兄弟，它们的双亲具有更大的编号。节点的编号对应哈夫曼算法中节点合并 的顺序，如节点1 和节点2 首先合并，然后是3 和4 ，再是5 和6 ，等等。 图2 2 在啥夫曼树中插入一个已存在的节点 假设已经有一鸬= q ，a 2 ，口f ) 共t 个字符已经处理，下一个字符q + 1 将按前t 个字符构造的h u f f m a n 树编码和解码，现在的主要问题是如何快速修改这 棵树，以得到一棵以+ l 的h u f f m a n 树。对于问题( i i ) ，如图2 2 ( a ) ，这时t = 3 ， 浙江大学硕士学位论文 q 。= b 。只是简单地在q + 1 所在的字母节点及其所有祖先节点的重量加1 显然是 不够的，因为其结果不是h u f f m a n 树。将违背上述的充要条件( 节点4 大于节点5 的重量) 。可以用一个两阶段的过程来处理。首先，将从的h u f f m a n 树作如下调 整：从q + l 所在的字母的节点开始，以此节点作为当前节点，连同子树一起与同 重量的最高序号的节点进行交换，然后以此节点的双亲作为当前节点，重复这个 过程，直到树根。这样得到的树仍然是h u f f m a n 树，如图2 2 ( b ) 。接着，从q + 1 所 在字母节点开始，对它及其祖先的重量加1 ，就得到鸬+ 1 的h u f f m a n 树。如图 2 2 ( c ) 。 对于问题( i ) ，我们用一个0 节点代替树中还没有的字母如果q + l 这个字 字母还没有出现在h u f f m a n 树中，我们用0 节点对q + 1 进行编码，后跟一些多余的 字符以区别那些还没有编码的字母( 一般是字符的a s c i i 码) 。在调整h u f f m a n 树方面，如图2 3 ，先将0 节点作为双亲再创建两个叶子为它的孩子其中左 孩子继续作为0 节点，右孩子为新的q + 1 这个字符的字母节点。然后同解决问题 ( i i ) 的方法一样，对整个啥夫曼树进行更新。如下图，对字符串a b c d 进行编码， 图2 3 ( a ) 表示在字符d 被处理之前，d 的码用0 节点的码表示，即1 0 0 ，图 2 3 ( b ) 表示字符d 被处理后，更新过的哈夫曼树。 图2 3 在啥夫曼树中插入一个不存在的节点 2 1 4 2 游程编码( r l c ) 基本的r l c 压缩方法最初出现在i b m3 7 8 0b i s y n c 通信协议中，如下图所示。 浙江大学硕士学位论文 图2 4 基本的r c l 数据结构 其中x 代表数据字符，品是一个在数据集合 ) 中不用的字符，即品不属 于 x ，表示有一个字符串在此起“异字头”作用，月三则代表串( 游程) 的长度， 也即字符重复出现的次数。由此可知，只有当r 3 ，才有数据压缩效益。于是编 码时要先判断r l 值，在决定是否做r l c ；而解码时则需要根据紧跟每一x 后的码 子是否为毋，再决定其下一个字的含义。 我们知道，游程编码是将信源符号序列中的相同字符转换成一个计数字段再 加上一个重复字符标志。这种方法对二值图像最为有效，对数据文件就不那么明 显，而对于课文压缩己无实用价值。 2 1 4 3 算术编码( a c ) 与哈夫曼编码和游程编码不同，算术编码跳出了分组编码的范畴：从全序列 出发，采用递推形式的连续编码【1 0 】。将单个信源符号根据出现的概率映射到实数 轴( 0 ，1 ) 区间内的一个小区间，其长度等于该序列的概率；再在该小区间内选 择个代表性的二进制小数，作为实际的编码输出，从而达到了高效编码的目的 b o 。算术编码的实现有两大缺陷：一个是很难在具有固定精度的计算机上完成无 限精度的算术操作；另一个缺陷是高度复杂的计算量不利于实时应用。主要用于 t b i g 图像压缩标准。 2 1 4 4 字典压缩 字典模型并不直接计算字符出现的概率，而是使用一本字典。其主要方法是 将已经编码过的信息作为原字典，如果需要编码过的信息曾经出现过，就输出该 字符串的出现位置及长度，否则就输出一个新的字符串。字典压缩模型通常使用 自适应的方式。如果使用静态字典模型方式，首先是适应性不强，其次是必须维护 一个信息量并不箅小的字典，从而影响了最终的压缩效果。以字典压缩模型为主 要思路的算法有l z 7 7 、l z 7 8 和l z w 等几种。l z w 算法压缩的原理在于用字典中词 浙江大学硕士学位论文 条的编码代替被压缩数据中的字符串。l z w 算法可简单描述如下m 3 ： ( 1 ) 字典初始化，使字典中包含所有由单个字符组成的词条，有汉字的情况 下一般为2 5 6 个字符； ( 2 ) 读取输入数据流中的第一个字符作为前缀串s ； ( 3 ) 读取下一个输入字符作为后缀字符c ； ( 4 ) 如果词条s c 不在字典中则转到( 5 ) 执行；把s c 放人s ，回到( 3 ) 执行； ( 5 ) 输出s 的编码，并把s c 存人字典，c 放人s ，回到( 3 ) 执行。 上述算法中( 3 ) 一( 6 ) 循环执行，直到被压缩数据流输人完毕。 解压缩算法刚好是压缩算法的逆过程，也是动态生成一个串表，然后根据读 入的代码将压缩数据还原，其输入流是压缩算法的编码输出流，其输出流是压缩 算法的输入流。 2 1 5 数据压缩算法的分析与比较 算术编码可以更好的接近无损珏缩的熵极限，但其高度复杂的计算量不利于 实时应用；游程编码对二值图像最为有效，对数据文件就不明显；l z w 算法能很 好的压缩重复字符串，逻辑简单、实现速度快，其主要缺点是所需存储空间与输 入串长度成正比，并未真正做到最佳地分析输人数据，从而削弱了它的压缩性能。 哈夫曼编码采用变长码，能很好的利用数据的统计信息，接近信息的熵，而且实 现简单；尤其是动态哈夫曼编码，可以不用传输哈夫曼树，对于少量数据压缩非 常关键。因为本系统要求压缩的数据量不是很大，每帧在几k 左右，所以结合动 态哈夫曼算法和l z w 算法的思想，提出了一种适合本系统的实用的数据压缩算法。 下一章着重介绍算法的思想。 2 。2 区域划分技术 2 2 。l 区域划分算法简介与分析 区域分解法的基本做法是把一个复杂系统( 或区域) 按照一定的原则( 如物 理特性几何形状离散方式算法特点与处理器个数) 分解成若干个子系统( 或子区 域) 。主要采用高效快速迭代方法来求原始问题的解。由于区域往往是大型的不 浙江大学硕士学位论文 规则的，手工子域划分对于这种情形是不现实的，所以寻找一种效果好的区域自 动划分算法是很有必要的。一个好的分割算法应该是普遍的、可以应用于任何形 状的区域，并且区域分解的好坏是一个载荷平衡的问题，关系到求解的效率。 上世纪八十年代，f a r h a t 1 9 1 首先提出网格自动区域划分的设想，并得到了一 些简单的有限元网格自动区域划分的结果。进入九十年代以后人们开始借用图论 的概念试图将有限元网格转换成图对图的结构进行数学的分析如s h a n g - h s i e n l l 9 1 采用的递归谱分析的方法来进行区域分解k a r y p i s 等“”则采用多级分割的技术， 但上述算法也有着明显的缺点，即本身耗用大量的计算时间不能适用于大规模有 限元并行计算任务。 2 2 2 几种典型的区域划分算法 2 2 2 1k 堋算法( k - n e a r e s tn e i g h b o ra l g o r i t h m ) k n n 算法( k - n e a r e s tn e i g h b o ra l g o r i t h m ) 是一种常用的模式聚类算法。但 是目前k - n n 算法和其它基于k n n 算法的聚类算法【2 0 】，如l b g 法( l i n d e ，b u z o ，g r a y a l g o r i t h m ) 2 1 】，都是随机选取聚类中心的，因此几乎不可避免的陷入局部最优解， 难以获得全局最优解。另外如果采用聚类算法对这种数目庞大的目标点进行分 类，所需的时间将非常可观。 2 2 。2 。2 贪婪算法( g r e e d ya l g o r i t h m ) “9 具体思想如f ； 1 搜索上一子域边界上最小权重的结点m 若是第一个子域则在整个域中搜 索； 2 将结点力相连的且末作标记的单元划分到当前的子域中，然后给这些单 元作上标记，并对其中的结点权重减1 。然后进行递归，直到与当前子域中单元 相连的单元都并入到当前子域中； 3 如果经过2 的划分，当前子域的单元数目已经达到要求，则进行下一个子 域的搜索；然后检查是否已经搜索完整个域，如果没有则回到1 重新开始搜索； 4 输出结果。 1 4 浙江大学硕士学位论文 算法要求事先将每个子域所要承担的单元数计算出来，各个子域应该包含差 不多的单元数。算法由多个循环构成，循环的开始是搜索最小权重结点，然后将 与该结点相连的单元归入当前子域中，同时将结点的权重减1 ，当子域所要求的 单元数满足要求时就终止当前的循环进入到下一个子域的结点搜索。若一个结点 已经分配到某一个子域中它的权重就应该是0 ，所以当完成一个子域的分割时其 内部结点的权重为0 ，丽处在本次搜索范围内的并且权重不为0 的那些结点则为该 子域的边界结点。贪婪算法的实现过程可以用下图来表示。整个过程如同动物在 晴皎它周围的食物是就近的原则因此称之为贪婪算法。 i， 酱 # 皇，。辜 匕 - 图2 5 贪婪算法示意图 2 2 2 3a n p ( a i - n a s r na n dn g u y e n sp a r t i t i o n i n g ) 算法 a n p ( a 1 一n a s r aa n dn g u y e n sp a r t i t i o n i n g ) 算法1 2 2 1 是一个简单而又高效的 有限元区域划分算法，它可以将有限元区域划分成包含指定个数元素的若干区 域，特别适用于多处理器并行处理的情况。该算法在平衡各个区域的工作量，减 少各个区域之间的信息交互都有非常好的表现。 1 根据该结点所连接的单元的数目计算每个结点的初始权重； 2 根据结点的坐标给结点附加权重，这一步是在有限元网格的拓扑结构中 引入几何信息即结点的坐标附加权重为“加2 翠2 l 亡j l 囊三+ 乏三一2 j ，其 中印为结点个数，x 为结点坐标，。、y 。、z 一分别为结点坐标绝对值的最大 值。这里假设总是大于。这一步的目的是鼓励寻找每个目标区域起始点 时能够从短轴方向开始。 浙江大学硕士学位论文 3 找到具有最小非零权重并且不在其他子域边界上的结点n ； 4 将与结点n 相连的未标记的单元及其结点划分到当前子域并将这些结点 的权重减1 ，并对结点进行标记； 5 找到一个具有最小权重的结点并且在当前子域中至少有一个与该结点相 连的末标记的单元； 6 重复4 和5 的过程直到当前子域的单元数满足要求； 7 重复3n 6 的过程直到所有子域都分割完成。 可以看f l s a n p 算法实际上是在贪婪算法的基础上加上了结点的坐标信息所 作的改进。a n p 算法在碰到会有分裂现象的时候它会死循环地搜索最小权重的结 点，这是a n p 算法的一个弱点，有待于进一步改进。 浙江大学硕士学位论文 第三章改进型数据压缩算法与区域划分算法 3