生成结构模式候选对象的方法、系统和程序

摘要

本发明提出了一种自动生成许多种复杂结构模式候选对象和便于选择适合的结构模式的生成结构模式候选对象的方法、系统和程序。在为系统提供了一个指向用户指定的一个结构化文档的文档逻辑结构内的一个元或一个元集的结构模式时，需编辑项确定装置在一些组成这个结构模式的项中确定一个需编辑项。结构模式候选对象生成装置根据结构化文档的文档逻辑结构信息用一些在不同表示内的项代替需编辑项，生成结构模式候选对象。结构模式候选对象表生成装置根据为用户提供选择准则的显示条件和指标对生成的结构模式候选对象进行排列，生成结构模式候选对象表。如果为系统提供了用户指定的对这个结构模式希望编辑的项，需编辑项确定装置就将这个希望编辑的项确定为需编辑项。

说明书

技术领域

本发明涉及生成一些指向在一个结构化文档(structureddocument)内的一个元(element)或一个元集(element set)的结构模式(structure pattern)的候选对象(can didate)的方法、系统和程序。

背景技术

结构化文档是涉及文档元和文档元之间的逻辑关系(文档逻辑结构)的文档。结构化文档包括例如SGML(标准通用标注语言)文档和XML(可扩展标注语言)文档。SGML是一个由ISO(国际标准化组织)制定的标准，而XML是一个由W3C(全球网协会)制定的标准。XML制定成可以在继承SGML的一些功能的同时考虑基本上是因特网的标准文档格式的HTML(超文本标注语言)的一些操作上的问题。

在这种结构化文档中文档变换和处理是很重要的。例如，PDA(个人数字助理)和移动电话近来都安装了web浏览器，但是这些小型的移动终端设备通常配备的是有限的显示区和低速的通信装置。因此，需要对台式PC的HTML文档进行处理，用一种遵从XML的注释语言从中提取只是适合小型显示屏显示的内容。此外，还强烈希望能在遵从HTML的浏览器上显示以XML描述的内容和很容易变换各企业之间格式不同的数据。因此，用XSLT(XSL变换)执行将以XML描述的内容变换成遵从HTML或PDF的显示格式的变换或者对XML文档的变换。XSL(可扩展页面格式语言)是XML文档的页面格式语言，由对需格式化的XML文档的结构变换和描述需得到的格式的意义的词汇表组成。上面提到的XSLT是实现结构变换部分的技术。

在这种对结构化文档的变换/处理中，需变换/处理的元由结构模式(structure pattern)指定。结构模式是一种指向结构化文档的文档逻辑结构内的元的表示，在这里所谓“结构模式”是指一种采用一串层次指定项(hierarchy specifying item)的表示，每个层次指定项包括一个指定目标结构的层次/层次组的层次说明符(hierarchy specifier)和一个指定在这层内需选择的元/元集的元模式(elemeni pattern)。层次指定项以下简称为“项(item)”例如，XML结构模式包括一种由WSC(全球网协会)制定的XPath(XML路径语言)模式。在XPath内，项称为定位步(location step)。稍后将以XPath作为结构模式的具体例子进行详细说明。

然而，用结构模式指定需处理的目标有着以下问题。结构模式在所讨论的结构化文档改变时可能不指向原来的元。因此，必须在原来的结构化文档改变时改变结构模式。然而，这样的维护工作必须手动执行，因此需要大量的劳力。如果所涉及的结构化文档是一个通过因特网接入的HTML文档，其内容是逐日改变的，这个问题的影响就更为显著。

一种现有的技术是给每个需指定的元一个唯一标识符。例如，在Amaya(W3C(全球网协会)开发的一种Web编辑工具)中，一个元用一个ID属性规定(见非专利文献1：Irene Vatton等七人的“Amaya内的注释(Annotations in Amaya)”，W3C自2002年12月起在线提供，2003年1月经因特网(URL：http：//www.w3.org/Amaya/User/Annotations.html)检索得到)。采用通过ID属性指定一个元，文档的改变就不会影响这个元，除非删去这个元本身。然而，用ID指定元需要花费编辑成本，因此不是现实的解决方案。

另一种现有技术是使结构模式适应在改变后文档内的任何改变(见非专利文献2：Thomas A.Phelps和Robert Wilensky的“强健的文档内定位(Robust intra-document location)”，第9届全球网会议(2000年)在线提供，2003年1月14日经因特网(URL：http：//www9.org/w9cdrom/312/312.html)检索得到)。采用这种方法，对原来的元用它的名称作为线索按照一种策略沿文档的分层结构进行搜索。然而，有着怎样确定这个预定策略即怎样规定搜索范围或搜索次序的问题。

可以有多种结构模式指向一个结构化文档内的一个特定元。下面将举例对此进行说明。图15(a)示出了一个树形结构化文档的层次结构。文档次序，即元在文档内出现的次序为元R130、元A131、元B132、元C133和元D134。图15(a)所示的指向元D134的一种结构模式是相继从父至子搜索，也就是说，一种表示为“命名为R的元的命名为A的子元的命名为B的子元的命名为D的子元”的结构模式。在稍后要说明的XPath表示法中，这可以表示为“/child∷R[1]/child∷A[1]/child∷B[1]/child∷D [1]”(第一结构模式)。在另一种指向元D134的结构模式中，可以直接从元R130指定。在这种情况下，元D134是元R130的后代，可以表示为“命名为R的元的命名为D的孙元”。在XPath表示法中，这可以表示为“child∷R[1]/descendant∷D[1]”(第二结构模式)。类似，在只跳过元B132时，可以表示为“命名为R的元的命名为A的子元的命名为D的孙元”。在XPath表示法中，这可以表示为“/child∷R[1]/child∷A[1]/descendant∷D[1]”(第三结构模式)。

虽然上面提到的三种结构模式都指向元D134，但后两种结构模式具有对上述文档改变的耐受性。例如，假设删去元B132，改变文档，结果元C133和元D134成为元A131的子元(参见图15(b))。在这种情况下，第一结构模式指向一个在这个文档中不存在的元。相反，后两种结构模式仍然继续指向元D134。此外，后两种结构模式在它们的耐受性上也是不同的。例如，具有与元D134相同的名称的元D135添加在元R130之下，使它出现在元A131之前(参见图15(c))。在这种情况下，指向元R130的命名为D的第一孙元的第二结构模式指向新添加的元D135。相反，指向元R130的元A131的命名为D的第一孙元的第三结构模式继续正确地指向原来的元D134。

这样，上面提到的由于文档内作了改变而引起的问题可以通过采用一种耐久的结构模式解决。然而，一种耐久的结构模式不是象相继从父至子搜索(以下称为“固定路径”)的结构模式那样简单，而是很难建立。此外，有许多种耐久的结构模式，因此很难选择一种最为适合将来可能对文档作出的改变。

尽管有上述情况，还没有用现有技术提供的建立耐久的结构模式的编辑环境。有一些XSLT编辑系统，包括例如excelon公司(http：//www.exceloncorp.com)的“excelon Stylus”、Altova公司(http：//www.xmlspy.com)的“XML Spy”、IBM公司(http：//www.alphaworks.ibm.com/tech/xsleditor)的“IBM XSLEditor”等等。虽然这些编辑环境提供了一种自动产生XPath的功能，但是所产生的XPath只局限于一种简单的相继从父至子的固定路径搜索。因此，为了产生一个耐久的结构模式，用户必须通过直接输入字符串或者应用通过菜单选择的辅助工具编辑固定路径。因此它难以产生许多种复杂的结构模式。此外，还要求用户具有结构模式的详细知识。

在一种现有技术中，用户给出一个搜索结果的例子，然后自动建立一个结构模式，它包括根据用户的例子得到的结构化文档内的部分结构，作为搜索结果(见专利文献1：公开的未审专利申请No.7-225771)。然而，这种技术只是根据其中是否包括根据用户的例子得到的结构化文档的部分结构来确定结构模式是否正确，它并不积极支持建立具有耐久性的结构模式。这是因为这种技术只是旨在使甚至没有结构化文档内部结构或结构模式语法的知识的用户可以容易地得到想要的结构模式。因此，自动建立的结构模式并不总是具有耐久性的结构模式。此外，用户仍然需要具有结构模式的详细知识，以便知道自动建立的结构模式是否具有耐久性。

根据结构化文档的内容，可以预测将来可能会改变到某种程度的部分。因此，如果能将结构模式的预测为将来要改变的部分指定为一个希望编辑的项，并且以一个耐久的表示补充这个部分，用户就能迅速地从许多种结构模式中得到只是一种适合他的用途的结构模式。

就这方面来说，在处理具有树结构的UNIX^文件系统的用户接口(诸如外壳)内提供了一种补充一条文件路径的功能。在这条UNIX^文件路径内，每个文件层次用“/”隔开，每个目录和文件示为一个字符串。在采用bash(Bourne Again SHell)的环境下，例如通过在输入“Ls/home/user”后接连按压Tab键，在“/home/”下的目录和文件示为“/home/user1”、“home/user2”等等，带有自动补充的文件路径。然而，这种补充文件路径的功能从顶向下补充文件路径，用户必须搜索从作为路径内基点的层次至存在所需信息的层次的所有各个层次。指定路径内的一个特定层次和只自动补充这个层次是不可能的。

因此，需要实现一种可以自动生成许多种复杂的结构模式的系统。特别是，需要实现一种能很容易从一些生成的结构模式中选择一种最佳结构模式的自动结构模式生成系统。使用这种系统，不要求用户具有结构模式的详细知识，从而防止了诸如编辑错误和输入错误之类的差错。如果可以自动生成许多种结构模式使用户可以很容易从它们中选择一种最佳的结构模式，用户就能处理在结构化文档内所作出的各种改变，也就是说就为用户提供了一种具有高度适应性的系统。此外，还需要实现一种指定结构模式内任何一项和只将这项自动编辑入一个耐久的表示的功能。利用这种功能，用户可以迅速得到一种适合他的用途的结构模式而不会有从需编辑的项一直搜索到具有需指向的元的项的麻烦。

发明内容

按照本发明生成的结构模式如上所述是一种通过重复一个由一个层次说明符和一个元模式组成的层次指定项来指向结构化文档内一个元或一个元集的表示。

本发明的系统包括需编辑项确定装置、结构模式候选对象生成装置和结构模式候选对象表生成装置。这种系统还包括一个存储结构化文档的文档逻辑结构信息和为用户提供选择准则的显示状态和指标的存储装置。在为本发明的系统提供了一个指向用户指定的一个结构化文档内的一个元或一个元集的结构模式时，需编辑项确定装置在这个结构模式的这些项中确定一个需编辑项。然后，结构模式候选对象生成装置根据结构化文档的文档逻辑结构信息用一些在不同表示内的项代替需编辑项，生成一些结构模式候选对象。结构模式候选对象表生成装置根据显示条件和指标对生成的一个或多个结构模式候选对象进行排列，生成一个结构模式候选对象表。最后，显示结构模式候选对象表，提供给用户。

本发明的另一种系统可以从用户接收一个由用户在需编辑的结构模式的这些项中指定的希望编辑的项，将这个希望编辑的项确定为需编辑项。

按照本发明，为用户提供选择准则的显示条件和指标包括，例如一个示出在结构化文档内生成的结构模式候选对象所指向的元集与指定的结构模式所指向的元集之间的包含关系的指标，和一个表示生成的结构模式候选对象的特征的可数特征量。

此外，按照本发明，结构化文档的文档逻辑结构信息包括例如结构化文档本身和结构化文档的文档类型定义。

按照本发明，用户只要为系统指定一个指向一个结构化文档内的一个特定的元或元集的结构模式就可以得到一个示出多种复杂的结构模式的结构模式候选对象表，从而避免了输入的麻烦和防止了诸如输入出错和编辑出错之类的差错。结构模式候选对象可以根据显示条件和指标排列，显示为一个结构模式候选对象表。因此，用户可以得到选择结构模式的判定准则而不需要有关结构模式的专门知识，从而使选择适合他的用途的结构模式变得更为方便。

此外，按照本发明，用户可以对需编辑的结构模式指定一个希望编辑的项。因此，可以根据需编辑的结构化文档的内容预测将来可能要改变的部分，于是用户通过将这部分指定为一个希望编辑的项可以迅速地从许多可能类型的结构模式中得到只是一个适合他的用途的结构模式。

附图说明

图1(a)和1(b)为示出实现本发明的方法的系统的总体情况的示意图，图1(a)示出了独立计算机实现的配置情况，而图1(b)示出了计算机网络实现的配置情况；

图2为示出本发明的结构模式候选对象生成系统的例子的方框图；

图3为示出本发明的生成一个或多个结构模式候选对象的方法的例子的总体流程图；

图4为示出确定一个需编辑项的方法的例子的流程图；

图5为示出生成一个或多个结构模式候选对象的方法的例子的流程图；

图6为示出用结构化文档生成一个或多个结构模式候选对象的方法的例子的流程图；

图7为示出用文档类型定义生成一个或多个结构模式候选对象的方法的例子的流程图；

图8(a)示出了结构化文档的例子，图8(b)示出了图8(a)的结构化文档的文档类型定义，而图8(c)示出了图8(a)的结构化文档的树结构；

图9示出了显示结构模式候选对象的方法的例子的流程图；

图10示出了显示根据示出包含关系的显示条件和指标生成的结构模式候选对象表的显示屏幕例子；

图11示出了显示根据示出包含关系的显示条件和指标生成的结构模式候选对象表的显示屏幕例子；

图12示出了显示根据示出作为特征量的定位步数的显示条件和指标生成的结构模式候选对象表的显示屏幕例子；

图13示出了显示根据示出作为特征量的节点数的显示条件和指标生成的结构模式候选对象表的显示屏幕例子；

图14示出了支持选择希望编辑的项的显示屏幕例子；以及

图15(a)示出了结构化文档的树结构，图15(b)和15(c)各示出了结构化文档作了一些改变后的树结构。

具体实施方式

下面将结合附图对本发明的优选实施例进行说明。然而，本发明可以用种种方式实现，并不局限于对实施例所作的说明。在整个实施例中，同样的组成部分都用同样的标号标示。

在下面所说明的实施例中，主要说明一种方法和系统，但是熟悉该技术领域的人员显然清楚本发明除了方法和系统之外还可以实现为一种计算机可读程序。因此，本发明可以用硬件、软件或者软件和硬件的组合实现。

1.系统硬件配置

图1(a)和1(b)为示出实现本发明的方法的系统的总体情况的示意图。本发明的系统可以在一个独立计算机系统上或一个包括多个计算机系统的计算机网络上实现。图1(a)示出了独立计算机实现的配置示意图，而图1(b)示出了计算机网络实现情况。

这个计算机系统包括中央处理单元1(CPU)、主存储器2(RAM)、非易失存储器3(ROM)等，通过总线4相互连接。诸如协处理器、图像加速卡、超高速缓存器和I/O控制器之类的其他配备也可以连接到总线4上。外部存储装置5、输入装置6、输出装置7、通信控制器8等可以通过适当的接口也连接到总线4上。当然，这个计算机系统可以具有通常为一个计算机系统装备的其他硬件资源。

外部存储装置5的典型例子是一个硬盘设备，但并不局限于此。外部存储装置5内也包括磁光盘存储器、光存储器和诸如闪速存储器之类的半导体存储器。外部存储器在只用来从中读出数据或程序时还包括只供读出数据用的诸如CD-ROM之类的只读存储器。

输入装置6可以装备有诸如键盘之类的输入装置和诸如鼠标之类的指点器。输入装置6还包括一个语音输入装置。输出装置7的例子有CRT、液晶显示器和等离子显示器。

在用多个计算机系统实现本发明时，这些计算机系统可以通过LAN/WAN或因特网相互连接，如图1(b)所示。用来连接的通信线路可以是专用的，也可以是公用的。这些计算机系统包括各种类型的计算机，诸如个人计算机9、工作站10和大型计算机11之类。

在一个有多个相互连接的计算机系统的计算机网络内，可以将程序分布成部分程序在用户的计算机上执行而其他部分程序在一些远程计算机上执行。程序所用的数据存储在哪个计算机处是无关紧要的。只要有关数据位置(地址)的信息已知，数据或程序可以存储在计算机的任何位置处。网络计算机之间的通信可以应用众所周知的通信技术。例如，可以采用诸如TCP/IP和HTTP之类的协议。存储在每个存储器内的每个文件(数据或程序)的位置(地址)可以用DNS、URL等标识。在这里所谓的因特网包括内部网或外部网。在这里所谓的“接入因特网”也是指接入内部网或外部网。所谓的“计算机网络”包括公众可接入的计算机网络和只允许私人接入的计算机网络。

2.结构模式候选对象生成系统

图2示出了这个实施例的结构模式候选对象生成系统的配置示意图。如图2所示，本实施例的结构模式候选对象生成系统包括需编辑项确定装置20、结构模式候选对象生成装置21和结构模式候选对象表生成装置22。本实施例的结构模式候选对象生成系统还包括外部存储装置5、输入装置6和输出装置7。

外部存储装置5是一个存储作为由用户指定的结构模式的基础的结构化文档的文档逻辑结构信息以及为用户提供选择准则的显示条件和指标25的存储装置。在本发明中，结构化文档23和结构化文档的文档类型定义24至少其中之一用作文档逻辑结构信息。在结构化文档23和文档类型定义24都存在时，文档类型定义24可以在结构化文档23内描述。或者，可以将文档类型定义24作为一个独立的文档文件记录，使得在结构化文档23内可以引用这个文档类型定义文件。在这种情况下，虽然在图2中结构化文档23和文档类型定义24示为存储在同一个存储装置内，但是它们不是一定要存储在同一个存储装置内。显示条件和指标25也不一定要存储在与存储结构化文档23或文档类型定义24的相同的存储装置内。

输入装置6是一个可用来指定需编辑的结构模式和该结构模式中的希望编辑的项的装置。输出装置7是一个显示生成的结构模式候选对象表的装置。

输入装置6可以配备有诸如键盘之类的输入装置和诸如鼠标之类的指点器。用户可以用键盘之类输入一个结构模式，指定需对它进行编辑。用户可以用鼠标之类在输出装置7的屏幕上显示的结构化文档上指定一个目标元。在这种情况下，通过众所周知的技术自动生成指向这个元的结构模式的固定路径表示。

需编辑项确定装置20的功能通过执行存储在上述诸如硬盘之类的外部存储装置5内的程序代码得到执行。主要使用的是外部存储装置5和诸如中央处理单元1和主存储器2之类的硬件资源。需编辑项确定装置20具有根据用户通过输入装置6的指定从给系统的结构模式的一些项中确定需编辑项的功能。由于没有对需编辑项的位置和范围的限制，因此可以编辑构成结构模式的一些项的任何组合(包括只是一个项的情况)。在接收到用户指定的希望编辑的项时，需编辑项确定装置20将希望编辑的项确定为需编辑项。

结构模式候选对象生成装置21的功能通过执行存储在上述诸如硬盘之类的外部存储装置5内的程序代码得到执行。主要使用的是外部存储装置5和诸如中央处理单元1和主存储器2之类的硬件资源。结构模式候选对象生成装置21具有通过根据至少结构化文档的文档逻辑结构信息(即结构化文档23)和结构化文档的文档类型定义24其中之一相继用一些在不同的表示中的项代替由需编辑项确定装置20确定的每个需编辑的项生成结构模式候选对象的功能。因此，由结构模式候选对象生成装置21生成的结构模式候选对象的数目就是在不同的表示中可代替需编辑项的项的数目。这种编辑方法稍后将详细予以说明。

结构化文档23是文档的元用元名称、元内容、元属性、属性名称、属性值等构成的文档。结构化文档23包括例如XML、SGML和HTML文档。文档类型定义24是定义结构化文档23的文档类型或语法的数据，其中定义元名称、结构、元内容的形式和陈述元的属性以定义属性名称、属性值形式、缺省属性值等。文档类型定义24例如在XML文档的情况下包括DTD和XML模式而在SGML文档的情况下包括DTD。

结构模式候选对象表生成装置22的功能通过执行存储在上述诸如硬盘之类的外部存储装置5内的程序代码得到执行。主要使用的是外部存储装置5和诸如中央处理单元1和主存储器2之类的硬件资源。结构模式候选对象表生成装置22具有根据为用户提供选择准则的显示条件和指标25对生成的结构模式候选对象重新排序、生成结构模式候选对象表的功能。如上所述，生成的结构模式候选对象表在输出装置7上显示，提供给用户。

在本申请中，以下是用作为用户提供选择准则的显示条件和指标25：示出生成的结构模式候选对象所指向的一些元集与结构化文档23内一个指定的结构模式所指向的一个元集之间的包含关系的指标；和/或示出生成的结构模式候选对象的特征的可数特征量。示出包含关系的指标和示出特征的可数特征量稍后将详细予以说明。

3.生成一个或多个结构模式候选对象的方法

图3为示出本发明的结构模式候选对象生成系统的整体工作情况的流程图。在步骤30，在由用户指定的结构模式的这些项中确定一个需编辑项。然后，在步骤31，通过编辑在步骤30确定的需编辑项生成一些结构模式候选对象，以根据至少结构化文档23和结构化文档的文档类型定义24其中之一改变成不同的表示。最后，在步骤32，根据显示条件和指标25排列生成的结构模式候选对象，生成和显示结构模式候选对象表。下面将更详细地对每个步骤进行说明。

图4为示出确定一个需编辑项的方法的例子的流程图。在步骤40，确定对于用户所指定的结构模式用户是否指定任何希望编辑的项。如果没有指定希望编辑的项，就在步骤41确定一个需编辑项。本发明的目的是自动生成许多种复杂结构模式，而没有对需编辑项的位置和范围的限制。因此，得到所指定的结构模式各项的所有组合，它们中每个都确定为一个需编辑项。可以在步骤41一次得到所有的项组合，也可以转到图3中的步骤31每次得到一个项组合，在处理后再回到步骤41。在指定了一个希望编辑的项时，在步骤42将它确定为需编辑项。因此，如果有根据结构化文档的内容能预测到将来要改变的任何部分，通过指定一个希望编辑的项来标识只有一个需编辑项，就可以迅速和正确地得到必要的信息。

图5至7示出了示出生成一个或多个结构模式候选对象的方法的一个例子的流程图。在图5的步骤50，确定在外部存储装置5内是否存储有作为用户指定的结构模式的源的结构化文档23。如果存储有结构化文档23，就在步骤51根据结构化文档23生成结构模式候选对象。如果没有存储结构化文档23，就在步骤52确定在外部存储装置5内是否存储有结构化文档的文档类型定义24。如果存储有文档类型定义24，就在步骤53根据文档类型定义24生成结构模式候选对象。如果在外部存储装置5内既没有存储结构化文档23也没有存储文档类型定义24，就在步骤54发现出错后过程结束。在步骤51或步骤53生成结构模式候选对象后，在步骤54确定是否还有任何未处理的需编辑项。如果还有任何需编辑项，过程返回步骤50，再重复这一系列步骤(步骤50至54)。否则，过程就结束。

图6为示出用结构化文档23生成一个或多个结构模式候选对象的方法的一个例子的流程图。通过将一个需编辑项用一些不同表示内的项代替生成结构模式候选对象。如前面所述，一个结构模式的项包括一个层次说明符和一个元模式。因此，用一些不同表示内的项代替一个需编辑项意味着确定这些不同表示内的不同项的层次说明符和元模式。在以下说明中，不同表示的项简称为“补充候选项(candidateitem for completion)”。

首先，根据需编辑项确定装置20在步骤60确定的需编辑项将用户指定的结构模式划分成位于需编辑项前的前项、需编辑项和位于需编辑项后的后项三个部分。然后，在步骤61，确定对于指定的结构模式在步骤60执行的划分是否得到了前项。如果存在前项，过程就转到步骤63。否则，在步骤62将前项设置为根，从而指出结构模式的最高项已选为一个需编辑项。在步骤63，确定对于指定的结构模式是否存在后项。如果存在，就在步骤65根据后项和结构化文档23确定补充候选项的元模式。如果不存在，就在步骤64提取结构化文档23内存在的所有元模式，将它们各确定为一个补充候选项的元模式。如果在步骤64或65确定有多个元模式，就对于这些元模式中的每个元模式重复执行以下所说明的步骤66至72。过程从步骤64或65进至步骤66，将有限个层次说明符中的一个层次说明符确定为一个补充候选项的层次说明符。对于所有的这些种类的层次说明符，重复执行下面所说明的步骤67至71。在步骤67，将在步骤66确定的层次说明符与在步骤64或65确定的元模式相连接，生成一个补充候选项。在步骤68，通过依此连接前项、生成的补充候选项和后项得到的结构模式应用于结构化文档23。在步骤69，确定在作为应用结果的结构化文档23内是否存在这个结构模式指向的元。如果确定存在，在步骤70将这个结构模式登记为一个结构模式候选对象。如果在结构化文档23内不存在这个结构模式指向的元，过程从步骤70转到步骤71，确定对于所有种类的层次说明符是否执行了66至71这一系列步骤。如果还有任何未处理的层次说明符，过程就返回步骤67。如果所有种类的层次说明符都已得到处理，就在步骤72确定对于在步骤64或65确定的所有元模式是否都已执行了66至72这一系列步骤。如果还有任何未处理的元模式，过程就返回步骤66。否则，过程结束。

图7为示出用文档类型定义24生成一个或多个结构模式候选对象的方法的一个例子的流程图。这个过程与用结构化文档23生成一个或多个结构模式候选对象的方法的过程几乎相同。然而在用文档类型定义24的情况下，确定是否将生成的结构模式登记为一个结构模式候选对象是根据这个结构模式按文档类型定义24是否适当，也就是说根据生成的结构模式是否符合文档类型定义24定义的结构化文档23的文档类型或语法(步骤88)。

4.提供结构模式候选对象的方法的具体例子

在解释本发明的结构模式候选对象提供系统的具体的操作前，先用一些具体例子对文档类型定义24和结构模式进行说明。

图8(a)示出了一个XML文档personnel.xml，作为在本发明中所用的结构化文档23的一个例子。一个XML文档的内容包括三个部分：XML说明、文档类型定义和XML文档主体。XML说明是对XML版本和本文档所用的字符代码的描述，位于XML文档的顶端。图8(a)所示的personnel.xml的XML说明示出了XML建议书版本为1.0，而用来对文档进行字符编码的方法是UTF-8(示于personnel.xml的第一行)。可以将文档类型定义24记录为一个独立的文档文件，使得在结构化文档23内可以引这个用文档类型定义文件，如上所述。图8(a)所示的personnel.xml在personnel.xml内引用了文档类型定义personnel.dtd((图8(b))(示于personnel.xml的第二行)。XML文档主体包括多个由标签分开的元(示于personnel.xml的第三至第十三行)。在一个XML文档内，元是构成XML文档的逻辑结构的基本单位，由开始标签、内容和结束标签组成。开始标签是标示一个元的开始的标记，为一个小于符号(＜)接有一个元类型名(标签名)和一个大于符号(＞)。结束标签是标示一个元的结束的标记，为一个小于符号和斜线(＜/)接有一个元类型名(标签名)和一个大于符号(＞)。内容是开始标签和结束标签之间的主体部分，由字符数据组成。通过将一些子元插入内容，可以建立一种嵌套结构，即分层结构。在图8(a)所示的personnel.xml内，一些命名为“person”的子元被插入命名为“personnel”的元的内容，而一些命名为“name”的子元被插入命名为“person”的子元，从而建立了一个3分层结构。整个分层结构形成了一个树结构。图8(c)示出了这个树结构。

结构模式通过重复由结构层说明符和元模式组成的项指向形成这种树结构的结构化文档内的元。如上所述，XML文档内的结构模式是Xpath。因此，下面将举个XPath的例子来说明表示结构模式的具体方式。

在Xpath中，项称为定位步，定位步之间由分界符“/”分隔。也就是说，一个XPath包括一个以上由分界符“/”衔接分隔的定位步(以下简称“步”)，这些是从左至右结合的。每步相继选择与一个上下文节点(context node，当前正在处理的节点)有关的一组节点。(“节点”是构成XML文档的树的元，严格来说它包括属性、域名空间名称、元内字符串等。)例如，“child∷div/child∷para”选择一个上下文节点的命名为“div”的子元的命名为“para”的子元。

一个定位步包括一个基准点(reference point)、一个节点测试(node test)和零个以上的谓词(predicate)三个部分。它表示为由双冒号分隔的基准点和节点测试，接有由方括号包围的零个以上的表示式。基准点规定了定位步骤所选择的节点与上下文节点之间的树关系。也就是说，基准点是Xpath内的层次说明符。节点测试规定了定位步所选择的节点的节点类型和限定名。谓词用任何表示式更详细地选择一组需用定位步选择的节点。也就是说，节点测试和谓词是XPath内的元模式。例如，“child∷data[2]”在上下文节点的命名为“data”的子元中选择第二个“data”。

在Xpath中，可以用13种基准点作为结构层说明符。下面将对每种基准点进行说明。“child”基准点选择上下文节点的子节点。“parent”基准点选择上下文节点的父节点。“descendant”基准点选择上下文节点的后代节点。后代节点是一个子节点或一个子节点的子节点，诸如此类。“ancestor”基准点选择上下文节点的前代节点。前代节点是一个父节点或一个父节点的父节点，诸如此类。“following-sibling”基准点选择上下文节点后的所有兄弟节点。“precedinging-sibling”基准点选择上下文节点前的所有兄弟节点。“following”基准点在与上下文节点相同的文档内，以文档次序选择上下文节点后的所有节点，但是后代节点除外。“precedinging”基准点在与上下文节点相同的文档内，以文档次序选择上下文节点前的所有节点，但是后代节点除外。“self”基准点只选择上下文节点本身。“descendant-or-self”基准点选择上下文节点和上下文节点的后代节点。“ancestor-or-self”基准点选择上下文节点和上下文节点的前代节点。“attribute”基准点选择上下文节点的属性。“namespace”基准点选择上下文节点的域名空间。

下面将结合图8说明结构模式候选对象提供系统的具体操作。图8(a)所示的personnel.xml假设作为结构化文档23存储在外部存储装置5内。假设用户指定需编辑指向图8(c)中所示的元“name”100的结构模式。按照上面所说明的XPath，指向元“name”100的固定路径为“child：personnel[1]child∷person[1]/child∷name[1]”。

现在说明第一实施例，用户将一个位于一个结构模式内中途的项指定为希望编辑的项。对于用户所指定的结构模式“/child∷personnel[1]child∷person[1]/child∷name[1]”来说，用户再将“/child∷person[1]”指定为一个希望编辑的项。需编辑项确定装置20将“/child∷person[1]”确定为一个需编辑项(步骤40和42)。

然后，结构模式候选对象生成装置21对结构化文档personnel.xml是否存储在外部存储装置5内进行确认(步骤50)。在这得到确认时，结构模式候选对象生成装置21对结构模式“child∷personnel[1]/child∷person[1]/child∷name[1]”进行划分，根据从需编辑项确定装置20接收到的需编辑项的信息将″/child∷personnel[1]”设置为前项而将“child∷name[1]”设置为后项(步骤60)。然后，由于存在后项，结构模式候选对象生成装置21根据后项“/child∷name[1]”和personnel.xml确定补充候选项的元模式即标签名(步骤63和65)。如图8(c)所示的personnel.xml的树结构所示，只有“person”是具有元“name[1]”作为子元的父元。因此，生成结构模式候选对象21的装置确定“ person”为补充候选项的标签名。然后，将所确定的标签名“person”分别与各种分层结构说明符即13种基准点结合在一起，确定诸如”/descendant∷person”和“/ancestor∷person”之类的各个补充候选项(步骤66和67)。将通过依次连接上面提到的前项、每一个所确定的补充候选项和后项得到的结构模式应用于结构化文档personnel.xml(步骤68)。如果，作为应用结果，在结构化文档personnel.xml存在由一个结构模式指向的元，就将这个结构模式记录为一个结构模式候选对象(步骤70)。以通过将标签名“person”与基准点“descendant”相结合得到的补充候选项“/descendant∷person”为例，所产生的结构模式将为“/child∷personnel[1]/descendant∷person/child∷name[1]”。这个结构模式指向图8(c)中所示的元“name”100至102。因此，结构模式“/child∷personnel[1]/descendant∷person/child∷name[1]”记录为一个结构模式候选对象。另一方面，以通过将标签名“person”与基准点“ancestor”相结合得到的补充候选项“/ancestor∷person”为例，所产生的结构模式将为“/child∷personnel[1]/ancestor∷person/child∷name[1]”。在结构化文档personnel.xml内不存在这个结构模式指向的元。因此，结构模式“/child∷personnel[1]/ancestor∷person/child∷name[1]”不记录为一个结构模式候选对象。检查了这样所有与13种基准点的组合后，最后记录为结构模式候选对象的将有以下三个结构模式：

/child∷personnel[1]/descendant∷person/child∷name[1]

/child∷personnel[1]/descendant-or-self∷person/child∷name[1]

/child∷personnel[1]/child∷person/child∷name[1]

这些结构模式都指向一个由命名为“name”的元100至102构成的元集。

现在说明第二实施例，用户将一个结构模式内相继的两项指定为一个希望编辑的项。这是所谓的收缩情况，将两项表示为一项。用户将“/child：；person[1]/child∷name[1]”指定为他已指定的结构模式“/child∷personnel[1]/child∷person[1]/child∷name[1]”中的一个希望编辑的项。需编辑项确定装置20将“/child∷person[1]/child∷name[1]”确定为一个需编辑项(步骤40和42)。

然后，结构模式候选对象生成装置21对结构化文档personnel.xml是否存储在外部存储装置5内进行确认(步骤50)。在这得到确认时，结构模式候选对象生成装置21根据从需编辑项确定装置20接收到的需编辑项的信息对结构模式“/child∷personnel[1]/child∷person[1]/child∷name[1]进行划分，将“/child∷personnel[1]”设置为前项(步骤60)。由于这次没有后项，结构模式候选对象生成装置21从personnel.xml提取所有可能的元模式即标签名，将它们确定为补充候选对象项(步骤63和64)。从图8(c)可见，所提取的标签名为“personnel”、“person”和“name”。确定标签名后执行的步骤，即结构模式候选对象生成装置21对于每标签名执行的步骤，与对第一实施例所说明的确定标签名后执行的那些步骤相同。最后记录为结构模式候选对象的有以下这些结构模式：

/child∷personnel[1]/child∷person

/child∷personnel[1]/descendant∷person

/child∷personnel[1]/descendant-or-self∷person

/child∷personnel[1]/descendant∷name

/child∷personnel[1]/descendant-or-self∷name

/child∷personnel[1]/descendant-or-self∷personnel

/child∷personnel[1]/self∷personnel

/child∷personnel[1]/ancestor∷personnel

以上结构模式候选对象中，“/child∷personnel[1]/descendant∷name”和“/child∷personnel[1]/descendant-or-self∷name”之外的那些都不指向原来的结构模式指向的元“name”100。这取决于下面要说明的显示条件和指标25的内容是否为用户提供这样的不指向原来的元的结构模式。

上面说明的两个实施例都是由用户指定希望编辑的项的情况。在希望编辑的项不是由用户指定时，就由一个程序进行伪选择。也就是说，需编辑项确定装置20将所指定的结构模式的各项的所有组合各确定为一个需编辑项。例如，如果所指定的结构模式是“/child∷personal[1]/child∷person[1]/child∷name[1]，于是需编辑项确定装置20得到“/child∷personnel[1]”、“/child∷person[1]”、“/child；：name[1]”、“/child∷personnel[1]/child∷person[1]”和“/child∷person[1]/child∷name[1]各个组合，将它们各确定为一个需编辑项。

5.生成和显示结构模式候选对象表的方法

图9为示出生成结构模式候选对象表的方法的一个例子的流程图。结构模式候选对象表生成装置22在步骤110确定在外部存储装置5内是否存储有一个示出包含关系的显示条件和指标。如果存储有示出包含关系的显示条件和指标，在步骤111根据显示条件和指标排列结构模式候选对象生成装置21记录的结构模式候选对象。在生成结构模式候选对象表中需考虑的不包括不属于显示条件和指标所示的任何包含关系的结构模式候选对象。于是，在步骤112确定是否存储有与一个特征量有关的显示条件和指标。如果存储有与一个特征量有关的显示条件和指标，在步骤113根据特征量排列结构模式候选对象。对于在步骤111得到排列的这些结构模式来说，将再按照特征量予以排列。在步骤114，根据所排列的结构模式候选对象生成一个结构模式候选对象表。如果不存在显示条件和指标，结构模式候选对象表生成装置22通过只是列出所有所记录的结构模式候选对象生成一个结构模式候选对象表。

图10至13示出了显示结构模式候选对象的用户接口的例子。假设在外部存储装置5内存储有一个HTML文档，如结构化文档23。图10至13中“当前XPath”栏120显示用户指定的需编辑的结构模式。这个结构模式的一些反相显示的项标示它们是用户指定的希望编辑的项。在自动生成的结构模式候选对象中指定希望予以显示的结构模式候选对象时需要使用这些图中所示的复选框121至124。

图10示出了显示结构模式候选对象表的一个屏幕显示例子，这个结构模式候选对象表是根据示出结构模式候选对象所指向的一些元集与原来的结构模式(当前XPath)所指向的元集之间的包含关系的显示条件和指标25生成的。结构模式候选对象生成装置21记录的这些结构模式候选对象根据显示条件和指标25分为四类。“包含当前所选元”栏125显示结构模式候选对象所指向的元集包括原来的结构模式所指向的元集这样一些结构模式候选对象。由于显示区的限制可以不是显示结构模式候选对象的整个表示而是只显示其中的补充候选项。图10中示出了两个补充候选项“/descendant∷TD”和“/descendant-or-self∷TD”。“指向与当前所选元相同的元”栏126显示结构模式候选对象所指向的元集与原来的结构模式所指向的元集相同这样一些结构模式候选对象。在这个实施例中，没有这样的结构模式候选对象。“包含部分当前所选元”栏127显示结构模式候选对象所指向的元集部分与原来的结构模式所指向的元集相同这样一些结构模式候选对象。在这个实施例中，没有这样的结构模式候选对象。“不包含任何当前所选元”栏128显示结构模式候选对象所指向的元集根本不包含原来的结构模式所指向的元集这样一些结构模式候选对象。如图10所示，有六个结构模式候选对象归入这一栏。

图11示出了在以上所说明的图10所示的用户接口下指定另一个XPath为当前XPath的例子。如图11所示，结构模式候选对象生成装置21记录的六个结构模式候选对象归入“指向与当前所选元相同的元”栏126和“包括部分当前所选元”栏127。

按照图10和11所示的实施例，自动生成的多个结构模式候选对象根据示出包含关系的显示条件和指标排列，提供给用户。用户可以知道结构模式候选对象与当前XPath之间的关系而不需要他自己来分析这些关系。因此，用户可以很容易根据排列情况从许多种结构模式候选对象中选择一种最适合目标结构化文档的改变特征之类的结构模式。

此外，图12示出了显示根据与特征量有关的显示条件和指标生成的结构模式候选对象表的显示屏幕的例子。在这种情况下，特征量意味着一个示出结构模式候选对象的特征的可数量。在图12所示的用户接口中，结构模式候选对象根据作为特征量的定位步数即项数排列。项数表示了信息量。因此可以说，项数越多XPath越严密，项数越少XPath越模糊。因此，项数还提供了表示结构模式候选对象的耐久性的指标。定位步数在这里作为特征量添加给上面提到的显示条件和指标有助于用户选择结构模式候选对象。在这个实施例中，用户没有指定希望编辑的项。与包含关系有关的显示条件和指标只指定指向与当前XPath所指向的相同的元集的结构模式候选对象需予以显示。这样的指定最好通过选取上面所说明的复选框122执行。这样，用户可以只显示必要的信息。

图13示出了显示根据作为特征量的节点(元)数的显示条件和指标生成的结构模式候选对象表的显示屏幕的例子。在这个实施例中，用户又没有指定希望编辑的项。然而，与包含关系有关的显示条件和指标指定这次只是指向包含当前XPath所指向的元集的元集的结构模式候选对象需予以显示。因此，显示的结构模式候选对象所指向的所有元集包含当前XPath所指向的元集。每个显示的结构模式候选对象所指向的元的数目各不相同，因此可以说，所指向的元越多，与当前Xpath有关的XPath越模糊。因此一个结构模式候选对象所指向的元的数目还提供了一个表示结构模式候选对象的耐久性。节点数在这里作为特征量添加给上面提到的显示条件和指标有助于用户选择结构模式候选对象。

虽然在图12和13所示的实施例中同时使用示出包含关系的显示条件和指标以及与特征量有关的显示条件和指标，但当然只有与特征量有关的显示条件和指标可以使用。如图12和13所示，由于将项/节点数与结构模式候选对象一起显示，因此可以提供更为友好的结构模式候选对象提供系统。

图14示出了支持用户选择希望编辑的项的功能。原则上，希望编辑的项的位置和数目可以是任意的。然而，在显示条件和指标指定如图14所示只有指向与当前XPath所指向的相同的元集的结构模式候选对象需予以显示时，可选为希望编辑的项是有限的。因此，这个实施例根据显示条件和指标的规定用一个长方形的边框包围可选为希望编辑的项来帮助用户选择。

虽然本发明的发明者上面基于本发明的实施例对本发明作了具体说明，但本发明并不局限于这些实施例，在不背离本发明的精神实质的专利保护范围内各种改变都是可行的。

虽然在这些实施例中主要对系统和方法作了说明，但很明显，在上面提到的这些实施例中也揭示了录有计算机可读程序的媒体，因为这些系统和方法的功能是这计算机可读程序实现的。这样的媒体不仅包括安装在存储装置内的诸如硬盘之类的媒体，而且还包括可从存储装置取出的诸如CD-ROM、DVD-ROM、闪速存储器和软盘之类的媒体。

作为本文件的总结，就本发明的配置揭示了以下内容。

(1)一种生成指向一个结构化文档内的一个元或一个元集的结构模式的一个或多个候选对象的方法，所述方法包括下列步骤；准备结构化文档的文档逻辑结构信息和为用户提供选择准则的显示条件和指标；接收用户指定的指向结构化文档内的一个元或一个元集的结构模式，其中所述结构模式由一个或多个项组成；在这一个或多个项中确定一个需编辑项；通过根据文档逻辑结构信息用一些在不同表示内的项代替需编辑项生成一个或多个结构模式候选对象；以及根据显示条件和指标重新排列生成的一个或多个结构模式候选对象，生成一个结构模式候选对象表。

(2)在(1)中所述的生成一个或多个结构模式候选对象的方法，其中所述确定需编辑项的步骤包括接收一个由用户指定为对这个结构模式希望编辑的项的步骤和将这个希望编辑的项确定为需编辑项的步骤。

(3)在(1)或(2)中所述的生成一个或多个结构模式候选对象的方法，其中所述显示条件和指标包括一个示出在结构化文档内生成的一个或多个结构模式候选对象所指向的元集与用户指定的结构模式所指向的元集之间的包含关系的指标。

(4)在任何(1)至(3)中所述的生成一个或多个结构模式候选对象的方法，其中所述显示条件和指标包括一个示出生成的一个或多个结构模式候选对象的特征的可数特征量。

(5)在任何(1)至(4)中所述的生成一个或多个结构模式候选对象的方法，其中所述准备文档逻辑结构信息的步骤包括准备结构化文档和结构化文档的文档类型定义至少其中之一。

(6)一种生成指向一个结构化文档内的一个元或一个元集的结构模式的一个或多个候选对象的系统，所述系统包括：一个存储结构化文档的文档逻辑结构信息和为用户提供选择准则的显示状态和指标的存储装置；接收用户指定的指向结构化文档内的一个元或一个元集的结构模式的装置，其中所述结构模式由一个或多个项组成；在这一个或多个项中确定一个需编辑项的装置；通过根据文档逻辑结构信息用一些在不同表示内的项代替需编辑项生成一个或多个结构模式候选对象的装置；以及根据显示条件和指标重新排列生成的一个或多个结构模式候选对象、生成一个结构模式候选对象表的装置。

(7)在(6)中所述的生成一个或多个结构模式候选对象的系统，其中所述确定需编辑项的装置包括接收一个由用户指定为对这个结构模式希望编辑的项的装置和将这个希望编辑的项确定为需编辑项的装置。

(8)在(6)或(7)中所述的生成一个或多个结构模式候选对象的系统，其中所述显示条件和指标包括一个示出在结构化文档内生成的结构模式候选对象所指向的元集与用户指定的结构模式所指向的元集之间的包含关系的指标。

(9)在任何(6)至(8)中所述的生成一个或多个结构模式候选对象的系统，其中所述显示条件和指标包括一个示出生成的结构模式候选对象的特征的可数特征量。

(10)在任何(6)至(9)中所述的生成一个或多个结构模式候选对象的系统，其中所述存储装置将结构化文档和结构化文档的文档类型定义存储为文档逻辑结构信息。

(11)一种生成指向一个结构化文档内的一个元或一个元集的结构模式的一个或多个候选对象的程序，所述程序使一个计算机执行下列功能：准备结构化文档的文档逻辑结构信息和为用户提供选择准则的显示条件和指标；接收用户指定的指向结构化文档内的一个元或一个元集的结构模式，其中所述结构模式由一个或多个项组成；在这一个或多个项中确定一个需编辑项；通过根据文档逻辑结构信息用一些在不同表示内的项代替需编辑项生成一个或多个结构模式候选对象；以及根据显示条件和指标重新排列生成的一个或多个结构模式候选对象，生成一个结构模式候选对象表。

(12)一种生成指向一个XML文档内的一个元或一个元集的XPath的一个或多个候选对象的方法，所述方法包括下列步骤：准备XML文档的文档逻辑结构信息和为用户提供选择准则的显示条件和指标；接收用户指定的指向XML文档内的一个元或一个元集的XPath，其中所述XPath由一个或多个定位步组成；在这一个或多个定位步中确定一个需编辑的定位步；通过根据文档逻辑结构信息用一些不同的表示的定位步代替所确定的定位步生成一些XPath候选对象；以及根据显示条件和指标排列生成的一个或多个XPath候选对象，生成一个XPath候选对象表。