用于信息检索的分层数据驱动导航系统及方法

1.一种用于检索与资料集相关联的信息的计算机实现的方法， 该方法包括：
存储与所述资料相关联的多个属性-值对，其中多个值中的每一 个具有与表征所述资料的多个属性中的至少一个的关联；以及
计算多个导航状态，每个导航状态对应于特定属性-值对集和特 定资料子集，其中对于每个导航状态，对应于所述导航状态的特定资 料子集包括下述资料，所述资料各自由对应于所述导航状态的特定属 性-值对集中的每个属性-值对来描述；
其中在所述多个计算的导航状态中，至少有以下情况，
第一导航状态包括具有第一属性的第一属性-值对，其中第一属 性-值对不描述第一属性所表征的所有资料，
第二导航状态包括具有第一属性的第二属性-值对，其中第二属 性-值对细化第一属性-值对，以及
第一导航状态和第二导航状态中的至少一个包括具有第三属性 的第三属性-值对，第三属性与第一属性不同，其中第三属性-值对与 第一属性-值对相互不可比并且与第二属性-值对相互不可比，以及第 三属性-值对不描述第三属性所表征的所有资料；
在数据结构中存储所计算的导航状态；
提供界面，该界面提供多个转变，每个转变提供在两个导航状 态之间的没有中介导航状态的直接路径，其中每个转变表示从对应于 始发导航状态的属性-值对集到对应于目的地导航状态的属性-值对集 的变化，其中一系列的一个或多个转变提供任意两个导航状态之间的 路径，其中所述界面提供在第一导航状态和第二导航状态间的没有中 介导航状态的直接路径；
接受指向所述资料的查询；以及
响应所述查询，检索所存储的导航状态。
2.如权利要求1所述的方法，其中所述数据结构是包括节点和 节点间的边缘的图形数据结构，所述节点表示导航状态，所述边缘表 示转变。
3.一种用于检索与资料集相关联的信息的计算机实现的方法， 该方法包括：
在第一数据结构中存储与所述资料相关联的多个属性-值对，其 中多个值中的每一个具有与表征所述资料的多个属性中的至少一个的 关联；以及
其中第一数据结构允许动态地计算多个导航状态，每个导航状 态对应于特定属性-值对集和特定资料子集，其中对于每个导航状 态，对应于所述导航状态的特定资料子集包括导航系统中的下述资 料，所述资料各自由对应于所述导航状态的特定属性值对集中的每个 属性-值对来描述；
其中在所述多个导航状态中，至少有以下情况，
第一导航状态包括具有第一属性的第一属性-值对，其中第一属 性-值对不描述第一属性所表征的导航系统中的所有资料，
第二导航状态包括具有第一属性的第二属性-值对，其中第二属 性-值对细化第一属性-值对，以及
第一导航状态和第二导航状态中的至少一个包括具有第三属性 的第三属性-值对，第三属性与第一属性不同，其中第三属性-值对与 第一属性-值对相互不可比并且与第二属性-值对相互不可比，以及第 三属性-值对不描述第三属性所表征的导航系统中的所有资料；
产生预先计算的导航状态集；
在第二数据结构中存储预先计算的导航状态集，在第二数据结 构中存储的预先计算的导航状态集包括第一导航状态和第二导航状态 中的至少一个；
提供界面，该界面提供多个转变，每个转变提供在两个导航状 态之间的没有中介导航状态的直接路径，其中每个转变表示从对应于 始发导航状态的属性-值对集到对应于目的地导航状态的属性-值对集 的变化，其中一系列的一个或多个转变提供任意两个导航状态之间的 路径，其中所述界面提供在第一导航状态和第二导航状态间的没有中 介导航状态的直接路径；
接受指向所述资料的查询；以及
响应所述查询，检索所存储的、预先计算的导航状态，或者使 用第一数据结构动态地计算多个导航状态中的一个。
4.一种用于检索与资料集相关联的信息的计算机实现的方法， 该方法包括：
在数据结构中存储与所述资料相关联的多个属性-值对，其中多 个值中的每一个具有与表征所述资料的多个属性中的至少一个的关 联；以及
响应于多个顺序查询，使用所述数据结构在运行时动态地计算 多个导航状态，每个导航状态对应于特定属性-值对集和特定资料子 集，其中对于每个导航状态，对应于所述导航状态的特定资料子集包 括导航系统中的下述资料，所述资料各自由对应于所述导航状态的特 定属性-值对集中的每个属性-值对来描述；
其中在所述多个导航状态中，至少有以下情况，
第一导航状态包括具有第一属性的第一属性-值对，其中第一属 性-值对不描述第一属性所表征的所有资料，
第二导航状态包括具有第一属性的第二属性-值对，其中第二属 性-值对细化第一属性-值对，以及
第一导航状态和第二导航状态中的至少一个包括具有第三属性 的第三属性-值对，第三属性与第一属性不同，其中第三属性-值对与 第一属性-值对相互不可比并且与第二属性-值对相互不可比，以及第 三属性-值对不描述第三属性所表征的所有资料；
提供界面，该界面提供多个转变，每个转变提供在两个导航状 态之间的没有中介导航状态的直接路径，其中每个转变表示从对应于 始发导航状态的属性-值对集到对应于目的地导航状态的属性-值对集 的变化，其中一系列的一个或多个转变提供任意两个导航状态之间的 路径，其中所述界面提供在第一导航状态和第二导航状态间的没有中 介导航状态的直接路径；以及
响应每个查询，显示计算的导航状态。
5.如权利要求4所述的方法，还包括以下步骤：将所述动态计 算的导航状态存储在高速缓存中。
6.如权利要求4所述的方法，其中从始发导航状态到目的地导 航状态的至少一个转变表示细化用于始发导航状态的相应的属性-值 对集的一个的值的细化。
7.如权利要求4所述的方法，其中从始发导航状态到目的地导 航状态的至少一个转变表示用于始发导航状态的相应的属性-值对集 的一个的值的概括。
8.如权利要求4所述的方法，其中从始发导航状态到目的地导 航状态的至少一个转变表示取消选定用于始发导航状态的相应的属 性-值对集的一个的属性。
9.如权利要求4所述的方法，其中从始发导航状态到第一目的 地导航状态的第一转变表示选择对应于第一属性的属性-值对，以及 从始发导航状态到第二目的地导航状态的第二转变表示选择对应于第 二属性的属性-值对。
10.如权利要求4所述的方法，其中从始发导航状态到目的地 导航状态的至少一个转变表示对应于下述属性的属性-值对的说明， 对于所述属性，在对应于始发导航状态的属性-值对集中没有对应的 属性-值对。
11.如权利要求4所述的方法，其中始发导航状态对应于资料 集中的仅一个资料，从所述始发导航状态到目的地导航状态的至少一 个转变表示选择与所述始发导航状态相关的特定属性-值对。
12.如权利要求4所述的方法，其中清楚地定义与所述多个属 性的至少一个关联的值。
13.如权利要求4所述的方法，其中隐含地定义与所述多个属 性的至少一个关联的值。
14.如权利要求4所述的方法，其中对共享共同属性的属性-值 对，没有属性-值对细化多个相互不可比属性-值对。
15.如权利要求4所述的方法，其中对共享共同属性的属性-值 对，至少一个属性-值对细化多个相互不可比属性-值对。
16.如权利要求4所述的方法，其中没有属性-值对细化多个相 互不可比属性-值对。
17.如权利要求4所述的方法，其中至少一个属性-值对细化多 个相互不可比属性-值对。
18.如权利要求4所述的方法，其中对相应于不同属性的任意 两个属性-值对，所述两个属性-值对是不可比的。
19.如权利要求4所述的方法，其中所述资料集包括与单个主 题区相关的资料。
20.如权利要求4所述的方法，其中所述资料集包括与多个主 题区相关的资料。
21.如权利要求4所述的方法，其中在所述资料集中的所述资 料的一部分被指定到所述资料集的子集，所述子集可整体导航。
22.如权利要求21所述的方法，其中采用所述界面来提供与所 述资料子集有关的多个转变。
23.如权利要求4所述的方法，其中所述资料集包括多个子 集，所述多个子集的每一个可独立地整体导航，所述资料集中的一部 分资料被指定到每个子集，所述资料的至少一个被指定到不止一个子 集。
24.如权利要求4所述的方法，进一步包括对用于所述资料集 中的每个资料的配置文件进行存储，所述配置文件包括属性-值对 集。
25.如权利要求24所述的方法，所述配置文件进一步包括说明 性信息。
26.如权利要求4所述的方法，所述界面包括人工用户界面。
27.如权利要求4所述的方法，所述界面包括应用程序界面。
28.如权利要求4所述的方法，其中所述界面能在基于环球网 的环境中操作。
29.如权利要求4所述的方法，其中所述界面能在基于XML 的环境中操作。
30.如权利要求4所述的方法，其中所述界面补充独立面向数 据程序的功能性。
31.如权利要求4所述的方法，所述界面包括用于搜索属性的 全文搜索工具。
32.如权利要求4所述的方法，所述界面包括用于搜索值的全 文搜索工具。
33.如权利要求4所述的方法，进一步包括对用于所述资料集 中的每个资料的配置文件进行存储，所述配置文件包括说明性信息， 所述界面包括用于搜索所述配置文件中的说明性信息的全文搜索工 具。
34.如权利要求4所述的方法，所述界面包括访问所述资料集 中的资料。
35.如权利要求4所述的方法，所述界面包括显示对应于当前 导航状态的属性-值对。
36.如权利要求35所述的方法，显示对应于当前导航状态的属 性-值对包括用户选定的属性-值对和推理的属性-值对，所述界面包括 用户选定的属性-值对和推理的属性-值对的指示。
37.如权利要求35所述的方法，显示对应于当前导航状态的属 性-值对仅包括相互不可比属性-值对。
38.如权利要求35所述的方法，其中所述显示按属性组织对应 于当前导航状态的属性-值对。
39.如权利要求35所述的方法，其中所述显示按更通用属性- 值对组织对应于当前导航状态的属性-值对。
40.如权利要求4所述的方法，所述界面包括用于基于所述多 个导航状态中的多个转变而允许从当前导航状态导航的指导搜索工 具。
41.如权利要求40所述的方法，所述指导搜索工具包括显示用 于从当前导航状态选择的导航选项，所述选项对应于从所述当前导航 状态的转变。
42.如权利要求41所述的方法，所述导航选项包括作为对应于 当前导航状态的所述属性-值对的细化的属性-值对。
43.如权利要求41所述的方法，其中所述选项包括显示属性- 值对列表集，每个列表对应于所述属性的一个，一些列表包括用于对 与当前导航状态相应的属性-值对进行细化的属性-值对，以及一些列 表包括对相应于当前导航状态的属性-值对不可比的属性-值对。
44.如权利要求41所述的方法，其中所述显示按属性组织导航 选项。
45.如权利要求41所述的方法，其中所述显示按更通用属性- 值对组织导航选项。
46.如权利要求41所述的方法，所述导航选项包括对相应于当 前导航状态的属性-值对不可比的属性-值对。
47.如权利要求41所述的方法，所述导航选项包括作为对应于 当前导航状态的属性-值对的概括的属性-值对。
48.如权利要求41所述的方法，所述导航选项包括从对应于当 前导航状态的所述属性-值对集取消选定属性-值对。
49.如权利要求41所述的方法，所述导航选项进一步包括到相 关的导航状态的链接。
50.如权利要求49所述的方法，其中所述相关导航状态是当前 导航状态的概括。
51.如权利要求49所述的方法，其中所述相关导航状态是当前 导航状态的细化。
52.如权利要求49所述的方法，其中所述链接对应于一个或多 个转变的路径。
53.一种用于检索与资料集相关联的信息的计算机实现的方 法，该方法包括：
在第一数据结构中存储与所述资料相关联的多个属性-值对，其 中多个值中的每一个具有与表征所述资料的多个属性中的至少一个的 关联；以及
其中第一数据结构允许动态地计算多个导航状态，每个导航状 态对应于特定属性-值对集和特定资料子集，其中对于每个导航状 态，对应于所述导航状态的特定资料子集包括导航系统中的下述资 料，所述资料各自由对应于所述导航状态的特定属性值对集中的每个 属性-值对来描述；
其中在所述多个导航状态中，至少有以下情况，
第一导航状态包括具有第一属性的第一属性-值对，其中第一属 性-值对不描述第一属性所表征的导航系统中的所有资料，
第二导航状态包括具有第一属性的第二属性-值对，其中第二属 性-值对细化第一属性-值对，以及
第一导航状态和第二导航状态中的至少一个包括具有第三属性 的第三属性-值对，第三属性与第一属性不同，其中第三属性-值对与 第一属性-值对相互不可比并且与第二属性-值对相互不可比，以及第 三属性-值对不描述第三属性所表征的导航系统中的所有资料；
产生预先计算的导航状态集；
在第二数据结构中存储预先计算的导航状态集，在第二数据结 构中存储的预先计算的导航状态集包括第一导航状态和第二导航状态 中的至少一个；
提供界面，该界面提供多个转变，每个转变提供在两个导航状 态之间的没有中介导航状态的直接路径，其中每个转变表示从对应于 始发导航状态的属性-值对集到对应于目的地导航状态的属性-值对集 的变化，其中一系列的一个或多个转变提供任意两个导航状态之间的 路径，其中所述界面提供在第一导航状态和第二导航状态间的没有中 介导航状态的直接路径，其中在第二导航状态中提供的第一转变对应 于下述第一导航属性，对于该第一导航属性，在第一导航状态中不提 供任何转变；
接受指向所述资料的查询；以及
响应所述查询，检索所存储的、预先计算的导航状态，或者使 用第一数据结构动态地计算多个导航状态中的一个。
54.一种用于检索与资料集相关联的信息的计算机实现的方 法，该方法包括：
在第一数据结构中存储与所述资料相关联的多个属性-值对，其 中多个值中的每一个具有与表征所述资料的多个属性中的至少一个的 关联；以及
其中第一数据结构允许动态地计算多个导航状态，每个导航状 态对应于特定属性-值对集和特定资料子集，其中对于每个导航状 态，对应于所述导航状态的特定资料子集包括导航系统中的下述资 料，所述资料各自由对应于所述导航状态的特定属性值对集中的每个 属性-值对来描述；
其中在所述多个导航状态中，至少有以下情况，
第一导航状态包括具有第一属性的第一属性-值对，其中第一属 性-值对不描述第一属性所表征的导航系统中的所有资料，
第二导航状态包括具有第一属性的第二属性-值对，其中第二属 性-值对细化第一属性-值对，以及
第一导航状态和第二导航状态中的至少一个包括具有第三属性 的第三属性-值对，第三属性与第一属性不同，其中第三属性-值对与 第一属性-值对相互不可比并且与第二属性-值对相互不可比，以及第 三属性-值对不描述第三属性所表征的导航系统中的所有资料；
产生预先计算的导航状态集；
在第二数据结构中存储预先计算的导航状态集，在第二数据结 构中存储的预先计算的导航状态集包括第一导航状态和第二导航状态 中的至少一个；
提供界面，该界面提供多个转变，每个转变提供在两个导航状 态之间的没有中介导航状态的直接路径，其中每个转变表示从对应于 始发导航状态的属性-值对集到对应于目的地导航状态的属性-值对集 的变化，其中一系列的一个或多个转变提供任意两个导航状态之间的 路径，其中所述界面提供在第一导航状态和第二导航状态间的没有中 介导航状态的直接路径，所述界面还提供全文搜索工具，该全文搜索 工具使得能够对多个属性和多个值进行全文搜索；
接受指向所述资料的查询；以及
响应所述查询，检索所存储的、预先计算的导航状态，或者使 用第一数据结构动态地计算多个导航状态中的一个。

技术领域\n本发明通常涉及信息导航系统和搜索引擎。\n背景技术\n随着增强的计算能力和网络体系结构允许集聚大量信息和对那 种信息的广泛访问，从信息数据库的信息检索是愈加具有挑战性的问 题，特别是在环球网(WWW)。信息检索过程的目的是允许识别用 户感兴趣的资料。\n随着用户可以检索的资料数量的增加，识别与搜索有关的资料 变得日益重要，但也日益困难。由信息检索过程引起的挑战包括提供 直观、灵活的用户界面以及在合理的时间量内精确地识别与用户需要 有关的资料。信息检索过程包含两个相关的技术方面，即，信息组织 和访问。\n当前信息导航系统通常遵循三个范例的一个。一种信息导航系 统采用数据库查询系统。在典型的数据库查询系统中，用户通过指定 用于固定数据字段来制定结构化查询，以及该系统列举其数据字段包 含那些值的文档。例如，PriceSCAN.com使用这种界面。通常，数 据库查询系统为用户提供基于表格的界面，将表格输入转换成以正式 数据库语言，诸如 SQL 的查询，然后在关系数据库管理系统上执行 查询。典型的基于查询的系统的缺点包括它们允许用户进行不返回文 档的查询以及它们提供仅导致另外的结果集(对应于用户搜索说明的 文档)限制的查询修改选项，而不扩展或扩充结果集。\n第二种信息导航系统是全文(free-text)搜索引擎。在典型的全 文搜索引擎中，用户通常以布尔表达式的形式输入任意的文本串，以 及系统通过列举包含匹配文本的文档来响应。例如Google.com包括 全文搜索引擎。通常，全文搜索引擎向用户提供搜索表格，通常是单 行，以及使用预计算过的索引处理查询。通常这一索引将每个文档与 包含在那个文档中的大部分字关联，而不独立地考虑文档的内容。因 此，结果集通常是混合相关和不相关文档的大量、无组织列表。尽管 已经开发出试图确定用户查询的目的并提供结果的相关等级或者缩小 或组织结果集的变形，但这些系统在实现这些目的方面是有限制的并 且不可靠。\n第三种信息导航系统是基于树的目录。在基于树的目录中，用 户通常以树的根节点开始并通过相继地选择通向树中的其他节点的细 化分支来指定查询。例如，Shopping.yahoo.com使用基于树的目 录。在典型的实现中，将硬编码树(hard-coded tree)存储在数据 结构中，以及相同或另一数据结构将文档映射到他们所处的树的节点 或多个节点。特定的文档通常通过树，从仅一条或至少几个路径访 问。导航状态的集合是相对静止的-虽然通常将文档增加到目录中的 节点上，目录的结构通常保持相同。在纯基于树的目录中，将目录节 点排列成所有用户都从其开始的单个根节点，以及经用户从根节点选 择的分支的独特序列仅能到达的每个其他的目录节点(directory node)。这种目录强加树的分支必须是导航不相交的限制-即使分配 给不相交分支的文档的方式对用户来说不直观。可以通过增加另外的 链接以便将树转换成非循环有向图来解决这一刻板性。更新目录结构 仍然是困难的任务，而且叶节点特别倾向于以大量相应的文档告终。\n在所有这些类型的导航系统中，对用户在浏览其结果集后有效 地修改查询是很困难的。在数据库查询系统中，用户可以增加项或从 查询去除项，但对用户来说避免指定太少查询(即，太多结果)或指 定太多查询(即，无结果)通常很困难。在全文搜索引擎中，出现相 同的问题。在基于树的目录中，对用户来说，唯一修改查询的方法是 通过选择分支来缩小它或通过退回到在前分支来概括它。\n用于信息检索的各种其他系统也是可用的。例如，Danish et al. 的美国专利No.5,715,444和5,983,219，均名为“Method and Systme for Executing a Guided Parametric Search”公开了用于从一系列项识 别单个项的界面。该界面向用户提供存在于一系列项中的特征的一组 列表并识别满足所选定的特性的项。\n发明内容\n本发明的分层数据驱动信息导航系统和方法使用与那些资料有 关的某些共同的属性，启动文档集或其他资料的导航。该导航系统界 面允许用户选择用于与当前导航状态中的资料相关的属性值并返回对 应于用户选择的资料。本发明通过将项(属性-值对)与文档关联、 定义项中的分层细化关系集(即，偏序)，以及基于项与文档的关联 以及项中的关系，提供导向导航机制来启动这一导航模式。\n本发明包括与分层数据驱动导航系统有关的几个部分和特性。 在这些中为用户界面、知识库、用于生成和维护知识库的方法、可导 航的数据结构和用于生成数据结构的方法、基于WWW的系统应 用，以及实现该系统的方法。尽管在此主要参考用于导航产品数据库 的基于WWW的系统来描述本发明，应当理解到能在任何数据库上 下文中采用类似的导航系统，其中资料可以与术语相关并且用户能通 过那些术语识别感兴趣的资料。\n本发明使用有关资料集的信息知识库来设计界面并采用该界面 来通过提供相关的导航选项引导用户通过导航状态集。知识库包括列 举与资料有关的属性、用于每个属性的值范围以及与术语(属性-值 对)有关的偏序的表示。用于与娱乐有关的资料的属性-值对可以是 例如product:Movie和Director.Spike Lee。(在本说明书中，这一属 性中表示属性-值对：Value格式；导航状态表示为属性-值对的相对 集)。知识库还包括将资料集中的每个项与特征化那个项的术语集关 联的分类映象。\n知识库通常是按域组织的，域是符合自然分组的资料集。最 好，选择域以便易处理的多个属性足以有效地区分以及在那个域的资 料中导航。知识库最好包括每个域的特性，其可以包括涉及那个域中 的文档的分类的规则或缺省期望。特定项可以在不止一个域中。\n本发明包括用于导航的用户界面。用户界面最好将用户导航状 态呈现为按属性组织的一组术语。对指定的术语集，用户界面显示与 那些术语有关的资料并显示用于缩小或概括导航状态的相关导航选 项。在本发明的一个方面中，用户通过选择和取消选定术语来在资料 集中导航。\n在本发明的一个方面中，用户界面立即响应选择或取消选定术 语，而不等待用户指示和提交由多个术语组成的复杂查询。只要已经 执行查询，用户可以通过选择另外的术语或通过细化现有的术语来缩 小导航状态(navigation state)。另外，用户可以通过取消选定已经 选择过的术语或通过概括术语来扩大导航状态。在优选实施例中，用 户可以通过以不同于选择它们的顺序取消选定术语来扩大导航状态。 例如，用户可能以{products:Movies}开始，通过选择另外的术语缩小 到{product:Movies；Genre:Drama}，再次缩小到{product:Movies；Genre: Drama；Director:Spike Lee}，然后通过取消选定术语来概括到 {product:Movies；Director:Spike Lee}。\n在本发明的另一方面中，用户界面允许用户使用全文搜索来查 找感兴趣的术语。在本发明的另一方面中，用户界面还允许用户在与 资料有关的描述信息上使用全文搜索。\n在本发明的另一方面中，用户界面向用户显示用于缩小导航状 态的上下文相关的导航选项。用户界面不向用户显示其选择没有对应 于最终导航状态中的文档的术语。用户界面仅向用户显示与当前导航 状态中的至少一个项关联的术语。同时，当它们变得相关时，用户界 面显示新的导航选项。知识库可以包含确定特定属性或术语何时变得 可用于用户以便导航的规则。\n在本发明的另一方面中，例如，当资料对应于可用于从各个源 购买的产品时，知识库包括已经从资料聚集的标准表示的目录。\n在本发明的另一方面中，知识库可以包括库定义、组成同时可 搜索的资料集。库可以包括来自一个或多个域的文档。可以将项指定 给不止一个库。知识库可以包括定制用于特定库的导航的规则。\n在本发明的另一方面中，通过多级、重复过程来开发知识库。 工作流管理分配资源以便最小化生成和维护知识库的效率。\n使用知识库来通过资料集生成支持导航的数据结构。在本发明 的一方面中，导航系统由将术语集映射到与那些术语相关的资料集的 导航状态的分层(即偏序)组成。在本发明的另一方面中，通过对应 于从一个导航状态缩小到另一个的术语的转变，关联导航状态。可以 预先全部或部分计算，或在运行时整个计算导航状态。\n根据本方面的一个方面，提供了一种用于检索与资料集相关联 的信息的计算机实现的方法，该方法包括：存储与所述资料相关联的 多个属性-值对，其中多个值中的每一个具有与表征所述资料的多个 属性中的至少一个的关联；以及\n计算多个导航状态，每个导航状态对应于特定属性-值对集和特 定资料子集，其中对于每个导航状态，对应于所述导航状态的特定资 料子集包括下述资料，所述资料各自由对应于所述导航状态的特定属 性-值对集中的每个属性-值对来描述；\n其中在所述多个计算的导航状态中，至少有以下情况，\n第一导航状态包括具有第一属性的第一属性-值对，其中第一属 性-值对不描述第一属性所表征的所有资料，\n第二导航状态包括具有第一属性的第二属性-值对，其中第二属 性-值对细化第一属性-值对，以及\n第一导航状态和第二导航状态中的至少一个包括具有第三属性 的第三属性-值对，第三属性与第一属性不同，其中第三属性-值对与 第一属性-值对相互不可比并且与第二属性-值对相互不可比，以及第 三属性-值对不描述第三属性所表征的所有资料；\n在数据结构中存储所计算的导航状态；\n提供界面，该界面提供多个转变，每个转变提供在两个导航状 态之间的没有中介导航状态的直接路径，其中每个转变表示从对应于 始发导航状态的属性-值对集到对应于目的地导航状态的属性-值对集 的变化，其中一系列的一个或多个转变提供任意两个导航状态之间的 路径，其中所述界面提供在第一导航状态和第二导航状态间的没有中 介导航状态的直接路径；\n接受指向所述资料的的查询；以及\n响应所述查询，检索所存储的导航状态。\n根据本方面的另一个方面，提供了一种用于检索与资料集相关 联的信息的计算机实现的方法，该方法包括：\n在第一数据结构中存储与所述资料相关联的多个属性-值对，其 中多个值中的每一个具有与表征所述资料的多个属性中的至少一个的 关联；以及\n其中第一数据结构允许动态地计算多个导航状态，每个导航状 态对应于特定属性-值对集和特定资料子集，其中对于每个导航状 态，对应于所述导航状态的特定资料子集包括导航系统中的下述资 料，所述资料各自由对应于所述导航状态的特定属性值对集中的每个 属性-值对来描述；\n其中在所述多个导航状态中，至少有以下情况，\n第一导航状态包括具有第一属性的第一属性-值对，其中第一属 性-值对不描述第一属性所表征的导航系统中的所有资料，\n第二导航状态包括具有第一属性的第二属性-值对，其中第二属 性-值对细化第一属性-值对，以及\n第一导航状态和第二导航状态中的至少一个包括具有第三属性 的第三属性-值对，第三属性与第一属性不同，其中第三属性-值对与 第一属性-值对相互不可比并且与第二属性-值对相互不可比，以及第 三属性-值对不描述第三属性所表征的导航系统中的所有资料；\n产生预先计算的导航状态集；\n在第二数据结构中存储预先计算的导航状态集，在第二数据结 构中存储的预先计算的导航状态集包括第一导航状态和第二导航状态 中的至少一个；\n提供界面，该界面提供多个转变，每个转变提供在两个导航状 态之间的没有中介导航状态的直接路径，其中每个转变表示从对应于 始发导航状态的属性-值对集到对应于目的地导航状态的属性-值对集 的变化，其中一系列的一个或多个转变提供任意两个导航状态之间的 路径，其中所述界面提供在第一导航状态和第二导航状态间的没有中 介导航状态的直接路径；\n接受指向所述资料的的查询；以及\n响应所述查询，检索所存储的、预先计算的导航状态，或者使 用第一数据结构动态地计算多个导航状态中的一个。\n根据本方面的另一个方面，提供了一种用于检索与资料集相关 联的信息的计算机实现的方法，该方法包括：\n在数据结构中存储与所述资料相关联的多个属性-值对，其中多 个值中的每一个具有与表征所述资料的多个属性中的至少一个的关 联；以及\n响应于多个顺序查询，使用所述数据结构在运行时动态地计算 多个导航状态，每个导航状态对应于特定属性-值对集和特定资料子 集，其中对于每个导航状态，对应于所述导航状态的特定资料子集包 括导航系统中的下述资料，所述资料各自由对应于所述导航状态的特 定属性-值对集中的每个属性-值对来描述；\n其中在所述多个导航状态中，至少有以下情况，\n第一导航状态包括具有第一属性的第一属性-值对，其中第一属 性-值对不描述第一属性所表征的所有资料，\n第二导航状态包括具有第一属性的第二属性-值对，其中第二属 性-值对细化第一属性-值对，以及\n第一导航状态和第二导航状态中的至少一个包括具有第三属性 的第三属性-值对，第三属性与第一属性不同，其中第三属性-值对与 第一属性-值对相互不可比并且与第二属性-值对相互不可比，以及第 三属性-值对不描述第三属性所表征的所有资料；\n提供界面，该界面提供多个转变，每个转变提供在两个导航状 态之间的没有中介导航状态的直接路径，其中每个转变表示从对应于 始发导航状态的属性-值对集到对应于目的地导航状态的属性-值对集 的变化，其中一系列的一个或多个转变提供任意两个导航状态之间的 路径，其中所述界面提供在第一导航状态和第二导航状态间的没有中 介导航状态的直接路径；以及\n响应每个查询，显示计算的导航状态。\n根据本方面的另一个方面，提供了一种驻留在计算机可读介质 中的计算机程序产品，用于检索与资料集相关联的信息，所述计算机 程序产品包括用于使得计算机执行以下步骤的指令：\n存储与所述资料相关联的多个属性-值对，其中多个值中的每一 个具有与表征所述资料的多个属性中的至少一个的关联；以及\n计算多个导航状态，每个导航状态对应于特定属性-值对集和特 定资料子集，其中对于每个导航状态，对应于所述导航状态的特定资 料子集包括下述资料，所述资料各自由对应于所述导航状态的特定属 性-值对集中的每个属性-值对来描述；\n其中在所述多个计算的导航状态中，至少有以下情况，\n第一导航状态包括具有第一属性的第一属性-值对，其中第一属 性-值对不描述第一属性所表征的所有资料，\n第二导航状态包括具有第一属性的第二属性-值对，其中第二属 性-值对细化第一属性-值对，以及\n第一导航状态和第二导航状态中的至少一个包括具有第三属性 的第三属性-值对，第三属性与第一属性不同，其中第三属性-值对与 第一属性-值对相互不可比并且与第二属性-值对相互不可比，以及第 三属性-值对不描述第三属性所表征的所有资料；\n在数据结构中存储所计算的导航状态；\n提供界面，该界面提供多个转变，每个转变提供在两个导航状 态之间的没有中介导航状态的直接路径，其中每个转变表示从对应于 始发导航状态的属性-值对集到对应于目的地导航状态的属性-值对集 的变化，其中一系列的一个或多个转变提供任意两个导航状态之间的 路径，其中所述界面提供在第一导航状态和第二导航状态间的没有中 介导航状态的直接路径；\n接受指向所述资料的的查询；以及\n响应所述查询，检索所存储的导航状态。\n根据本方面的另一个方面，提供了一种驻留在计算机可读介质 中的计算机程序产品，用于检索与资料集相关联的信息，所述计算机 程序产品包括用于使得计算机执行以下步骤的指令：\n在数据结构中存储与所述资料相关联的多个属性-值对，其中多 个值中的每一个具有与表征所述资料的多个属性中的至少一个的关 联，以及\n响应于多个顺序查询，使用所述数据结构在运行时动态地计算 多个导航状态，每个导航状态对应于特定属性-值对集和特定资料子 集，其中对于每个导航状态，对应于所述导航状态的特定资料子集包 括导航系统中的下述资料，所述资料各自由对应于所述导航状态的特 定属性-值对集中的每个属性-值对来描述；\n其中在所述多个导航状态中，至少有以下情况，\n第一导航状态包括具有第一属性的第一属性-值对，其中第一属 性-值对不描述第一属性所表征的所有资料，\n第二导航状态包括具有第一属性的第二属性-值对，其中第二属 性-值对细化第一属性-值对，以及\n第一导航状态和第二导航状态中的至少一个包括具有第三属性 的第三属性-值对，第三属性与第一属性不同，其中第三属性-值对与 第一属性-值对相互不可比并且与第二属性-值对相互不可比，以及第 三属性-值对不描述第三属性所表征的所有资料；\n提供界面，该界面提供多个转变，每个转变提供在两个导航状 态之间的没有中介导航状态的直接路径，其中每个转变表示从对应于 始发导航状态的属性-值对集到对应于目的地导航状态的属性-值对集 的变化，其中一系列的一个或多个转变提供任意两个导航状态之间的 路径，其中所述界面提供在第一导航状态和第二导航状态间的没有中 介导航状态的直接路径；以及\n响应每个查询，显示计算的导航状态。\n根据本方面的另一个方面，提供了一种用于检索与资料集相关 联的信息的计算机实现的方法，该方法包括：\n在第一数据结构中存储与所述资料相关联的多个属性-值对，其 中多个值中的每一个具有与表征所述资料的多个属性中的至少一个的 关联；以及\n其中第一数据结构允许动态地计算多个导航状态，每个导航状 态对应于特定属性-值对集和特定资料子集，其中对于每个导航状 态，对应于所述导航状态的特定资料子集包括导航系统中的下述资 料，所述资料各自由对应于所述导航状态的特定属性值对集中的每个 属性-值对来描述；\n其中在所述多个导航状态中，至少有以下情况，\n第一导航状态包括具有第一属性的第一属性-值对，其中第一属 性-值对不描述第一属性所表征的导航系统中的所有资料，\n第二导航状态包括具有第一属性的第二属性-值对，其中第二属 性-值对细化第一属性-值对，以及\n第一导航状态和第二导航状态中的至少一个包括具有第三属性 的第三属性-值对，第三属性与第一属性不同，其中第三属性-值对与 第一属性-值对相互不可比并且与第二属性-值对相互不可比，以及第 三属性-值对不描述第三属性所表征的导航系统中的所有资料；\n产生预先计算的导航状态集；\n在第二数据结构中存储预先计算的导航状态集，在第二数据结 构中存储的预先计算的导航状态集包括第一导航状态和第二导航状态 中的至少一个；\n提供界面，该界面提供多个转变，每个转变提供在两个导航状 态之间的没有中介导航状态的直接路径，其中每个转变表示从对应于 始发导航状态的属性-值对集到对应于目的地导航状态的属性-值对集 的变化，其中一系列的一个或多个转变提供任意两个导航状态之间的 路径，其中所述界面提供在第一导航状态和第二导航状态间的没有中 介导航状态的直接路径，其中在第二导航状态中提供的第一转变对应 于下述第一导航属性，对于该第一导航属性，在第一导航状态中不提 供任何转变；\n接受指向所述资料的的查询；以及\n响应所述查询，检索所存储的、预先计算的导航状态，或者使 用第一数据结构动态地计算多个导航状态中的一个。\n根据本方面的另一个方面，提供了一种用于检索与资料集相关 联的信息的计算机实现的方法，该方法包括：\n在第一数据结构中存储与所述资料相关联的多个属性-值对，其 中多个值中的每一个具有与表征所述资料的多个属性中的至少一个的 关联，以及\n其中第一数据结构允许动态地计算多个导航状态，每个导航状 态对应于特定属性-值对集和特定资料子集，其中对于每个导航状 态，对应于所述导航状态的特定资料子集包括导航系统中的下述资 料，所述资料各自由对应于所述导航状态的特定属性值对集中的每个 属性-值对来描述；\n其中在所述多个导航状态中，至少有以下情况，\n第一导航状态包括具有第一属性的第一属性-值对，其中第一属 性-值对不描述第一属性所表征的导航系统中的所有资料，\n第二导航状态包括具有第一属性的第二属性-值对，其中第二属 性-值对细化第一属性-值对，以及\n第一导航状态和第二导航状态中的至少一个包括具有第三属性 的第三属性-值对，第三属性与第一属性不同，其中第三属性-值对与 第一属性-值对相互不可比并且与第二属性-值对相互不可比，以及第 三属性-值对不描述第三属性所表征的导航系统中的所有资料；\n产生预先计算的导航状态集；\n在第二数据结构中存储预先计算的导航状态集，在第二数据结 构中存储的预先计算的导航状态集包括第一导航状态和第二导航状态 中的至少一个；\n提供界面，该界面提供多个转变，每个转变提供在两个导航状 态之间的没有中介导航状态的直接路径，其中每个转变表示从对应于 始发导航状态的属性-值对集到对应于目的地导航状态的属性-值对集 的变化，其中一系列的一个或多个转变提供任意两个导航状态之间的 路径，其中所述界面提供在第一导航状态和第二导航状态间的没有中 介导航状态的直接路径，所述界面还提供全文搜索工具，该全文搜索 工具使得能够对多个属性和多个值进行全文搜索；\n接受指向所述资料的的查询；以及\n响应所述查询，检索所存储的、预先计算的导航状态，或者使 用第一数据结构动态地计算多个导航状态中的一个。\n附图说明\n从下述说明和附图，将更全面地理解本发明，包括那些和其他 特征，其中：\n图1是根据本发明的实施例的导航系统的用户界面的视图。\n图2是图1的用户界面的视图，表示导航术语的下拉选择列 表。\n图3是图1的用户界面的视图，表示导航状态。\n图4是图1的用户界面的视图，表示导航状态。\n图5是图1的用户界面的视图，表示导航状态。\n图6是图1的用户界面的视图，表示导航状态。\n图7是图1的用户界面的视图，表示导航状态。\n图8是图1的用户界面的视图，表示导航状态。\n图9是图1的用户界面的视图，表示用于术语的全文搜索的结 果。\n图10是图1的用户界面的视图，表示有关特定文档的信息。\n图11A-11C是根据本发明的实施例，如何能部分排序属性值范 围的代表性例子。\n图12是用于根据本发明的实施例，选择和分类文档的过程的框 图。\n图13是示例说明根据本发明的实施例，如何分类文档集的表。\n图14是根据本发明的实施例，导航状态的代表性偏序(partial order)。\n图15是根据本发明的实施例，用于预计算导航状态的过程的框 图。\n具体实施方式\n用户界面\n根据本发明的一个实施例，图1表示分层、数据驱动导航系统 的用户界面10。导航系统在知识库中定义的文档集上操作。如所 示，最好向用户提供使用导航系统的至少两种备选方法：(1)通过 选择术语来在文档集中导航，或(2)通过在搜索框中输入所需关键 词。\n导航系统最好按域组织文档。根据本发明的一个实施例，如图 1-10所示的用户界面10在为葡萄酒域的一部分的文档集上操作。最 好，域定义反映自然分组的一部分文档集。通常，用来分类域中的文 档的属性集将是用来分类整个文档集的易处理的属性子集。域定义可 以是产品类型，例如，酒或消费者电子设备。可以将域分成子域以便 进一步组织文档集。例如，能分成电视的子域、立体声设备等等的消 费者电子设备域。文档可以对应于产品或服务。\n用户界面可以允许用户每次在一个域中导航。另外，用户界面 可以允许同时导航多个域，特别是当某些属性对多个域是通用时。\n用户界面允许用户在导航状态集中导航。每个状态由一组术语 和与那些术语有关的文档集组成。用户通过选择和取消选定术语来在 导航状态集中导航以便获得对应于每个选定术语集的导航状态。最 好，如图4中，用户界面10显示通过显示术语52的列表50的导航 状态和对应于那个状态的一些或全部文档42的列表41。最好，用户 界面显示按属性组织的导航状态的术语52。最好，初始导航状态是 对应于无术语选择，因此，对应于集合中的所有文档的根状态。\n如图2所示，用户界面10允许用户通过选择用于属性22的值 28，或通过用更具体的一个(如果适当的话)代替当前所选定的值来 缩小导航状态。最好，用户界面10向用户呈现可用于缩小当前导航 状态的选项，最好具有按属性组织的相关术语。在本发明的一些实施 例中，如图2所示，用户能从用在当前导航状态中按属性22组织的 指示符24所表示的下拉列表26选择值28。用户界面10可以以各种 格式显示这些导航选项。例如，值能呈现为图形或符号而非文本。界 面可以考虑到选择项的任一方法，例如，鼠标点击、击键、或语音命 令。可以通过各种媒介和设备，诸如电视或WWW，或电话或无线 设备提供界面。尽管在此主要论述为可视界面，界面可以包括音频部 分或主要是基于音频的。\n最好，在当前导航状态下，用户界面仅显示将导致具有最小一 个文档的导航状态的用于缩小导航状态的选项。用于提供导航选项的 这一最佳标准确保无“僵局”，或无对应于空结果集的导航状态。\n最好，用户界面可以显示用于缩小导航状态的选项，如果它们 导致具有确实比当前更少的文档的导航状态的话。这样做以确保用户 界面不必向用户显示在当前导航状态中已经通过术语暗示过的选择。\n最好，用户一选择术语28来缩小当前导航状态，用户界面就显 示新导航状态，而没有由用户的任何另外的触发动作。因为系统通过 立即反馈响应每个用户，用户不需要制定全面的查询，然后提交查 询。\n根据本发明的一个实施例，如图3和4所示，用户界面10可以 通过允许用户从所选定的术语的列表50去除术语52来扩大当前导航 状态。例如，界面10可以通过用于去除选择的复选框54和按钮56 提供列表50以便触发新选择。在所示的实施例中，用户可以按任何 顺序去除所选定的术语52并能一次去除不至一个选择52。\n最好，显示给用户的导航选项是上下文相关的。例如，细化在 前选定的术语的术语可以变为最终导航状态中的导航选项。例如，参 考图5，在选择术语Flavors:Wood and Nut Flavors52后(用户已经 选定属性Flavors的值Wood和Nut Flavors23)，Wood和Nut Flavors23则出现在属性列表20中的新导航状态的界面中并允许选择 与那个特定属性有关的值以便进一步细化查询。用户界面也可以显示 最初未显示的某些属性，当它们变为新相关时。例如，将图3与图2 相比，仅在用户已经选择在前导航状态中的术语Region:French Region后，属性French Vineyards25才出现在属性的列表20中。用 这种方式，可以将属性嵌入成所需的多个等级。当那些属性变得相关 时，将属性显示为导航选项避免在那些选项变得有意义之前，由于导 航选项使用户不知所措。\n另外，对一些属性22，可以应用多个无比(非细化)选择值 28。例如，对属性Flavor，值Fruity和Nutty，它们的没有任一个细 化另一个，可以被选择以便术语Flavors:Fruity和Flavors:Nutty缩 小导航状态。因此，用户有时能通过选择单个属性下的多个值来细化 查询。\n最好，将除去作为导航选项的某些属性，如果它们不再是有效 或有用的选择。例如，如果结果集中的所有文档共享共用术语(除选 择来达到导航状态的术语外)，那么选择那个术语将不会进一步细化 结果集，因此，作为导航选项的与那个术语有关的属性被除去。例 如，将图6与图4比较，已经除去作为导航选项的属性Wine Types27，因为在结果集中的所有文档42共享相同的术语，Wine Types:Appelational Wines。在优选实施例中，界面10的另外特性在 于将这一信息作为结果集中的文档42的共同特性显示给用户。例 如，参考图6，界面10包括表示结果集中的文档42的共同特性的显 示60。当结果集中的所有文档共享那个术语时，除去作为导航选项 的术语防止用户由于选择不细化结果集而浪费时间。\n最好，用户界面可以除去作为导航选项的值，如果它们的选择 将导致结果集中无文档。例如，将图8与图7比较，在用户选择术语 Wine Spectator Range：95-100后，用户界面除去作为导航选项的属性 Appelations22的值的列表26中的所有值28，29，除值Alexander Valley29和Napa Valley29外。Alexander Valley29和Napa Valley29 仅是用于返回结果集中的至少一个文档的属性Appellations的值的列 表26中的两个值；所有其他值28返回空集。除去作为将导致空结果 集的导航选项的值通过防止用户到达僵局来节省用户时间。\n最好，用户界面允许用户使用全文搜索来搜索所需词。根据本 发明的一个实施例，如图9所示，搜索框30最好允许用户执行用于 感兴趣的术语的全文搜索，而不执行文档本身的全文本搜索。最好， 用户界面通过显示包括由属性36组织的术语34的列表32，并允许 用户从它们中选择来响应这种搜索。最好，用户界面通过向用户显示 对应于选择的那个术语的导航状态来响应用户选择。然后用户可以从 那个状态导航(即，通过缩小或扩大它)，或执行用于术语的另外的 全文搜索。\n最好，用户界面10显示对应于当前导航状态的全部或部分文档 列表41。最好，如果用户对特定文档42感兴趣，用户可以选择它并 获得包含有关它的另外的信息的记录70，包括与那个文档有关的术 语74的列表72，如图10所示。最好，用户界面10允许用户选那些 术语74的任一子集，以便导航到对应于所选定的术语集的导航状 态。\n最好，用户界面10还提供直接链接到相关但不一定概括或细化 本发明的相关导航状态的导航选项。这些链接最好由本导航状态推断 用户兴趣并允许用户横跨相关主题。例如，如果用户正观看食品域中 的特定导航状态，链接可以将用户引导到使那些食品更全面的葡萄酒 域中的葡萄酒的导航状态。\n尽管在此已经将导航系统的界面描述为用户界面10，界面能提 供访问导航系统的其它形式。在另外的实施例中，界面可以是应用程 序界面以允许为或通过其他应用访问导航系统。界面还可以增强独立 的面向数据的应用的功能性。界面还可以用在基于WWW的应用或 基于XML应用的上下文中。导航系统还可以同时支持多个界面模 式。用多种方式可以使导航系统可用，例如，经无线通信或在手持设 备上。\n知识库\n最好，导航系统将与导航有关的所有信息存储在知识库中。知 识库是来自两个过程的信息库：分类学定义的分类。分类学定义是识 别相关属性以便特征化文档、确定用于那些属性的可接受值(诸如值 列表或范围)，以及定义术语(属性-值对)中的细化关系的偏序的 过程。分类是将术语与文档关联的过程。还可以使用知识库来维护支 持这两个过程的任何信息资产，诸如域、分类规则和缺省期望。另 外，可以使用知识库来维护影响用户导航经历的互补信息和资料。\n分类学定义过程识别适当地特征化文档的一组属性。组织分类 学定义过程的典型方法是将文档集排列成为符合自然分组的文档集的 域，以及对那个域来说，易处理的多个属性足以在那个域的文档中有 效地区分和导航。知识库最好包括每个域的特征，其可以包括涉及那 个域中的文档分类的规则或缺省期望。\n分类学定义过程还识别当适当时，用于每个属性的在变化的特 征级的值的全集。这些值最好识别集合中的文档的特定属性。可以清 楚地列举或隐含地定义这些值。例如，对“颜色”属性，可以指定有 效颜色值的全集，但对“价格”或“日期”属性，可以指定值落在其中 的范围或通用日期类型，而不定义范围。识别那些值的过程可以包括 研究域或分析文档集。\n分类学定义过程还定义术语中的细化关系的偏序(属性-值 对)。例如，术语Origin:France能细化术语Origin:Europe。细化关 系是可传递和反对称的，但不一定全部。传递性表示如果术语A细 化术语B以及术语B细化术语C，那么术语A细化术语C。例如， 如果Origin:Paris细化Origin:France和Origin:France细化 Origin:Europe，那么Origin:Paris细化Origin:Europe。反对称表示 如果两个术语不同，那么术语不能彼此细化。例如，如果 Origin:Paris细化Origin:France，那么Origin:France不细化 Origin:Paris。\n另外，术语中细化关系的偏序不一定全部一个。例如，能有两 个术语，Origin:France和Origin:Spain以便没有一个术语细化另一 个。具有这一属性的两个术语被说成是不可比。通常，如果对从那个 集选择的不同术语的任一对，一组两个或多个术语为互相不可比，则 两个术语不可比。典型地，但不一定，具有不同属性的两个术语将是 不可比的。\n假定一组术语，如果术语不细化该集中的任一其他术语，则为 最大术语，以及如果该集中的没有其他术语细化它，则它是最小术 语。例如，在集{Origin:France，Origin:Paris，Origin:Spain， Origin:Madrid}中，Origin:France和Origin:Spain是最大的，而 Origin:Paris和Origin:Madrid是最小的。在知识库中，术语如果不 细化任何其他术语则为根术语，如果没有其他术语细化它，则该术语 为叶术语。\n图11A、11B和11C示例说明根据偏序关系排列的、能用于分 类葡萄酒的属性112和值114。属性112是Type/Varietal、Origin和 Vintage。每个属性112对应于用于那个属性的最大术语。属性112 能具有相比不可比值(例如，Vintage)、值的树(例如，Origin) 或允许值细化两个或多个相互不可比值的集(例如，Type/Varietal) 的通用偏序的固定集。箭头113表示值114中的细化关系。\n可以用几种方法识别和开发属性和值，包括手动或自动处理和 分析文档。此外，这种分析可以是自顶向下或自底向上；即，从根术 语开始并进行达到叶术语，或从叶术语开始并努力进行根术语。对具 有所显示的发明来传播消息的感兴趣的零售商或其他人也可以定义属 性和术语。\n分类过程通过将每个文档与一组术语关联来定位(locate)导航 状态中的文档。每个文档与一组相互不可比术语，例如 {Type/Varietal:Chianti，Origin:Italy，Vintage：1996}以及任何其他所 需描述性信息相关。如果文档与指定术语有关。那么文档也将与指定 术语细化的所有术语相关。\n分类过程可以根据各种工作流处理。以串行或并行分类文档， 以及可以一次或多次并以任何顺序执行自动和手动分类步骤。为提高 精确性和吞吐量，可以将人类专家指定为监视用于特定文档子集分类 任务，或甚至用于特定文档子集的特定属性的专家。另外，可以交织 分类和分类学过程，特别是从一个过程获得的知识允许在另一中改 进。\n图12表示说明在用于分类过程250的可能流程中的阶段。数据 采集步骤252，即，用于数据库的文档集，可以用各种不同方法。例 如，具有导航系统将在其上操作的产品目录的零售商可以将描述其产 品的文档集提供为预先定义集。另外，可以从一个源，例如一个 Web站点，或从多个源，诸如多个Web站点收集文档，然后聚集。 如果所需文档是Web页，那么可通过适当地爬行Web、选择文档并 删除该域中不适合的文档来收集文档。在数据转换步骤254，格式化 并解析所收集的文档以便于进一步处理。在自动分类步骤256中，按 序处理格式化和解析文档以便自动将文档与术语联系。在手动分类步 骤258中，人类评论家可以校验和修改自动分类，从而确保质量控 制。最好，在自动分类步骤256或手动分类步骤258中违反的任何规 则或期望将被标记并显示给人类评论家作为手动分类步骤258的一部 分。如果将收集的文档分成域，那么通常将有指定用来分类来自每个 域的文档的最小或最佳属性集的规则以及其他域特定的分类规则。当 完成分类处理时，每个文档将具有与其相关的一组术语，其定位导航 状态集中的文档。\n在图13中，表180表示所分类的葡萄酒瓶集的可能表示。最 好，每个记录与能是唯一标识符的文档号182、名称184和相关术语 186相关。名称最好是允许经全文搜索引擎以及经基于术语的导航系 统可以访问的集合的描述性信息。\n在本发明的另一方面中，知识库可以包括文档的规范表示的目 录。每个目录记录表示可以与一个或多个文档有关的概念上不同的 项。目录允许来自与项有关的多个文档，可以是来自多个源的配置文 件信息的聚集。例如，如果由两个卖主销售相同的葡萄酒，以及如果 一个卖主提供制造年份以及地理位置信息以及另一个提供口味信息， 能在用于那种葡萄酒的目录记录中组合来自两个卖主的信息。目录也 可能通过删除重复配置来提高分类过程的效率。在图12中，目录创 建步骤260将所分类的文档与目录记录关联，当适当时，创建新目录 记录。为便于参照，通过唯一标识符，可在目录中唯一地标识项。\n知识库也可以定义库，其中库是分组以便一次可搜索的文档的 子集。例如，特定的在线葡萄酒商人可能不希望显示对应于由那个商 人的竞争者销售的产品的文档，即使知识库包含这种文档。在这种情 况下，知识库可以定义不包括由商人的竞争者销售的葡萄酒的文档 库。在图12中，库创建步骤262可以定义基于属性、术语或文档的 任何其他属性的库。可以用不止一个库标识文档。知识库可以包含已 经为特定库定制的属性或术语。\n在图12中，输出处理步骤264将来自知识库的信息输出到执行 生成可导航数据结构所需的另外的处理的系统的另一阶段。\n导航状态\n导航系统清楚或隐含地表示导航状态的集合。这些导航状态通 过由涉及术语的偏序导出的细化的偏序来关联。\n导航状态具有两种表示。第一，导航状态对应于文档集合的子 集。第二，导航状态对应于相互不可比术语集。图14基于如上所述 的葡萄酒例子，示例说明用于文档和术语的一些导航状态。例如，一 个导航状态224是{Origin:South America}(文档#1，#4，#5)； 第二导航状态224是{Type/Varietal:White，Origin:United States}(文档 #2，#9)。对应于每个导航状态的文档的子集包括通常与相应的相 互不可比术语集中的所有术语关联的文档。同时，对应于每个导航状 态的相互不可比术语集包括来自对文档子集来说共同的术语集的所有 最小术语，即，共同与子集中的每个文档关联的术语集。每个导航状 态最好是唯一的并且全部指定，对每个特定的术语集来说，或对指定 文档集来说，仅有一个对应的导航状态。\n定义导航状态集最好的一个方法是通过标准的相互不可比术语 集唯一地识别每个导航状态。将任意术语集映射到规范相互不可比术 语集的两步映射过程创建满足这一属性的状态。在该过程的第一步 中，将任意术语集映射到与所有这些术语相关的文档的子集上。回想 如果文档与指定术语关联，那么文档也将与指定术语细化的所有术语 关联，在过程的第二步中，将这一文档子集映射到对那个文档集中的 所有文档共同的术语集中的最小术语集上。从这一第二步导出的术语 集是唯一识别相应的文档子集，从而是用于导航状态的规范表示的相 互不可比术语集。通过示例，参考图14中的葡萄酒例子，术语集 {Origin:France}映射到文档子集{文档#8，#11}上，其依次映射到 规范术语集{type/varietal:Red，Origin:France}上。\n通过从与术语有关的偏序导出的细化关系220的偏序，关联导 航状态222，224，226。能根据文档子集或定义导航状态的术语集来 表示这一偏序。根据文档子集表示的导航状态A细化导航状态B， 如果对应于状态A的文档集是对应于状态B的文档集的子集的话。 根据术语集表示的导航状态A细化导航状态B，如果状态B中的所 有术语均在状态A中或被状态A中的术语细化的话。参考图14，对 应于术语集{type/Varietal:Red，Origin:Chile}{文档#4}的导航状 态226细化对应于{Origin:Chile}(文档#4，#5)的导航状态 224。由于导航状态中的细化关系产生偏序，因此它们是可传递并且 反对称的。在例子中，{Type/Varietal:Red，Orgin:Chile}(文档# 4)细化{Origin:Chile}(文档#4，#5)以及{Origin:Chile} (文档#4，#5)细化{Origin:South America}(文档#1，#4，，# 5)；因此，{Type/Varietal:Red，Orgin:Chile}(文档#4)细化 {Origin:South America}(文档#1，#4，，#5)。将根导航状态 222定义成对应于整个文档集的导航状态。将叶导航状态226定义成 不能进一步细化的导航状态，并且通常(尽管不一定)对应于各个文 档。在根222和叶226之间能有任意多个间接导航状态224。假定一 对导航状态A和B，其中B细化A，那么在偏序中有多个能将A连 接到B的间接导航状态224的路径。为便于定义，参考在此所述的 实现，将导航状态视为自细化。\n用户通过察看通常在根导航状态22开始的一个或多个导航状态 的序列来浏览文档集。在这些状态中，有三个基本的模式。第一模式 是细化，或将当前导航状态移动到细化它的导航状态。用户能通过将 术语增加到当前导航状态上或通过细化当前导航状态中的术语来执行 细化，即用术语的细化来代替那个术语。在用户增加或细化术语后， 根据如上所述的两步映射，能将新术语集映射到规范术语集上。第二 模式是概括，或将当前导航状态移动到当前状态细化的更通用的导航 状态上。用户能通过从当前导航状态去除术语或通过概括当前导航状 态中的术语，即，用当前术语细化的术语代替当前术语来执行概括。 在用户去除或概括术语后，能将新术语集映射到规范术语集上。第三 模式以所需术语集的形式简单地创建查询，所需术语集能被再次映射 到规范术语集上以便获得导航状态。\n实现\n将知识库变换成可导航数据结构以便实现本发明。可以全部预 计算、运行时动态计算或部分预计算导航状态。可以使用超高速缓存 来避免导航状态的冗余计算。\n在优选实施例中，导航状态集可以表示为图形，最好是具有标 记边缘的有向非循环多重图。图形是由节点和边缘组成的组合结构， 其中每个边缘链接一对节点。由边缘链接的两个节点被称为终点。根 据本发明，节点对应于导航状态，以及边缘表示从一个导航状态细化 到另一个的转变。由于细化是有向的，每个边缘从更通用的节点指向 细化它的节点。因为在导航状态上存在偏序，在图中没有有向循环， 即，图形是非循环的。最好，图形是多重图，因为其允许连接指定节 点对的多个边缘的可能性。每个边缘用术语标记。每个边缘具有从更 通用的终点的术语集开始、增加边缘术语和使用两步映射来使这一术 语集翻译成进行细化的规范形式的属性，细化导致为另一终点的导航 状态。即，每个边缘表示基于增加单个术语的节点间的细化转变。\n为理解图形的结构，下述定义是有用的：后裔、先辈、最小共 同先辈(LCA)、真先辈、真后裔以及最大下界(GLB)。这些定 义应用于术语中和节点中的细化偏序上。如果A和B是术语以及B 细化A，那么B被说成是A的后裔以及A被说成是B的先辈。另 外，如果A和B是不同的术语，那么B被说成A的真后裔，以及A 被说成是B的真先辈。如果A和B均是节点，应用相同的定义。\n如果C是A的先辈，以及C也是B的先辈，那么C被说成是 A和B的共同先辈，其中A、B和C均是术语或者均是节点。A和 B的共同先辈集的最小元素被称为A和B的最小共同先辈 (LCA)。如果没有术语具有一对不可比先辈，那么两个术语或两 个节点的LCA是唯一的。例如，Origin:Argentina和Origin:CHile 的LCA是图11B的术语110的偏序中的Origin:South America。然 而，一般来说，可以有用于指定术语或节点对的LCA集。\n图形中的节点计算最好自底向上执行。\n可以由分类文档直接计算图形中的叶节点-即，对应于叶导航状 态的节点。典型地，但不一定必须，叶节点将对应于包含单个文档的 集。通过计算叶节点的LCA闭合-即叶节点的子集的LCA的所有节 点，获得剩余的、非叶节点。\n根据称为用于标记方便的R函数的细化函数，确定图形的边 缘。R函数将两个节点A和B用作自变量，其中A是B的真先辈， 以及返回最大术语集以便如果术语C在R(A，B)中，那么用术语 C细化节点A导致A的真后裔和B的先辈(不一定是真的)的节 点。例如，在图14中，R({Type/Varietal:Red}，{Type/Varietal: Merlot，Orgin:Argentina，Vintage：1998})＝{Type/Varietal:Merlot， Origin:South America，Vintage：1998}。如果B1是B2的先辈，那么R (A，B1)是R(A，B2)的子集-假定A是B1和B2的真先辈。例 如，R({Type/Varietal:Red}{Type/Varietal:Red，Origin:South America})＝{Origin:South America}，\n在图中，节点A和B之间的边缘将对应于R(A，B)中的术语 子集。同时，没有来自单个先辈节点A的两个边缘使用用于细化的 相同术语。如果节点A具有后裔节点集(B1，B2，...)以便术语C 处于所有R(A，Bi)中，那么仅来自具有术语C的节点A的边缘到 达LCA(B1，B2，...)，其被保证是节点Bi中的唯一最大节点。在图 14中，例如，来自具有术语Origin:South America的节点 {Type/Varietal:Red}的边缘经过节点{Type/Varietal:Red， Origin:South America}而不是节点的真后裔{Type/Varietal:Merlot， Orgin:South America，Vintge：1998}和{Type/Varietal:Red，Origin: Chile}。图形的LCA闭合属性确保在Bi中存在唯一最大节点。因 此，每个边缘将节点-术语对唯一地映射到那个节点的真后裔上。\n图形的LCA闭合导致对指定术语集S来说，其术语集细化S的 节点集具有唯一最大节点的有用特性。这一节点被称为S的最大下 界(GLB)。\n可以清楚地计算图形并将图形存储在组合数据结构中；在不一 定包含清楚的节点和边缘表示的结构中隐含地表示图形，或使用结合 这些策略的方法来表示图形。因为导航系统通常将在大量文档集上操 作，最好用可缩放的方法来表示该图形。\n能通过计算每个可能的叶节点的子集的LCA来获得该图形。然 而，这种方法在叶节点的数量方面按指数增长，并且固有的不能伸 缩。用于获得LCA闭合的另外的策略是重复地考虑图中的所有节点 对，检索每个对的LCA是否在图形中，以及根据需要，将那个LCA 增加到该图形中。这一策略尽管在前一个上有显著的改进，但仍然相 对地不可缩放。\n预计算节点的更有效的方法是顺序地处理文档集，计算用于每 个文档的节点，以及将那个节点以及维护LCA闭合所需的任何其他 节点增加到图形上。系统存储节点和边缘作为有向非循环多重图形。 初始化该图形以便包含对应于空术语集的单个节点，根节点。参考图 15，在用于将新节点插入该图形的过程230中，在步骤232，为将插 入不对应于现有节点的图形的每个新文档，系统创建新节点。在步骤 234，在将新节点插入图形中之前，系统递归地生成任何缺少的LCA 节点并将其插入根节点(或先辈节点)和新节点之间。为确保每个节 点插入后的LCA闭合，系统在插入其真先辈的所有其他节点后，插 入在步骤236和238中丢失的文档节点。\n插入新节点需要在步骤236中增加从先辈到节点的适当的边 缘，以及在步骤238中增加新节点外的后裔。最好通过识别具有引起 新节点的细化术语并且还没有用在通向新节点的中间先辈的边缘上的 那些细化术语的先辈来确定进入节点的边缘。节点外的边缘最好通过 计算新节点的GLB和适当地增加从新节点到GLB以及到GLB具有 到其边缘的节点的边缘来确定。\n通过遵循用于集合中的每个文档的上述过程，可以预计算整个 图形。在图形的大小易处理的情况下，或如果用户很想察看具有相等 概率的每个导航状态，最好预计算图形。然而，实际上，用户通常比 其他更频繁地察看一些导航状态。的确，当图形变大时，可能根本看 不到一些导航状态。不幸的是，将察看导航状态的频率的可靠预测是 很困难的。\n预计算导航状态的另外的策略是创建允许动态地计算导航状态 的索引。特别地，能按与那个文献有关的或具有与那个文档相关的细 化的所有术语来索引每个文档。最终的索引通常在大小方面比存储导 航状态的图形的数据结构更小。这一动态方法可以节省空间和预计算 时间，但其可能以用于操作的较高响应时间或较高计算需求的代价来 完成此操作。动态实现可以使用从指定导航状态返回所有细化术语R 函数的一个变量形式，以及用于计算术语集的GLB的过程。\n可以预计算导航状态的子集。最好预计算动态计算代价最高的 状态。例如，如果状态对应于大量文档子集，最好预先计算它。在一 个可能的部分预计算方法中，可以预计算对应于高于阈值大小的文档 子集的所有导航状态。如果频繁地察看状态，最好预计算状态。在一 些实例中，可以预测将察看导航状态的频率。即使将察看导航状态的 频率不能预先预测，能通过高速缓存动态计算的结果来降低连续地预 计算需要。可以高速缓存最近或最频繁察看的状态。\n如参考界面所述，系统支持三种查询操作-即通过指定术语来细 化、概括和查询。可以根据图形来进一步描述这些操作。对查询细 化，系统列举在从对应于当前导航状态的节点的边缘上的术语。当用 户选择用于细化的术语时，系统通过显示那个边缘通向的节点来响 应。类似地，对查询概括选项，系统列举和选择通向(而不是从)对 应于当前导航状态的节点的边缘。另外，可以通过指定术语集，将查 询概括实现为特定的查询情形。对通过指定一组关键字的查询来说， 系统创建对应于指定术语集的虚拟节点并确定图形中的虚拟节点的 GLB。如果未发现GLB，那么将没有文档满足查询。否则，GLB节 点将是对应于所有文档满足查询的导航状态的图形中的最通用节点。\n本发明的导航系统允许信息提供者使导航系统覆盖在所有文档 集上。通过不同的提供者能独立地执行本发明的知识库和导航方面， 以及信息提供者可以向单独的实体外界供应这些函数。类似地，通过 导航专家，可以输入所生成的知识库。信息提供者也可以将这一导航 需求外界供应给导航系统提供者。导航系统提供者能向消费者收取用 于系统的许可费，而与其使用量无关。另外，如果产品是可用的，导 航系统提供者能经系统按每次点击、每次购买向消费者收费，或通 过导航系统，由一次点击生成的每个交易收费。导航系统提供者还能 充当聚集器-由多个源编译记录、将它们组合到全局数据集中，以及 生成导航系统以便搜索数据集。\n根据本发明的导航系统也可以提高用户配置能力和销售能力。 导航系统可以基于用户选择，包括选择来开发导航状态集的特定路径 来维护用户配置文件。使用知识库，系统还可以通过将具有关于相关 文档、属性和术语的信息的选择信息补充到知识库中来推断有关用户 喜好和兴趣的另外的信息。可以将那个信息使用到与用户感兴趣的文 档有关的市场商品和服务上。\n已经针对本发明的特定实施例给出了上述说明。本发明可以以 其他特定形式具体实现而不背离本发明的范围和范围。仅通过参考和 示例说明而不通过限制在此使用的实施例、图、术语和例子。通过附 加权利要求表示本发明的范围以及落在权利要求的等效的意思和范围 内的所有改变打算包含在此。