用于多版本Web文档的Web服务器

具体实施方式

下文的具体描述首先呈示多版本文档的Web服务器的概述，然后将描述用户界面，最后将呈示Web服务器的多种组成部分的细节。

用于多版本文档的Web服务器的概述：图2

图2是用于多版本Web文档的Web服务器201的框图。在下文一些部分中，服务器201称为仓库服务器。从Web客户端125的角度来看，Web服务器201是标准Web服务器111。当客户端125将指定Web服务器201的URL置于Web 123上时，Web 123将该URL传递到服务器201，服务器201通过向客户端125返回Web页面来响应URL。与任何其他Web服务器一样，服务器201具有两个主要组成部分：响应指定服务器201的主机名115的URL来执行代码的处理器202，以及用于URL指定的Web页面或用于制作该Web页面所需的信息的存储器。这里，存储器119包括用户界面的Web页面225，Web客户端125使用该用户界面来控制文档服务器201和登记Web文档的数据库213。登记Web文档是已经在服务器201中登记的Web文档，即服务器201已经在Web文档在数据库213中登记时制作了该Web文档的副本223，并已经制作登记版本URL 227，其中多版本文档服务器201可以通过向作为登记版本URL的源的Web客户端125提供登记版本URL 227引用的版本副本223来响应登记版本URL 227。在该优选实施例中，副本223有两个部分：作为与登记时接收的副本完全一样的副本的原始副本222，以及其中重写了链接的重写副本224。稍后将详细论述为什么重写链接是必要的以及如何实现。

利用登记版本URL 227提取Web页面

登记版本URL 227是标准的URL：它指定协议105、主机名107(这里是服务器201的主机名)和Web页面源信息109。登记版本URL 227中的Web页面源信息包括指定程序230的参数列表，上述程序230要在处理器202中执行以提供要在程序执行中使用的Web页面和数据。这里，程序是gc，它提取登记Web页面的内容，gc是处理器202执行的版本位置代码203中的程序之一。当执行版本位置代码203时，服务器201是稍后称为登记文档提供器的一个实施例，gc取用两个参数：唯一地标识数据库213中的登记Web页面的副本223的登记标识符231和所提取的页面的原始URL 233。在优选实施例中，当多版本文档服务器201接收到登记版本URL 227时，它执行gc程序。gc首先尝试建立服务器201与原始URL 233指定的服务器111(i)之间的连接；如果成功的话，gc重定向Web客户端以使用原始URL 233提取Web页面。如果建立连接的尝试失败，则gc使用登记ID 231来定位数据库213中的副本223，然后将该副本返回到Web客户端125。当如刚才所描述的在使用时，多版本文档服务器201确保当Web客户端125将登记版本URL 227提供到服务器201时，客户端125将接收到由登记标识符231所指定的Web页面的副本223，即使原始URL 233指定的文档是不可获取时。

版本位置代码203需要解释登记版本URL 227的信息包含在登记文档表215中的登记信息217中。登记信息217使副本223与用于提取据由之制作副本223的Web页面的原始URL相关以及与唯一地标识该副本223的登记标识符相关。因为登记标识符唯一地标识副本223，所以数据库213可以包含由原始URL标识的不同版本的Web文档。而且，因为登记标识符包括在登记版本URL 227中，所以登记版本URL对于每个版本是唯一的，并且可被客户端125用于从服务器201提取特定版本的副本223。在优选实施例中，这通过将来自URL227的登记ID 231输入到服务器201提供的用户界面来执行；在其他版本中，这可以通过将URL 227提供到用户界面，然后指定服务器201是否要返回原始URL 223当前指定的版本或登记标识符231指定的副本。正如稍后将更详细解释的，对于给定副本223(i)，用户还可以指定他或她想要原始副本222(i)还是重写副本224(i)。

在服务器201中登记Web页面

Web客户机的用户通过将要登记的Web页面的URL输入到用户界面Web页面225的Web页面而在服务器201中登记Web页面。响应从Web页面的输入，服务器201执行登记代码207，该登记代码207提取URL当前指定的文档，为它生成登记ID，在登记信息217中为该登记ID创建项(包括原始URL、登记ID和该文档的副本在数据库213中的位置)，然后创建副本223的URL 227并将其返回到用户，然后该用户可以如上述地使用它。当执行登记代码207时，服务器201是稍后称为文档登记器的一个实施例。

Web页面的自动登记

服务器201的优选实施例将执行Web页面的自动登记。在优选实施例中，服务器201的管理员可以指定一定范围的感兴趣IP地址。服务器201将执行自动登记代码212，这提取那些地址处的Web内容并在服务器201中如上述地登记它们。自动登记的变化包括：

1.链接的自动登记：从登记URL开始，分析该URL标识的文档中的所有引用链接，并自动登记那些URL链接。系统可以提供选项以将URL的登记限于来自相同Web网站(域)的那些。

2.链接的递归自动登记：从登记URL开始，以递归方式跟踪URL标识的文档中的所有URL链接，只要它们来自相同Web网站(域)。注意该选项对于某些Web网站将是耗时的。

3.自动计划的登记：设置时间表以登记其内容版本和更改均是频繁/周期性的且重要的某些URL。例如，可以使用每日时间表自动登记指向内部每日“应做”列表的URL。

当然，可以将链接的自动登记和链接的递归自动登记与其他形式的自动登记组合。本发明的其他实施例还可以提供用户界面，该用户界面允许服务器201的用户设置Web客户端125的用户个人感兴趣的URL的自动登记。使用下文描述的文档指纹和指纹比较技术，另一个实施例中的服务器201可以将文档的自动登记限于与已经登记的文档有实质性不同的那些。

使用服务器201产生副本223的版本历史

登记信息217还可以用于提供使用特定原始URL提取的版本副本223的版本历史。因为登记信息使原始URL与登记ID相关，所以处理器202可以使用登记ID查询登记信息217并接收与该登记ID所标识的副本223的URL具有相同原始URL的文档版本的副本223的登记标识符的列表。服务器201使用登记ID和原始URL来构造登记ID所指定的副本223的URL 227的列表。该列表作为Web页面中的链接被返回到Web客户端125，然后用户就可以单击链接以选择特定的版本。当服务器201接收到对应于所选链接的URL 227时，它使用该URL将URL 227所指定的副本223返回到Web客户端125。在其他实施例中，服务器201可以响应原始URL或登记版本URL 227的输入来提供版本历史。在前一种情况中，原始URL用于执行查询；在后一种情况中，来自登记版本URL 227的原始URL 233用于执行查询。

URL搜索

服务器201可以具有数以千计的登记文档，每个登记文档具有各自的副本223和登记版本URL 227。在一些实施例中，提供URL搜索功能会是有用的。在URL搜索中，Web客户端125处的用户将搜索字符串输入到服务器201提供的Web页面225，服务器201搜索包含用户输入的搜索字符串的原始URL的登记信息217。当然在搜索字符串中可以使用通配字符。服务器201还可以提供区分大小写和不区分大小写搜索和基于URL或登记时间的排序。作为从URL搜索操作的输出，服务器201返回Web页面，Web页面上具有包含匹配URL 227的链接的列表和对应于每个匹配URL的登记ID 231和登记时间。

这里应该指出的是虽然服务器201登记URL，但是刚才描述的技术可以结合任何类型的可用于提取数据项的定位符或标识符来使用。为此，有时在下文中使用通用术语文档定位符作为任何其他类型的可用于提取数据项的定位符或标识符的URL的通用术语。如下是登记所需的项：

·将三件事彼此相关的服务器201可获取的数据结构：

-服务器201可访问的已登记的数据项的副本；

-登记时用于提取数据项的原版的文档定位符；以及

-唯一地标识服务器201可访问的副本的副本登记标识符。

·服务器201通过提取副本来响应副本的文档定位符。

对副本223执行的操作

可以对版本副本223执行许多操作，这进一步增加服务器201的有用性。其中有相对链接重写、对副本223进行指纹处理、基于它们的指纹比较副本223，以及将索引包括到数据库213中的副本223的内容中。

链接重写

Web页面使用HTML来定义(超文本标记语言)。在HTML中，可以将至另一个Web页面的链接编写为绝对链接，绝对链接指定完整的URL，包括协议105、主机名107和Web页面源信息109，或者编写为相对链接，相对链接由追加到用户用来提取包含相对链接的Web页面的URL的Web页面源信息109组成。因为使用相对链接构成的URL总是具有来自用于提取含该相对链接的Web页面的URL的协议和主机名，所以使用相对链接引用与包含该相对链接的Web页面相同的主机中包含的其他Web页面。

当在服务器201中登记URL并且将该URL指定的Web页面的副本添加到版本副本223时，副本223自然不再存在于为其写副本223的原版的主机的Web服务器中，并且副本223中的相对链接将结束用于提取副本223的URL，即指定服务器201的URL。为了解决这个问题，当服务器201提取正在登记的URL所引用的Web页面并将该Web页面的副本添加到版本副本223时，它制作两个副本-其一，原始副本222，这是登记时提取的原版的真正副本，其二，重写副本224，这是在其中重写了版本副本223中的所有相对链接的副本，由此当用户单击相对链接时，服务器201提供绝对URL，该绝对URL与登记版本URL 227一样采用gc程序以将客户端125重定向到从其中获取所提取的Web页面的主机的主机名所构成的URL指定的服务器111(i)。服务器201执行此操作所需的信息是从正在登记的URL获取的。该优选实施例还以相同方式重写大多数绝对链接的URL，其中利用gc程序将客户端125重定向到原始绝对链接中指定的服务器111(i)。

指纹处理版本副本223

文档的指纹是比文档小得多的值，它是以可以比较两个文档的指纹来确定文档彼此的相似程度的方式根据文档产生的。指纹与散列函数产生的文档摘要不同，在于两个摘要的比较只能指示产生这些摘要的文档是否相同。另一方面，指纹比较指示正在比较的文档的相似度。文档服务器201在登记文档时采用指纹处理代码209制作每个登记文档的指纹，并将指纹存储在指纹信息219中。稍后将详细解释优选实施例中使用的指纹处理算法。

比较版本副本223

因为服务器201中的每个版本副本223具有一个指纹，所以可以通过将版本副本223(i)的指纹与版本副本223(j)的指纹相比较来确定任意两个版本副本223(i)和(j)之间的相似性。该比较通过文档比较代码211来执行。在优选实施例中，服务器201为每个版本副本223维护该特定版本副本223与其原始URL与该特定版本副本具有相同主机名107的版本副本223之间的指纹比较的结果列表。

当Web客户端125的用户请求给定版本副本223的版本历史时，服务器201不仅返回与用户作为输入提供到客户端125的登记ID 231相关联的版本副本具有相同原始URL 233的版本副本223的链接列表，而且还返回至指纹比较结果列表中出现的版本副本223的链接的列表。与链接一起包括的是至给定版本副本223的链接所指定的版本副本的相似度的值。在其他实施例中，用户可以仅仅提供文档的登记ID或从用户界面Web页面225中的列表中选择至该文档的链接能够独立于版本历史操作来获取相似的版本副本的列表。能够显示两个版本副本223之间的相似度具有两个重要的优点：

·当制作给定原始URL引用的版本的版本历史时，版本相似度允许用户进行有关版本之间的关系的一些推测。

·如果相同或非常相似的内容已经与来自相同Web网站的两个不同原始URL相关联，则这些不同原始URL的副本223之间的相似度反映与这些原始URL相关联的内容实质是相同的。

对版本副本223建索引

可以采用2004年3月26日提交的、Hu等人的USSN 10/810,756、标题为具有永久性用户可访问的位图值的数据管理系统(A databasemanagement system with persistent，user-accessible bitmap values)中所描述的技术来制作数据库213中的版本副本223的内容的位图索引。可以对所有版本副本223制作索引，或者可以对与给定原始URL相关联的版本副本223制作单独的索引。

可以使用服务器201的方式示例

服务器201具有如下特征：

·它可以在Web文档所来自的Web站点不可用时提供该文档的版本副本223。

·登记制作Web文档所来自的Web站点上当前可获取的文档的版本的版本副本223，并将该副本和原始URL关联到版本编号，以便可以跟踪该Web文档的版本。

·登记可以是自动的。

·可以搜索版本副本223的原始URL。

·使版本副本223与指纹819相关，这允许对版本副本进行比较。

下文将解释利用这些特征的服务器201的使用。

服务器201作为共享信息的鲁棒源

一个公司可能具有许多内部Web站点的内联网，包括位于PC上的一些个人Web页面。当这些站点的其中之一工作时，其上的Web文档当然可被获取。在高可用性处理器和数据库系统中实现的服务器201可以解决该问题。可以在服务器201中自动登记一般需要随时可供获取的来自内部Web站点的Web文档。该公司的工作人员可以使用该文档的登记版本URL 227来提取它。如上文所描述的，服务器201将通过如下操作响应登记版本URL：首先尝试使用该文档的原始URL233以将Web客户端125重定向到该文档的主Web站点，如果失败的话，则将提供URL 227的登记ID 231引用的版本副本223。可以将以此方式使用的服务器201与已修改为搜索公司的内联网的搜索引擎组合。当搜索引擎索引到Web文档时，也将该文档登记到服务器201，搜索引擎返回的URL列表是Web文档的登记副本223的URL 227列表。

服务器201作为Web文档的版本的源

目前，如果公司希望制作可通过单个URL获取的Web文档的历史版本，则响应该单个URL产生的Web页面必须是历史版本的列表，而且该列表必须在每次新版本成为可供获取时被更新。利用服务器201，公司只需在服务器201中登记每个新版本；为了查看可用的版本副本223并检索它们中的任何一个，用户只需利用登记版本URL227对这些版本的其中之一使用版本跟踪操作。

服务器201作为用户希望保留并使之可供其他人获取的Web文档的版本的存储位置

目前，如果某个人发现他自己和其他人当前感兴趣的Web文档的版本，则感兴趣的那些人接收到稍后可能完全失效的Web文档的URL或检索出与当前感兴趣的版本不同的文档版本。可以通过登记感兴趣的Web文档的版本并将它的登记版本URL 227提供到对登记版本感兴趣的那些人来避免这种情况。

优选实施例中的用户界面的详情：图3-5

图3示出第一用户界面Web页面225，服务器201向希望使用服务器201来登记Web页面、提取Web页面或跟踪存储在服务器201中的特定页面的版本的用户返回该第一用户界面Web页面225。在303处是用户可以输入要登记的URL、登记版本URL 227或登记ID编号231以使服务器201提取原始文档或副本223或跟踪服务器201中的文档的副本的可写字段。当输入了URL或登记ID编号时，用户单击字段303下的按钮的其中之一以指定操作。正如从标签可看到的，当用户单击按钮305时，服务器201登记字段303中的URL。当登记该URL时，服务器301返回315所示的含有内容的Web页面；如图中所示，所返回的页面指示已经登记了URL 317并由登记产生的登记版本URL 227。如果已登记了URL 317，则消息315如此指示。

当字段303包含URL 227或登记ID 231时，所发生的情况取决于用户单击了按钮307-313中的哪一个。

·如果用户单击获取内容(Get cpmtemts)按钮307，则服务器201尝试建立至该文档的原始URL所指定的服务器111(i)的连接，并将Web客户端125重定向到该服务器。如果尝试失败，则服务器201提取URL 227或登记ID 231指定的版本副本223，并将其提供到客户端125。服务器301能够重定向客户端125时出现的Web页面仅仅是服务器111(i)上当前可获取的版本；如果重定向失败且服务器301提取版本副本223(i)，则所出现的是图4所示的Web页面401。Web页面401由重写副本224产生，并且它包括说明链接已被重写并指示登记副本223(i)的日期和时间的突出显示的图例403。

·如果用户单击“请跟踪它(Track it please)”按钮309，则服务器301产生Web页面501(图5)，其中包含URL 227或登记ID 231指定的副本223的版本列表503和与URL 227指定的副本相似的副本223的列表505。在每个列表项中，指定副本223的登记ID和登记副本223的时间；在相似的副本的列表中，每个项还包含507所示的相似度的值。在509，最后，页面指示何时执行跟踪。单击列表项使该项表示的版本副本223的重写副本224返回。

·如果用户单击“获取版本(Get that version)”按钮311，则返回的是URL 227或登记ID 231指定的版本副本223的重写副本224。显示内容与图4所示的相同。

·如果用户单击“获取它的原版(Get it in original)”按钮313，则所返回的是URL 227或登记ID 231指定的版本副本223的原始版本222。

当然该界面的许多其他版本也是可能的。在一些应用中，并非所有这些操作都是必需的。例如，如果服务器201仅仅要确保Web文档的版本始终可供获取并且自动或仅通过系统管理器来登记文档，则可能只需要获取内容操作。相似地，如果使用服务器201仅仅是为了跟踪版本并且自动或仅通过系统管理器登记版本，则可能仅需要跟踪操作。在一些实施例中，仅系统管理器将对原始副本224感兴趣，所以用户将只查看到重写副本224。在其他实施例中，界面可以提供用于其他操作的按钮，例如独立于版本跟踪操作或URL搜索操作的文档比较操作。

登记文档表215的详情

在优选实施例中，关系数据库系统中的登记文档表215中包含使登记ID 231与Web页面的原始URL 233相关的信息以及指纹处理和文档比较所需的信息。图6是表215的实体关系示意图以及它们之间的关系。图6中的虚线框表示表与图2所示的信息类型之间的关系。

由登记信息217开始，该信息包含在两个表中：PAGE_CACHE表601和REGISTERED_URL表607。REGISTERED_URL表607使登记ID 231与原始URL 233相关。表607中对应于每个登记版本副本223有一行。行中与当前论述有关的字段是包含版本副本223的原始URL 233的REG_URL字段field 233、包含版本副本223的登记ID231且对于该行是唯一关键字的REG_ID字段、以及包含表示登记版本副本223的日期和时间的数据时间戳的REGISTER_TIME字段。

PAGE_CACHE表601使登记ID 231与版本副本223相关。表601中对应于每个登记版本副本223有一行，因此对应于REGISTERED_URL表607中的每一行在表601中有一行。该行中与当前上下文有关的字段是包含版本副本的登记ID 231且对于该行是唯一关键字的REG_ID字段、CONTENT_ENCODING、CONTENT_TYPE、以及LAST_MODIFIED，它们全部包含有关版本副本223的信息，并且版本副本223的两个版本：FULL_CONTENT字段中的重写副本224和ORIG_CONTENT字段中的原始版本222。REG_ID同时出现在PAGE_CACHE和REGISTERED_URL表中进一步使原始URL与版本副本223相关。

FINGER_PRINT表609中包含指纹信息219。表609中对应于每个登记ID 231有一行，因此对应于每个版本副本223有一行。该行中的相关字段是包含版本副本233的登记ID 231且对于该行是唯一关键字的REG_ID字段、包含由版本副本的原始版本222制作的指纹的FINGER_PRINT字段、以及包含来自与REG_ID字段的值指定的版本副本223相同的Web站点且与REG_ID字段的值标识的版本副本具有实质相似性的版本副本223的列表的SIMILAR_PAGES字段。该列表对于每个版本副本包含版本副本的登记ID和指示该版本副本与该行的REG_ID字段值标识的版本副本之间的相似度的值。LAST_FUZZY_MATCH_TIME字段包含指示SIMILAR_PAGES字段中的列表被更新的最后时间的时间-日期时间戳。

REFERENCED_LINK表617和ALL_LINK表613中包含链接信息221。版本副本223中发现的每个不同的链接由唯一的链接ID值标识。ALL_LINK表613中对应于每个链接有一个行。链接的行使链接ID(在LINK_ID字段中)与原始Web页面中的绝对或相对链接指定的URL所对应的绝对URL(在LINK_URL字段中)相关。LINK_ID字段的值是该行的唯一关键字。REFERENCED_LINK表617使登记ID与该登记ID指定的版本副本223中的链接的链接ID相关。对于每个登记ID，对应于该登记ID指定的版本副本223中的每个链接有一行。REG_ID字段包含版本副本的登记ID 231，而LINK_ID字段包含REG_ID字段中的这些链接的其中之一的链接ID。通过登记ID对REFERENCED_LINK表617的查询将返回该登记ID标识的版本副本223中的链接的链接ID列表，然后可以在ALL_LINK表使用这些链接ID来获取这些链接的URL。在优选实施例中，使用链接信息221对两个版本副本233是否足够相似以保证比较它们的指纹作出阈值确定。

Web服务器201操作的详情

当结合图3-5的图形用户界面研究图6的表时，立即显见对URL登记、获取登记URL的内容、跟踪版本、获取副本223的重写副本224和获取副本223的原始版本222的操作是如何执行的。

登记

当在输入用户界面页面301的字段303中输入原始URL并且用户单击“登记URL(Register URL)”按钮305时，登记代码207获取登记的唯一登记ID 231，在PACE_CACHE表601中设置一个行且使其中的REG_ID字段的值是登记ID 231，然后将原始URL引用的内容的副本222保存在该行的ORIG_CONTENT字段。登记代码207还为CONTENT_ENCODING和CONTENT_TYPE字段提供来自副本222的相关值，并且使用链接重写代码205来重写副本222中的链接以产生副本224，然后将副本224存储在该行的FULL_CONTENT字段中。链接重写代码205还根据需要在ALL_LINK表613和REFERENCED_LINK表617中设置用于链接的行。然后登记代码在REGISTERED_URL表607中为新登记标识符和原始url设置新的行，并对该新项设置时间戳。视实施例而定，登记代码207可以在登记时间调用指纹处理代码209来进行新版本副本223的原始版本222的指纹处理或在稍后执行指纹处理。当执行它时，在FINGER_PRINT表609中为新版本副本223和指纹设置一个行。因为将新版本副本223的指纹与来自相同Web站点的所有其他版本副本223的指纹进行比较需要相当多的资源，所以通常将在稍后执行在SIMILAR_PAGES中设置列表。自动登记基本如刚才所描述的那样来工作，例外的是由Web爬行器(Web crawler)来提供原始URL。

获取内容

当用户将登记版本URL 227或登记ID 231输入到字段303并单击“获取内容(Gwt content)”按钮307时，服务器201执行版本位置代码203。使用输入的登记ID 231或来自输入的登记URL 227的登记ID 231来定位REGISTERED_URL表607中对应于该登记ID 231的行，服务器201使用REG_URL字段中的原始URL 233尝试建立与原始URL 233指定的服务器的连接。如果服务器201成功，则它将Web客户端125重定向到该服务器；否则，服务器201从PAGE_CACHE 601中该登记ID的行提取登记ID标识的版本副本的重写副本224。从REGISTERED_URL表607中该登记ID的行中的REGISTERJTIME字段获取附有重写副本224的指示403中的日期-时间输出。

跟踪具有特定原始URL的Web文档的登记版本

当用户将登记版本URL 227或登记ID 231输入到字段303并单击“请跟踪它(Track it please)”按钮309时，服务器201还执行属于版本位置代码203的一部分的代码。该代码的执行使服务器201使用与登记版本URL 227中的登记ID相关联的或REGISTERED_URL表607中的原始URL来定位REGISTERED_URL表607中所有其REG_URL字段233具有与原始URL的值相同的值的行。当然这些行对应于存储在服务器201中对应于原始URL的Web文档的版本。该代码然后使服务器201使用这些行来产生每个行的登记版本URL227，并使用登记版本URL 227在Web页面501中产生版本503的列表。

跟踪与给定登记版本相似的Web文档的登记版本

在优选实施例中，Web页面501还包括与登记版本URL 227或登记ID 231指定的登记Web文档223相似的登记Web文档223的列表505。在优选实施例中，版本位置代码203使服务器201根据登记ID的列表和表FINGER_PRINT 609中对应于登记ID 231的行中的字段SIMILAR_PAGES中的相似性值来制作列表505。

检索Web文档的特定版本副本223

当用户将登记版本URL 227或登记ID 231输入到字段303并单击“获取该版本(Get that version)”按钮311时，版本位置代码203使服务器201从来自输入的登记ID 231或来自输入的URL 227的登记ID 231所指定的PAGE_CACHE表601的行中的字段FULL_CONTENT中检索重写副本224。当用户执行相同操作并单击“获取它的原版(Get it in original)”按钮313时，版本位置代码303使服务器201从该行的字段ORIG_CONTENT检索原始副本222。

链接重写的详情

如上文所描述的，当服务器201登记Web文档时，服务器201重写该Web文档中的相对链接以产生该Web文档的重写副本224。服务器201执行以进行重写的代码是链接重写代码205，它采用如下方法来重写正在登记的Web文档中遇到的每个URL。

URL rewriteUrl(URL baseURL，URL url).

{

1.首先，基于baseURL和url构造absoluteURL。注意如果url不是相对URL，则absoluteURL将等于url。

2.其次，如果url来自HTML表单操作，例如<form action＝″...″>，则返回absoluteURL。

3.否则，构造

http://wru-server-host-and-path？gc＝l&url＝absoluteURL并返回它。注意这里构造的是包含原始URL 233但不包含登记ID 231的特定形式的登记版本URL 227。

服务器201然后将该特定形式的URL 227写入到重写副本224，以替代原始链接中的URL。当用户查看重写副本224并单击具有重写URL的链接时，服务器201接收该特定形式的登记版本URL 227，并如上文所描述的作为标准登记版本URL 227来响应：它将Web客户端125重定向到特殊URL 227中所包含的绝对URL指定的Web文档。在其他实施例中，如果该Web文档是不可获取的且在服务器201中有对应于该URL的存储副本，则服务器201可以提取该副本，并且在一些情况中可以提取其登记日期使之与包含该链接的副本最相关的副本。实际上，在一些实施例中，服务器201可以首先尝试提取相关的存储副本，而不是提取当前版本。并不使用该特定形式的URL 227来重写HTML表单操作构造<form action＝″url″>中的URL，因为它们往往是仅在过去是原始文档的源的Web服务器中可获取的一些处理逻辑的入口点。一个示例是<form action＝″login.jsp″>。为了解决此问题，仅将HTML表单操作中的URL重写为源服务器的绝对URL。

重写代码205还使服务器201只要在它遇到或设置表613中尚不存在的绝对URL时便向ALL_LINK表613中添加一行，以及只要在它遇到或设置表617中没有版本副本223的登记ID的行所对应的绝对URL且在ALL_LINK表613中遇到该绝对URL的链接ID时便在REFERENCED_LINK表617中为重写版本224属于的版本副本添加一行。

指纹处理的详情

概述

如下是用于发现相似版本副本223的登记URL的整个流程：

·使用下文解释的算法为给定登记版本URL 227表示的副本223生成指纹

·按需要在ALL_LINK表613和REFERENCED_LINK表617中设置通过链接重写执行以产生重写版本224而产生的绝对链接的行。

·假设给定副本223的原始URL 233的情况下，获取所有其原始URL 233具有与该给定副本的原始URL的主机名和端口相同的主机名107和端口的其他副本223的登记ID 231和指纹的列表。

·使用形式标准对该列表进行过滤，以快速消除与该给定副本223具有无意义的相似性的副本223。在该优选实施例中，使用REFERENCED_LINK表617中的信息来实现此操作。

·对于通过过滤的副本223，对指纹应用下文定义的模糊匹配算法。

·制作支持与该给定副本223合理相似度的副本223的登记ID231和相似度的列表。

指纹处理算法：图7和8

该部分描述优选实施例中用来根据HTML文档产生指纹的技术，可以将该指纹与使用相同技术产生的另一个指纹比较以确定制作指纹所用的HTML文档之间的相似度。之所以可以比较这些指纹来确定相似度是因为它们包含HTML文档中所含的所有结构信息的缩小表示以及HTML文档的内容的缩小表示。可以调整这里描述的用于对HTML文档进行指纹处理的技术以便在表示清楚地将文档的结构信息与文档的内容分离的任何文档表示中使用。

如图7中707所示，HTML文档可以视为树。在该树中，有两种类型的节点：节点709，表示HTML文档中的结构信息；以及节点711，包含HTML文档的实际内容。内容节点711一般包含文本。701所示的树由701所示的简单HTML文档形成。如图中703所示，结构信息由HTML标记提供。每个标记被包围在尖括号中，而内容不在其中，如图中705所示。标记一般成对出现，例如<html>、</html>，其中标记对的第一个标记指示该标记所应用的HTML文档部分的开始，而第二个标记指示结束。一对标记可以在它之间嵌套其他标记或标记对。在树707中，每个标记节点709包含来自文档701的对应标记，每个文本节点711包含对应的文本。

如果指纹要用于确定HTML文档的相似性，指纹必须捕获由它的HTML标记定义的文档结构以及它的文本或其他内容，但是还必须实质性地小于用于产生它们的HTML文档。在优选实施例中使用的技术中，通过对这些标记编码并将HTML文档中的标记置换为它们编码的版本来缩减标记的大小。为了缩减指纹中内容的大小同时保留内容的可比性，可采用多种技术：

1.使用例如MD5的消息摘要算法，由消息生成固定大小的消息摘要；

2.使用例如安全散列标准的标准散列技术对内容进行散列处理；

3.将文本置换为其一部分以及或许外加整个文本的长度。

前两种技术都是公知的。有关MD5的详情请参阅http://www.faqs.org/rfcs/rfcl321.html；有关安全散列标准的详情请参阅http://www.itl.nist.gov/fipspubs/fip180-1.htm。该优选实施例采用第三个选择。例如，我们可以选择使用第一个(或中间或最后一个)词加文本长度。我们还可以使用第一个(中间或最后一个)非空格字符加文本长度。第三个选择产生比前两个选择短的文本表示，并且需要的计算也较少；其缺点是检测到文本中改变的概率低于采用散列或摘要的技术。

在该优选实施例中，以文本的前两个非空格小写字符加文本长度信息构成的文本特征替代文本。其他实施例可以选择其他字符，其选择通常取决于语言。将长度信息按58模数化(modularize)，然后将64加模数化的结果。模数化并加64为了使长度信息由可被人可读的ASCII字符表示。注意，64是“@”的ASCII码，121是“y”的ASCII码。试探性地选择这两个数字64和58，它们应该是可调节的系统参数。其他实施例可以使用MD5或某个其他散列标准来设置文本的特征。

图8示出算法805和将该算法应用于HTML文档701所得到的指纹819。在801所示的是文档701中采用的HTML标记的编码。表801的每个行具有起始标记及其对应的结束标记的编码。由此，行803给出<HTML>和</HTML>的编码。

在805所示的是，优选实施例中采用的指纹处理算法的伪代码。在最上层，算法具有三个部分：初始化807、指纹产生循环809和在817返回指纹。初始化807将指纹变量初始化为空字符串。循环809运行直到读取并处理了整个HTML文档为止。在树707中有三种不同类型的节点：用于HTML起始标记的那些节点、用于HTML结束标记的那些节点和包含内容的那些节点。IF语句811处理HTML起始标记：它仅仅发现对应于该起始标记的编码的表单，并将该编码的表单置于指纹中；IF语句813对HTML结束标记执行相同操作。内容节点711由IF语句815来处理，它按如上所描述来操作：向指纹添加文本的前两个非空格小写字符，然后添加其值由文本长度来确定的第三个字符。

使用来自HTML文档701的上文算法生成了图8所示的指纹819。821处示出编码的<HTML>起始标记，825处示出编码的</HTML>结束标记，以及823处示出用于表征文本Hello！的字符串。依据图707的树，算法通过处理节点709(b)并将处理结果添加到指纹819、然后依此类推地处理节点709(d)、节点709(f)、节点711(a)、节点709(g)、节点709(h)、节点711(b)、节点709(i)、节点709(e)和节点709(c)来产生指纹819。

使用指纹计算HTML文档的相似性：图9

凭直觉地，给定按刚才所描述的从两个HTML文档产生的两个字符串指纹，指纹中所共有的子字符串中的字符总数越大，产生这两个指纹的HTML文档的相似度越高。

图9是基于上述直觉的算法901的伪代码。下文呈示的算法的详情取决于指纹中所用的HTML起始标记的表示，但是该算法可以容易地调整为由其他文档表示构成的指纹。该算法取一对指纹fp1和fp2作为自变量，其中fp_不长于fp2。该算法从较短的指纹(称为源指纹)开始，查找第一个“<”，它是源指纹中映射的HTML标记的定界符，从该找到的位置开始查找最长的共有子字符串，然后移到共有子字符串之后的下一个“<”，并重复该过程。该算法使用需要理解的两个函数：locate_substring()和longestSubstr()。

locate_SubString()定位下一个匹配子字符串。该函数取用三个参数。第一个参数是源指纹。第二个参数是将在源指纹中找到的子字符串。第三个参数定义源字符串中用于匹配的起始位置。例如，locateSubString(″abcabc″，″ab″，2)将返回4。如果没有发现匹配的，则locateSubString将返回0。

longestSubstr(fp1，fp2，delimPos)返回fp1中起始于位置delimPos且也是fp2中的子字符串的最长可能子字符串。例如，longestSubstr(″xyABCGGD1234″，″88890ABCGGABZGGD1234″，3)将返回“ABCGG”。

接下来详细描述，在903，初始化步骤初始化标出源字符串中的位置的两个变量：lastPos，它标出源指纹中将开始进行匹配的当前位置，以及delimPos，它标出当前“<”定界符字符在源指纹中的位置。lastPos被初始化为1，delimPos被初始化为源指纹中的第一个“<”。将这两个指纹之间的相似性(similarity)初始化为0。这两个指纹的处理在执行while循环905中执行，该循环运行直到在源指纹中找不到左尖括号“<”为止。在循环体中，执行的第一件事是开始查找fp1的在当前“<”字符开始处的部分与fp2全部之间的最长子字符串匹配(906)；如果该匹配长度大于或等于6个字符，则将该匹配的长度添加到变量similarity。将当前匹配长度或至少1添加到lastPos，并在lastPos处开始，查找下一个“<”字符，并重复循环905。当循环终止时，通过将变量similarity的当前值除以源指纹的长度来计算文档的相似性。

注意IF语句906中的数字“6”是试探性选择的。它应该属于可调的系统参数。该参数的目的在于设置所发现的共有子字符串的大小的下限。凭直觉地，如果仅发现非常短的子字符串的匹配，例如是HTML中的“<p>”的“<v”，发现此类匹配的事实表明产生指纹的HTML文档的相似性很小。作为对上面算法的可能改进，一旦定位了共有子字符串，就可以从fp2移除它，由此将不再进一步对fp2测试匹配。虽然这是有点耗时。

限制要执行的指纹比较的次数：图10

因为服务器201中有每个版本副本223的指纹，所以可以将任何版本副本的指纹819与任何其他版本副本223的指纹比较。当然大多数情况中，比较都将显示没有相似性；但是从指纹查找要求算法901的性能，其执行时间对于不相似的指纹来说比相似指纹慢。这里所需要的是一种方法以在执行指纹比较之前过滤文档对，以便仅对具有合理概率是相似的文档执行指纹比较。

在优选实施例中，使用两种分开的技术来过滤文档对。一种技术用于在FINGER_PRINT表609中给定页面的行中设置SIMILAR_PAGES列表。该列表中的页面限于来自与给定页面相同Web站点的页面。另一种技术是检查要比较相似性的版本副本223中所含的链接的不相似性。该技术基于如下观察：

·相似的HTML文档往往具有相似的链接数量，这些链接往往在两个文档中指向相同的Web站点。

·HTML文档中的链接按远比HTML文档的内容或标记变更速度慢的速度变更。

根据前述内容，如果对于由文档服务器201正在比较的一对版本副本223可以确定该文档对中的这两个文档具有数量差异很大的链接或这些链接在这两个文档对中不指向相同Web站点，则显然该对副本223是不相似的，并且无需比较它们的指纹。当然可以将这两种过滤技术组合。当然立即将显见到有关HTML文档中的链接的观察同等地适用于任何其他文档表示中的链接，以及可以将这些过滤技术与包含链接的任何类型的文档一起使用。

服务器201维护有关它需要基于REFERENCED_LINK表617中的链接不相似性来过滤的链接的信息。可以利用正在比较的副本223的登记ID查询REFERENCED_LINK表617来获取过滤操作所需的所有信息。对副本对的每个副本223的查询确定副本对中的每个版本副本223的链接的数量。查询还返回版本副本223中链接的LINK_ID值的列表，并可以比较这些值。如果两个列表中都出现相同LINK_ID值，则两个版本副本223具有至相同URL的链接。

图10示出基于链接不相似性的过滤的算法。正如根据前文论述所期望的，以两个步骤执行该算法。第一步1001确定副本对的每个版本副本包含多少链接并基于此执行过滤。linkNum1包含副本对中的第一副本223中的链接数，linkNum2包含副本对中的第二副本223中的链接数。应用两个测试1003和1005，除非副本对223通过两个测试的其中之一，否则过滤掉它。测试1003仅让组合链接数不大于7的副本对223通过。测试1005将两个文档中的链接数之差除以两个文档中的链接数之和+2，如果除法的结果小于1/3，则让该副本对通过。所用的数字7、2和0.3333也是试探性选择的。它们可以属于系统的可调节配置参数。第一条件表明如果这两个URL包含仅少量的引用链接，则应该让它通过。第二条件表明如果这两个URL的引用链接的数量之差在预定义的范围内，则过滤器应该让它通过。

第二步1007确定两个页面共有的链接的数量。totalLinksNum是副本对223的其中之一中的链接数；sameLinksNum是两个副本223中都有的链接的相同URL的数量。1015处示出通过的条件。该测试中使用的数量也是试探性选择的，它们应该是可调节的系统配置参数。该条件表明如果较之引用链接的总数，相同链接的数量合理地大，则过滤器应该让该副本对223通过。当一对副本同时通过测试1001和测试1007时，服务器201将比较该副本对的指纹。

前文“具体实施方式”为相关技术领域的技术人员描述了如何制作和使用本发明的仓库服务器，并进一步描述了发明人用于实现仓库服务器的目前已知的最佳方式。对于相关技术领域的技术人员来说，使用不同于本文所描述的优选实施例来实现本发明是显见的。例如，优选实施例在因特网和http协议提供的环境中工作，因此该优选实施例的许多细节是由环境决定的。但是有必要确保通常可经网络访问的文档的副本在它们不可经网络获取时或需要从当前可经网络访问的那些副本获取不同版本时可访问的任何场合中都可以采用本发明的原理。

在优选实施例中，使用关系数据库系统中的表来维护仓库中存储的副本之间的必要关系、副本的文档URL、标识仓库服务器中的副本的标识符、副本及其指纹、以及副本及其相似副本的列表。这些表当然可以采取非本文所公开的形式的许多形式，此外，为能够表示必要关系的数据结构以及关系表的任何安排都是有效的。本发明的给定实现可以不执行优选实施例执行的所有操作，或者可以执行优选实施例不执行的操作。当然优选实施例的用户界面由http协议的要求、优选实施例执行的操作以及发明人的喜好来决定，并且许多其他用户界面也是可能的。

利用指纹，优选实施例的许多细节作为如下事实的结果：指纹设计为根据HTML文档制作，但是本文所描述用于制作和比较指纹的技术可以容易地调整以适应具有结构性组成部分以及内容的任何形式的文档。

就所有前文原因而言，“具体实施方式”应视为在各方面均是示范性的而非限定性的，本文公开的本发明的范围不应由“具体实施方式”来决定，而是由根据专利法所允许的完整范围解释的权利要求来决定。