CN103425719A - 结构化文档检索装置和程序 - Google Patents

Abstract

本发明提供一种结构化文档检索装置和程序，能够进行组合了基于XML标签的结构信息和基于注释标签的结构信息的双方的结构检索。具备：处理器，其执行程序；第一存储区域，其存储程序；第二存储区域，其存储满足树结构条件的结构化文档以及对该文档附加的注释数据；文档结构列表构筑部，其针对使根据上述结构化文档的标签的包含关系和上述注释数据的标签的包含关系单独得到的DOM树的根要素通用化的结构，分配结构化文档的文本，生成文本共有DOM树；检索处理部，其从文本共有DOM树中检索与检索查询符合的要素。

Description

结构化文档检索装置和程序

技术领域

本发明涉及一种根据标签的结构和/或字符串数据检索由结构化语言记载的文档（以下称为“结构化文档”）以及以任意的形式附加了注释数据的结构化文档的结构化文档检索装置和通过计算机实现其功能的程序。

背景技术

XML（Extensible Markup Language：可延伸性标志语言）是能够对文本记载结构信息的数据格式，通过使用被称为标签的“<”、“>”围住的字符串，能够向文本内记载结构信息。XML能够通过将标签记载为嵌套状来表现层级状的树结构，能够通过标签的追加/删除来变更层级状的树结构。因此，作为财务信息的记录、专利说明书的记录、电子商务交易中的数据交换、软件的文件形式的格式而广泛使用XML。以下，将使用XML记载的文档称为XML文档。在XML文档中，能够在检索条件中使用结构和文本双方来进行检索。在XML文档的检索查询方式中，有W3C推荐的XPath等。

另一方面，针对一般的文本数据，作为用于附加注释的技术之一，有UIMA（Unstructured Information Management Architecture非结构化信息管理架构）。UIMA是为了管理没有结构化的文档等数据而使用的技术，提供一种能够向文档附加注释标签的平台。UIMA与XML不同，不需要以满足树结构条件的形式附加标签。因此，UIMA用于作为计算机得到的文法结构分析的结果，如向文档中的技术上重要的部分等进行标记那样，保存在结构之间未必需要满足树结构关系的文档结构信息。

但是，想到在结构之间不保证满足树结构关系的文档结构信息会逐渐增加。因此，要求一种不受树结构关系约束，能够通过结构条件和文本条件进行检索的技术。

但是，作为计算机通过自动提取得到的结果（例如文法结构的分析结果、基于文本的含义信息（例如重要技术、效果等）的文档结构的分析结果）或手动进行标记的结果，该结构信息不限于满足树结构条件。因此，针对包含不满足树结构条件的结构信息的文档，无法利用现有的XML检索方法。

根据以上理由，在结构上没有制约的标签信息的检索中，使用了根据UIMA准备的检索功能（专利文献1）。但是，在该检索方式中，没有考虑到基于标签的包含关系的层级结构。因此，在UIMA所准备的检索功能中，被指定为检索查询的文本只能执行验证是否包含在各标签中的布尔检索。

结果在对XML文档准备的现有的检索功能或根据UIMA准备的现有的检索功能中，针对带有注释的XML文档，无法执行考虑到XML的结构条件和注释的结构条件双方的检索。

【专利文献1】美国专利申请公开第2004/0243560号说明书

【非专利文献1】清水敏之、鬼塚真、江田毅晴、吉川正俊、XMLデ一タの管理とストリ一ム処理に関する技術、電子情報通信学会論文誌D J9O-D(2)：159-184、2007

【非专利文献2】G.Navarro and V.Makinen、Compressed full-text indexes、ACM Computing Surveys39（1）、2007

发明内容

本发明考虑到上述的问题点，在由标签的结构满足树结构条件的结构化文档和与该文档对应的任意的注释的结构信息形成的结构不满足树结构条件的情况下，也能够进行考虑了结构条件和文本双方的检索。

本说明书包含用于解决上述问题的多个发明。作为其中一例的发明具备：处理器，其执行程序；第一存储区域，其存储程序；第二存储区域，其存储满足树结构条件的结构化文档以及对该文档附加的注释数据；文档结构列表构筑部，其针对使根据上述结构化文档的标签的包含关系和上述注释数据的标签的包含关系单独得到的DOM（Document Object Model：文档目标模型）树的根要素通用化的结构，分配结构化文档的文本，生成文本共有DOM树；检索处理部，其从文本共有DOM树中检索与作为检索查询提供的位置路径符合的要素。

根据本发明，能够实现通过包含以任意的形式附加的注释的结构信息和文本双方进行的检索。通过以下的实施方式的说明，能够了解上述以外的问题、结构和效果。

附图说明

图1-1是表示结构化文档检索装置的结构例的图（第一实施例）。

图1-2是表示存储在主存储装置中的程序和数据的一个例子的图（第一实施例）。

图2是说明注释组的一个例子的图（各实施例通用）。

图3是表示文本共有DOM树的一个例子的图（各实施例通用）。

图4是说明结构化文档检索装置的预处理的流程的图（第一实施例）。

图5是表示DOM树构筑部的处理例子的流程图（第一实施例）。

图6是表示文档结构列表构筑部的处理例子的流程图（第一实施例）。

图7是表示父子关系分析/登录部的处理例子的流程图（第一实施例）。

图8是说明结构化文档检索装置的检索处理的流程的图（第一实施例）。

图9是表示DOM DAG的一个例子的图（第二实施例）。

图10是说明综合了2个DOM DOG的路径DAG和转置索引的一个例子的图（第二实施例）。

图11是表示转置索引构筑部的处理例子的流程图（第三实施例）。

图12是表示深度分配部的处理例子的流程图（第三实施例）。

图13是表示路径DAG ID取得部的处理例子的流程图（第三实施例）。

图14是表示路径DAG要素生成/登录部的流程图（第三实施例）。

图15是表示转置索引登录部的处理例子的流程图（第三实施例）。

图16是说明DOM DAG的记录例子的图（第四实施例）。

图17是表示检索索引的概要的图（第四实施例）。

图18是表示检索索引构筑部的处理例子的流程图（第四实施例）。

图19是表示检索索引登录部的处理例子的流程图（第四实施例）。

图20是表示路径DAG ID登录部的处理例子的流程图（第四实施例）。

图21是表示位置路径检索部的处理例子的流程图（第四实施例）。

图22是表示XML要素检索部的处理例子的流程图（第四实施例）。

图23是表示注释要素检索部的处理例子的流程图（第四实施例）。

图24是表示扩展小波树的概要的图（第六实施例）。

图25是表示扩展小波树构筑部的处理例子的流程图（第六实施例）。

图26是表示等级计算部的处理例子的流程图（第六实施例）。

图27是表示选择计算部的处理例子的流程图（第六实施例）。

具体实施方式

下面，基于附图说明本发明的实施例。另外，本发明并不限于后述的实施例，在其技术思想的范围内，能够进行各种变形。

（第一实施例）

（概要）

在本实施例中，说明结构化文档检索装置，其对XML文档的集合和注释数据的集合进行预处理预先生成检索用数据，通过该检索用数据和检索查询的对照，将与检索查询符合的要素作为检索结果进行输出。在本实施例中，作为检索用数据，使用综合了XML标签和注释标签的结构信息的文本共有DOM树。

（装置结构）

图1-1表示结构化文档检索装置400的结构例子。结构化文档检索装置400构成为具有CPU（中央处理单元）401、主存储装置（存储器）402、辅助存储装置403A、用户接口部406的计算机。该结构化文档检索装置400经由LAN（局域网）等网络405与外部的网络装置连接。

CPU401是执行在主存储装置402中存储的程序的中央运算装置。在图1-2中，表示通过存储在主存储装置402中的程序实现的功能部和数据的一个例子。另外，在图1-2中，不只是通过在实施例1中使用的程序而实现的功能部，还表示了通过在其他实施例中使用的程序所实现的功能部、在各实施例中使用的数据。例如，CPU401通过执行程序而具有以下各部的功能，即从XML文档构筑DOM树的DOM树构筑部409、从注释数据构筑DOM树的DOM树构筑部410、文档结构列表构筑部411、文本共有DOM树构筑部415、文本数据/文本要素列表构筑部件417、文本分配部418、父子关系分析/登录部419、位置路径检索部420、DOM DAG构筑部422、转置索引构筑部424、深度分配部427、路径DAG ID取得部428、路径DAG要素生成/登录部429、路径DAGID登录部439、检索索引登录部440、XML要素检索部443、注释要素检索部444、扩展小波树构筑部451、检索索引构筑部454、简易比特矢量/小波树构筑部455。

主存储装置402是RAM（随机存取存储器）等存储装置。主存储装置402存储上述程序和执行程序所用的路径DAG423等。另外，如果有需要，主存储装置402还临时存储XML文档集合407、注释数据集合408、文档结构列表412。

辅助存储装置403A是存储XML文档、注释数据、上述程序等的HDD等存储装置或存储介质。

可移动介质404是记录XML文档、注释数据等的CD-ROM、DVD等记录介质。记录在辅助存储装置403A和可移动介质404中的各数据在结构化文档检索装置400的启动时，根据需要被读出到主存储装置402。

用户接口部406是提供用户接口的输入输出装置（例如键盘、鼠标、显示器）。

CPU401从主存储装置402、辅助存储装置403A、可移动介质404、或经由网络405连接的外部存储装置403B，根据需要取得XML文档和对该文档附加的注释数据。在此，外部存储装置403B是HDD等存储装置或存储介质。此外，网络405可以是局域网也可以是因特网。另外，网络405可以是有线网也可以是无线网。CPU401根据从这些存储装置取得的XML文档和注释数据，生成检索索引430。将生成的检索索引430存储在主存储装置402中。

在上述的说明中，表示了将XML文档和注释数据存储在主存储装置402、辅助存储装置403A、可移动介质404、网络405上的外部存储装置403B的任意一个中的例子，但也可以存储在CPU401可读写的存储装置上。例如也可以将XML文档存储在辅助存储装置403A中，将注释数据存储在主存储装置402中。

CPU401执行与上述各功能部对应的程序，作为实现预定功能的功能部而动作。例如CPU401依照文档结构构筑程序而动作，由此作为文本共有DOM树构筑部415发挥功能。对于其他程序也同样。例如CPU401依照位置路径检索程序而动作，由此作为位置路径检索部420发挥功能。另外，CPU401依照检索索引构筑程序而动作，由此作为检索索引构筑部454发挥功能。

可以将用于实现位置路径检索部420、DOM DAG构筑部422、检索索引构筑部454的各功能的程序、表等信息存储在辅助存储装置403A、可移动介质404、非易失性半导体存储器、硬盘驱动器、SSD（固态驱动器）等存储设备、或IC卡、SD卡、DVD等计算机可读取的非临时的数据存储介质中。

（注释数据）

接着，说明注释数据。通过对XML文档内的文本区域附加标签来提供注释。将通过注释赋予的标签称为注释标签。假设注释标签事先将相互基于包含关系的结构分为树结构的组。将注释标签的组称为注释组，对各注释组分配整数的ID。属于不同的注释组的注释标签彼此之间不需要满足树结构条件。

图2表示在XML文档中附加的注释和注释组的例子。在“注释组1”中，对文档中的文本“提高耐久性”附加“效果”这样的注释标签，对文本“关于刀”附加“内容”这样的注释标签。这些标签相互不重叠地满足树结构条件。另外，在“注释组2”中，对文档中的文本“医疗用”附加“对象”这样的注释标签，对文本“医疗用刀”附加“工具”这样的注释标签。这些注释标签彼此之间由于是嵌套的关系，所以满足树结构条件。

另一方面，对于属于“注释组1”的注释标签“内容”和属于“注释组2”的注释标签“工具”，标签之间不成为嵌套关系，不满足树结构条件。但是，“内容”和“工具”是属于不同的注释组的标签，因此作为注释数据没有问题。

注释标签由通过“标签名、注释组ID、文本区域的开始位置、文本区域的结束位置”赋予的4个信息的组构成。注释数据是对各注释标签记载了4个信息组的数据的集合。对于注释数据的一个例子，在各行中可以考虑用标签分隔符记载了各注释标签的数据即标签名、注释组ID、文本区域的开始位置、文本区域的结束位置的文本数据。

（XML要素、注释要素、文本要素）

XML要素是通过各XML标签的开始标签、结束标签表示的要素，具有标签名、文本区域中的开始标签、结束标签的位置。注释要素是具有标签名、注释组ID、各注释标签的开始标签、结束标签的位置的要素。文本要素是表示文本区域的要素，由文本区域的开始位置、结束位置、在文本区域中包含的文本构成。

（DOM树的要素）

构成DOM树的要素具备标签名、注释组ID、文本区域开始位置、文本区域结束位置、深度。在通常的基于XML标签的要素的情况下，将注释组ID设为“0”。在文本要素的情况下，将注释组ID设为“-1”，在标签名的部分保存文本。

（预处理的概要）

在此，说明结构化文档检索装置400在检索前执行的预处理的概要。由作为文档结构列表构筑部411而发挥功能的CPU401执行预处理。作为预处理，CPU401生成文本共有DOM树416。

首先，CPU401从XML文档集合407和注释数据集合408中，取得与未处理的XML文档对应的注释数据。接着，CPU401执行DOM树构筑程序，作为从XML文档构筑DOM树的DOM树构筑部409、从注释数据构筑DOM树的DOM树构筑410而动作。作为DOM树构筑部409和410发挥功能的CPU401生成XML文档的DOM树和属于注释数据的各注释组的要素的DOM树。

接着，CPU401执行文本共有DOM树构筑程序，作为文本共有DOM树构筑部415发挥功能。在此，CPU401向针对相同文本形成的2个DOM树的根要素通用化后的结构分配文本，生成文本共有DOM树416。对各XML文档和注释数据构筑的文本共有DOM树416作为在检索中使用的数据结构，保存在文档结构列表构筑部411中。

（文本共有DOM树）

接着，说明文本共有DOM树416。文本共有DOM树416是根据基于XML标签构筑的DOM树和基于属于各注释组的标签构成的1个或多个DOM树而构筑的数据结构，具有使各DOM树的根要素通用化的数据结构。在此，由作为DOM树构筑部409发挥功能的CPU401构筑基于XML标签的DOM树。另外，由作为DOM树构筑部410发挥功能的CPU401构筑基于注释标签的DOM树。在以下的说明中，在简称为DOM树时，是指基于XML标签构筑的DOM树或基于注释标签构筑的DOM树。

通过XML标签和注释标签划分构成XML文档的文本，对于划分的每个文本区域构成文本要素。在各DOM树中，文本要素被分配给包含的要素中的从根要素开始最深的位置的要素。不只是单一的DOM树，各文本区域也可能被分配给多个DOM树。

图3表示了根据用XML标签<p>、<mtd>、<fx>、<val>、<attr>、属于同一注释ID的标签[A]和[T]附加了标签的下述文章生成的文本共有DOM树的例子。

（附加标签前的文章）

“本発明では、粉末コ一クスを用いることで、粗鋼を生産し、2倍の効率化を達成した”。

（附加标签后的文章）

“<p>本発明では、[A]<mtd>粉末コ一クスを用いる<／mtd>ことで、<fx>[T]<obj>粗鋼<／obj>を生産[／T][／A]し、<val>2倍<／val>の<atr>効率化<／attr>を達成<／fx>した。<／p>”。

如图3所示，在文本共有DOM树的根要素中，将边缘与XML标签的<p>和注释标签的[A]连接。即，文本共有DOM树具有使基于XML标签的DOM树、基于属于同一注释组的注释标签的DOM树的根要素通用化的结构。另外，与XML标签、注释标签无关地划分文本，分为XML标签、注释标签的情况，根据文本区域的包含关系，分配给具有包含关系的最深位置的要素。例如在图3的例子的情况下，文本“粗鋼”被分配给XML标签<obj>和注释标签[T]的双方。

（预处理的详细处理）

在图4中，表示与预处理关联地执行的数据的流程。通过用户接口406将预处理的开始提供给CPU401（步骤S301）。另外，CPU401从辅助存储装置403A输入XML文档集合407和注释数据集合408（步骤S302）。另外，将所输入的XML文档集合407和注释数据集合408存储在作为工作区域的主存储装置402中。

在该阶段中，CPU401执行作为文本共有DOM树构筑部415的分析处理，构筑文档结构列表412（步骤S303）。

CPU401（文本共有DOM树构筑部415）根据作为XML文档集合407的要素的XML文档、作为与XML文档对应的注释数据集合408的要素的注释数据408，生成文本共有DOM树416。将在后面详细说明CPU401（文本共有DOM树构筑部415）执行的预处理。如果预处理结束，则CPU401将所生成的文本共有DOM树416作为文档结构列表412，输出到辅助存储装置403A（步骤S304）。

[注释数据用的DOM树构筑部410]

图5是表示作为根据注释数据构筑DOM树的DOM树构筑部410而发挥功能的CPU401的处理动作例子的流程图。

CPU401（DOM树构筑部410）读入所输入的注释数据的文件，准备“标签名、注释组ID、文本区域开始位置、文本区域结束位置”的4组数据的集合AS（步骤S401）。CPU401将集合AS中的最大的注释组ID设为“g”（步骤S402）。接着，CPU401将变量i设为“1”（步骤S403）。接着，CPU401判断变量i是否为“g”以下，在变量i变得大于“g”之前重复进行后述的步骤S405~S413（步骤S404）。

当在步骤S404中得到肯定结果的情况下，CPU401从集合AS中将注释组ID为变量i的要素的列表设定为AL（步骤S405）。接着，CPU401按照文本区域开始位置的升序对列表AL的要素进行排序，按照文本区域的结束位置的降序对文本区域开始位置相同的要素进行排序（步骤S406）。

接着，CPU401准备只由根要素构成的DOM树AT，将根要素设为v（步骤S407）。在此，CPU401将变量j设为1（步骤S408）。接着，CPU401直到变量j超过列表AL的长度（要素数）为止，重复进行后述的步骤S410~S412（步骤S409），在重复结束后，将变量i加“1”返回到步骤S404（步骤S413）。

当在前面的步骤S409中得到肯定结果的情况下，CPU401直到列表AL的第j要素的文本区域（通过文本开始位置和文本区域结束位置赋予的区域）包含在处于根要素v的文本区域（通过文本开始位置和文本区域结束位置赋予的区域）为止，重复进行将根要素v的父要素设为v的处理（步骤S410）。

然后，CPU401生成具有列表AL的第j要素的标签名、注释组ID、文本区域开始位置、文本区域结束位置的DOM树的要素，作为根要素v的子要素添加到DOM树AT中（步骤S411）。然后，CPU401将变量j加“1”，返回到步骤S409（步骤S412）。

CPU401针对各注释组，根据文本区域的开始位置和结束位置，事先对要素进行排序，然后，通过应用上述的方法，构筑注释数据的DOM树。另外，DOM树为顺序树，但通过上述的方法添加要素，同级要素彼此之间成为在文本区域的开始位置升序地排序的状态。

（XML文档用的DOM树构筑部409）

如上所述，CPU401还作为根据XML文档构筑DOM树的DOM树构筑部发挥功能。作为DOM树构筑部409的CPU401分析向所输入的XML文档赋予的标签的包含关系，构筑DOM树。可以通过非专利文献1中记载的方法来构筑XML文档的DOM树。所构筑的DOM树不包含与各标签对应的文本区域的开始位置、结束位置的信息。

在本实施例中，CPU401针对关于XML文档构筑的DOM树被分配的文本要素，计算文本区域中的开始位置和结束位置。接着，CPU401一边对各要素赋予计算出的位置信息，一边删除文本要素，生成将文本要素所保存的字符串连接起来的文本。

在此，将“t”设为空的文本。CPU401一边从根要素开始对所构筑的DOM树进行扫描，一边记录与文本要素对应的文本的长度，按照前序记录开始位置，按照后序记录结束位置。在扫描了各文本要素后，CPU401删除文本要素，对文本“t”添加删除的文本要素所保存的字符串。最后，CPU401输出所构筑的DOM树和文本t，结束一连串的处理。

（文档结构列表构筑部411）

图6是表示通过作为文档结构列表构筑部411发挥功能的CPU401执行的处理的一个例子的流程图。

首先，CPU401将XML文档集合407和注释数据集合408作为输入（步骤S501）。接着，CPU401将文档结构列表412初始化为空的列表（步骤S502）。然后，CPU401将变量i设为“1”（步骤S503）。接着，CPU401将文本数据列表初始化为空（步骤S504）。

然后，CPU401判断是否对XML文档集合407和注释数据集合408中包含的XML文档和注释数据的全部的对进行了处理（步骤S505）。直到在该判断处理中得到肯定结果为止，CPU401重复执行后述的步骤S506~S510的处理。

在步骤S505中得到了否定结果的情况下，CPU401读入未处理的XML文档和注释数据的对（步骤S506）。接着，CPU401作为XML文档用的DOM树构筑部409和注释数据用的DOM树构筑部410发挥功能，生成分别对应的DOM树（步骤S507）。

然后，CPU401当输入了从XML文档得到的DOM树和从属于各注释组的标签得到的DOM树时，作为后述的文本共有DOM树构筑部415发挥功能，生成文本共有DOM树416，得到构成所生成的文本共有DOM树416的要素的列表N（步骤S508）。接着，CPU401将列表N追加到文档结构列表（文本共有DOM树列表）412中（步骤S509）。

接着，CPU401将读入的XML文档和注释数据设为已处理，返回到步骤S505（步骤S510）。

（文本共有DOM树构筑部415）

作为文本共有DOM树构筑部415发挥功能的CPU401输入由基于XML要素的DOM树、XML文档内的文本和各注释组的要素构成的DOM树。在此，CPU401准备各DOM树的根要素以外的要素的列表N。

CPU401将列表N和XML文档内的文本输入到文本数据/文本要素列表构筑部417，对文本数据列表414和文本要素列表413进行更新。

然后，CPU401输入由文本要素列表413、XML要素、各注释组的要素构成的DOM树。作为文本分配部418发挥功能的CPU401将文本要素作为子要素分配给各要素。CPU401将文本要素列表413的各要素添加到列表N中。另外，CPU401将各DOM树的根要素通用化为1个，将通用化的根要素添加到列表N的开头。最后，CPU401输出列表N，结束文本共有DOM树的生成处理。

（文本数据/文本要素列表构筑部417）

作为文本数据/文本要素列表构筑部417发挥功能的CPU401输入文本N和文本t。CPU401取出列表N内的各要素的文本区域的开始位置、结束位置，将由升序地排序的数值构成的列表设为S。CPU401除去列表S内数值重复的部分。在列表S的开头的值不为0的情况下，CPU401将0追加到开头。另外，在列表S的最末尾的值与文本t相同的情况下，CPU401删除最末尾的值。CPU401将文本t和列表S作为文本数据，追加到文本数据列表414的最末尾。

CPU401将文本要素列表413初始化为空。列表S的各值赋予文本区域的开始位置、结束位置。因此，CPU401从列表S的开头的要素开始按顺序将文本区域的开始位置设为当前看到的要素的值，将结束位置设为下一个要素的值，将标签名设为#，生成DOM DAG421的要素，按照顺序追加到文本要素列表413的最末尾。另外，在列表S的最后的要素的情况下，不存在下一个要素，因此，CPU401将文本t的长度设为文本区域的结束位置。

（文本分配部418）

文本要素列表413的各要素由于相互的文本区域不重叠，所以不具有包含关系。因此，作为文本分配部418发挥功能的CPU401根据文本要素列表413的各要素和根要素，能够生成文本要素彼此为兄弟的DOM树。将生成的DOM树设为Tt。CPU401针对DOM树Tt，从各注释组的DOM树，通过作为后述的父子关系分析/登录部419的功能，登录注释组以外的父。

（要素间的包含关系）

在本实施例中，XML要素或注释要素与文本要素之间的包含关系依照以下的规则。在XML要素或注释要素的文本区域包含文本要素的文本区域、或相同的情况下，设为XML要素或注释要素包含文本要素。在除此以外的情况下，设为没有包含关系。

（父子关系分析/登录部419）

图7是表示由作为父子关系分析/登录部419发挥功能的CPU401执行的处理的一个例子的流程图。

首先，CPU401将DOM树T和DOMU作为输入（步骤S601）。接着，CPU401将DOM树U的要素的集合设为V（步骤S602），判断V是否为空（步骤S603）。直到V成为空为止，重复后述的步骤S604~S608。

从V中取出要素v，从V中删除（步骤S604）。CPU401在DOM树T的要素中，将包含v的要素中的从根开始的深度最深的要素设为要素u（步骤S605）。判断u是否是DOM树T的根要素（步骤S606），如果不是根要素，则CPU401将u作为v的注释组以外的父要素进行登录，返回步骤S603（步骤S607）。

（检索动作的概要）

接着，说明在结构化文档检索装置400中执行的检索处理的概要。由作为后述的位置路径检索部420发挥功能的CPU401来执行检索处理。作为位置路径检索部420发挥功能的CPU401沿着位置路径，追溯由各XML文档和注释数据构筑的文本共有DOM树，取得与检索查询符合的要素来作为检索结果。

在图3中，表示了对于文本共有DOM树，检索位置路径“/p/fx/obj”和位置路径“A/T/”通用的要素的情况。在图3的例子的情况下，位置路径“/p/fx/obj”表示在根要素下的标签<p>以下的标签<fx>以下的标签<obj>以下分配的要素，位置路径“/A/T”表示在根要素以下的标签[A]以下的标签[T]以下分配的要素。在图3中，用虚线的箭头表示这些2个位置路径。其结果是通用的要素为文本要素“粗鋼”。

（检索动作的详细）

在图8中表示在结构化文档检索装置400中执行检索处理时的数据的流动。假设CPU401将检索中使用的文档结构列表412（在本实施例的情况下，为文本共有DOM树416）事先从辅助存储装置403A读出到主存储装置402中（步骤S401）。

在该状态下，用户通过用户接口406，将作为检索查询的位置路径输入到结构化文档检索装置400（具体地说是CPU401）（步骤S402）。

于是，作为位置路径检索部420发挥功能的CPU401访问文档结构列表412中的文本共有DOM树416，计算与被指定为检索查询的位置路径符合的要素的位置（步骤S403）。然后，CPU401将与检索查询符合的要素的集合输出到用户接口406（步骤S405）。

（位置路径检索部420）

最后，说明作为位置路径检索部420发挥功能的CPU401的动作。构成文档构筑列表412的各要素的列表的开头成为文本共有DOM树的根要素。因此，CPU401沿着位置路径从各文本共有DOM树的根要素开始追溯文本共有DOM树，得到与检索查询符合的文本共有DOM树的要素。

（实施例的效果）

作为预处理，本实施例的结构化文档检索装置400生成在根据XML标签构筑的DOM树、根据属于注释组的标签构筑的DOM树之间使根要素通用化的文本共有DOM树416。在文本共有DOM树416中，以通用的根要素为起点包含各DOM树的结构。因此，在以任意的形式对XML文档附加了注释的情况下，也能够考虑基于XML的层级结构和基于注释的层级结构的双方来进行检索。

（第二实施例）

在本实施例中，定义XML要素和注释要素之间、或属于不同的注释组的注释要素之间这样的不同种类的要素之间的包含关系。因此，在本实施例中，使用将第一实施例的文本共有DOM树的结构扩展后的DOM DAG（DirectedAcyclic Graph：非循环有方向标志）。另外，本实施例的结构化文档检索装置400的基本结构与实施例1相同。即，以图1-1和图1-2所示的结构为基本结构。但是，在本实施例中，使用DOM DAG构筑部422来代替文本共有DOM树构筑部415。

（预处理的概要）

如上所述，在本实施例中，说明关于XML要素和注释要素之间以及属于不同的注释组的要素间的文本区域的包含关系，使用作为父子关系考虑的DOM DAG的结构检索。通过导入DOM DAG，实现能够执行考虑了不同种类的要素间的包含关系的检索的结构化文档检索装置。

（DOM DAG）

在此，说明本实施例中使用的DOM DAG。DOM DAG是在文本共有DOM树还记载了XML标签、属于不同的注释组的标签等不同种类的要素间的包含关系的数据结构。即，是在通过根要素通用化的各DOM树之间，记载了基于包含关系的父子关系的数据结构。

在DOM DAG中，例如作为与包含DOM树T2的要素的DOM树T1的要素中的、位于从DOM树T1的根要素开始最深位置的要素之间具有父子关系的要素来处理，在DOM树T1和DOM树T2之间扩展链接。由此，表现从DOM树T1的要素向DOM树T2的要素的包含关系。

在图9中，表示根据图3所示的文本共有DOM树416构筑的DOM DAG的例子。在图9的情况下，如从作为XML标签的标签<fx>向注释标签的标签<T>的链接、从作为注释标签的标签[T]向作为XML标签的标签<obj>的链接那样，在不同种类的标签之间也考虑父子关系。

（DOM DAG内的要素的包含关系）

DOM树或DOM DAG内的要素的包含关系依照以下的规则。

（1）根要素也包含根要素以外的哪个要素。

（2）在XML要素和注释要素的文本区域开始位置和结束位置相同的情况下，XML要素包含注释要素。

（3）在注释要素彼此的文本区域开始位置和结束位置相同的情况下，注释组ID小的要素包含注释组ID大的要素。

（4）对于文本要素和文本要素以外的其他要素，在文本区域开始位置和结束位置相同的情况下，后者包含前者。

（5）在通过（1）~（4）没有决定包含关系的情况下，根据要素中的文本区域的包含关系决定要素的包含关系。但是，在文本要素的文本区域包含其他要素的文本区域的情况下，设为没有要素的包含关系。

（6）在通过（1）~（5）没有决定包含关系的情况下，设为相互没有包含关系。

（DOM DAG构筑部422）

作为DOM DAG构筑部422发挥功能的CPU401输入由XML要素构筑的DOM树、XML文档内的文本、由各注释组的要素构筑的DOM树。

作为父子关系分析/登录部419发挥功能的CPU401向包含XML要素的注释组的全部DOM树的组分配注释组以外的父。在此，CPU401针对各DOM树，准备根要素以外的要素的列表N。CPU401将列表N和XML文档内的文本输入到文本数据/文本要素列表构筑部417，对文本数据列表414和文本要素列表413进行更新。

作为文本分配部418发挥功能的CPU401当输入了由文本要素列表413、XML要素、各注释组的要素构成的DOM树时，将文本要素作为子要素，分配给DOM树的各要素。CPU401将文本要素列表413的各要素添加到列表N中，并且将深度信息分配给各要素。CPU401针对DOM树的各要素所具有的注释组以外的父要素列表的要素，扩展父子关系的链接。另外，CPU401将各DOM树的根要素通用化为1个，将通用化后的根要素添加到列表N的前头。然后，CPU401输出列表N，结束DOM DAG的生成处理。

（本实施例的效果）

作为预处理，本实施例的结构化文档检索装置400生成针对构成在实施例1中说明的文本共有DOM树416的不同的DOM树的要素之间也规定了包含关系的DOM DAG。因此，如果使用本实施例的结构化文档检索装置400，则在实施例1的效果以外，还能够考虑不同种类的要素之间的包含关系（父子关系）来进行检索。

（第三实施例）

如上所述，如果使用DOM DAG，则能够进行利用了不同种类标签之间的结构关系的检索。但是，在位置路径的检索时，从根要素开始追溯所构筑的全部DOM DAG，因此并非高效。

因此，在本实施例中，定义集合了多个DOM DAG的结构的数据结构即路径DAG。并且，能够将路径DAG内的要素作为条目，根据以DOM DAG内的要素作为值的转置索引进行检索，由此能够以位置路径作为检索查询进行高效的检索。

在本实施例的情况下，结构化文档检索装置400的基本结构与实施例1相同。即，以图1-1和图1-2所示的结构作为基本结构。但是，在本实施例的情况下，对DOM DAG构筑部422和位置路径检索部420的功能进行了扩展。

[预处理的概要]

在本实施例的情况下，转置索引构筑部424执行预处理。作为转置索引构筑部424发挥功能的CPU401将路径DAG423初始化为只由根要素构成的数据结构，并且根据与各XML文档对应的注释数据构筑DOM DAG。

作为路径DAG ID取得部428发挥功能的CPU401根据构成DOM DAG的各要素的标签名和父要素，判断是否是已经登录在路径DAG内的结构。在判断对象的结构已经登录在路径DAG内的情况下，CPU401对该结构赋予对应的路径DAG内的要素的ID即路径DAG ID。与此相对，在没有登录判断对象的结构的情况下，CPU401作为路径DAG要素生成/登录部429发挥功能，针对路径DAG423新生成要素，并且对生成的要素得到路径DAG ID。在取得路径DAG ID后，CPU401向转置索引425的与取得的路径DAG ID对应的条目追加各要素。

图10表示在登录了2个DOM DAG后生成的路径DAG和转置索引425的例子。根据图10所示，构筑路径DAG423，以便针对由XML文档1构筑的DOM DAG和由XML文档2构筑的DOM DAG，使父节点的集合相同的要素通用化。在图中，白圈所示的要素表示XML要素，涂黑表示的要素表示注释要素。

其中，如要素c那样，在2个文档之间父的集合的关系不同的要素的情况下，在路径DAG423上，登录为不同的要素。在图10中，区分地登录为“c：1”和“c：2”。

另外，要素d可以看作父要素都只是要素c，父的集合是通用的。但是，路径DAG上的要素c如上所述被登录为不同的要素。因此，要素d也被登录为路径DAG上不同的要素。在DOM DAG的各要素中，分配以文档的顺序、文档内的标签的出现顺序为组的编号。将各要素的编号登录在转置索引425内对应的路径DAG要素的路径DAG ID的条目中。

另外，在图10中，将与路径DAG423对应的转置索引425的结构也记载为ID与标签编号的关系。在下面说明该转置索引的生成方法。

（转置索引构筑部424）

图11是表示作为转置索引构筑部424发挥功能的CPU401的处理动作的流程图。

首先，CPU401输入XML文档集合407和注释数据集合408（步骤S1001）。接着，CPU401将DOM DAG列表初始化为空的列表（步骤S1002）。接着，CPU401将转置索引425初始化为空的表（步骤S1003）。另外，CPU401将变量i设为“1”（步骤S1004）。接着，CPU401将文本数据列表初始化为空（步骤S1005）。

然后，CPU401判断是否对XML文档集合407和注释数据集合408中包含的XML文档和注释数据的全部的对进行了处理（步骤S1006）。直到在该判断处理中得到肯定结果为止，CPU401重复进行后述的步骤S1007~S1013的处理。

作为DOM DAG构筑部422发挥功能的CPU401读入未处理的XML文档和注释数据的对（步骤S1007）。在此，CPU401作为XML文档用的DOM树构筑部409和注释数据用的DOM树构筑部410发挥功能，根据各个XML文档和注释数据生成DOM树（步骤S1008）。

接着，CPU401作为后述的DOM DAG构筑部422发挥功能，根据从XML文档得到的DOM树和从属于各注释组的标签得到的DOM树生成DOMDAG421，得到构成DOM DAG421的要素的列表N（步骤S1009）。

接着，CPU401将列表N输入到后述的DOM DAG要素列表排序部426进行排序（步骤S1010）。并且，CPU401将列表N和变量i输入到转置索引登录部440，将各要素登录到转置索引425中（步骤S1011）。然后，CPU401将列表N追加到DOM DAG列表中（步骤S1012）。另外，CPU401将读入的XML文档、注释数据设为已处理，返回到步骤S1006（步骤S1013）。

（DOM DAG要素列表排序部426）

在此，说明执行步骤S1010的处理的DOM DAG要素列表排序部426的处理动作。当然通过CPU401执行程序来实现作为DOM DAG要素列表排序部426的功能。作为DOM DAG要素列表排序部426发挥功能的CPU401将DOM DAG要素的列表N作为输入。接着，CPU401根据文本区域开始位置和包含关系，按照文档内的出现顺序对列表N内的要素进行排序。当事先针对与每个注释组对应的DOM树按照前序对XML要素进行排列，按照合并排序的方针对排列后的要素之间进行合并时，能够高效地对列表N内的要素进行排序。要素的排列依照以下的规则。

（1）根要素处于其他任何要素之前。

（2）文本区域开始位置在前面的要素之前或者在文本区域开始位置相同的情况下包含的要素在前。

[深度分配部427]

在此，说明作为深度分配部427发挥功能的CPU401的功能。图12是表示深度分配部427的处理例子的流程图。

首先，CPU401将由DOM DAG421的要素构成的列表N作为输入（步骤S1101）。接着，CPU401将XML文档中位于最深位置的要素的深度设为D，将长度D的排列设为E（步骤S1102）。接着，CPU401将变量i设为1，将变量d设为0（步骤S1103）。然后，CPU401判断变量i是否为N的长度以下（步骤S1104）。直到判断为变量i比N的长度大为止，CPU401重复进行后述的步骤S1105~S1113。

在步骤S1104中得到肯定结果的情况下，CPU401将列表N的第i要素设为v（步骤S1105）。接着，CPU401判断v是XML要素还是文本要素（步骤S1106）。在此，在v是XML要素或文本要素的情况下，CPU401将从DOMDAG421的根要素开始的深度设为d（步骤S1107）。进而，CPU401将v的文本区域结束位置设为E的第d要素，返回到步骤S1104（步骤S1108）。

另一方面，在步骤S1106的判断处理中，在判断为v既不是XML要素也不是文本要素的情况下，CPU401判断v是否是注释标签的开始要素（步骤S1109）。在此，在判断为v是注释标签的开始要素的情况下，CPU401将v的文本区域开始位置设为变量e（步骤S1110）。与此相对，在步骤S1109的判断处理中，判断为v不是注释标签的开始要素的情况下，CPU401将v的文本区域的结束位置设为变量e（步骤S1111）。

在v是文本区域开始位置和文本区域结束位置的任意一个的情况下，CPU401直到变量d成为1、或E的第d-1要素比变量e大为止，从变量d减去1（步骤S1112）。然后，CPU401将v的深度设为d，另一方面，将变量i加1，返回到步骤S1104（步骤S1113）。

（路径DAG ID取得部428）

在此，说明从DOM DAG取得路径DAG的路径DAG ID取得部428的处理功能。图13是表示作为路径DAG ID取得部428发挥功能的CPU401的处理例子的流程图。

首先，CPU401将DOM DAG421的要素的列表N作为输入（步骤S1201）。接着，CPU401将变量i设为1（步骤S1202）。然后，CPU401判断变量i是否为N的长度以下，直到判断为变量i大于N的长度为止，重复进行后述的步骤S1204~S1213（步骤S1203）。

在变量i为列表N的长度以下的情况下，CPU401将列表N的第i要素设为v（步骤S1204）。接着，CPU401判断要素v是否是注释的结束标签要素（步骤S1205）。在作为判断结果得到肯定结果的情况下，CPU401将变量i加1，返回到步骤S1203（步骤S1206）。与此相对，在步骤S1205的判断处理中得到否定结果的情况下，CPU401将DOM DAG421中的要素v的父要素的集合设为V（步骤S1207）。并且，CPU401将相当于集合V的各要素的路径DAG423的要素的集合设为P（步骤S1208）。并且，CPU401在属于集合P的路径DAG423的要素中的通用的子要素中，将具有与要素v相同的标签名的路径DAG423的要素的集合设为I（步骤S1209）。

在此，CPU401判断在集合I中是否存在父要素的集合与集合P相同的要素（步骤S1210）。在该判断处理中得到肯定结果的情况下，CPU401将该要素具有的路径DAG ID登录在要素v，返回步骤S1203（步骤S1211）。与此相对，在步骤S1210的判断处理中得到否定结果的情况下，CPU401向后述的路径DAG要素生成/登录部429输入要素v和集合P（步骤S1212）。然后，CPU401将变量i加1，返回到步骤S1203（步骤S1213）。

（路径DAG要素生成/登录部429）

在此，说明作为在步骤S1212中使用的路径DAG要素生成/登录部429的CPU401的处理功能。图14是表示作为路径DAG要素生成/登录部429发挥功能的CPU401的处理例子的流程图。

CPU401将DOM DAG421的要素v和路径DAG423的要素P作为输入（步骤S1301）。在此，CPU401将要素v保持的深度设为d（步骤S1302）。

接着，CPU401判断要素v是否是注释要素（步骤S1303）。在要素v是注释要素的情况下，CPU401将（2，d，AI）作为路径DAG ID而赋予给要素v，将AI加1（步骤S1304）。然后，CPU401生成具有要素v保持的路径DAG ID的路径DAG要素，作为集合P的各要素的子要素（步骤S1305）。

与此相对，在步骤S1303中得到否定结果的情况下（即要素v是XML要素的情况），CPU401判断要素v的标签名是否是“#”（步骤S1306）。

在要素v的标签名是“#”的情况下，CPU401将（1，d，XI[d]）作为路径DAG ID而赋予给要素v（步骤S1307）。与此相对，在要素v的标签名不是“#”的情况下，CPU401将（0，d，XI[d]）作为路径DAG ID而赋予给要素v（步骤S1308）。在对要素v赋予了任意的路径DAG ID后，CPU401将XI[d]加1（步骤S1309）。

（转置索引登录部442）

接着，说明转置索引登录部442的处理动作。图15是表示作为转置索引登录部442发挥功能的CPU401的处理的流程图。

首先，CPU401将DOM DAG要素的列表N和文档编号n作为输入（步骤S1401）。接着，CPU401将变量i设为1（步骤S1402）。接着，CPU401判断变量i是否为列表N的长度以下（步骤S1403）。CPU401直到判断为变量i超过列表N的长度为止，重复后述的步骤S1404~S1409。

在变量i不超过列表N的长度的情况下，CPU401判断要素v是否是根要素（步骤S1404）。在要素v是根要素的情况下，CPU401将变量i加1，返回到步骤S1403（步骤S1409）。与此相对，在要素v不是根要素的情况下，CPU401向后述的路径DAG ID取得部428输入要素v，取得要素v保持的路径DAG IDj（步骤S1405）。

然后，CPU401在转置索引425中，判断是否不存在与变量j对应的条目（步骤S1406）。在不存在对应的条目的情况下，CPU401生成与变量j对应的条目（步骤S1408）。然后，CPU401向与变量j对应的条目追加（n，i）的元组（tuple）（步骤S1407）。然后，CPU401将变量i加1，返回到步骤S1403（步骤S1409）。

（检索动作的概要）

如下那样进行本实施例的检索动作。在本实施例的情况下，由作为位置路径检索部420的CPU401根据转置索引425，执行基于位置路径的检索。作为位置路径检索部420的CPU401沿着位置路径追溯路径DAG，取得与位置路径的结构符合的路径DAG要素的路径DAG ID。

CPU401根据所取得的路径DAG ID检索转置索引425，从DOM DAG列表取得与位置路径符合的DOM DAG要素的标签编号。接着，CPU401取得根据该标签编号确定的DOM DAG要素作为检索结果。

通过具体例子说明以上的处理动作。在此，参照图10。图10表示使用路径DAG423和转置索引425，执行与位置路径“/a/b/#”符合的要素的检索的要素。在该情况下，CPU401在路径DAG（左下所示的结构图）上追溯位置路径，取得（1,3,1）作为路径DAG ID。接着，CPU401从转置索引425（右下所示的表）中检索与（1,3,1）对应的条目。在图10的例子中，如虚线箭头所示那样，得到DOM DAG要素的标签编号即（1,5）和（2,4）。接着，CPU401从文档1的DOM DAG和文档2的DOM DAG中取得与该标签编号对应的要素。

（位置路径检索部420）

在此，说明作为位置路径检索部420发挥功能的CPU401的处理。CPU401沿着位置路径追溯路径DAG423，将与到达的要素对应的路径DAG ID设为变量i。接着，CPU401从转置索引425中取得与路径DAG IDi对应的条目E。条目E内的各要素为位于DOM DAG列表中的DOM DAG的要素的列表的场所和DOM DAG列表内的要素的场所的组。位置路径检索部420从转置索引425中取得全部与它们对应的DOM DAG的要素并进行输出。

（实施例的效果）

在本实施例的结构化文档检索装置400中，通过定义集合了多个DOMDAG的结构的路径DAG，与上述的实施例相比，能够提高检索效率。

（第四实施例）

在此，考虑DAG421在计算机上的保存形式。在C语言等中，将结构信息表示为指针。因此，在DAG421的结构复杂的情况下，在要素间设有许多指针，需要比原始的XML文档和注释数据多的存储器。因此，在本实施例中，说明通过路径DAG和数列数据表示DOM DAG的结构的方法。

另外，本实施例的结构化文档检索装置400根据XML文档的开始标签和按照出现顺序对在注释数据中出现的开始要素和结束要素分配的要素编号，检索与检索查询符合的标签的开始位置和结束位置相当的要素。

（预处理的概要）

由作为检索索引构筑部424发挥功能的CPU401来执行本实施例的预处理。如在上述的实施例说明的那样，检索索引430通过路径DAG和数列数据，记载DOM DAG421的结构。因此，不需要将与各XML文档所对应的注释数据有关的DOM DAG421保存在主存储装置402中。

首先，CPU401针对与各XML文档对应的注释数据构筑DOM DAG421。接着，CPU401作为路径DAG ID取得部428发挥功能，取得所构筑的DOMDAG421的各要素的路径DAG ID。然后，CPU401按顺序将取得的路径DAGID登录在数列数据。

图16表示将图10所示的DOM DAG记录为数列数据的情况。如左上段所示那样，在DOM DAG421的各要素中，按照出现顺序分配序号。在图16的情况下，对文档1的DOM DAG的各要素按照其出现顺序赋予从“1”到“7”的序号，对文档2的DOM DAG的各要素按照其出现顺序赋予从“8”到“15”的序号。另外，如右上段所示那样，对集合了2个DOM DAG421的路径DAG423的各要素，按照路径DAG ID在各层级的出现顺序记录数列数据。

（检索索引430）

图17表示检索索引430的概要。检索索引430由集合了多个DOM DAG的结构的路径DAG423、将路径DAG423的各要素被分配的ID分配给DOMDAG的各要素，按照要素的出现顺序登录的数列数据群、比特列的数据群、文本数据列表414构成。

数列数据群由注释要素判别比特列431、文本要素判别比特列432、XML要素的深度数列433、按深度区别ID列列表434、注释结束标签判断比特列435、注释开始标签ID列436、注释结束标签ID列437、注释要素的深度数列438构成。文本数据列表414由按照出现顺序将各XML文档内的全部字符串连接起来的文本、通过XML标签和注释标签划分的文本分割位置的列表构成。

（检索索引构筑部454）

图18表示作为检索索引构筑部454发挥功能的CPU401的处理例子的流程图。

首先，CPU401将XML文档集合407和注释数据集合408作为输入（步骤S1701）。接着，CPU401将注释要素判别比特列431、文本要素判别比特列432、XML要素的深度数列433、注释结束标签判别比特列435、注释开始标签ID列436、注释结束标签ID列437、注释要素的深度数列438初始化为空的数列（步骤S1702）。

接着，CPU401在将XML文档集合407中包含的XML文档中位于最深位置的要素的深度设为D时，在按深度区别ID列列表434中设置D个空的数列（步骤S1703）。

然后，CPU401将路径DAG423初始化为只具有根要素的图表，对根要素赋予（0,0,1）作为路径DAG ID（步骤S1704）。另外，CPU401将数字XD、长度D的数列XI的各要素、数字AI初始化为0（步骤S1704）。

进而，CPU401将文本数据列表初始化为空（步骤S1705）。

然后，CPU401判断是否对XML文档集合407和注释数据集合408中包含的XML文档和注释数据的全部对进行了处理（步骤S1706）。直到在该判定处理中得到肯定结果为止，CPU401重复执行后述的步骤S1707~S1713的处理。

当在步骤S1706中得到否定的结果的情况下，CPU401读入未处理的XML文档和注释数据的对（步骤S1707）。根据XML文档通过来自XML文档的DOM树构筑部409生成DOM树，并根据注释数据通过来自注释数据的DOM树构筑部410生成DOM树（步骤S1708）。

接着，CPU401当输入了从XML文档得到的DOM树和从属于各注释组的标签得到的DOM树，则通过作为后述的DOM DAG构筑部422的功能生成DOM DAG421，得到要素的列表N（步骤S1709）。

然后，CPU401将列表N输入到DOM DAG要素列表排序部426进行排序（步骤S1710）。进而，CPU401将列表N输入到后述的注释结束标签插入部441（步骤S1711）。接着，CPU401将列表N输入到检索索引登录部440（步骤S1712）。然后，CPU401将读入的XML文档和注释数据设为已处理，返回到步骤S1706（步骤S1713）。

（注释结束标签要素）

注释结束标签要素是指表示注释的结束标签的要素，保存对应的注释要素、深度、路径DAG ID。为了表示对DOM DAG421的要素进行排序后的列表内的注释标签的结束位置，使用注释结束标签要素。

（注释结束标签插入部441）

作为注释结束标签插入部441发挥功能的CPU401将DOM DAG421的要素的列表N作为输入。在此，CPU401准备空的注释要素的列表L。

CPU401从开头开始顺序地扫描列表N的要素。在列表N的要素是注释要素的情况下，生成注释标签的结束要素，在记录了相当的注释要素后，追加到列表的最末尾。CPU401在扫描列表N后，按照合并排序的方针将列表内的要素插入到列表N中，将列表L合并到列表N中。排序时的顺序依照以下的规则。

DOM树的要素的排序时依照以下的规则，降序地进行排序。

（1）根要素处于其他任何要素之前。

（2）在列表N内的要素和注释结束标签要素的比较中，在前者的文本区域开始位置与后者的文本区域结束位置相同的情况下，如果后者保存的注释要素包含在前者中，则前者在前面。在不是这样的情况下，后者在前面。

（3）在列表N内的要素和注释结束标签要素的比较中，在前者的文本区域结束位置与后者的文本区域结束位置相同的情况下，如果与后者对应的注释要素包含前者，则前者在前面。在不是这样的情况下，后者在前面。

（检索索引登录部440）

图19是表示作为检索索引登录部440发挥功能的CPU401的处理例子的流程图。

CPU401将由DOM DAG421的要素构成的列表N作为输入（步骤S1801）。接着，CPU401将变量i设为1（步骤S1802）。然后，CPU401判断变量i是否为列表N的长度以下（步骤S1803）。CPU401直到变量i超过列表N的长度为止，重复进行后述的步骤S1804~S1811。

在变量i为列表N的长度以下的情况下，CPU401将列表N的第i要素设为v（步骤S1804）。在此，CPU401判断要素v是否是注释标签的结束要素（步骤S1805）。在得到肯定结果的情况下，CPU401取得与要素v对应的开始要素的路径DAG IDj，对IDj的第1要素设置3（步骤S1806）。另一方面，在步骤S1805中得到否定结果的情况下，CPU401将要素v输入到后述的路径DAG ID取得部428，取得要素v所保存的路径DAG IDj（步骤S1807、S1808）。

在以上的处理后，CPU401将IDj作为路径DAG ID登录到DN中（步骤S1809）。进而，CPU401将IDj输入到路径DAG ID登录部439（步骤S1810）。然后，CPU401将变量i加1，返回到步骤S1803（步骤S1811）。

（路径DAG ID登录部439）

说明在上述的步骤S1810中使用的路径DAG ID登录部439的处理内容。图20是表示作为路径DAG ID登录部439发挥功能的CPU401的处理内容的流程图。

首先，CPU401将路径DAG IDi作为输入（步骤S1901）。接着，CPU401将IDi的第j要素设为i[j]（步骤S1902）。在此，CPU401判断j[1]是否是0或1（步骤S1903）。在i[1]是0或1时，CPU401向注释要素判别比特列431的最末尾添加0（步骤S1904），向XML要素的深度数列433的最末尾添加i[2]（步骤S1905），向文本要素判别比特列432的最末尾添加i[1]（步骤S1906）。

进而，CPU401判断i[2]是否是0（步骤S1907）。如果i[2]是0，则CPU401在该时刻结束登录处理。与此相对，在i[2]为0以外的情况下，CPU401向按深度区别ID列列表434中的第i[2]数列的最末尾添加i[3]，结束登录处理（步骤S1908）。

另一方面，在步骤S1903中是否定结果的情况下，即i[1]是2或3时，CPU401向注释要素判别比特列431的最末尾追加1（步骤S1910）。进而，CPU401向注释要素的深度数列438的最末尾添加i[2]（步骤S1911）。

然后，CPU401判断i[1]是否是2（步骤S1912）。在i[1]是2的情况下，CPU401向注释结束标签判别比特列435的最末尾添加0，并且向注释开始标签ID列436的最末尾添加i[3]，结束登录处理（步骤S1913、S1914）。

与此相对，当在步骤S1912中得到否定结果的情况下，即i[1]是3的情况下，CPU401向注释结束标签判别比特列435的最末尾添加1，并且向注释结束标签ID列437的最末尾添加i[3]，结束登录处理（步骤S1915、S1916）。

[检索动作的概要]

在此，说明本实施例的检索动作。由作为位置路径检索部420发挥功能的CPU401来执行本实施例的检索动作。CPU401沿着通过检索查询赋予的位置路径追溯路径DAG，取得与位置路径的结构符合的路径DAG要素的路径DAGID。

CPU401根据取得的路径DAG ID，判断检索结果的要素是XML要素还是注释要素。在检索结果的要素是XML要素的情况下，CPU401作为XML要素检索部443发挥功能，计算与检索查询符合的数列数据中的要素的位置。另一方面，在检索结果的要素是注释要素的情况下，CPU401作为注释要素检索部444发挥功能，计算与检索查询符合的数列数据中的要素的位置。

在此，XML要素检索部443和注释要素检索部444针对数列，执行以下被称为等级（rank）、选择（select）、最近（nearest）的运算。

（1）等级（c，p）：在数列中，位于第p位置的要素的c的数

（2）选择（c，p）：在数列中，第n次出现的c的位置

（3）最近（c，p）：在数列中，第p以后的要素具有d以下的值的最接近p的要素的位置

在此，参照图16，说明一连串的处理动作。图16表示使用路径DAG423和数列数据检索与位置路径“e/c/d”符合的要素的例子。

首先，CPU401沿着位置路径追溯路径DAG，由此得到路径DAG ID即（0，3，3）。在图16中，用虚线围住相当的路径DAG ID来表示。在此，在路径DAG ID的第1要素是0时，表示XML要素，第2要素的“3”表示深度。

因此，CPU401在按深度区别ID列列表434的第3数列（深度为“3”的位置的数列）中，查找包含路径DAG ID的第3要素即“3”的位置。在图16的情况下，“3”位于深度“3”的数列内的第4个。在图16中，也用虚线围住表示该要素。

接着，CPU401针对XML要素的深度数列433，计算选择（3,4），得到第四次出现“3”的位置即“14”。接着，CPU401针对注释要素判别比特列431，计算选择（0，14）。这是因为在注释要素判别比特列431中，在XML要素的位置登录有0。因此，该计算表示在注释要素判别比特列431中求出第14次出现的XML要素的位置。在此，作为运算结果得到“15”。

如图16的左上段所示那样，与“15”对应的DOM DAG的要素是XML文档2的DOM DAG的“d”。另外，“15”表示要素的开始标签的位置。对于要素的结束标签的位置，也能够通过同样的方法取得。

（位置路径检索部420）

图21是表示作为位置路径检索部420发挥功能的CPU401的处理的流程图。

CPU401沿着位置路径追溯路径DAG423，将与到达的要素对应的路径DAG ID设为i（步骤S2001）。接着，CPU401将IDi的第1要素设为s，将第2要素设为d（步骤S2002）。另外，CPU401对变量j设置1（步骤S2003）。进而，CPU401将L设为用于保存检索对象的标签的开始位置和结束位置的对的空的列表（步骤S2004）。

在此，CPU401判断要素s是否是0或1（步骤S2005）。如果要素s是0或1，则CPU401向XML要素检索部443输入i和j，得到所得的标签的开始位置、结束位置的元组t（步骤S2006）。

接着，CPU401判断元组t是否是（-1,-1）（步骤S2007）。在元组t不是（-1,-1）的情况下，CPU401将元组t添加到列表L的最末尾，将j加1（步骤S2008、S2009）。直到元组t成为（-1,-1）为止，重复进行步骤S2006~S2009（步骤S2007）。另外，CPU401直到元组t成为（-1,-1）为止，重复进行步骤S2006~S2009（步骤S2007）。然后，如果元组t成为（-1,-1），则CPU401输出列表L，结束检索处理（步骤S2014）。

与此相对，在步骤S2005中得到否定结果的情况下（在该情况下，要素s不是0和1的任何一个的情况），CPU401向注释要素检索部444输入i和j，将所得到的标签的开始位置和结束位置的元组设为t（步骤S2010）。

在此，CPU401判断元组t是否是（-1,-1）（步骤S2011）。此时，在元组t不是（-1,-1）的情况下，CPU401将元组t添加到列表L的最末尾，将变量j加1（步骤S2012、S2013）。然后，直到元组t成为（-1,-1）为止，CPU401重复进行步骤S2010~S2013。然后，如果元组t成为（-1,-1），则CPU401输出列表L，结束检索处理（步骤S2014）。

（XML要素检索部443）

图22表示作为XML要素检索部443发挥功能的CPU401的处理的流程图。

首先，CPU401将输入的路径DAG ID设为i，将检索编号设为n（步骤S2101）。接着，CPU401将路径DAG IDi的第2要素设为d，将第3要素设为j（步骤S2102）。进而，CPU401将按深度区别ID列列表434的第d数列中包含j的数设为m（步骤S2103）。

在此，CPU401判断m是否小于n（步骤S2104）。在m小于n的情况下，CPU401输出由2个要素构成的元组（-1，-1），结束检索处理（步骤S2105）。

与此相对，在m为n以上的情况下，CPU401针对按深度区别ID列列表434的第d数列，计算选择（j，n），将结果设为n（步骤S2106）。

接着，CPU401针对XML要素的深度数列433，计算选择（d，n），将其结果设为n（步骤S2107）。

进而，CPU401针对注释要素判别比特列431，计算选择（0，n），并设为变量s（步骤S2108）。

接着，CPU401针对XML要素的深度数列433，计算最近（n，d），将其结果设为变量p（步骤S2109）。

然后，CPU401针对注释要素判别比特列431，计算选择（0，p），将其结果设为p（步骤S2110）。

接着，CPU401针对注释要素判别比特列431，计算等级（1，n），将其结果设为变量r（步骤S2111）。

进而，CPU401针对注释要素的深度数列438，计算最近（r，d），将其结果设为r（步骤S2112）。

另外，CPU401针对注释要素判别比特列431，计算选择（1，q），对变量q设置（步骤S2113）。

另外，CPU401将p和q中小的一方设给变量e（步骤S2114）。

然后，CPU401输出s和e的对的元组（s，e）（步骤S2115）。

（注释要素检索部444）

图23是表示作为注释要素检索部444发挥功能的CPU401的处理的流程图。

首先，CPU401将输入的路径DAG ID设为i，将检索编号设为n（步骤S2201）。接着，CPU401将i的第3要素设为j（步骤S2202）。另外，CPU401将注释开始标签ID列436中包含j的数设为m（步骤S2203）。

在此，CPU401判断m是否小于n（步骤S2204）。在m小于n的情况下，CPU401输出由2个要素构成的元组（-1，-1）后结束检索处理（步骤S2205）。

另一方面，在m为n以上的情况下，CPU401针对注释开始标签ID列436，计算选择（j，n），将结果设置给m（步骤S2206）。

接着，CPU401针对注释结束标签判别比特列435，计算选择（0，m），将其结果设置给m（步骤S2207）。

进而，CPU401针对注释要素判别比特列431，计算选择（1，m），并设给变量s（步骤S2208）。

另外，CPU401针对注释结束标签ID列437，计算选择（j，n），将结果设置给m（步骤S2209）。

然后，CPU401针对注释结束标签判别比特列435，计算选择（1，m），将结果设置给m（步骤S2210）。

另外，CPU401针对注释要素判别比特列431，计算选择（1，m），设置给变量e（步骤S2211）。

进而，CPU401输出s和e的对的元组（s，e）（步骤S2212）。

（实施例的效果）

在本实施例的结构化文档检索装置400中，采用通过路径DAG和数列数据记载DOM DAG的结构的方法。在该情况下，结构化文档检索装置400不需要保存根据XML文档和对应的注释数据生成的DOM DAG，与上述的实施例相比能够大幅降低存储器容量的消耗量。

（第五实施例）

作为能够根据常数等级的计算量对比特列计算等级、选择的数据结构，已知简洁比特矢量。另外，作为在数据压缩的状态下保存数列数据，在压缩的状态下高效地计算等级、选择的数据结构，已知小波树。

小波树是使简洁比特矢量发展的数据结构，事先都需要用于计算的辞典数据。使用了辞典数据的构筑法、数据结构的等级、选择的计算方法可以使用非专利文献2所记载的方法等。

在本实施例中，在执行作为检索索引构筑部454的处理功能后，简易比特矢量/小波树构筑部455通过上述公知的方法，针对注释结束标签判断比特列435、文本要素判别比特列432、注释要素判别比特列431生成简洁比特矢量，并且针对要素的深度数列433、按深度区别ID列列表434、注释开始标签ID列436、注释结束标签ID列437、注释要素的深度数列438生成小波树。

（实施例的效果）

本实施例的结构化文档检索装置400通过使用准备的简洁比特矢量、小波树，能够提高XML要素检索部443、注释要素检索部444中的等级计算和选择计算的效率。

（第六实施例）

在实际应用方面，希望能够对相同的XML文档追加或删除不同的注释数据。在本实施例中，说明在对赋予的XML文档已经构筑了索引的状态下，不大幅变更索引的结构地追加注释要素组的方法。

当追加注释要素时，各要素的父的集合被变更。因此，必须将以前被认为在路径DAG上相同的要素作为不同的要素来处理。另外，如果追加注释，则文本区域被划分，存在不仅路径DAG ID被变更，表示文本区域的要素的个数也增加的问题。另外，如果追加注释，则不仅变更路径DAG的结构，还需要将数列数据中的数字c的一部分置换为到此为止不是数列的数字和c构成的数列。

以下，说明在将小波树446中登录的数列中的数字c的一部分变更为到此为止不是数列的数字构成的数列N的情况下，通过向既有的小波树446追加数据结构，由此能够进行变更时的等级（rank）、选择（select）、查找（lookup）的扩展小波树445。

（扩展小波树445）

图24是表示扩展小波树445的概要的图。扩展小波树445由以下部分构成：由原始的数列构成的小波树446、表示变更后的数字x成为登录在原始的数列中的哪个数字的数字变更表447、表示在全体数列中追加了哪个部分的数字的追加标志448、表示对原始数列的各数字追加在哪个位置的按数字区别追加标志449、在构成原始数列的数字中与变更相关联的数字所对应的变更小波450。

（扩展小波树构筑部451）

图25是表示作为扩展小波树构筑部451发挥功能的CPU401的处理的流程图。在将小波树446中登录的数列的第p个数字c变更为数列N的情况下，CPU401通过以下的步骤，对小波树446进行扩展。

首先，CPU401通过与小波树446中登录的数列相同的长度准备全部值用0初始化的数列B（步骤S2401）。接着，CPU401将列表N的长度设为“N”，在数列B的第p以后追加|N|－1个“1”（步骤S2402）。

然后，CPU401生成数列B的简洁比特矢量，将其设为追加标志448（步骤S2403）。接着，CPU401计算追加标志448的等级（p，c），将计算结果设为q（步骤S2404）。

在此，CPU401将小波树446中登录的数字c的个数设为m（步骤S2405）。进而，CPU401准备全部的值用0初始化的长度m的数列V，在第q以后追加|N|－1个“1”（步骤S2406）。

然后，CPU401生成数列V的简洁比特矢量，将其设为与数字c对应的按数字区别追加标志449（步骤S2407）。进而，CPU401生成保存数列N的小波树，将其设为与数字c对应的变更小波450（步骤S2408）。然后，CPU401生成用于记载构成变更后的数列的各数字与构成原始数列的哪个数字对应的数字变更表447（步骤S2409）。

（扩展小波树的等级计算部452）

图26是表示作为对扩展小波树445执行等级计算的等级计算部452发挥功能的CPU401的处理的流程图。

首先，CPU401针对追加标志448计算等级（0，p），设为q（步骤S2501）。接着，CPU401从数字变更表447中取得c的原始数列中的数字，将其设为d（步骤S2502）。接着，CPU401针对原始的小波树446，计算等级（c，q），将计算结果设为r（步骤S2503）。

在此，CPU401判断c和d是否相同（步骤S2504）。在c和d不相同的情况下，CPU401输出r，结束计算处理（步骤S2508）。

与此相对，在c和d相同的情况下，CPU401针对追加标志448，计算选择（0，q），将计算结果设为s（步骤S2505）。接着，CPU401针对与d对应的按数字区别追加标志449，计算选择（0，r），将计算结果设为t（步骤S2506）。另外，CPU401针对与d对应的按数字区别追加标志449，计算等级（c，t+p-s），输出计算结果，结束计算处理（步骤S2507）。

（扩展小波树的选择计算部453）

图27是表示作为针对扩展小波树445执行选择计算的选择计算部453发挥功能的CPU401的处理的流程图。

首先，CPU401从数字变更表447中取得c在原始数列中的数字，将其设为d（步骤S2601）。

在此，CPU401判断c和d是否不同（步骤S2602）。在c和d不同的情况下（肯定结果），CPU401针对与d相当的追加小波树，计算选择（c，n），将计算结果设为s（步骤S2603）。进而，CPU401针对与d对应的按数字区别追加标志449，计算等级（0，s），将计算结果设为n（步骤S2604）。

在该步骤S2604之后，或在步骤S2602中得到否定结果后，CPU401针对与d对应的按数字区别追加标志449，计算选择（0，n），将计算结果设为t（步骤S2606）。

接着，CPU401针对原始的小波树446，计算选择（d，n），将计算结果设为m（步骤S2607）。另外，CPU401针对追加标志448，计算选择（0，m），将计算结果设为u（步骤S2608）。

在此，CPU401判断c和d是否相同（步骤S2609）。在c和d相同的情况下，CPU401输出u结束计算处理（步骤S2610）。另一方面，在c和d不同的情况下，CPU401将s－t+u作为计算结果输出，结束计算处理（步骤S2611）。

（实施例的效果）

根据本实施例的结构化文档检索装置400，能够针对相同的XML文档追加或删除不同的注释数据。

（其他实施例）

本发明并不限于上述的实施例，包含各种变形例子。例如上述实施例是为了容易理解地说明本发明而详细说明的，并不一定限于具备所说明的全部结构的情况。

另外，能够将某实施例的结构的一部分置换为其他实施例的结构。另外，也能够向某实施例的结构追加其他实施例的结构。另外，对于各实施例的结构的一部分，也能够追加、删除、或置换其他结构。

另外，对于上述的各结构、功能、处理部、处理单元等，例如也可以通过用集成电路进行设计等用硬件来实现它们的一部分或全部。另外，也可以通过由CPU对实现各个功能的程序进行解释执行，通过软件实现上述的各结构、功能等。

可以将实现各功能的程序、表、文件等信息放置在存储器、硬盘、SSD（固态驱动器）等记录装置、或IC卡、SD卡、DVD等记录介质中。

另外，在说明上表示了需要考虑到控制线、信息线，在产品上并不限于一定表示出全部的控制线、信息线。实际上，也可以考虑将几乎全部的结构相互连接起来。

符号说明

400：结构化文档检索装置；401：CPU（中央运算装置）；402：主存储装置；403A：辅助存储装置；403B：外部存储装置；404：可移动介质；405：网络；406：接口部；407：XML文档集合；408：注释数据集合；409：DOM树构筑部（XML文档用）；410：DOM树构筑部（注释数据用）；411：文档结构列表构筑部；412：文档结构列表；413：文本要素列表；414：文本数据列表；415：文本共有DOM树构筑部；416：文本共有DOM树；417：文本数据/文本要素列表构筑部；418：文本分配部；419：父子关系分析/登录部；420：位置路径检索部；421：DOM DAG；422：DOM DAG构筑部；423：路径DAG；424：转置索引构筑部；425：转置索引；426：DOM DAG要素列表排序部；427：深度分配部；428：路径DAG ID取得部；429：路径DAG要素生成/登录部；430：检索索引；431：注释要素判别比特列；432：文本要素判别比特列；433：XML要素的深度数列；434：按深度区别ID列列表；435：注释结束标签判断比特列；436：注释开始标签ID列；437：注释结束标签ID列；438：注释要素的深度数列；439：路径DAG ID登录部；440：检索索引登录部；441：注释结束标签插入部；442：转置索引登录部；443：XML要素检索部；444：注释要素检索部；445：扩展小波树；446：由原始数列构成的小波树；447：数字变更表；448：追加标志；449：按数字区别追加标志；450：变更小波树；451：扩展小波树构筑部；452：扩展小波树的等级计算部；453：扩展小波树的选择计算部；454：检索索引构筑部；455：简易比特矢量/小波树构筑部。

Claims (12)

1.一种结构化文档检索装置，其特征在于，具备：

处理器，其执行程序；

第一存储区域，其存储程序；

第二存储区域，其存储满足树结构条件的结构化文档以及对该文档附加的注释数据；

文档结构列表构筑部，其针对使根据上述结构化文档的标签的包含关系和上述注释数据的标签的包含关系单独得到的DOM树的根要素通用化的结构，分配结构化文档的文本，生成文本共有DOM树；

输入装置，其用于输入检索查询；

地址路径检索部，其从上述文本共有DOM树中检索与作为上述检索查询提供的位置路径符合的要素。

2.一种结构化文档检索装置，其特征在于，具备：

处理器，其执行程序；

第一存储区域，其存储程序；

第二存储区域，其存储满足树结构条件的结构化文档以及对该文档附加的注释数据；

文档结构列表构筑部，其针对使根据上述结构化文档的标签的包含关系和上述注释数据的标签的包含关系单独得到的DOM树的根要素通用化的结构，加入不同的DOM树的标签之间的包含关系，并且针对该加入后的结构，分配结构化文档的文本，生成DOM DAG；

输入装置，其用于输入检索查询；

地址路径检索部，其从上述DOM DAG中检索与作为上述检索查询提供的位置路径符合的要素。

3.根据权利要求2所述的结构化文档检索装置，其特征在于，具备：

路径DAG要素生成登录部，其生成集合了多个上述DOM DAG的结构的路径DAG；

转置索引构筑部，其构筑由上述路径DAG的要素的ID即路径DAG ID、处于对应关系的一个或多个上述DOM DAG的要素的位置信息构成的转置索引，

上述位置路径检索部根据上述路径DAG和上述转置索引，计算与作为检索查询的位置路径符合的要素出现的位置。

4.根据权利要求2所述的结构化文档检索装置，其特征在于，具备：

路径DAG要素生成登录部，其生成集合了多个上述DOM DAG的结构的路径DAG；

检索索引构筑部，其构筑保存上述路径DAG、比特列、存储与上述DOMDAG的各要素对应的位置路径的种类的数列数据的检索索引，

上述位置路径检索部根据上述路径DAG计算与作为检索查询的位置路径对应的路径DAG ID，通过上述比特列和上述数列数据的扫描，计算通过计算求出的上述路径DAG ID确定的要素出现的位置。

5.根据权利要求2所述的结构化文档检索装置，其特征在于，具备：

路径DAG要素生成登录部，生成集合了多个上述DOM DAG的结构的路径DAG；

检索索引构筑部，其构筑保存上述路径DAG、比特列、存储与上述DOMDAG的各要素对应的位置路径的种类的数列数据的检索索引；

简洁比特矢量/小波树生成部，其根据上述检索索引保存的上述比特列和上述数列数据生成简洁比特矢量和小波树，

上述位置路径检索部根据上述路径DAG计算与作为检索查询的位置路径对应的路径DAG ID，通过对上述简洁比特矢量或上述小波树的等级运算和选择运算，计算通过计算求出的上述路径DAG ID确定的要素出现的位置。

6.根据权利要求5所述的结构化文档检索装置，其特征在于，

具备：扩展小波树构筑部，其在通过追加注释数据将登录在上述小波树中的数列的一部分数字置换为其他数列的情况下，将上述小波树变换为包含针对该小波树的变更信息的扩展小波树，

上述位置路径检索部在上述等级运算和选择运算中使用上述扩展小波树。

7.一种程序，其特征在于，使计算机执行以下的处理：

针对使根据满足树结构条件的结构化文档的标签的包含关系和对该文档附加的注释数据的标签的包含关系单独得到的DOM树的根要素通用化的结构，分配结构化文档的文本，生成文本共有DOM树的第一处理；

从上述文本共有DOM树中检索与作为上述检索查询而提供的位置路径符合的要素的第二处理。

8.一种程序，其特征在于，使计算机执行以下的处理：

针对使根据满足树结构条件的结构化文档的标签的包含关系和对该文档附加的注释数据的标签的包含关系独立得到的DOM树的根要素通用化的结构，加入不同的DOM树的标签之间的包含关系，并且对该加入后的结构分配结构化文档的文本，生成DOM DAG的第一处理；

从上述DOM DAG中检索与作为上述检索查询提供的位置路径符合的要素的第二处理。

9.根据权利要求8所述的程序，作为使计算机执行的处理，还具有：

生成集合了多个上述DOM DAG的结构的路径DAG的第三处理；

构筑由上述路径DAG的要素的ID即路径DAG ID和处于对应关系的一个或多个上述DOM DAG的要素的位置信息构成的转置索引的第四处理，

上述上述第二处理根据上述路径DAG和上述转置索引，计算与作为检索查询的位置路径符合的要素出现的位置。

10.根据权利要求8所述的程序，其特征在于，作为使计算机执行的处理，还具有：

生成集合了多个上述DOM DAG的结构的路径DAG的第三处理；

构筑保存上述路径DAG、比特列、存储与上述DOM DAG的各要素对应的位置路径的种类的数列数据的检索索引的第五处理，

上述第二处理根据上述路径DAG计算与作为检索查询的位置路径对应的路径DAG ID，通过上述比特列和上述数列数据的扫描，计算通过计算求出的上述路径DAG ID确定的要素出现的位置。

11.根据权利要求8所述的程序，其特征在于，作为使计算机执行的处理，还具有：

生成集合了多个上述DOM DAG的结构的路径DAG的第三处理；

构筑保存上述路径DAG、比特列、存储与上述DOM DAG的各要素对应的位置路径的种类的数列数据的检索索引的第五处理；

根据上述检索索引保存的上述比特列和上述数列数据生成简洁比特矢量和小波树的第六处理，

上述第二处理根据上述路径DAG计算与作为检索查询的位置路径对应的路径DAG ID，通过针对上述简洁比特矢量或上述小波树的等级运算和选择运算，计算通过计算求出的上述路径DAG ID确定的要素出现的位置。

12.根据权利要求11所述的程序，其特征在于，作为使计算机执行的处理，具有：

在通过追加注释数据，将上述小波树中登录的数列的一部分数字置换为其他数列的情况下，将上述小波树变换为包含针对该小波树的变更信息的扩展小波树的第七处理，

上述第二处理在上述等级运算和选择运算中使用上述扩展小波树。

Images