基于LazyDFA的XPath在XML数据流上查询优化算法

Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用　

ＸＭＬ数据流上查询优化算法　

基于ＬａｚｙＤＦＡ的ＸＰａｔｈ在　

张晓琳，崔敏，谭跃生　

ＺＨＡＮＧ　Ｘｉａｏ—ｌｉｎ，ＣＵＩ　Ｍｉｎ，ＴＡＮ　Ｙｕｅ—ｓｈｅｎｇ　

内蒙古科技大学信息工程学院，内蒙古包头０１４０１０　

Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｃｏｌｌｅｇｅ，Ｉｎｎｅｒ　Ｍｏｎｇｏｌｉａ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｂａｏｔｏｕ，Ｉｎｎｅｒ　Ｍｏｎｇｏｌｉａ　０１４０１０，Ｃｈｉｎａ　

Ｅ—ｍａｉｌ：ｂｔｃｍ４５＠ｙａｈｏｏ．ｅｏｍ．ｃｎ　

ＺＨＡＮＧ　Ｘｉａｏ—ｌｉｎ，ＣＵＩ　Ｍｉｎ，ＴＡＮ　Ｙｕｅ－ｓｈｅｎｇ．ＬａｚｙＤＦＡ　ｂａｓｅｄ　ＸＰａｔｈ　ｑｕｅｒｙ　ｏｐｔｉｍｉｚｅｄ　ａｌｇｏｒｉｔｈｍ　ｏｖｅｒ　ＸＭＬ　ｄａｔａ　ｓｔｒｅａｍ．　

Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ，２００８，４４（２８）：１２５－１２７．　

Ａｂｓｔｒａｃｔ：Ｔｈｉｓ　ｐａｐｅｒ　ｇｉｖｅｓ　ａ　ｓｏｌｕｔｉｏｎ　ｂａｓｅｄ　ｏｎ　ｌａｚｙＤＦＡ　ｔｅｃｈｎｏｌｏｇｙ　ａｎｄ　ｐｒｅｓｅｎｔｓ　ｔｈｅ　ｏｐｔｉｍｉｚｅｄ　ａｌｇｏｒｉｔｈｍ　ｗｈｉｃｈ　ａｉｍｓ　ａｔ　ｔｈｅ　

ＸＰａｔｈ　ｑｕｅｒｙ　ｐｒｏｃｅｓｓｉｎｇ　ａｎｄ　ｑｕｅｒｙ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｐｒｏｂｌｅｍ　ｏｖｅｒ　ＸＭＬ　ｄａｔａ　ｓｔｒｅａｍ．Ｓｈａｒｅｄ　ＮＦＡ　ｓｔａｔｅ　ｔａｂｌｅ，ｗｈｉｃｈ　ｄｉｖｉｄｅｓ　ｔｈｅ　ｓｔａｔｅｓ　

ｉｎ　ＮＦＡ　ｉｎｔｏ　ｔｗｏ　ｓｅｔｓ，ｔｈｅｙ　ａｒｅ　ｓｈａｒｅｄ　ｓｅｔ　ａｎｄ　ｅｘｃｌｕｓｉｖｅ　ｓｅｔ．Ｂｙ　ｔｈｉｓ　ａｌｇｏｒｉｔｈｍ　ｗｅ　ｃａｎ　ｒｅｄｕｃｅ　ｔｈｅ　ｍｅｍｏｒｙ　ｕｓａｇｅ　ｏｆ　ｌａｚｙＤＦＡ．　

Ａｎｏｔｈｅｒ　ｏｐｔｉｍｉｚａｔｉｏｎａｌ　ａｌｇｏｒｉｔｈｍ　ａｄｄｓ　ａ　ｓｔａｔｅ　ｔｒａｎｓｉｔｉｏｎ　ｔａｂｌｅ　ｉｎ　ｌａｚｙＤＦＡ　ｓｔｒｕｃｔｕｒｅ，ｗｈｉｃｈ　ｃａｎ　ｉｍｐｒｏｖｅ　ｌａｚｙＤＦＡ　ｑｕｅｒｙ　ｓｐｅｅｄ．　

Ｔｈｅ　ｅｘｐｅｒｉｍｅｎｔａｌ　ｒｅｓｕｌｔｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ｍｅｔｈｏｄ　ｉｓ　ｓｕｐｅｒｉｏｒ　ｔｏ　ｔｈｅ　ｔｒａｄｉｔｉｏｎａｌ　ａｌｇｏｒｉｔｈｍｓ　ｉｎ　ｔｈｅ　ｉｍｐｋｍｅｎｔａｔｉ０ｎａｌ　ｅｆｉｃｉｅｎｃｙ　ａｎｄ　ｆ

ｓｐａｃｉａｌ　ｃｏｓｔ．　

Ｋｅｙ　ｗｏｒｄｓ：ＸＭＬ　ｄａｔａ　ｓｔｒｅａｍ；ＸＰａｔｈ；ｌａｚｙＤＦＡ；ｑｕｅｒｙ　ｏｐｔｉｍｉｚａｔｉｏｎ　

摘要：针对ＸＭＬ数据流上ＸＰａｔｈ查询处理及查询优化问题，给出了一种基于ｌａｚｙＤＦＡ技术的解决方案，并提出了优化算法。共　

享ＮＦＡ状态表，通过将ＮＦＡ中的状态分成共享和独享两个状态集来降低ｌａｚｙＤＦＡ的内存使用量；建立状态转移表优化算法通过　

在ｌａｚｙＤＦＡ状态结构中增加一个状态转移表，来提高ｌａｚｙＤＦＡ的查询速度。实验结果表明，提出的方法能够在执行效率和空间代　

价方面优于传统算法　

关键词：ＸＭＬ数据流；ＸＰａｔｈ；ｌａｚｙＤＦＡ；查询优化　

ＤＯＩ：１０．３７７８／ｊ．ｉｓｓｎ．１００２—８３３１．２００８．２８．０４２　文章编号：１００２—８３３１（２００８）２８—０１２５—０３　文献标识码：Ａ　中图分类号：ＴＰ３ｌ１．１３　

１引言　

随着ＸＭＬ成为Ｉｎｔｅｒａｃｔ环境中的数据表示和交换的标准，　

出现了许多基于ＸＭＬ数据流的应用，如：基于内容的ＸＭＬ路　

是基于确定化自动机的，利用支持表达路径之间ＡＮＤ／ＯＲ关系　

的ＡＦＡ解决了ＮＦＡ的表达能力的问题，可提高系统的查询效　

率，但也同样面临着指数级别的空间代价问题。　

由、信息的选择传播（ＳＤＩ）Ｉ”、股票行情等。这些应用的普遍需求　

是在不问断的ＸＭＬ数据流上执行大量的ＸＰａｔｈ查询。　

ｘＰａｔｈｌ２提供了一种ＸＭＬ文档选定部分的定位及导航的方　ｌ

本文应用ｌａｚｙＤＦＡ及其优化技术来解决ＸＭＬ数据流上的　

ＸＰａｔｈ查询问题，实验结果表明，该方法可以有效地处理ＸＭＬ　

数据流上的ＸＰａｔｈ查询。共享ＮＦＡ状态表优化算法将ＮＦＡ状　

态分成共享和独享两个集合，共享集合是由ＮＦＡ状态中那些　

具有自循环边的状态构成的，那么不具有自循环边的状态就构　

法，定义了如何在ＸＭＬ文档中精确定位和匹配ＸＭＬ元素节　

点。根据ＸＰａｔｈ语法，任意一个ＸＰａｔｈ路径表达都可以转化成　

一

个正则表达式，依据自动机理论，则必然存在一个接受该语　

ＹＦｉｌｔｅｒＩ：１根据ＸＰａｔｈ构造了ＮＦＡ，它减少了不同查询处理　

言的有限状态机（Ｆｉｎｉｔｅ　Ｓｔａｔｅ　Ｍａｃｈｉｎｅ，简称ＦＳＭ）。　

成了独享集合，在这两个集合上分别执行不同的转移算法，得　

到最终结果。针对该优化算法降低空间消耗是以查询速度为代　

中的重复计算，能高效地处理不包含ｆ『１）的ＸＰａｔｈ。ｘｔｒｉｅＨＪ是对基　

于ＮＦＡ查询处理的一种扩展，它减少了对元素输入序列可能　

响应的查询处理器的数量，从而提高了处理效率。Ｄａｎ　ＳｕｅｉｕｔｓＪ　

根据ＸＰａｔｈ构造了ＮＦＡ，并在ＮＦＡ之上执行确定化，这种方法　

价的缺陷，提出了建立状态转移条件表的优化算法，该优化算　

法是对共享ＮＦＡ状态表优化算法的进一步改进。通过在　

ｌａｚｙＤＦＡ的状态结构中增加一个状态转移条件表，避免为了不　

需要的事件而去查找ＮＦＡ状态表这种情况的出现，从而提高　

ｌａｚｙＤＦＡ的查询速度。　

可能导致相对于查询数目指数级别的空间复杂性。ＸＰｕｓｈ￣６１也　

基金项日：国家社会科学基金（ｔｈｅ　Ｎａｔｉｏｎａｌ　Ｓｏｃｉａｌ　Ｓｃｉｅｎｃｅ　Ｆｏｕｎｄａｔｉｏｎ　ｏｆ　Ｃｈｉｎａ　ｕｎｄｅｒ　Ｇｒａｎｔ　Ｎｏ．０７ＸＴＱ００３）；内蒙古自然科学基金（ｔｈｅ　Ｎａｔｕｒａｌ　

Ｓｃｉｅｎｃｅ　Ｆｏｕｎｄａｔｉｏｎ　ｏｆ　Ｉｎｎｅｒ　Ｍｏｎｇｏｌｉａ　ｏｆ　Ｃｈｉｎａ　ｌｌｎｄｅｒ　Ｇｒａｎｔ　Ｎｏ．２００５０８０１０８０８）　

作者简介：张晓琳（１９６６一），女，博士，教授，研究方向：对象数据库、ＸＭＬ数据处理；崔敏（１９７４一），女，硕士研究生，研究方向：ＸＭＬ数据流；谭跃生　

（１９５９一），男，教授，研究方向：数据库理论与技术。　

收稿日期：２００７—１１－１６　修回口期：２００８一Ｏ１—２８　

１２６　２００８，４４（２８）　Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用　

件有：ｓｔａｒｔＤＯＣＵｍｅｎｔ（）、ｓｔａｒｔＥ１ｅｍｅｎｔ（）、ｅｎｄＥ１ｅｍｅｎｔ（）、ｅｎｄＤｏｃｕ—　

２　ｌａｚｙＤＦＡ的优化算法　

２．１　ＮＦＡ的构造　

根据ＸＰａｔｈ语法和自动机理论，必须存在一个接受ＸＰａｔｈ　

查询语言的有限状态机（ＦＳＭ）。因为ＸＰａｔｈ路径表达式中存在　

ｍｅｎｔ（ｏ　ｌａｚｙＤＦＡ的数据模型及构造算法如下。　

数据模型如图２。　

ＤＦＡ状态ＤＶｅｒｔｅｘｌｎｆｏ　

图１　ＮＦＡ的数据模型　

ｉｆ（ｓｔａｃｋ．ｔｏｐ．ｓａｔｉｓｉｆｅｄ）　

ｇｅｔ　ｄｅｓｔ，ｐｕｓｈ　ｄｅｓｔ；　

算法１　ＸＰａｔｈ表达式的ＮＦＡ构造。　

输入：ＸＰａｔｈ表达式ｘｐａｔｈ　

输出：ＮＦＡ状态集合　

（１）ｎｅｗ　ｃｕｒｒｅｎｔ；　

（２）ＮＦＡ．ａｄｄ（ｃｕｒｒｅｎｔ）；　

ｅｌｓｅ　

ｇｅｔ（ＮＦＡｓｔａｔｅ　ｔａｂｌｅ）；　

ＤＦＡ．ｓｔａｔｅ＝ｍ０ｖｅ（ＮＦＡｓｔａｔｅ　ｔａｂｌｅ．ｓｔａｔｅ，ｑＮａｍｅ）；　

ｐｕｓｈ（ＤＦＡ．ｓｔａｔｅ）ｌ；　

ｅｎｄＥｌｅｍｅｎｔ（Ｓｔｒｉｎｇ　ｑＮａｍｅ）　

｛ｐｏｐ（ｓｔａｔｃｋ．ｔｏｐ）；）　

ｅｎｄＤｏｅｕｍｅｎｔ（）　

（３）ｉｆ（ＸＰａｔｈ表达式的前缀＝“／／”）　

ｎｅｗ　ｎｅｘｔ，ｎｅｘｔ自反性＝ｔｒｕｅ；　

ｎｅｗ　ｅｄｇｅ（ｅ，ｎｅｘｔ），ｃｕｒｒｅｎｔ．ｅｄｇｅＬｉｓｔ．ａｄｄ（ｅｄｇｅ）　

ｃｌｅａｒ　ｓｔａｃｋ；｝　

ＮＦＡ．ａｄｄ（ｃｕｒｒｅｎｔ），ｃｕｒｒｅｎｔ＝ｎｅｘｔ，ｎｅｗ　ｎｅｘｔ；　

ｌａｚｙＤＦＡ的大小是由两个因素决定的，一个是ｌａｚｙＤＦＡ的　

状态数，另一个是ｌａｚｙＤＦＡ的每个状态对应的ＮＦＡ状态集合　

的大小。其中ｌａｚｙＤＦＡ的状态数不会随ＸＰａｔｈ表达式的数量而　

发生变化，它只与ＸＭＬ文档的结构有关；而ｌａｚｙＤＦＡ的每个状　

态对应的ＮＦＡ状态集合的大小随ＸＰａｔｈ表达式的数量呈线性　

增长，所以ｌａｚｙＤＦＡ的大小就会随着ＸＰａｔｈ表达式的数量呈线　

（４）ｉｆ（ＸＰａｔｈ表达式的前缀是“／”）　

ｎｅｗ　ｅｄｇｅ（ＸＰａｔｈ　ｎｏｄｅ，ｎｅｘｔ），ｃｕｒｒｅｎｔ．ｅｄｇｅＬｉｓｔ．ａｄｄ（ｅｄｇｅ）；　

ＮＦＡ．ａｄｄ（ｃｕｒｒｅｎｔ）；　

ＮＦＡ的不确定性决定了ＮＦＡ中的一个状态在同一个状态　

转移条件下会发生不确定的状态转移，即目的状态不确定，这　

对于海量的ＸＭＬ数据流上的ＸＰａｔｈ查询来说，ＮＦＡ的执行效　

率会随着ＸＰａｔｈ表达式数量的增加而下降。将ＮＦＡ确定化，产　

生与之相等价的确定性自动机（Ｄｅｔｅｒｍｉｎｉｓｔｉｃ　Ｆｉｎｉｔｅ　Ａｕｔｏｍａｔａ，　

简称ＤＦＡ），可唯一确定自动机的目的状态，但ＤＦＡ的状态数　

随ＸＰａｔｈ表达式中所含…／／’路径关系和“　’通配符的数量呈指　

数级增长，ＤＦＡ的执行效率下降。　

性增长。因此为了降低ｌａｚｙＤＦＡ处理ＸＭＬ数据流上大量ＸＰａｔｈ　

表达式的内存消耗，需要对ｌａｚｙＤＦＡ的构造算法进行优化。　

２．３　ｌａｚｙＤＦＡ构造算法的优化　

２．３．１共享ＮＦＡ状态表　

ｌａｚｙＤＦＡ的每个状态对应的ＮＦＡ状态集是影响ｌａｚｙＤＦＡ　

大小的主要因素，所以减小ＮＦＡ状态集的大小可减少ｌａｚｙＤＦＡ　

的内存使用量。　

在共享ＮＦＡ状态表优化算法中，将ｌａｚｙＤＦＡ状态对应的　

ＮＦＡ状态集中的状态分成两个集合：一个是共享状态集合，一　

个是独享状态集合。共享状态集合包含的是ＮＦＡ中那些具有　

自循环边的状态，那些不具有自循环边的状态就构成了独享状　

态集合。如果一个ｌａｚｙＤＦＡ状态的ＮＦＡ状态表里包含了共享　

状态集合，那么这个集合将存在于该ｌａｚｙＤＦＡ状态的所有后代　

ｌａｚｙＤＦＡ是ＮＦＡ在运行阶段生成的，ｌａｚｙＤＦＡ的状态数与　

ＸＰａｔｈ表达式数量无关，只与ＸＭＬ文档的结构有关，因此应用　

ｌａｚｙＤＦＡ处理ＸＭＬ数据流上的ＸＰａｔｈ查询时，ｌａｚｙＤＦＡ的状态　

数不会随ＸＰａｔｈ表达式的数量呈指数级增长，执行效率也不会　

随ＸＰａｔｈ表达式的数量而下降。　

２．２　ｌａｚｙＤＦＡ的构造　

ｌａｚｙＤＦＡ是在运行阶段由ＮＦＡ惰性地构造。ｌａｚｙＤＦＡ的一　

个状态对应　ＦＡ的一个状态集合，ｌａｚｙＤＦＡ的状态转移是由　

状态的ＮＦＡ状态表中，这是因为共享状态集合中的状态的转　

移条件是通配符“　’。　

例１　ＸＰａｔｈ表达式Ｑ＝ｌａ／Ｉｂｌ＊／ｄ／ｅ，根据Ｑ构造的ＮＦＡ和　

ＳＡＸ解析器解析ＸＭＬ文档产生的事件来触发的，包括的事　

张晓琳，崔　敏，谭跃生：基于ＬａｚｙＤＦＡ的ＸＰａｔｈ在ＸＭＬ数据流上查询优化算法　

ＤＦＡ如图３所示。状态ｓ２是ＮＦＡ中具有白循环边的一个状　

态，它构成了ＮＦＡ的共享状态集ｓｈａｒｅｄ＝ｓｅｔ＝｛Ｓ２｝，ＮＦＡ中其余　

状态构成了ＮＦＡ的独享状态集ｅｘｃｌｕｓｉｖｅ＝￣ｅｔ＝｛ＳＯ，Ｓ１，５３，ｓ４，　

５５，ｓ６）。ＤＦＡ状态｛ｓ１，５２｝包含了共享状态集ｓｈａｒｅｄ＿ｓｅｔ，从图中　

可以看到ｓｈａｒｅｄ＿ｓｅｔ存在于状态｛ｓｌ，ｓ２｝的所有后代状态中。　

，，

２００８，４４（２８）　１２７　

２．３．２建　状态转移表　

ｌａｚｙＤＦＡ的状态对应ＮＦＡ的一个状态集，因为ｌａｚｙＤＦＡ的　

构造是基于事件机制的，所以在自动机构造过程中，会出现为　

了不需要的事件而去查找ＮＦＡ状态表的情况，这会浪费查询　

时间。　

假设例１中，当前的ｌａｚｙＤＦＡ状态是Ｔ＝｛Ｓ２，Ｓ４｝，如果当前　

毫　

／　／　

、

．　

、一／　／　

宣　、　

＼一一　一，　

、　ｅ　

＼一，　

、　

解析到的事件是ｅ，正常情况下处理器会建立一个新的　

ｌａｚｙＤＦＡ状态并检查ｓ２和＿ｓ４的状态转移条件，发现在ｓ２和　

ｓ４中部没有ｅ转移条件，则丢弃这个新建的ｌａｚｙＤＦＡ状态。事　

件ｅ就是不需要的事件，而为了这个不需要的事件去查找状态　

对应的ＮＦＡ状态表，浪费了查询时『日Ｊ。　

图３　ＮＦＡ与对应的ＤＦＡ　

在这个优化算法中要对ｌａｚｙＤＦＡ状态的结构进行改进，在　

ｌａｚｙＤＦＡ状态中新增一个ＮＦＡ状态转移条件表，它存储的是　

ｌａｚｙＤＦＡ状态对应的ＮＦＡ状态集中的状态的转移条件，该状态　

转移条件表不包括　和　转移条件，一旦ｌａｚｙＤＦＡ状态建立，　

这个表就相应地建立了。　

数据结构如图４。　

含有共享状态表的ｌａｚｙＤＦＡ状态在状态转移条件下生成　

一

个新状态，新状态对应的ＮＦＡ状态集不仅包含共享状态集　

合，而且还包含目的独享状态集合。优化算法中将共享状态集　

合从ｌａｚｙＤＦＡ状态对应的ＮＦＡ状态集中独立出来，这时　

ｌａｚｙＤＦＡ状态对应的ＮＦＡ状态集是一个独享状态集合。构造　

ｌａｚｙＤＦＡ时分别对共享状态集合和独享状态集合进行运算，得　

到的两个结果集合中不具有自循环边的状态构成了一个新的　

ｌａｚｙＤＦＡ状态。通过这种方法可以减少ｌａｚｙＤＦＡ对应的ＮＦＡ状　

态集的大小，从而降低ｌａｚｙＤＦＡ的内存消耗。　

算法３　ｌａｚｙＤＦＡ的优化——共享ＮＦＡ状态表。　

ｓｔａｒｔＤｏｃｕｍｅｎｔ（）　

｛ｇｅｔ（ＮＦＡ．ｉｎｉｔｉａ１），ＤＦＡ．ｓｔａｒｔＳｔａｔｅ＝ＮＦＡ．ｉｎｉｔｉａｌ，ｐｕｓｈ（ＤＦＡ．ｓｔａｒｔＳｔａｔｅ）１　

ｓｔａｒｔＥｌｅｍｅｎｔ（Ｓｔｒｉｎｇ　ｑＮａｍｅ）ｆ　

ｅｘｃｌｕｓｉｖｅ

ｄｙｅｒ＝ｇｅｔ（ＤＦＡＳｔａｃｋ．ｔｏｐ）；　

ｅｘｃｌｕｓｉｖｅ

ｄｅｓｔ＝ｍｏｖｅ（ｅｘｃｌｕｓｉｖｅｄｙｅｒ，ｑＮａｍｅ）；　

ｓｈａｒｅｄ

ｄｅｓｔ＝ｍｏｖｅ（ｓｈａｒｅｄ，ｑＮａｍｅ）；　

ＤＦＡ图存储在Ａｎ＇ａｙＩ，ｉｓｔ数组ｌ｝】　

ｎｅｗ

ｅｄ

ｄｅｓｔ））；

ｄｖｅｒ＝ｅ—ｃｌｏｓｕｒｅ（ｕｎｉｏｎ（ｅｘｃｌｕｓｉｖｅ

ｄｅｓｔ，ｓｈａｒ

图４优化算法的数据模型　

ｔｈｅＳｔａｃｋ．ｐｕｓｈ（ｎｅｗ

ｄｖｅｒ）；ｌ　

例如，ｒ＝｛ｓ２，Ｓ４ｌ，由图３中的ＮＦＡ可看到，状态ｓ２的状态　

ｅｎｄＥｌｅｍｅｎｔ（Ｓｔｒｉｎｇ　ｑＮａｍｅ）　

转移条件是“　和ｂ，状态ｓ４的状态转移条件是ｄ，则与集合　

｛ｐｏｐ（ＤＦＡＳｔａｃｋ．ｔｏｐ）；｝　

ｅｎｄＤｏｃｕｍｅｎｔ（）　

｛ｃｌｅａｒ（ＤＦＡＳｔａｃｋ）；】　

｛ｓ２，ｓ４｝相对应的状态转移表Ｔｒａｎｓ＿ｔａｂｌｅ＝｛ｂ，ｄ｝。当解析到事件　

ｅ时，查询处理器将检查这个状态转移表，发现７１中不存在转　

移条件ｅ，这意味着事件ｅ是不需要的事件，查询处理就可以　

跳过ｅ及其下面的元素，这样大大缩短了查询时间。图５是状　

例２以例１的ＸＰａｔｈ查询语句为例，待查的ＸＭＬ数据　

流片断为：＜ｎ＞＜６＞＜ｃ＞＜ｄ＞＜ｅ＞＜，ｅ＞＜，ｄ＞＜／ｃ＞＜／６＞＜／０＞，表１为　

ｌａｚｙＤＦＡ运行时的独享ＮＦＡ状态集合及相应的共享ＮＦＡ状态　

集合。　

表１　ｌａｚｙＤＦＡ运行时的状态及共享集合　

态　所包含的ＮＦＡ状态集和相应的状态转移条件表。　

５状态　对应的ＮＦＡ状态集及状态转移条件表　

３性能测试与分析　

本文用Ｊａｖａ语言实现了ＮＦＡ、ｌａｚｙＤＦＡ构造算法和　

ｌａｚｙＤＦＡ构造的优化算法，并进行了性能测试。实验平台为：操　

作系统为ＷｉｎｄｏｗｓＸＰ，ＣＰＵ为Ｐ４，主频为１．７　Ｇ，内存５１２　Ｍ。实　

验数据是ＮＡＳＡ的ＸＭＬ数据集合，ＸＰａｔｈ表达式使用ＹＦｉｌｔｅ的　

通过实验可知，共享ＮＦＡ状态表的优化算法可以有效地　

ＸＰａｔｈ表达式生成工具生成。图６是ｌａｚｙＤＦＡ优化前后的内存　

减少ｌａｚｙＤＦＡ的内存使用量，但是以查询时问为代价。为了在　

减少ｌａｚｙＤＦＡ内在使用量的同时提高ｌａｚｙＤＦＡ的查询速度，在　

该优化算法基础上进行了进一步的优化。　

使用量比较，从实验结果可以看出共享ＮＦＡ状态表的优化算　

法可以减少ｌａｚｙＤＦＡ的内存使用量。图７是ｌａｚｙＤＦＡ优化前后　

（下转１３９页）　

陈园园，陈治平：一种基于代表点和点密度的聚类算法　２００８，４４（２８）　１３９　

参考文献：　

塑瓣　

（ａ）Ｄａｔａｓｅｔ２：Ｋ＝９，６＝０．７０　（ｂ）Ｄａｔａｓｅｔ２：Ｋ：９，６＝０．６７　

［１１　Ｈａｒｔ　ＪＷ，Ｋａｍｂｒ　Ｍ．Ｄａｔａ　ｍｉｎｉｎｇ　ｃｏｎｃｅｐｔｓ　ａｎｄ　ｔｅｃｈｎｉｑｕｅｓ［Ｍ］．Ｂｅｉ—　

ｊｉｎｇ：Ｈｉｇｈｅｒ　Ｅｄｕｃａｔｉｏｎ　Ｐｒｅｓｓ，２００１．　

［２］Ｅｓｔｅｒ　Ｍ，Ｋｒｅｇｅｌ　Ｈ　Ｐ，Ｓａｎｄｅｒ　Ｊ，ｅｔ　ａ１．Ａ　ｄｅｎｓｉｔｙ—ｂａｓｅｄ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　

ｄｉｓｃｏｖｅｒｉｎｇ　ｃｌｕｓｔｅｒｓ　ｉｎ　ｌａｒｇｅ　ｓｐａｔｉａｌ　ｄａｔａｂａｓｅｓ　ｗｉｔｈ　ｎｏｉｓｅ［Ｃ］／／Ｐｒｏ－　

ｃｅｅｄｉｎｇｓ　ｏｆ　２ｎｄ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ　

ａｎｄ　Ｄａｔａ　Ｍｉｎｉｎｇ，Ｐｏｒｔｌａｎｄ，Ｏｒｅｇｏｎ，Ｕ　Ｓ　Ａ，１９９６．　

图５　ＣＢＲＤ算法在Ｄａｔａｓｅｔ２上的聚类结果　

本实验表明，当簇密度分布不均时，本文的算法比ＤＢＳＣＡＮ　

算法可以得到更好的聚类结果。　

通过对这两个数据集的实验比较，可以发现ＣＢＲＤ算法不　

仅可以象ＤＢＳＣＡＮ算法一样可以发现任意形状的聚类，同时　

［３】Ａｎｋｅｒｓｔ　Ｍ，Ｂｒｅｕｎｉｇ　Ｍ，Ｋｒｉｅｇｅｌ　Ｈ　Ｐ，ｅｔ　ａ１．ＯＰＴＩＣＳ：Ｏｒｄｅｒｉｎｇ　Ｐｏｉｎｔｓ　

Ｔｏ　Ｉｄｅｎｔｉｆｙ　ｔｈｅ　Ｃｌｕｓｔｅｒｉｎｇ　Ｓｔｍｃｔｕｒｅ［Ｃ］／／Ｐｒｏｃ　ＡＣＭ　ＳＩＧＭＯＤ’９９，Ｉｎｔ　

Ｃｏｎｆ　ｏｎ　Ｍａｎａｇｅｍｅｎｔ　ｏｆ　Ｄａｔａ，Ｐｈｉｌａｄｅｌｐｈｉａ，ＰＡ，１９９９．　

［４］Ｌｉｎ　Ｃｈｉｈ—Ｙａｎｇ，Ｃｈａｎｇ　Ｃｈｉｎ—Ｃｈｅｎ，Ｌｉｎ　Ｃｈｉａ—Ｃｈｅｎ．Ａ　ｎｅｗ　ｄｅｎｓｉｔｙ－　

ｂａｓｅｄ　ｓｃｈｅｍｅ　ｆｏｒ　ｃｌｕｓｔｅｒｉｎｇ　ｂａｓｅｄ　ｏｎ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ［ＪＩ．Ｆｕｎｄａ－　

ｍｅｎｔａ　Ｉｎｆｏｒｍａｔｉｃａｅ，２００５，６８（４）：３１５—３３１．　

［５］Ｍａ　Ｄａｏｙｉｎｇ，Ｚｈａｎｇ　Ａｉｄｏｎｇ．Ａｎ　ａｄａｐｔｉｖｅ　ｄｅｎｓｉｔｙ－ｂａｓｅｄ　ｃｌｕｓｔｅｒｉｎｇ　

ｌｇｏｒｉａｔｈｍ　ｆｏｒ　ｓｐａｔｉａｌ　ｄａｔａｂａｓｅ　ｗｉｔｈ　ｎｏｉｓｅ［Ｃ］／／ＩＣＤＭ’０４．Ｆｏｕｒｔｈ　ＩＥＥＥ　

Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｄａｔａ　Ｍｉｎｉｎｇ，１－４　Ｎｏｖ　２００４：４６７－４７０．　

还解决了ＤＢＳＣＡＮ算法不能发现密度分布不均的数据样本的　

问题。　

５小结　

本文提出了一种基于代表点和点密度的聚类算法，算法以　

［６］Ｄａｓｈ　Ｍ，Ｌｉｕ　Ｍ，Ｘｕ　Ｘ．１＋１＞２：ｍｅｒｇｉｎｇ　ｄｉｓｔａｎｃｅ　ａｎｄ　ｄｅｎｓｉｔｙ　ｂａｓｅｄ　

ｃｌｕｓｔｅｒｉｎｇ［Ｃ］／／Ｐｒｏｃ　ｏｆ　７ｔｈ　ｌｎｔ　Ｃｏｎｆ　Ｄａｔａｂａｓｅ　Ｓｙｓｔｅｍｓ　ｆｏｒ　Ａｄｖａｎｃｅｄ　

Ａｐｐｌｉｃａｔｉ０ｎｓ（ＤＡＳＦＡＡ’０１），Ｈｏｎｇ　Ｋｏｎｇ，Ａｐｒｉｌ　２００１：１８－２０．　

点ｋ近邻的平均距离作为点密度，首先通过点密度及其近邻点　

的平均密度比，获取一满足密度阈值的点作为种子点。以此种　

子点作为第一个代表点，以后反复地在代表点的代表区域中寻　

找代表点，这些区域相连的代表点及其代表区域构成了一个　

类。算法不需要全局的密度分布隋况，因此对于样本分布不均　

［７］马帅，王腾蛟，唐世渭，等．一种基于参考点和密度的快速聚类算法ＩＪＪ　－

软件学报，２００３，１４（６）：１０８９—１０９５．　

【８］Ｄｅｒｙａ　Ｂｉｒａｎｔ，Ａｌｐ　Ｋｕｔ．ＳＴ—ＤＢＳＣＡＮ：ａｎ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｃｌｕｓｔｅｒｉｎｇ　

的数据集的聚类不受密度分布不均的影响，总能正确找到相应　

的聚类，实验结果证明本算法具有较好的聚类结果。但是算法　

在计算点的密度过程中需要消耗大量的时问和内存，如何提高　

算法的执行效率、减少内存消耗将是下一步的工作重点。　

ｓｐａｔｉａｌ—ｔｅｍｐｏｒａｌ　ｄａｔａ［Ｊ１．Ｄａｔａ＆Ｋｎｏｗｌｅｄｇｅ　Ｅｎｇｉｎｅｅｒｉｎｇ，２００７，６０　

（１）：２０８—２２１．　

［９］Ｇｅｏ￣ｅ　Ｋ，Ｈａｎ　Ｅ　Ｈ，Ｋｕｍａｒ　Ｖ．ＣＨＡＭＥＬＥＯＮ：ａ　ｈｉｅｒａｒｃｈｉｃａｌ　ｃｌｕｓ～　

ｔｅｒｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｕｓｉｎｇ　ｄｙｎａｍｉｃ　ｍｏｄｅｌｉｎｇ［Ｊ］．ＩＥＥＥ　Ｃｏｍｐｕｔｅｒ，１９９９，　

２７（３）：３２９—３４１．　

（上接１２７页）　

径表达式查询问题。并针对ｌａｚｙＤＦＡ的执行效率，从时间和空　

间两方面对ｌａｚｙＤＦＡ的构造进行了优化。由实验结果可以看出　

ｌａｚｙＤＦＡ及其优化技术可以有效地处理ＸＭＬ数据流上的　

ＸＰａｔｈ查询问题。　

的运行时间比较，可以看到，在ｌａｚｙＤＦＡ状态的结构中建立一　

个状态转移条件表会提高自动机的查询速度。实验结果可以表　

明，ｌａｚｙＤＦＡ构造的优化算法可以提高ｌａｚｙＤＦＡ的执行效率。　

舞　

ｌ　ｋ　】０　ｋ　１００　ｋ　

匿　

参考文献：　

［１］Ａｈｉｎｅｌ　Ｍ，Ｆｒａｎｋｌｉｎ　Ｍ．Ｅｆｉｃｉｆｅｎｔ　ｆｉｌｔｅｒｉｎｇ　ｏｆ　ＸＭＬ　ｄｏｃｕｍｅｎｔｓ　ｆｏｒ　

ｓｅｌｅｃｔｉｖｅ　ｄｉｓｓｅｍｉｎａｔｉｏｎ　ｏｆ　ｉｎｆｏｒｍａｔｉｏｎ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ＶＬＤＢ，　

Ｃａｉｒｏ，Ｅｇｙｐｔ，Ｓｅｐｔｅｍｂｅｒ　２０００：５３－６４．　

【２］Ｃｌａｒｋ　Ｊ．ＸＭＬ　Ｐａｔｈ　ｌａｎｇｕａｇｅ（ＸＰａｔｈ）［０　ＬＪ．［１９９９］．Ａｖａｉｌａｂｌｅ　ｆｒｏｍ　ｔｈｅ　

Ｗ３Ｃ，ｈｔｔｐ：／／ｗｗｗ．ｗ３．ｏｒｇ／ＴＲ／ＸＰａｔｈ．　

（３】Ｄｉａｏ　Ｙ，Ｆｉｓｃｈｅｒ　Ｐ．ＹＦｉｌｔｅｒ：ｅｆｆｉｃｉｅｎｔ　ａｎｄ　ｓｃａｌａｂｌｅ　ｆｉｌｔｅｒｉｎｇ　ｏｆ　ＸＭＬ　

ｄｏｃｕｍｅｎｔｓ［Ｃ］／／Ｐｒｏｃ　ｏｆ　ｔｈｅ　１８ｔｈ　Ｉｎｔ’１　Ｃｏｎｆ　ｏｎ　Ｄａｔａ　Ｅｎｇｉｎｅｅｒｉｎｇ，　

２００２：３４１—３４５．　

『４］Ｃｈａｎ　Ｃ，Ｆｅｌｂｅｒ　Ｐ，Ｇａｒｏｆａｌａｋｉｓ　Ｍ，ｅｔ　ａ１．Ｅｆｆｉｃｉｅｎｔ　ｆｉｌｔｅｒｉｎｇ　ｏｆ　ＸＭＬ　

ｄｏｃｕｍｅｎｔ　ｗｉｔｈ　ＸＰａｔｈ　ｅｘｐｒｅｓｓｉｏｎｓ［Ｃ］／／Ｐｒｏｃ　ｏｆ　ｔｈｅ　Ｉｎｔ’１　Ｃｏｎｆ　ｏｎ　

Ｄａｔａ　Ｅｎｇｉｎｅｅｒｉｎｇ．Ｓａｎ　Ｊｏｓｅ：ＩＥＥＥ　Ｃｏｍｐｕｔｅｒ　Ｓｏｃｉｅｔｙ，２００２：２３５—２４４．　

ｘｐａｔｈ大小　

［５］Ｇｒｅｅｎ　ｒｒＪ，Ｍｉｋｌａｕ　Ｇ，Ｏｎｉｚｕｋａ　Ｍ，ｅｔ　ａ１．Ｐｒｏｃｅｓｓｉｎｇ　ＸＭＬ　ｓｔｒｅａｍｉｎｇ　

ｗｉｔｈ　ｄｅｔｅｒｍｉｎｉｓｔｉｃ　ａｕｔｏｍａｔａ［Ｃ］／／Ｃａｌｖａｎｅｓｅ　Ｄ，Ｌｅｎｚｅｒｉｎｉ　Ｍ，Ｍｏｔｗａｎｉ　

Ｒ．Ｐｒｏｃ　ｏｆ　ｔｈｅ　Ｉｎｔ’１　Ｃｏｎｆ　ｏｎ　Ｄａｔａ　Ｔｈｅｏｒｙ，Ｓｉｅｎａ，Ｉｔａｌｙ．Ｎｅｗ　Ｙｏｒｋ，　

ＵＳＡ：ＡＣＭ　Ｐｒｅｓｓ．２００４：７５２—７８８．　

图７优化前后的ｌａｚｙＤＦＡ的运行时间比较　

４结束语　

本文给出了ＮＦＡ、ｌａｚｙＤＦＡ、优化的ｌａｚｙＤＦＡ的数据结构，　

［６］Ｇｕｐｔａ　ＡＫ，Ｓｕｃｉｕ　Ｄ．Ｓｔｒｅａｍ　ｐｒｏｃｅｓｓｉｎｇ　ｏｆ　ＸＰａｔｈ　ｑｕｅｒｉｅｓ　ｗｉｔｈ　

ｐｒｅｄｉｃａｔｅｓ［Ｃ］／／Ｈａｌｅｖｙ　ＡＹ，Ｉｖｅｓ　ＺＧ，Ｄｏａｎ　ＡＨ．Ｐｒｏｃ　ｏｆ　ｔｈｅ　２００３ＡＣＭ　

ＳＩＧＭＯＤ［ｎｔ’１　Ｃｏｎｆ　ｏｎ　Ｍａｎａｇｅｍｅｎｔ　ｏｆ　Ｄａｔａ

［Ｓ．１．］：ＡＣＭ，２００３：　

．

并在相应的数据模型上实现了ＮＦＡ、ｌａｚｙＤＦＡ构造算法和　

ｌａｚｙＤＦＡ构造的优化算法，解决了ＸＭＬ数据流上简单ＸＰａｔｈ路　

４１　９－４３０．