XCfde:高压缩率的XML文档压缩技术

维普资讯

ＣＮ４３—１２５８／ＴＰ　

ＩＳＳＮ　１００７—１３ＯＸ　

计算ｔｄ１．－ｒ￣与科学

．　

２００７年第２９卷第２期　

ＶｏＬ　２９，Ｎｏ．２，２００７　

ＣＯＭＰＵＴＥＲ　ＥＮＧＩＮＥＥＲＩＮＧ＆ＳＣＩＥＮＣＥ　

文章编号：１００７—１３０Ｘ（２００７）００２—００４４—０３　

ＸＣｆｄｅ：高压缩率的ＸＭＬ文档压缩技术　

ＫＣｆｄｅ．Ａ　ＸＭＬ　Ｃｏｍｐｒｅｓｓｏｒ　ｗｉｔｈ　Ｈｉｇｈ　Ｃｏｍｐｒｅｓｓｉｏｎ　Ｒａｔｉｃ　

胡和平。魏裕凯　

ＨＵ　Ｈｅ－ｐｉｎｇ，ＷＥＩ　Ｙｕ－ｋａｉ　

（华中科技大学计算机科学与技术学院，湖北武汉４３００７４）　

（Ｓｃｈｏｏｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　ｃＳｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｈｕａｚｈｏｎｇ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　ｃＳｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｗｕｈａｎ　４３００７４，Ｃｈｉｎａ）　

摘要：本文提出了一种用于数据交换的ＸＭＬ压缩技术ＸＣｆｄｅ。ＸＣｆｄｅ采取四步压缩方案：把ＸＭＬ文档分离为结构　

数据和内容数据；自动识别数据类型并自动分类数据；对不同类型的数据采用不同的编码策略；将初步编码后的结构数据　

和内容数据使用７Ｚｉｐ进行整体压缩。ＸＣｆｄｅ拥有较高的压缩率，改善了ＸＭＬ数据交换的传输效率和存档中的空间利用　

率。　

Ａｂｓｔｒａｃｔ：Ｉｎ　ｔｈｉｓ　ｐａｐｅｒ　ＸＣｆｄｅ，ａｎ　ｅｆｆｅｃｔｉｖｅ　ＸＭＬ　ｃｏｍｐｒｅｓｓｏｒ　ｆｏｒ　ｄａｔａ　ｅｘｃｈａｎｇｅ，ｉｓ　ｐｒｅｓｅｎｔｅｄ．ＸＣｆｄｅ　ｓｅｐａｒａｔｅｓ　ａ　ＸＭＬ　

ｄｏｃｕｍｅｎｔ　ｉｎｔｏ　ｔｈｅ　ｓｔｒｕｃｔｕｒａｌ　ｄａｔａ　ａｎｄ　ｔｈｅ　ｃｏｎｔｅｎｔ　ｄａｔａ　ｆｉｒｓｔ，ａｕｔｏｍａｔｉｃａｌｌｙ　ｒｅｃｏｇｎｉｚｅｓ　ｄａｔａ　ｔｙｐｅｓ　ｗｉｔｈｏｕｔ　ｓｃｈｅｍａ　ｉｎｆｏｒｍａ—　

ｔｉｏｎ，ａｎｄ　ｕｓｅｓ　ｄｉｆｆｅｒｅｎｔ　ｅｓｐｅｃｉａｌ　ｓｔｒａｔｅｇｉｅｓ　ｔＯ　ｅｎｃｏｄｅ　ｄａｔａ　ｗｉｔｈ　ｄｉｆｆｅｒｅｎｔ　ｔｙｐｅｓ．Ｆｉｎａｌｌｙ　ｉｔ　ｃｏｍｐｒｅｓｓｅｓ　ｔｈｅ　ｅｌｅｍｅｎｔａｒｉｌｙ　ｅｎｃｏ－　

ｄｅｄ　ｓｔｒｕｃｔｕｒｅ　ａｎｄ　ｃｏｎｔｅｎｔ　ｄａｔａ　ｔｏｇｅｔｈｅｒ　ｕｓｉｎｇ　７Ｚｉｐ．Ｉｔ　ｇｒｅａｔｌｙ　ｉｍｐｒｏｖｅｓ　ｔｈｅ　ｅｆｆｉｃｉｅｎｃｙ　ｏｆ　ｓｔｏｒａｇｅ　ａｎｄ　ｄａｔａ　ｅｘｃｈａｎｇｅ　ｏｆ　ｔｈｅ　

ＸＭＬ　ｄａｔａ　ｐｒｏｆｉｔｉｎｇ　ｆｒｏｍ　ｉｔｓ　ｈｉｇｈ　ｃｏｍｐｒｅｓｓｉｏｎ　ｒａｔｉｏ．　

关键词：ⅪｖＩＬ压缩；ＬＺ７７；数据分类；数据交换　

Ｋｅｙ　ｗｏｒｄｓ：ＸＭ　ｃｏｍｐｒｅｓｓｉｏｎ；ＬＺ７７；ｄａｔａ　ｃｌａｓｓｉｆｉｃａｔｉｏｎ；ｄａｔａ　ｅｘｃｈａｎｇｅ　

中图分类号：ＴＰ３９３　文献标识码：Ａ　

ＸＭＬ压缩技术ＸＣｆｄｅ（ＸＭＬ　Ｃｏｍｐｒｅｓｓｉｏｎ　Ｆｏｒ　Ｄａｔａ　Ｅｘ－　

１　引言　

ｃｈａｎｇｅ，简称ＸＣｆｄｅ），它根据ＸＭＬ文档自身特点，采取特　

有的压缩策略，获取较高的压缩率，应用于数据交换和数据　

ＸＭＬ是Ｗ３Ｃ于１９９８年２月发布的一种标记语言。　

存档，有效地利用了网络带宽和存储空间。　

它是ＳＧＭＬ的一个简化子集，将ＳＧＭＬ的丰富功能与　

ＨＴＭＬ的易用性结合到Ｗｅｂ的应用中，以一种开放的自　

２相关技术　

我描述方式定义了数据结构，在描述数据内容的同时能突　

出对结构的描述，从而体现出数据之间的关系。它具有平　

２．１　ＸＭＬ　

台无关、自我描述、可扩展等优点。　

虽然对ＸＭＬ的某些技术标准尚有争议，但人们已经　

ＸＭＬ文档由三类标识组成：标签、属性、数据值。　

普遍认识到ＸＭＬ的作用和巨大潜力，已将ＸＭＬ应用到互　

定义１标签和属性为结构数据，数据值为内容数据。　

联网的各个方面，如数据交换、替代传统的ＥＤＩ、集成不同　

定义２将ＸＭＬ文档建模为树：结点为标签或属性，　

数据源、数据的多种显示和网络出版、文件保值等。因其特　

叶子则代表数据值。通向数据值的路径是从根到数据值叶　

有的自我描述和平台无关等特性，在数据交换和不同数据　

子的结点序列，如／书／书名。ＸＭＬ文档深度是指最长路径　

源集成等方面的应用尤为突出。　

的长度即树的深度。　

但是，ＸＭＬ格式的信息冗余过大，对磁盘空间、带宽都　

定义３压缩编码时属性也当作标签，借用ＸＰａｔｈ的　

存在着浪费。为了有效地存储和交换ＸＭＬ数据，有必要　

表示方法，在属性前加上字符＠，以便解压还原时从标签中　

对ＸＭＬ数据进行压缩。本文介绍了一种高压缩比的　

辨别它们。　

收稿日期：２００５—０６—２１；修订日期：２００５—０９—２８　

成、

作者简介：

软件工程和数据挖掘。

胡和平（１９５２一），

男，湖北武汉人，教授，研究方向为软件工程、数据挖掘和信息安全；魏裕凯，硕士生，研究方向为系统集　

通讯地址：

Ａｄｄｒｅｓｓ：Ｓｃｈｏｏｌ

４３００７

　ｏｆ

４湖北省武汉市华中科技大学计算机科学与技术学院；

　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｈｕａｚｈｏｎｇ　Ｕｎｉｖｅｒｓｉ

Ｔｅ

ｔｙ　ｏｆ

ｌ：（Ｏ２７）

　Ｓｃｉｅｎｃｅ　ａｎｄ　

８７５４９７６Ｏ；

Ｔｅｃｈｎｏｌ

Ｅ－ｍａｉ

ｏｇｙ，Ｗｕｈａｎ，Ｈｕｂｅｉ

ｌ：ｈｐｈｕ＠ａｎｄｉｎ．ｎｅｔ

　４３００７４，Ｐ．Ｒ　

Ｌｈｉｎａ　

４４　

维普资讯

２．２　ＬＺ７７及改进算法　

通用的压缩程序中常用的字典压缩程序起源于Ｚｉｖ和　

Ｌｅｍｐｅｌ的经典论文［　，经改进后形成Ｌｚ系列压缩程序，如　

ＬＺ７８、ＬＺＷ、ＬＺＳＳ等。ＬＺ７７采用一个包括字典窗口和先　

＜／书＞　

其中，书、书名、作者、出版时间为标签，语言为属性，依照标　

签出测顶序标号，则有：＜书＞＝＃１，＜书名＞一＃２，＠语　

言一＃３，＜作者＞一＃４，＜出版时间＞一＃５；使用Ｃ加　

行缓冲区两部分的文本窗口作为动态字典。文本窗口存储　

大小固定，存放最近经过编码处理的输入文本。压缩时首　

先从输人数据流中读取待压缩的文本串，放人先行缓冲区，　

然后进行编码。把先行缓冲区中的内容与字典窗口中的内　

容进行比较。如有相匹配的部分，则按规定的格式表示输　

入字符串。经匹配、编码后的数据流从先行缓冲区依次进　

入到字典窗口中，成为字典的一部分。而原有字典中的一　

上容器序号替换数据值。使用上述编码替换后，ＸＭＬ文档　

结构形式如下：　

＃１＃２＃３（３３／Ｃ２／＃４　ＣＡ／＃５　Ｃ５／／　

当一个ＸＭＬ文档中包含许多如上所示的书籍的集合　

时，则该文档结构形式可以表示成简化后的字符串的重复　

集合：　

＃１＃２＃３（３３／Ｃ２／＃４　ＣＡ／＃５　Ｃ５／／　

部分内容将从窗口的另一端滑出。随着窗口的滑动，字典　

的内容不断发生变化，滑动窗口中总保持着最近刚处理过　

的文本。　

例如，ＡＢ（　ＥＦＢＣＤＥＧ当读取第二个Ｂ时，压缩程序　

发现子序列ＢＣＤＥ已经在字典中出现过，则用回退指针（一　

偏移，长度）的形式替换它：ＡＢＣＤＥＦ（一５，４）Ｇ。　

拥有较高的压缩比的７ＺｉｐＥ２］是Ｉｇｏｒ　Ｐａｖｌｏｖ组织开发　

的开源软件项目，它以ＬＺ７７改良和优化后的新版本ＬＺ－　

ＭＡ算法为基础，兼容其它众多算法。ＬＺＭＡ算法具有高　

压缩比、可变字典大小、压缩和解压缩速度快、较小的解压　

缩内存需求等优点。　

３体系结构　

３．１　ＸＣｆｄｅ体系结构　

ＸＣｆｄｅ是建立在三个主要的基本步骤之上的：ＸＭＬ文　

档结构内容分析／分离器、自动类型识别器、不同数据类型　

的压缩编码器，如图１所示。　

兰竺　：　竺）—．１　Ｘ分Ｍ析Ｌ　Ｉ　

‘

／　

．．……　。　

　Ｉ内容数据　

鞴俐裂僻Ｉ　●　

　．．　

熹　。　Ｉ自动类型识别ｌ　

　ｌ羽　错　Ｉ　●　

Ｉ　各种编码器（

ＣＴ、ＤＩ、Ｕ８等ｌ

ｌ　

●　

整合编码后的结构和内容数据　

图１　ＸＣｆｄｅ的体系结构　

３．２　ＸＭＬ结构内容数据分离及处理　

通过重载ＳＡＸＥ。］中关键的类和接口实现自己的ＸＭＬ　

解析器，识别ＸＭＬ文档标签、属性和数据值并且分离为结　

构数据和内容数据。将起始标签和属性使用字典方式编　

码，这里使用标签的顺序序号标识；所有结束标签用‘／，代　

替；数据值使用Ｃ加上代表它们的容器序号（和标签字典　

编码相同）替代，容器是一组具有相同标签或者相同数据类　

型的数据集合，包含数据值和数据值的路径［４］。考虑如下　

）（Ｉ　Ｌ文档：　

＜书＞　

＜书名语言＝“中文”＞数据压缩＜／书名＞　

＜作者＞张三＜／作者＞　

＜出版时间＞１９９５－５＜／出版时间＞　

＃１＃２＃３（３３／Ｃ２／＃４　ＣＡ／＃５　Ｃ５／／　

ｉ　

这种简单重复的信息压缩性是非常好的。上面的介绍　

忽略了标签和数据值中附带的空白（制表符和空格等），如　

果考虑空白的话，则容器数量、结构信息、压缩后的大小都　

会有所增加，但在压缩处理上无本质区别。　

３．３自动类型识别　

将结构数据按照上述方法编码后，通过指定编码器进　

行初步压缩，而对于分离后的数据值的处理则复杂一些。　

为了获取更高的压缩比，我们对于不同数据类型的容器采　

取不同的编码方法。　

因此，在将分离的数据值存人相应容器中的同时，需要　

判别该容器存放的数据值的数据类型，并据此数据类型决　

定该容器的编码方法。注意，这一步和上节的数据分离是　

同时进行的。　

如果ＸＭＬ文档提供有Ｓｃｈｅｍａ描述文件，则可以根据　

此文件信息获取相应的数据类型。如果没有此类文件，对　

于类型的识别有两种方式：一是用户可以在压缩时根据　

ＸＭＬ的内容自己判别后指定类型参数，此方式繁琐且适应　

性差；另外一种方法是通过在分离结构和内容数据时使用　

自动类型识别器来实现。　

进行自动类型识别时，我们先约定一个基本原则［５］：如　

果数据值中包含的字符都是数字（‘０’～‘９’），并且第一个　

字符不是‘０’，则认为此数据值为整数，否则为字符串。据　

此原则，ＸＣｆｄｅ对数据进行简单分类，而对于字符串需进一　

步判别，以识别浮点数、中文字符串等其它基本类型，提高　

压缩率。　

ＸＣｆｄｅ采用正则表达式ＲＥ（Ｒｅｇｕｌａｒ　Ｅｘｐｒｅｓｓｉｏｎ，简称　

ＲＥ）来实现匹配，正则表达式是由普通字符（例如字符ａ到　

ｚ）以及特殊字符（称为元字符）组成的文字模式，该模式描　

述在查找文字主体时待匹配的一个或多个字符串［６］。基本　

压缩编码对应类型的ＲＥ描述为：　

整型（‘［１－９３｛１｝［Ｏ一９］＊Ｓ）；　

中文字符串（＇［－＼ｕ４ｅＯＯ－－＼ｕ９ｆａ５￣＊Ｓ）；　

浮点数（　（一？＼ｄ＋）（＼．＼ｄ＋）？Ｓ）。　

另外，ＸＣｆｄｅ还提供扩展接口，用户可以根据自己的需　

要更新扩充正则表达式库，将一些复杂的数据类型（如时　

间、ＩＰ地址等）拆分成上述基本类型；然后使用联合压缩程　

序进行编码，以期获取最好的压缩率，当然处理时间会适当　

增加。　

４５　

维普资讯

３．４编码技术　

３．４．１基本编码方法　

自动识别数据类型后，根据不同的数据类型采取相应　

表２压缩测试结果　

数据源原始大／Ｊ、　錾摹ＸＣｆｄｅ　ｘＭⅢＩＣＩ＇＿ＸｐｒｅｓｓＷ￣ｎＲＡＲ　

的编码方法。基本编码方法如表１所示。　

表１常用的基本编码方法　

代码　

功能说明　

Ｆ　

浮点数编码器　

Ｉ　

整数编码器　

Ｕ８　

小于２５６的正整数编码器　

ＤＩ　

整数的差分编码器　

Ｔ　

默认文本编码器　

ＣＴ　

中文文本压缩编码器　

浮点数编码器Ｆ采用ＩＥＥＥ７５４标准把浮点数字符串　

表示成二进制格式。整数编码器Ｉ采用二进制编码表示整　

数字符串：二进制编码中每个字节最高位用来表示序列的　

长度，小于１２８的数字使用１字节，大于１２８而小于１６　３８４　

的使用两字节，依此类推。Ｕ８类似于Ｉ，它直接用一个字　

节存储０到２５５之间的数值。整数的差分编码器ＤＩ将连　

续数字序列表示成（基值、差数）的形式，如１　５００、１　５２０、１　

６００、１　５４０编码成（１　５００，２０，１００，４０）。文本编码器Ｔ不进　

行任何压缩编码，而是直接复制字符串，整合后由压缩程序　

７Ｚｉｐ进行压缩。中文文本压缩编码器ＣＴ是为了提高中文　

文本的压缩效率而加入的，由于中文文本和西文文本有诸　

多差异，ＣＴ从编码方案、自适应扩展位、最大索引位等方　

面改进ＬＺＳＳ，从基本码集、更新策略和哈希函数等方面改　

进ＬＺＷ，然后联合使用改进后的ＬＺＳＳ和ＬＺＷ对中文文　

本进行压缩［７］。它在英文文本压缩率不变的情况下更适合　

于压缩中文，比其它ＸＭＬ压缩技术使用的文本压缩算法　

压缩率高。　

３．４．２联合编码方法　

ＸＣｆｄｅ中提供Ｌｉｎｋ功能进行基本编码方式的组合。　

假定用ｘ代表小于２５５的正数，ＩＰ地址通过正则表达式　

（　？＼ｄ＼ｄ？ｌ　２［ｏ一４］＼ｄｌ　２５［ｏ一５］）＼．（［ｏ１］？＼ｄ＼ｄ？ｌ　２［ｏ一　

４］＼ｄｌ　２５Ｅｏ一５］）￥）解析，分解为Ｘ　Ｘ　ｘ的形式，使用　

Ｌｉｎｋ（Ｕ８．Ｕ８．Ｕ８．Ｕ８）联合编码方式，对其中的整数ｘ分　

别采用Ｕ８编码，这要比无法识别该数据值而将其当成一　

般字符串进行压缩的效率要高许多，同时也提高了程序的　

灵活性。　

最后，将初步编码处理后的结构数据和内容数据整合　

通过７Ｚｉｐ压缩工具再次进行压缩，以提高整体的压缩率。　

４实验　

４．１数据源　

本文综合采用ＸＭｉｌｌ和Ｘｐｒｅｓｓ中的典型测试数据＿４　］，　

包括蛋白质结构数据库ＳｗｉｓｓＰｒｏｔ、学术论文索引数据库　

ＤＢＬＰ、按照莎士比亚剧本集Ｓｈａｋｅｓｐｅａｒｅ相同格式制作的　

《雷雨》的剧本Ｉ＊ｉＹｕ和棒球队伍球员信息文档ＢａｓｅＢａｌｌ。　

ＤＢＬＰ和ＳｗｉｓｓＰｒｏｔ数据容量大，虽然深度小但标签数　

目多，而Ｂａｓｅｌ￣ｌｌ数值型多，ＬｅｉＹｕ则是为了测试中文文本　

压缩能力，数据源具体参数见表２。　

４６　

４．２测试结果　

在赛扬２．４Ｇ　ＣＰｕ和５１２Ｍ内存、采用ＷＩＮＸＰ　ＳＰ２操　

作系统的计算机上使用比较流行的几种软件进行测试对　

比，包括通用的压缩程序ＷｉｎＲＡＲ３．４２、专用的ＸＭＬ压缩　

工具ＸＭｉｌｌｃ　］和ＩＣＴ—ＸｐｒｅｓｓＥ　，测试时所有工具都采用默　

认的标准参数设置。表２中工具对应的四行数据从上到下　

依次为压缩后的大／ｂ（字节）、压缩比（压缩后的容量／压缩　

前的容量）、压缩时间（秒）、解压缩时间（秒）。　

４．３实验结果分析　

４．３．１压缩分析　

从表２中的数据可以看出，ＸＣｆｄｅ对于不同容量、标　

签、深度、数据类型的ＸＭＬ文档都取得了较高的压缩比率　

且有较快的平均处理速度，尤其是对于包含数值型和中文　

文本的ＸＭＬ文档压缩更具优势。　

４．３．２改善传输测试　

在局域网服务器上使用微软ＩＳＡ２００４防火墙和Ｂａｎｄ—　

ＷｉｄｔｈＣｏｎｔｒｏｌｌｅｒ软件进行带宽限制以模拟真实网络。以　

ＤＢＬＰ为例，限定带宽为２００ＫＢ／ｓ（相当于流行的２Ｍ　ＡＤ—　

ＳＬ下行网络速度），不压缩传输：总传输时间为１　３２３ｓ；压　

缩传输：压缩ＩＥｔ，Ｊ＂Ｉ＇－￣］为５１ｓ，传输时间为１４４ｓ，解压缩时间为　

３０ｓ，总时间为２２５ｓ。压缩后的总时间比不压缩的时间少了　

将近半个小时，重要的是减轻了网络负担，改善了传输效　

率，更加有效地利用了带宽资源。　

５结束语　

ｘＣｆｄｅ是一种高压缩率的ＸＭＬ压缩技术，主要应用于　

ＸＭＬ存储和数据交换，和其它压缩技术相比，有比较高的　

压缩率和比较快的运算时间。但是，它没有提供压缩后的　

ＸＭＬ文档的查询功能，如果需要查找信息则必须先进行解　

压操作，不是很方便；另外，在某些类型的ＸＭＬ源数据处　

理上速度有些慢，这都是需要在将来解决的问题。　

（下转第６５页）　

维普资讯

明，ＳＶＭ算法对交通标志识别的准确性远远高于ＢＰ算　

法。同时，在交通标志细分类的实验中，由于训练集样本数　

苎＝　

替　

嘉　

』薹　

替　

磊　

目较少，ＳＶＭ算法在抗噪能力和泛化能力上显示出了比　

ＢＰ算法更为突出的优越性。因此，在模式分类问题上具有　

良好泛化能力的ＳＶＭ算法在交通标志识别领域也具有广　

０　３　５　ｌ０　ｌ５　

高斯噪声含量　

扭曲度　

阔的应用前景。　

图７　ＳＶＭ算法和ＢＰ算法在警告标志细分类中的比较　

参考文献：　

［１］Ｚｈｕ　Ｓｈｕａｎｇｄｏｎｇ．Ｔｗｏ　Ｈｉｅｒａｒｃｈｙ　Ｃｌａｓｓｉｆｉｅｒ　ｆｏｒ　Ｒｅｃｏｇｎｉｔｉｏｎ　ｏｆ　

Ｔｒａｆｆｉｃ　Ｓｉｇｎｓ　Ｂａｓｅｄ　ｏｎ　Ｎｅｕｒａｌ　Ｎｅｔｗｏｒｋ［Ａ］．Ｆｉｆｔｈ　Ｗｏｒｌｄ　

对于大小为２Ｏ×２Ｏ、噪声为０．３的交通标志图，人眼几乎　

都不能准确地识别出每一种标志，ＢＰ网络的识别率也都几　

乎为０。但是，利用ＳＶＭ网络识别，指示标志的识别率却　

Ｃｏｎｇｒｅｓｓ　ｏｎ　Ｉｎｔｅｌｌｉｇｅｎｔ　Ｃｏｎｔｒｏｌ　ａｎｄ　Ａｕｔｏｍａｔｉｏｎ［Ｃ］．２００４．　

可以达到１００　，禁令标志和警告标志的识别率也都达到　

了７Ｏ　以上。这充分说明了利用ＳＶＭ进行交通标志分类　

时在抗噪声能力方面的优越性。对于大小为２Ｏ×２Ｏ的交　

通标志图，发生轻度的扭曲，像素点的值就会发生很大的变　

化。尤其是警告标志之间的差别很小，轻度扭曲就会导致　

识别错误。ＢＰ网络在这一方面也体现了极强的敏感性，从　

轻微的３度扭曲到较明显的１５度扭曲，ＢＰ算法的识别率　

都很低，但ＳＶＭ算法的识别率仍然较高。　

另外，对比中国交通标志粗分类与细分类的实验结果　

可见，无论是ＢＰ算法还是ＳＶＭ算法，粗分类的识别效果　

都明显优于细分类。这主要是由训练集的样本数量造成　

的。粗分类实验是将１１６个交通标志分为三大类，每一类　

都对应着几十个训练样本。而在细分类实验中，禁令标志、　

指示标志、警告标志分别对应４２类、２９类、４５类，每一类只　

有一个训练样本。通常，训练集的样本数量应当尽可能地　

多一些，以便更好地反映样本对象的整体特征。但是，正是　

在这种训练样本很少的情况下，ＳＶＭ算法相对于ＢＰ算法　

的优势得到了更好的体现。　

需要指出的是，ＳＶＭ算法良好的泛化能力是在付出了　

比ＢＰ算法更大的计算复杂性的基础上获得的。因此，在　

对网络进行测试时，ＳＶＭ算法的运行速度显然要比ＢＰ算　

法慢。不过，当前的计算机技术已经相当发达，ＳＶＭ算法　

的响应速度足以满足实际应用的要求。因此，ＢＰ算法在运　

行速度上的优势对ＳＶＭ算法并无威胁。此外，对于交通　

标志分类这样大规模的问题来说，由于ＢＰ算法的学习过　

程需要反复调整大量的设计参数，因此ＳＶＭ算法的学习　

速度要远远优于ＢＰ算法。这些都说明了ＳＶＭ算法的性　

能和应用前景更好。　

５结束语　

本文介绍了一种适用于交通标志分类的ｓＶＭ分类方　

法，粗分类的识别率近乎完美，细分类也取得了较好的识别　

效果。同时，本研究还将ＳＶＭ算法和传统流行的ＢＰ算法　

进行了对比分析。众所周知，ＢＰ算法存在着一些难以克服　

的缺点。例如，在学习过程中易于陷入局部极小点，不可能　

达到全局优化；易于发生过拟合，严重影响学习后网络的泛　

化能力。而ＳＶＭ算法绕过了局部极小的陷阱，以接近最　

优的方式解决了模式分类问题，同时具有更好的泛化能力。　

本研究成功地将ＳＶＭ算法应用于道路交通标志的分类，　

取得了令人满意的识别效果。本文介绍的实验研究结果表　

５３０２－５３０６．　

［２］Ｈａｙｋｉｎ　Ｓ　Ｎｅｕｒａｌ　Ｎｅｔｗｏｒｋｓ：Ａ　Ｃｏｍｐｒｅｈｅｎｓｉｖｅ　Ｆｏｕｎｄａｔｉｏｎ．　

Ｓｅｃｏｎｄ　Ｅｄｉｔｉｏｎ［Ｍ］．北京：清华大学出版社，２００１．　

［３］Ｉ　Ｕ　Ｇａｎｙｕｎ，Ｃｈｅｎｇ　Ｈａｏｚｈｏｎｇ，Ｚｈａｉ　Ｈａｉｂａｏ，ｅｔ　ａ１．Ｆａｕｌｔ　Ｄｉ—　

ａｇｎｏｓｉｓ　ｏｆ　Ｐｏｗｅｒ　Ｔｒａｎｓｆｏｒｍｅｒ　Ｂａｓｅｄ　ｏｎ　Ｍｕｌｔｉ－Ｌａｙｅｒ　ＳＶＭ　

Ｃｌａｓｓｉｆｉｅｒ［Ｊ］．Ｅｌｅｃｔｒｉｃ　ｏＰｗｅｒ　Ｓｙｓｔｅｍｓ　Ｒｅｓｅａｒｃｈ，２００１，１７（１）：　

２３－３０．　

－１４］马笑潇，黄席樾，柴毅．基于ＳＶＭ的二叉树多分类算法及其　

在故障诊断中的应用［Ｊ］．控制与决策，２００３，１８（３）：２７２－２７６．　

［５］赵晶，张旭东，高隽．基于支持向量机的多类形状识别系统　

［Ｊ］．合肥工业大学学报，２００４，２７（１）：２３－２６．　

（上接第４６页）　

参考文献：　

［１］Ｚｉｖ　Ｊ，Ｌｅｍｐｅｌ　Ａ　Ａ　Ｕｎｉｖｅｒｓａｌ　Ａｌｇｏｒｉｔｈｍ　ｏｆｒ　Ｓｅｑｕｅｎｔｉａｌ　Ｄａｔａ　

ｏＣｍｐｒｅｓｓｉｏｎ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓ　ｏｎ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｔｈｅｏｒｙ，１９７７，　

２３（３）：３３７－３４３．　

［２］７ｚｉｐ［（　／ＯＩ　．ｈｔｔｐ：／／Ⅵ　７ｚｉｐ．ｏｒｇ，２００５－０１．　

［３］曾春平，王超，张鹏．ＸＭＩ　编程从人门到精通Ｉ－Ｍ］．北京：希　

望电子出版社，２００２．　

－１４］　ＩＡｅｆｋｅ　Ｈ，Ｓｕｃｉｕ　ｎ　ＸＭＩＩ　Ｉ　：Ａｎ　Ｅｆｆｉｃｉｅｎｔ　ｏＣｍｐｒｅｓｓｏｒ　ｆｏｒ　

ＸＭＩ　Ｄａｔａ　ｒＡ］．Ｐｒｏｃ　ｏｆ　ｔｈｅ　２０００　ＡＣＭ　ＳＩＧＭＯＤ　Ｃｏｎｆ　ｏｎ　

Ｍａｎａｇｅｍｅｎｔ　ｏｆ　ａＤｔａ［Ｃ］．２０００．１５３—１６４．　

［５］　Ｍｉｎ　ＪｕｎＫｉ，Ｐａｒｋ　Ｍｙｕｎｇ－Ｊａｅ，Ｃｈｕｎｇ　ｃｈｉ　ｎ．ＸＰＲＥＳＳ：　

Ａ　Ｑｕｅｒｉａｂｌｅ　Ｃｏｍｐｒｅｓｓｉｏｎ　ｆｏｒ　ＸＭＩ　Ｄａｔａ［Ａ］．Ｐｒｏｃ　ｏｆ　ｔｈｅ　

２００３　ＡＣＭ　ＳＩＧＭＯＤ　ｏＣｎｆ　ｏｎ　ａＭｎａｇｅｍｅｎｔ　ｏｆ　ａＤｔａ［Ｃ］．２００３．　

１２２—１３３．　

［６］陈怡，卿锋．在Ｃ语言中使用正则表达式［Ｊ］．华南金融电　

脑，２００４，（４）：６０－６２．　

［７］华强．在文本压缩中联合使用ＬＺＳＳ和ＬＺＷ［Ｊ］．计算机应　

用与软件，２００２，１９（１）：６０－６２．　

［８］　ＩＣＴ—ＸＭＩ　Ｅｘｐｒｅｓｓ［ＣＰ／ＯＩ　］．ｈｔｔｐ：／／ｗｗｗ．ｉｃｔｃｏｍｐｒｅｓｓ．　

ｏｃｒｎ／ｄｏｗｎｌｏａｄｘｍ１．ｈｔｍｌ，２００５—０１．　

６５