基于Huffman编码与XML的大对象数据交换.doc

基于Huffman编码与XML的大对象数据交换贾长云1 朱跃龙2 张新华3江苏连云港(222069)摘 要：XML作为异构数据交换的标准格式在数据交换平台的建设中得到了广泛的应用，多媒体数据由于其容量巨大在数据库中往往作为大对象数据来保存，因此在异构数据交换中必然涉及到大对象数据交换的问题。本文通过对Huffman编码原理的讨论提出了基于XML使用Huffman编码方式实现大对象数据的交换，并设计了相应的实现模型，对异构数据库大对象数据交换的实现具有一定的借鉴意义。关键词：XML，Huffman，大对象数据，编码0 引言随着计算机处理能力的大幅度提高，多媒体早已经融入到了计算机当中了，如果缺少了多媒体，缺少了各种多姿多彩的图像，音频，视频，很难想象计算机如今会走入千家万户。长期以来，多媒体信息在计算机中都是以文件形式存放，由操作系统管理的，但是随着计算机网络，分布式计算的发展，这种单纯的文件式管理已经力不从心了，对多媒体信息进行高效的管理，存取，查询已经成了一种迫切需求。而关系数据库却有着强大的数据管理能力。两方面密切结合，多媒体数据库由此应运而生。这些多媒体数据往往容量巨大如照片、WORD文档等，因此通常将这些数据称为大对象数据(LOB)。LOB数据基本有两大类：CLOB(字符大对象)与BLOB(二进制大对象)。CLOB主要用于存储超长的文本数据；BLOB则用于存储大量的二进制数据，如图像、视频、音频等。目前几乎所有的关系数据库对LOB数据都有比较强大的支持。如Oracle从8i开始就有了三种LOB数据类型：CLOB、BLOB和NCLOB，其最大存储长度可达4GB。SQL Server 2000对LOB数据的支持也是以三种数据类型实现的：text、ntext、image，其存储的最大长度也可达到2GB。无论是在学校、政府还是企业，都分布着各种各样的应用系统，这些应用系统的后台数据库绝大部分都是基于关系数据库的(如Oracle、SQL Server等)，而且不同的应用系统其后台数据库并不相同。因此，在实际应用中经常要将一个应用系统中的LOB数据交换到另一个应用系统中，往往这两个应用系统的数据库是异构的。当前由于XML格式简单、扩展性强等特点使得它已经成为异构数据交换上事实标准。所以完全可以通过使用XML作为两个异构数据库数据交换的中间格式，实现大对象数据的交换。但是从理论上来说，由于XM文档只能描述文本信息，而LOB数据通常都是以二进制方式来描述的。这样如何在XML文档中完整准确地保存LOB数据所对应的二进制数据是大对象数据交换中必须解决的难题。1 LOB数据转换为XML数据的Huffman编码法当需要在异构数据库之间进行大对象数据交换时，可以先使用以上方法将LOB数据从数据库中读出，然后将其随其它数据一起转换到XML文档，最后再用以上方法写入到目标数据库中。当大对象数据从源数据库读取以后会形成一个二进制数据文件，这些二进制数据文件不能直接存放到XML文档中，必须经过适当的转换。这是因为，其一从严格意义上来说，XML文档中的所有数据都是文本类型的，它并不能识别二进制格式的数据；其二，XML文档从源到目标是要经过编码、解码之类的解析，对二进制数据就会出现错误。因此，要想将二进制数据嵌入到XML文档中，必须先将二进制数据编码成合法的字符集才能嵌入到XML文档中。很显然，在目标端还必须将这些数据解码。2.1 LOB数据转换的常规方法能够实现二进制数据编码的方法有多种方法如直接转换法、Base-64编码法等。(1)直接转换法这种办法是将每一个二进制数据字节转换成两个以十六进制表示的字符。要做到这一点，必须有一个256种可能编码表用于将每个字节变成两个从字符集0-9，a-f而来的字符。编码表如下所示：00,01ef,ff转换以后的XML文档片断如下所示：424d6a8d0f0000000000360400尽管这种方法能够非常简单地将二进制数据转换到XML文档中，但它浪费了网络的带宽。因为，原始二进制文件中的每一个字节，在XML文档中变成了两个字符。在传送很大的二进制数据集时，这一点是非常值得考虑的。(2)Base-64编译法Base-64编码是一种MIME编码方法，可以将二进制数据映射成ASCII码的子集，它应用已经有很长时间了。开始它主要用于电子邮件的编码。Base-64编码(RFC2045)使用一个64个字符的子集(包括A-Z、a-z、0-9、+和/)来表示二进制数据，并使用“=”来进行填充。这种编码算法每次处理3个字节序列的字节流，每3个字节序列被解析如图1所示的4个6位的数据单元。每个6位被用作为映射表(Base-64字母表)的索引，以获得相应数据的编码字符。图1 Base-64编码转换示意图这种方法的好处是将三个数据字节编码成4个字符，这样形成的编码文档比原始文档只大了33%。前一种方法每个字节产生2个字符，而这种方法每个字节只生成1.33个字符。另一个好处是它已经被广泛应用了很长时间，在因特网上有很多免费的实现工具。经过Base-64编码转换后的二进制文档片断如下所示：Qk1qjQ8AAAAAADYEAAAoAAAAkgUAAMkCAAABAAgAAAAAADSJDwAAAAAAAAAAAAABAAAAAQAA+/v7APv2+QD59PUA9vn5AP这两种方法尤其是第二种方法是目前二进制数据向XML文档映射的常用方法，但由于其编码后的文档长度比原文档增大了33%，因此对网络带宽还有一定的浪费。实际上对大多数数据集，如果画一个每一个字节数据在数据集中出现频率的直方图，发现各个字节值出现的频率分布是很不均匀的(如图片数据最为典型)。有些字节使用频率很高，而有些却很低或根本没有。这也称为字节数据的统计特性。利用这个特性，可以进一步降低编码后的字符长度，关键是选择一种合适的算法，这就是Huffman编码法。这也是本文重点讨论的编码方法。2.2 LOB数据转换的Huffman编码法Huffman编码的基本思想完全按照字符出现概率的大小,概率大的字符分配短码,概率小的字符分配长码,来构造最短的平均码长的异头前码。此构造出来的码一定是最优的。设某二进制数据的数据空间为: 为各种可能的二进制数据字节，为各字节出现的频度，。现在用个码符号的码符号集:1，2，对数据中的每一个字节符号(=1，2，)进行编码，步骤如下：(1)将字节符号按其出现概率分布，由大到小排列；(2)将个最小概率的字节合并成一个符号，这时数据减少到-(-1)个符号，形成一个新的数据，令该数据为1;将信源1的符号按步骤(1)的要求重新排列，并将最小概率分布的个字节符号按某一次序分别用码符号1，2，表示。再按步骤(2)的做法合并，此时数据1缩减到-(-1)-(-1)个字节符号，形成另一个数据2；(3)依此下去，若合并了次后，总减少的字节符号为(-1)个；若数据中的符号数-(-1)时，将重复前面过程;若-(-1)=时，结束编码；(4)从结束处(根)沿授码符号的路线向前返回，依次写出字符对应的码符号序列，这就是码；(5)若-(-1)时，这种情况表明，合并了次后，数据缩减后的字节符号个数已经小于码符号集:1，2，的码符号数，为了使短码得到充分利用，则必须终止编码过程。在原数据中增加=-(-1)(个)概率为零的虚假字节符号，重新开始按上面的过程进行编码。Huffman编码的基本思想完全可以应用到二进制数据的编码转换上，很显然如何科学地构造一个码符号集(编码表)是实现该算法的关键，因为需要保证所构造的编码表在转换后不能出现二义性。一般按照字节数据出现概率的大小,概率大的字符分配短码,概率小的字符分配长码,来构造最短的平均码长的异头前码。另一方面，由于一个字节有256种可能不同的数据，这样只要构造一个长度为256的的编码表不仅可以实现转换还可以实现对数据的压缩，这也是Huffman算法的初衷。首先以A-Z, a-z, 0-9, +, and /形成基本的Base-64的单字符代码集。然后再通过在每一个字符前加上“:、;、-”形成192个附加的双字符编码。这样就形成了如下描述的Huffman编码表。 A,B,.,Z,a,.,z,0,.9,+,/, :A,:B,.,:Z,:a,.,:z,:0,.:9,:+,:/, ;A,;B,.,;Z,;a,.,;z,;0,.;9,;+,;/, -A,-B,.,-Z,-a,.,-z,-0,.-9,-+,-/;下一步就是要按照字节值在数据集中出现的频率将每一个代码映射到一个字节值。通过分析数据集的子集来计算每一个字节值出现的频率，然后可以根据它的频度将该字节值映射到代码表中的某一个字符；在此之后再映射其余的字节。编码进程只需要在映射表中简单地查找每一个字节值将其转换成为一个字符串，然后将该字符串追加到字符流中。对普通的二进制文档，用这种编码方法编码后的文档的平均编码长度为每字节1.0002个字符，这就意味着编码后的文档几乎与原始的二进制文档相等。经过Huffman编码对同一二进制数据转换后所得的XML文档片断如下所示：:l:m:n:puAAAAASKAA2AAA:qBAA:0FAAMA:kAAAAA5:ouAAAAAAAAAAMAAAMAA:R:R:RA:R:N:QA:Q很显然，Huffman编码通过使用字节数据的分布统计特性来减少平均编码长度。用单字符或短字符序列来表示使用频率最高的字节，而用较长的字符序列表示使用频率最低的字节。在分布非常明显地偏向某一个字节子集的情况下，这种编码方法非常有效；但对于相当均衡的分布，这种方法效率就不高了。Huffman编码法与前面介绍的两种编码方法相比有较大的优势，有较好的数据交换性能。当然这种编码算法比较复杂，机器的开销也比较大，但在现代的计算机软件硬件技术条件下应该不成问题。表1对使用不同方式编码同样的二进制数据文件时(jia.bmp,995.35KB)的比较结果。表1 不同编码方式的性能比较编码方式编码速率(B/ms)XML文档大小(KB)平均编码长度(字符数/字节)解码后文件长度(KB)直接编码法160019902995.35Base-64编码法720013271.33995.35Huffman编码法2210995.61.0002995.353 系统实现模型基于上述的讨论，可以建立如图2所示的异构数据库大对象数据交换模型XML文档Huffman编码转换LOB数据提取JDBC/ODBCInternetXML文档Huffman解码转换LOB数据写入OracleSQL Server图2 LOB数据交换模型系统既可以基于因特网也可以基于校园网、政务网或企业网。整个系统分为两大模块：LOB数据提取与转换模块、LOB数据转换与写入模块。当需要进行大对象数据交换时，由LOB数据提取模块通过数据库访问接口从源数据库中读出LOB数据形成二进制数据文件；调用Huffman编码转换模块对二进制数据进行编码再通过XML文档生成模块形成XML文档。所生成的包含源数据的XML文档通过网络传送到目标系统，首先需要对经过编码的二进制数据进行Huffman解码使其还原成二进制数据文件，然后再调用LOB数据写入模块将二进制数据写入到目标数据库中，这样即完成了一次LOB数据的交换。3 结论在因特网技术迅猛发展的当今信息社会，研究数据交换与数据集成特别是异构数据的集成与交换对消除“信息孤岛”现象有着非常重要的意义，从实际应用与发展趋势来看，使用XML技术作为数据交换与集成的中间格式也是大势所趋。而如何保证LOB数据的无损传输也是异构数据集成与交换中必须要解决的问题，本文通过XML技术与Huffman编码的结合较好地解决了这个问题，应该说有较好的应用前景。参考文献：1 汪炼 韩震宇. 无损图像压缩技术，实用测试技术，2002年，第5期2 陈基漓 严小卫 杨祥. 基于单词的Huffman压缩方法，桂林工学院学报，2002年，第4期3 Thomas M. Cover, Joy A. Thomas Eleme