FastMatch一种高效的XML关键字查询算法.pdf

第２９卷第６期 计 算 机 应 用 研 究 Ｖｏｌ．２９Ｎｏ．６ ２０１２年６月　 ＡｐｐｌｉｃａｔｉｏｎＲｅｓｅａｒｃｈｏｆＣｏｍｐｕｔｅｒｓ Ｊｕｎ．２０１２ ＦａｓｔＭａｔｃｈ：一种高效的ＸＭＬ关键字查询算法 崔　健，周军锋，郭景峰 （燕山大学信息科学与工程学院，河北秦皇岛０６６００４） 摘　要：现有的ＸＭＬ关键字查询方法包括两步：确定满足特定语义的节点；构建满足特定条件的子树。这种处 理方式需要多次扫描关键字倒排表，效率低下。针对这一问题，提出快速分组方法来减少扫描倒排表次数，进而 基于快速分组方法提出ＦａｓｔＭａｔｃｈ算法。该算法仅需扫描一次关键字倒排表就能构建满足特定条件的子树，从 而提高了查询效率。最后通过实验验证了该方法的高效性。 关键词：ＸＭＬ；关键字查询；效率；快速分组；ＦａｓｔＭａｔｃｈ 中图分类号：ＴＰ３１１１３　　　文献标志码：Ａ　　　文章编号：１００１３６９５（２０１２）０６２１８４０４ ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１３６９５．２０１２．０６．０４８ ＦａｓｔＭａｔｃｈ：ａｎｅｆｆｉｃｉｅｎｔａｌｇｏｒｉｔｈｍｆｏｒＸＭＬｋｅｙｗｏｒｄｓｅａｒｃｈ ＣＵＩＪｉａｎ，ＺＨＯＵＪｕｎｆｅｎｇ，ＧＵＯＪｉｎｇｆｅｎｇ （ＣｏｌｌｅｇｅｏｆＩｎｆｏｒｍａｔｉｏｎＳｃｉｅｎｃｅ＆Ｅｎｇｉｎｅｅｒｉｎｇ，ＹａｎｓｈａｎＵｎｉｖｅｒｓｉｔｙ，ＱｉｎｈｕａｎｇｄａｏＨｅｂｅｉ０６６００４，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：ＥｘｉｓｔｉｎｇｍｅｔｈｏｄｓｏｆＸＭＬｋｅｙｗｏｒｄｓｅａｒｃｈｎｅｅｄｆｉｒｓｔｌｙｉｄｅｎｔｉｆｙｑｕａｌｉｆｉｅｄｒｏｏｔｎｏｄｅｓｓａｔｉｓｆｙｉｎｇｓｐｅｃｉｆｉｅｄｓｅｍａｎｔｉｃｓ， ｔｈｅｎｃｏｎｓｔｒｕｃｔｓｕｂｔｒｅｅｒｅｓｕｌｔｓｔｈａｔｍｅｅｔｓｏｍｅｃｅｒｔａｉｎｃｏｎｄｉｔｉｏｎｓ．Ｓｕｃｈａｓｔｒａｔｅｇｙｎｅｅｄｓｔｏｐｒｏｃｅｓｓａｌｌｎｏｄｅｓｉｎｔｈｅｉｎｖｅｒｔｅｄｌｉｓｔｓ ｍｏｒｅｔｈａｎｏｎｃｅ，ｓｏｉｔｉｓｉｎｅｆｆｉｃｉｅｎｔｉｎｐｒａｃｔｉｃｅ．Ｔｏｓｏｌｖｅｔｈｉｓｐｒｏｂｌｅｍ，ｔｈｉｓｐａｐｅｒｐｒｏｐｏｓｅｄａｍｅｔｈｏｄｕｓｅｄｆａｓｔｇｒｏｕｐｔｏｒｅｄｕｃｅ ｔｈｅｔｉｍｅｓｏｆｓｃａｎｉｎｇｔｈｅｉｎｖｅｒｔｅｄｌｉｓｔｓ，ｔｈｅｎｐｒｏｐｏｓｅｄａａｌｇｏｒｉｔｈｍｎａｍｅｄＦａｓｔＭａｔｃｈｂａｓｅｄｏｎｔｈｅｍｅｔｈｏｄ．Ｔｈｉｓａｌｇｏｒｉｔｈｍｆｏｕｎｄ ａｌｌｓｕｂｔｒｅｅｒｅｓｕｌｔｓｍｅｅｔｉｎｇｓｏｍｅｃｅｒｔａｉｎｃｏｎｄｉｔｉｏｎｓｂｙｓｃａｎｎｉｎｇａｌｌｎｏｄｅｓｉｎｔｈｅｉｎｖｅｒｔｅｄｌｉｓｔｓｏｎｌｙｏｎｃｅ．Ｔｈｅｅｘｐｅｒｉｍｅｎｔａｌｒｅ ｓｕｌｔｓｖｅｒｉｆｙｔｈｅｈｉｇｈｐｅｒｆｏｒｍａｎｃｅｏｆｔｈｉｓｍｅｔｈｏｄ． Ｋｅｙｗｏｒｄｓ：ＸＭＬ；ｋｅｙｗｏｒｄｓｅａｒｃｈ；ｅｆｆｉｃｉｅｎｔ；ｆａｓｔｇｒｏｕｐ；ＦａｓｔＭａｔｃｈ Ｐ 径子树ｔ，是以ｖ为根的子树，包含从ｖ到直接包含关键字的 ｖ 　引言 Ｍ 所有节点的路径；ｃ）匹配子树ｔ，是以ｖ为根，并在去除冗余信