维普资讯 http://www.cqvip.com 第２４卷第１１期 计算机应用研究 Ｖｏ１．２４ Ｎｏ．１１ ２００７年１１月 Ａｐｐｌｉｃａｔｉｏｎ Ｒｅｓｅａｒｃｈ ｏｆ Ｃｏｍｐｕｔｅｒｓ ＮＯＶ．２００７ 一种支持高效检索的双重索引策略 唐恒娟 ，张云锋 （１．河南理工大学电气工程与自动化学院，河南焦作４５４００３；２．西安理工大学计算机科学与工程学院，西安 ７１００４８） 摘 要：从信息检索角度出发，提出一种高效的索引，在结构索引中集成了倒排文档，可同时查询ＸＭＬ结构部 分和关键词。双重索引策略很好地解决了基于路径表达式查询效率低的问题。 关键词：可扩展标记语言；路径表达式；双重索引；倒排文档 中图分类号：ＴＰ３１１ 文献标志码：Ａ 文章编号：１００１．３６９５（２００７）１１．００６３．０２ Ｄｕａｌ ｉｎｄｅｘ ｓｔｒａｔｅｇｙ ｗｈｉｃｈ ｓｕｐｐｏｒｔｓ ｈｉｇｈ ｅｆｆｉｃｉｅｎｔ ｓｅａｒｃｈｉｎｇ ＴＡＮＧ Ｈｅｎｇ－ｊｕａｎ ，ＺＨＡＮＧ Ｙｕｎ—ｆｅｎｇ （１．Ｃｏｌｌｅｇｅ ｏｆ Ｅｌｅｃｔｉｒｃａｌ Ｅｎｇｉｎｅｅｒｉｎｇ＆Ａｕｔｏｍａｔｉｏｎ，Ｈｅｎａｎ Ｐｏｌｙｔｅｃｈｎｉｃ Ｕｎｉｖｅｒｓｉｔｙ，ＪｉａＯＺＩＩ￣Ｈｅｎａｎ ４５４００３，Ｃｈｉｎａ；２．Ｃｏｌｅｌｇｅ ｏｆ Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ＆Ｓｃｉｅｎｃｅ，Ｘｉ’ａｎ ＴｅｃｈｎｏｌｏｇｙｏｆＵｎｉｅｖｒｓｉｔｙ，Ｘｉ’ａｎ ７１００４８，Ｃｈｉａｎ） ‘ Ａｂｓｔｒａｃｔ：Ｔｈｉｓ ｐａｐｅｒ ｅｘａｍｉｎｅｄ ａｎ ＸＭＬ ｃｏｌｌｅｃｔｉｏｎ ｆｒｏｍ ｔｈｅ ｖｉｅｗｐｏｉｎｔ ｏｆ ｉｎｆｏｒｍａｔｉｏｎ ｒｅｔｒｉｅｖａｌ（ＩＲ），ａｎｄ ｓｕｇｇｅｓｔｅｄ ａｎ ｅｆｉｆｃｉｅｎｔ ｉｎｄｅｘ ｗｈｉｃｈ ｃｏｍｂｉｎｉｎｇ ｔｈｅ ｉｎｖｅｒｔｅｄ ｆｉｌｅ ｗｉｔｈ ａ ｓｔｒｕｃｔｕｒｅ ｉｎｄｅｘ，ｉｔ ｃｏｕｌｄ ｉｍｐｌｅｍｅｎｔ ｒｅｔｒｉｅｖａｌ ｂｏｔｈ ｏｎ ｃｏｎｔｅｘｔ ａｎｄ ｓｔｒｕｃｔｕｒｅ．Ｔｈｅ ｐｒｏｂｌｅｍ ｏｆ ｌｏｗ ｑｕｅｒｙ ｅｆｉｆｃｉｅｎｃｙ ｂａｓｅｄ ｏｎ ｐａｔｈ ｅｘｐｒｅｓｓｉｏｎ ｗａｓ ｗｅｌｌ ｓｏｌｖｅｄ ｗｉｔｈ ｄｕａｌ ｉｎｄｅｘ ｓｔｒａｔｅｇｙ． Ｋｅｙ ｗｏｒｄｓ：ＸＭＬ（ｅｘｔｅｎｓｉｂｌｅ ｍａｒｋｕｐ ｌａｎｇｕａｇｅ）；ｐａｔｈ ｅｘｐｒｅｓｓｉｏｎ；ｄｕａｌ ｉｎｄｅｘ；ｉｎｖｅｔｒｅｄ ｉｆｌｅ 在当今的万维网中，ＸＭＬ语言形式无处不在。ＸＭＬ是 点相对应的节点类型和惟一标志符的集合；ｏｒｄ是实现为每个 Ｗｅｂ上进行信息表示与交换的一个层次数据格式” 。随着大 节点分配惟一标志符的映射函数；ｒｏｏｔ是文档的根节点；ｌｂａｅｌ 量ＸＭＬ数据的出现，如何有效地索引、存储和查询这些ＸＭＬ ＝ｌａｂｅｌＥ ＵｌｂａｅｌＴ Ｕｌａｂｅｌ 。其中：函数ｌｂａｅｌＥ中是每个元素节点 数据就成为目前值得研究的一个重要课题。因为ＸＭＬ是一种 的元素标记名；函数ｌａｂｅｌ 中是每个文本节点的内容；函数ｌａ— 半结构化的数据形式，传统的数据库存储方法和基于文本数据 ｂｅｌ 中是每个属性节点的属性名和属性值。 的信息检索方法都无法有效地对它进行操作。文献［２］提出， 当前处理半结构化数据的索引技术主要有值索引、字符串索 ２ 索引结构 引、路径索引、节点索引。其中路径索引和节点索引对查询条 ２．１ ＸＭＬ摘要树构造 件的结构部分是高效的，而值索引和字符串索引则是倾向于信 构造文档索引结构时首先要确定索引ＸＭＬ文档中需要的 息检索的方法，很容易实现对ＸＭＬ文本的检索，但是对于基于 词条；然后扫描整个解析后的文档，识别并抽取每一个元素和 路径表达式的查询效率很低。本文提出的索引技术可对包含 元素中的词条，并针对抽取出的每个词条和元素标志，取共有 路径和关键词的查询表达式实现高效检索，并给出了高效的更 词（ｓｔｏｐＷｏｒｄｓ），并抽取词根（ｓｔｅｍｍｅｒ）［３，４１。在扫描过程中， 新算法。 要按照共有词条表检查每个词条。如果一个词条不在共有词 １ 相关技术 条表中，则通过抽取词根算法加在共有词条表中。最后就是统 计文档中所有文本内容和标记出现情况。此过程会消除所有 一个ＸＭＬ文档可以看做是一个有序的、边标记的树。在 重复的路径和词条，并得到惟一的ＸＭＬ摘要树。如图１所示， ＸＭＬ树模型中一般有四种节点类型，即文档节点、元素节点、 ＸＭＬ摘要树保留了原始的ＸＭＬ文档结构，并比原始ＸＭＬ文 属性节点和文本节点。文档节点一般指向文档树的根节点，在 档占用的存储空问要小。例如：图２（ａ）是一个ＸＭＬ文档；（ｂ） 一个文档树中有且只有一个。元素节点指向其他的属性节点 是相应的ＸＭＬ摘要树。在摘要树中相同路径只出现一次，所 或文本节点。 有的文本内容和标记都用词根代替。 定义１一个ＸＭＬ文档树可以用一个有向图来表示：Ｇ＝ （ ， ， ，ＥＧ，∑Ｇ，ｒｏｏｔ，ｏｉｄ，ｌａｂｅｌ，ｏｒｄ）。其中： ， ， 分 别表示元素节点集、文本节点集和属性节点集；Ｅ。是树中边的 集合，边表示元素节点之间的关系；∑Ｇ和ｏｉｄ分别是每个节 图１ ＸＭＬ摘要树构造过程 收稿日期：２００６—０７—２０；修返日期：２００６—１０—１１ 基金项目：国家“８６３”计划资助项目（２００１ＡＡ１１３１８２）；陕西省科技攻关计划基金资助项 目（２００２Ｋ０６一Ｇ５） 作者简介：唐恒娟（１９６５一），女，河南济源人，讲师，主要研究方向为计算机应用与网络安全研究（ｈｅｎｇｊｕａｎ＠１２６．ｃｏｒｎ）；张云锋（１９８１一），男，河 南安阳人，助教，硕士，主要研究方向为网络安全、网格计算、无线传感器网络． 维普资讯 http://www.cqvip.com ・６４・ （ｄｏｃｕｍｅｎｔ ｉｄ＝２４） （ｒｅｐｏｒｔ＞ （ａｕｔｈｏｒ）Ｍ Ｂｌａｃｋ（ａｕｔｈｏｔ） （ｔｉｔｌｅ）ＸＭＬ（／ｔｉｔｌｅ） （／ｒｅｐｏｒｔ） ＜ｒｅｐｏｒｔ， 计算机应用研究 索引的内容是一件十分迫切的工作。 第２４卷 以前在倒排索引上，增量更新的工作大多是基于在静态文 档中增加一个新的文档 。通常是当一个文档内容发生变化 时，先将文档删除，再插入新的文档。当文档内容频繁地增加、 （ａｕｔｈｏｒ）Ｊ．Ｓｍｉｔｈ（ａｕｔｈｏｒ） （ｔｉｔｌｅ）Ｄａｔａ Ｍｏｄｅｌ（ｈｉｉｆｅ） （／ｒｅｐｏｒｔ） （／ｄｏｃｕｍｅｎｔ） （ａ１ ＸＭＬ文档实例 删除和更新时，这些过程会消耗大量的存储空间和时间。本文 Ｍ Ｂｌａｃｋ ＸＭＬ 提出，ＸＭＬ文档的插入和删除即转换为ＸＭＬ摘要树的插入和 Ｊ．Ｓｍｉｔｈ ｄａｔａ ｍｏｄｅｌ 删除，会使索引结构减小或增加。在ＸＭＬ文档库中增加一个 文档时，该文档相应的摘要树就会插入到索引结构中；同样，减 少一个文档也会删除它所对应的摘要树。ＸＭＬ文档的更新是 （ｂ１摘要树 图２ ＸＭＬ文档与摘要树 ２．２双重索引结构模型 在ＸＭＬ摘要树中简化了ＸＭＬ文档的重复路径，并减少了 通过一系列的插入、删除操作完成的。算法１给出了在索引结 构中插入一个新的摘要树的过程。其结构部分存储在结构索 存储空间。但是由于同时混合着ＸＭＬ的结构和内容信息，对 它进行查询的效率太低。当前ＸＭＬ文档索引技术主要分为倒 排索引和路径索引。路径索引对路径表达式的查询是高效的， 但是它对于文档中的属性值或关键词的搜索几乎没有效率。 倒排索引文档内容的检索很高效，但它用在路径表达式时需要 连接很多大型倒排文件，其Ｉ／Ｏ代价和连接的系统开销均 很大。 本文提出利用摘要树的特点，结合上述两种索引技术实现 对路径和文本内容更好的检索。由上述可知，摘要树中消除了 重复路径，可以利用摘要树构造结构索引。结构索引是路径索 引的一个分支，其主要思想就是用最少的节点和边表示文档树 中所有的路径信息，把摘要树中所有的等价节点用一个节点表 示。在此定义一个函数Ｆ（ｎ）用于记录节点ｎ在摘要树中的等 价节点。如果从Ｆ（ｏ）中的某节点到Ｆ（ｂ）的某节点有一条边， 则在索引节点ａ与索引节点ｂ之间加一条边。结构索引中的 每个节点ａ均有一个惟一标志符ｉｄ（ｏ）。 在ＸＭＬ文档系统库中，倒排表是在标记名和关键词上构 造的，它可以有效支持ＸＭＬ文档中关键词的搜索。对文档树 中的每个文本词条，在倒排表中可以用四元组形式表示：（ｄｏ— ｃｉｄ，ｓｔａｒｔ，ｌｅｖｅｌ，ｉｎｄｅｘｉｄ）。倒排索引是一系列倒排表的集合。 ｄｏｃｉｄ表示文档的惟一标志符；ｓｔｍ＇ｔ表示词条在文档出现的位 置；ｌｅｖｅｌ表示在文档树中节点的深度；ｉｎｄｅｘｉｄ表示惟一索引ｉｄ 号。因此基于上述分析，根据路径和内容关系分离，可以得到 结构索引和倒排索引的ＸＭＬ摘要树双重索引结构模型，如图 ３所示。 倒排表 图３双重索引结构模型 在图３中，倒排表中存储的是内容数据，结构索引中记录 的则是文档的所有单路径信息。其中得到的结构索引中每 个节点的惟一标志符ｉｄ（ｏ）和倒排表中的ａ．ｉｎｄｅｘｉｄ域是等 价的。 ２．３双重索引更新算法 当前Ｗｅｂ上文档经常发生变化。在１９９８年ｃｒａｗｌｅｒ基本 上要用一个月才能完成一次网络的搜索 ｊ，而现在使用Ｇｏｏｇｌｅ 可以检索到三天前在Ｗｅｂ上发布的信息。对于每天发展变化 的网络来说，为使用户及时得到网络上的更新信息，快速更新 引中，节点的内容存储在倒排文档中。 算法１ Ｉｎｓｅｒｔ（Ｔ，Ｐ，Ｉ） 输入：Ｔ指向要插入索引结构Ｓ的摘要树的根节点。索引包括Ｉ和 Ｐ；Ｉ是倒排表中文本内容列表；Ｐ是结构索引的根。 输出：包含新的摘要树的索引结构。 ｉｆ Ｓ＝ ｛创建一个新的根节点Ｐ；｝ ．函数Ｆ（Ｎ）返回结构索引中指向Ｎ的等价节点； 调用递归函数ＡｄｄＳｕｍｍａｒｙＴｒｅｅ（Ｔ，Ｐ）； ＡｄｄＳｕｍｍａｒｙＴｒｅｅ（ｔ，Ｐ） ／／ｔ和Ｐ分别是指向树Ｔ和Ｐ中节点的指针 ｉｆ Ｐ中不含孩子节点 ｔｈｅｎ｛ 增加Ｐ的一个孩子节点ｃ； Ｓｅｔ Ｆ（Ｃ）＝Ｆ（ｔ）； ＵｐｄａｔｅＩｎｖｅｒｔｅｄＦｉｌｅ（Ｉ，ｔ，Ｃ）； ｝ ｆｏｒｔ中的每个孩子Ｘ ｄ０ ＡｄｄｓｕｍｍａｒｙＴｒｅｅ（ｘ，Ｃ）； ＵｐｄａｔｅＩｎｖｅｒｔｅｄＦｉｌｅ（Ｉ，ｔ，Ｃ）调用一个过程存储倒排文件Ｉ 中节点ｔ的文本内容，并在倒排表中更新所有必要的词条。此 外，该过程在结构索引的节点Ｃ和倒排表中每个新插入的文本 词条之间建立了联系，这样将词条与词条在文档中的路径联系 起来了。ＵｐｄａｔｅＩｎｖｅｒｔｅｄＦｉｌｅ过程用于更新倒排表，并在结构索 引中增加相应的链接。该过程描述如下： ＵｐｄａｔｅＩｎｖｅｒｔｅｄＦｉｌｅ（Ｉ，ｔ．Ｃ） 输入：ｃｏｎｔｅｎｔ（ｔ）是摘要树中节点ｔ的文本内容；Ｉ是存储ｃｏｎｔｅｎｔ （ｔ）的倒排表；ｃ是ｃｏｎｔｅｎｔ（ｔ）中所有词条与结构索引的连接。 输出：更新的倒排表。 ｏｆｒ ｃｏｎｔｅｎｔ（ｔ）的每个词条Ｘ ｄ０｛ Ｉｆ Ｘ不在Ｉ的词汇表中 ｔｈｅｎ 在Ｉ中加入ｘ； 根据倒排表中的词条Ｘ更新Ｉ； 在结构索引上标记词条Ｘ出现的位置Ｃ； ｝ 文档的删除实际是根据文档ＩＤ值删除倒排表中相应的词 条，然后在结构索引中删除那些与倒排表域ｄｏｃｉｄ中没有任何 联系的节点。由前文可知，倒排表中四元组中域ｄｏｃｉｄ存储的 就是文档的标志符。该算法实现起来比较简单，在此不再 赘述。 ２．４查询算法研究 查询索引的过程分为两个步骤：根据查询条件搜索文档的 路径部分；根据查询条件搜索文档的文本内容。（下转第７３页） 维普资讯 http://www.cqvip.com 第１１期 李玲娟，等：基于ＸＭＬ的案例表示和案例库构造方法 ・７３・ （ｒｅａｔｕｒｅｖｌａｕｅ）ＡＮＹ（／ｆｅａｔｕｒｅｖｌａｕｅ） 为目标，对基于ＸＭＬ语言的案例表示和案例库构造方法作了 （／ｒｅｕｉｒｅｄｆｅａｔｕｒｅ） 研究，提出了对规则进行基于ＸＭＬ的案例化的具体方法，分析 一（ｏｐｔｉｏｎａｌｆｅａｔｕｒｅ） （ｏ＿ｆｅａｔｕｒｅｎａｍｅ）ｄｈｏｓｔ（／ｏ＿ｆｅａｔｕｒｅｎａｍｅ） 了基于ＸＭＬ的案例表示方法较之传统数据库形式的优势，并 （ｆｅａｔｕｒｅｖｌａｕｅ）５（／ｆｅａｔｕｒｅｖａｌｕｅ） 通过将之应用于Ｓｎｏｒｔ规则的案例化，证明了所提出的方法的 （ｏ＿ｆｅａｔｕｒｅｎａｍｅ）ｄｐｏｒｔ（／ｏ＿ｆｅａｔｕｒｅｎａｍｅ） （ｆｅａｔｕｒｅｖａｌｕｅ）２０（／ｆｅａｔｕｒｅｖｌａｕｅ） 有效性。 （ｏ＿ｆｅａｔｕｒｅｎａｍｅ）ｔｉｍｅ（／ｏ＿ｆｅａｔｕｒｅｎａｍｅ） 参考文献： （ｆｅａｔｕｒｅｖｌａｕｅ）６０（／ｆｅａｔｕｒｅｖｌａｕｅ） ［１］ＷＡＴＳＯＮ Ｉ．ＣＢＲ ｉｓ ａ ｍｅｔｈｏｄｏｌｏｇｙ ｎｏｔ ａ ｔｅｃｈｎｏｌｏｇｙ［Ｊ］．Ｔｈｅ （／ｏｐｔｉｏｎａｌｆｅａｔｕｒｅ） 一（ｓｏｌｕｔｉｏｎ） Ｋｎｏｗｌｅｄｇｅ Ｂａｓｅｄ Ｓｙｓｔｅｍｓ Ｊｏｕｒｎａｌ，１９９９，１２（５—６）：３０３—３０８． 一（ｓｎｏｒｔｃａｓｅ） ［２］ＬＥＡＫＥ Ｄ Ｂ．Ｃａｓｅ—ｂａｓｅｄ ｒｅａｓｏｎｉｎｇ：ｅｘｐｅｉｒｅｎｃｅｓ，ｌｅｓｓｏｎｓ ａｎｄ ｆｕｔｕｒｅ （ｃａｓｅｉｄ）２（／ｃａｓｅｉｄ） ｄｉｅｒｃｔｉｏｎｓ［Ｍ］．２ｎｄ ｅｄ．Ｃａｍｂｒｉｄｇｅ：ＡＡＡＩ Ｐｒｅｓｓ／Ｍ１Ｔ Ｐｒｅｓ，２０００： ＋（ｒｅｑｕｉｒｅｄｆｅａｔｕｒｅ） ４２０． ＋（ｏｐｔｉｏｎａｌｆｅａｔｕｒｅ） ＋（ｓｎｏｒｔｃａｓｅ） ［３］陈文伟，黄金才．数据仓库与数据挖掘［Ｍ］．北京：人民邮电出版 田＜ｓｎｏｒｔｃａｓｅ） 社，２００４：２０４—２１０． （／ＳｎｏｒｔＣａｓｅＶａｃｔｏｒ） ［４］刘芳，姚莉，王长缨，等．基于语义Ｗｅｂ的案例表示和ＣＢＲ系统结 Ｓｎｏｒｔ规则转换成的案例由不同的特征组成，是非结构化 构研究［Ｊ］．计算机应用，２００４，２４（１）：１７—１９． 的。采用ＸＭＬ语言表示不仅简单、灵活、易于理解，而且能很 ［５］ＨＡＹＥＳ Ｃ，ＣＵＮＮＩＮＧＨＡＭ Ｐ．Ｓｈａｐｉｎｇ ａ ＣＢＲ ｖｉｅｗ ｗｉｔｈ ＸＭＬ［ｃ］／／ 好地反映复杂的层次型结构知识；它以文本形式存储，能 Ｐｍｃ ｏｆ ｔｈｅ ３ｒｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃａｓｅ—ｂａｓｅｄ Ｒｅａｓｏｎｉｎｇ， 于应用程序存在。 ＩＣＣＢＲ’９９．Ｓｅｅｏｎ Ｍｏｎａｓｔｅｒｙ：［Ｓ．ｎ．］，１９９９：４６８—４８１． ［６］周凯波，金斌，冯珊．一种分布式ＣＢＲ工具研究与设计［Ｊ］．华中 ３结束语 科技大学学报：自然科学版，２００５，３３（９）：３３—３５． ［７］李玲娟．基于数据挖掘的Ｓｎｏｔｒ增强模型的研究［Ｊ］．南京邮电学 案例表示是ＣＢＲ方法中的关键性技术，ＣＢＲ方法的成功 院学报，２００４，２４（４）：１—５． 与否很大程度上取决于其案例库，只有合理表示的案例才能使 ［８］李玲娟，王汝传．基于规则的ＩＤＳ中ＣＢＲ的研究［Ｊ］．计算机科 得ＣＢＲ方法正确推理。本文以拓展ＣＢＲ方法的研究和应用 学，２００６，３３（５）：１１７—１２０． （上接第６４页） 的搜索引擎系统。其中采用本文给出的索引策略，用Ｊａｖａ编 查询过程将查询条件分为几个连接条件。每个条件包含 程实现，不到２ ｒａｉｎ就完成了索引的构建，并占用了３．８ ＭＢ的 路径和文本部分。路径由结构索引给出查询结果。如果有匹 存储空间。对查询表达式的检索结果符合条件，对它进行了 配，就会得到所有符合条件的倒排表，令为集Ａ；同样文本内容 ５０次的查询，平均检索时间为０．１３ Ｓ。由此可见，本文所提出 的查询可得到集Ｂ。最后的查询结果就是Ａ和Ｂ的交集。算 的一种支持高效检索的双重索引策略具有较高的理论和实用 法２给出了查询的过程。 价值。 算法２双重索引查询算法 输入：由连接的查询条件 ， ，…，Ｘ 组成的ｑｕｅｒｙ（Ｑ）。 参考文献： 输出：查询结果集Ｓ。 ［１］Ｗｏｒｌｄ Ｗｉｄｅ Ｗｅｂ Ｃｏｎｓｏｒｔｉｕｍ Ｘｑｕｅｒｙ１．０ ａｎｄＸｐａｔｈ２．０ ｄａｔａｍｏｄｅｌ Ｑｕｅｒｙ—Ｆｕｎｃｔｉｏｎ（Ｑ）｛ ［ＥＢ／ＯＬ］．（２００４—０７—２３） ｈｔｔｐ：／／ｗｗｗ３．ｏｒｇ／ＴＲ／ｘｐａｔｈ ｄａｔａｍｏ一 Ｓｅｔ Ｓ＝ ： ｄｅｌ／． 把Ｑ分为几个连接的查询条件Ｘ；； ［２］ＷＡＮＧ Ｘｉａｏ—ｌｉｎｇ，ＷＥＮ Ｊｉ—ｍｎｇ，ＬＩＵ Ｗｅｎ—ｙｉｎ．Ｅｎｈａｎｃｉｖｅ ｉｎｄｅｘ ｆｏｒ Ｆｏｒ ｅａｃｈ ｔｅｒｍ Ｘｉ（１≤ｉ≤ｎ）ｏｆ Ｑ ｄ０｛ ｓｔｒｕｃｔｕｒｅｄ ｄｏｃｕｍｅｎｔ ｒｅｔｒｉｅｖａｌ［Ｃ］／／Ｐｒｏｃ ｏｆ ｔｌｌｅ １２ｔｌｌ Ｉｎｔｅｍａｔｉｏｎａｌ 在倒排表中找出与条件Ｘｉ匹配的集Ｔｉ； Ｗｏｒｋｓｈｏｐ ｏｎ Ｒｅｓｅａｒｃｈ Ｉｓｓｕｅｓ ｏｎ Ｄａｔａ Ｅｎｇｉｎｅｅｒｉｎｇ．２００２． 在文档词条中找出与条件Ｘ 路径匹配的集Ａｉ； ［３］ ＭＩＫＨＥＥＶ Ａ．Ｄｏｃｕｍｅｎｔ ｃｅｎｔｅｒｅｄ ａｐｐｒｏａｃｈ ｔｏ ｔｅｘｔ ｎｏｒｍａｌｉｚａｔｉｏｎ Ｅｘｔｒａｃｔ（倒排列表指向Ｘｉ文本的集合）ｆｒｏｍ Ｔｉ集合； ［Ｃ］／／Ｐｒｏｃ ｏｆ ｔｈｅ Ａｎｎｕｌａ ＡＣＭ Ｃｏｆｎｅｒｅｎｃｅ Ｏｉｌ Ｒｅｓｅａｒｃｈ ｎａｄ Ｄｅｖｅｌｏｐ— Ｓｅｔ文档列表为集Ｂ ； ｍｅｎｔ ｉｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｒｅｔｒｉｅｖａ１．２０００：１３６—１４３． ｝ ｝ ｎ ［４］ＰＯＲＴＥＲ Ｍ．Ｐｏｒｔｅｒ ｓｔｅｍｍｉｎｇ ａｌｇｏｉｒｈｔｍ［ＥＢ／ＯＬ］．（２００３）．ｈｔｔｐ：／／ 结果集Ｓ为Ｓ＝ｆ３Ａｌｆ３Ｂｌ ．ＷＷＷ．ｔａｒｂｔｒｕｓ，０ ～ｍａｒｉｔｎ． ［５］ＬＩＭ Ｌ，ＷＡＮＧ Ｍｉｎ，ＰＡＤＭＡＮＡＢＨＡＮ Ｓ．Ｄｙｎａｍｉｃ ｍａｉｎｔｅｎｎａｃｅ ｏｆ ３结束语 ｗｅｂ ｉｎｄｅｘ ｕｓｉｎｇ ｌｎａｄｍａｒｋｓ［Ｒ］．Ｂｕｄａｐｅｓｔ，Ｈｕｎｇａｒｙ：ＡＣＭ，２００３． ［６］ＢＲＯＷＮ Ｅ Ｗ，ＣＡＬＬＡＮ Ｊ Ｐ，ＣＲＯＦＦ Ｗ Ｂ．Ｆａｓｔ ｉｎｃｒｅｍｅｎｔａｌ ｉｎｄｅ— 本文提出的算法，采用ＮＡＳＡ公开的ＸＭＬ档案文件 数 ｘｉｎｇ ｆｏｒ ｕｆｌｌ—ｔｅｘｔ ｉｆｎｏｒｍａｔｉｏｎ ｒｅｔｉｒｅｖａｌ［Ｃ］／／Ｐｍｃ ｏｆ ｈｔｅ ２０ｔｈ Ｉｎｔｌ Ｃｏｆｎ 据集进行实验。结果表明，实验数据集由８５７个ＸＭＬ文件组 ｏｎ Ｖｅｒｙ Ｌａｒｇｅ Ｄａｔａ Ｂａｓｅｓ．１９９４：１９２—２０２． 成，约ｌ１ ＭＢ。在配置Ｐｅｎｔｉｕｍ４ ２．４ ＧＨｚ迅驰ＣＰＵ，２５６ ＭＢ内 ［７］ＸＭＬａｓｔｒｏｎｏｍｙａｒｃｈｉｖｅ ａｔＮＡＳＡ［ＥＢ／ＯＬ］．（２００２）．ｈｔｔｐ：／／ｘｍ１．ｇｓ— 存，装有Ｗｉｎｄｏｗｓ ２０００ Ｓｅｒｖｅｒ操作系统的Ｐｃ上运行一个小型 ｆｃ．ｎａｓａ．ｇｏｖ／ａｒｅｈｉｖｅ．
