使用编辑距离和文档信息进行搜索结果排名

摘要

一种用于基于查询串从接收到的作为搜索结果的文档中提取文档信息并计算数据串与该查询串之间的编辑距离的体系结构。编辑距离被用来通过检测整个查询或查询的一部分的接近匹配来确定文档的相关性以作为结果排名的一部分。编辑距离评估查询串与包括诸如TAUC(标题、锚文本、URL、点击)信息等文档信息的给定数据流有多接近。该体系结构包括用于允许更高效地发现查询项的、对URL中的混合项进行的索引时间划分。另外，锚文本的索引时间过滤被用来寻找文档结果中的一个或多个的前N个锚。TAUC信息可被输入到神经网络(例如，2层)以改进用于对搜索结果进行排名的相关性度量。

说明书

背景

在典型的搜索引擎服务中，用户可以通过从URL(统一资源定位符)的索引集合中选出与查询相匹配的最相关文档来输入查询。为了快速对查询进行服务，搜索引擎利用将关键字映射到文档的一种或多种方法(例如，倒排索引数据结构)。例如，引擎所执行的第一步骤可以是标识包含用户查询所指定的关键字的候选文档的集合。这些关键字可以位于文档正文或元数据或实际上存储在其他文档或数据存储中的关于该文档的附加元数据(如锚文本)中。

在一大型索引集合中，取决于查询项的共同性，候选文档集合的基数可以很大(例如，可能有数百万)。并非返回整个候选文档集合，搜索引擎根据相关性来执行对候选文档进行排名的第二步骤。通常，搜索引擎利用排名功能来预测文档与特定查询的相关性程度。排名功能从文档取得多个特征作为输入，并且计算允许搜索引擎按照所预测的相关性对文档进行排序的数量。

排名功能相对于该功能有多准确地预测文档的相关性的质量由用户对搜索结果的满意度或用户发现所提问题的答案的平均次数来最终确定。对系统的总体用户满意度可以由单个数字(或度量)来近似，因为该数字可以通过改变排名功能来优化。通常，该度量是在通过对查询日志进行随机采样来预先选择的代表性查询集合上计算的，并且涉及向引擎对于评估查询中的每一个所返回的每一结果分配相关性标记。然而，用于文档排名和相关性的这些过程仍然不足以提供所需结果。

概述

以下提出了简化概述以便提供对在此处描述的某些新颖实施例的基本理解。本概述不是详尽的概览，它不旨在标识关键/重要的元素，也不旨在描绘其范围。其唯一的目的是以简化的形式来介绍一些概念，作为稍后提出的更详细描述的序言。

该体系结构提供用于基于查询串从作为搜索结果接收到的文档中提取文档信息并计算数据串与该查询串之间的编辑距离的机制。数据串可以是从诸如TAUC(标题、锚文本、URL(统一资源定位符)、以及点击)等文档信息获得的文档的简短且准确的描述。编辑距离被用于确定文档的相关性以作为结果排名的一部分。该机制使用一组邻近度相关特征来检测整个查询或查询的一部分的接近匹配以改进搜索结果排名的相关性。

处理编辑距离以评估查询串与包括该文档信息的给定数据流有多接近。该体系结构包括对URL中的混合项进行的索引时间划分，以用于允许更高效地发现查询项。另外，锚文本的索引时间过滤被用来寻找文档结果中的一个或多个的前N个锚。使用TAUC信息可被输入到神经网络(例如，2层)以改进用于对搜索结果进行排名的相关性度量。

为实现上述及相关目的，本文结合下面的描述和附图描述某些说明性方面。然而，这些方面仅指示了可采用此处公开的原理的各种方法中的少数几种，且旨在包括所有这些方面及等效方面。结合附图阅读下面的详细描述，则其他优点和新颖特征将变得清楚。

附图简述

图1示出计算机实现的相关性系统。

图2示出用于计算编辑距离的示例性匹配算法的流程图。

图3示出使用经修改的编辑距离和匹配算法来基于查询串和数据串处理并生成编辑距离值。

图4示出使用经修改的编辑距离和匹配算法来基于查询串和数据串处理并生成编辑距离值的另一示例。

图5示出使用神经网络来帮助生成文档的相关性分数的计算机实现的相关性系统。

图6示出可以在用于确定查询串与数据串之间的编辑距离的文档信息中使用的数据的类型。

图7示出索引时间处理数据流。

图8示出例示来自图7的索引过程的、用于结果排名的对神经网络的输入的框图。

图9示出用于计算生成搜索结果的神经网络、编辑距离输入以及原始特征输入的示例性系统实现。

图10示出确定文档结果集的文档相关性的方法。

图11示出计算文档的相关性的方法。

图12示出根据所公开的体系结构的可用于使用TAUC特征执行编辑距离处理以进行搜索结果排名的计算系统的框图。

详细描述

所公开的体系结构通过实现一组邻近度相关特征来检测整个查询的接近匹配或具有与该文档有关的准确元数据(如，标题、锚、URL、或点击)的匹配以改进搜索结果排名的相关性。例如，考虑查询“company store”、第一文档的文档标题“company store online”和第二文档的文档标题“new NEC LCD monitors in company store”。假定其它特性对第一和第二文档而言相同，则该体系结构基于为使选定流与该查询相匹配要贡献多少编辑努力来向文档分配分数。在该示例中，选择文档标题来进行评估。第一文档的标题只需要一次删除操作(删除项“online”)就能得到完全匹配，而第二文档的标题需要五次删除(删除项“new”、“NEC”、“LCD”、“monitors”以及“in”)。因此，第一文档被计算成较为相关。

标题是TAUC(标题、锚、URL以及点击)文档信息的一个元素，对于TAUC文档信息，可以对一些数据流(例如，URL)应用处理以便可以从混合项中找到查询项的。例如，再次考虑查询“company store”，并且URL是www.companystore.com。结果是该URL被分成四个部分(即，项)：“www”、“company”、“store”以及“com”。

现在参照附图，在全部附图中，相同的附图标记用于表示相同的元素。在以下描述中，为解释起见，描绘了众多具体细节以提供对本发明的全面理解。然而，显然，各新颖实施例可以在没有这些具体细节的情况下实现。在其他情况下，以框图形式示出了公知的结构和设备以便于描述它们。

图1示出计算机实现的相关性系统100。系统100包括处理组件102，用于基于查询串110从作为搜索结果108接收到的文档106中提取文档信息104。系统100还可包括邻近度组件112，用于计算从文档信息104导出的数据串116与查询串110之间的编辑距离114。编辑距离114被用于确定作为搜索结果108的一部分的文档106的相关性。

用于生成数据串116的文档信息104可包括例如标题信息(即，字符)、链接信息(例如，URL字符)、点击流信息、和/或锚文本(即，字符)。处理组件102在索引时间划分文档信息104的混合项以计算编辑距离114。处理组件102还便于在索引时间过滤诸如锚文本等文档信息以计算排名最前的一组锚文本。

对编辑距离114的计算基于用于增加数据串116与查询串110之间的邻近度(使之更近)的项插入和项删除。对编辑距离114的计算还可基于与用于增加数据串116与查询串110之间的邻近度(使之更近)项插入和项删除相关联的成本。

考虑基于向查询串110插入和/或从中删除项来生成数据串116(例如，TAUC)的情况。该项处理可以根据四个操作来执行：将非查询字插入查询串110；将查询项插入查询串110；从查询串110删除TAUC项；和/或从查询串110删除非TAUC项。

编辑距离114是基于插入和删除操作的，但不基于置换。对于插入，可以定义两种类型的成本。考虑从查询串110生成数据串116的情况。在生成时，可以将一个字插入查询串110，当该字在原始查询串110中存在时则成本被定义为1；否则成本被定义为w1(≥1)。在此，w1是所调节的加权参数。例如，如果查询串110是AB，则生成数据串ABC的成本高于数据串ABA的成本。直观上，通过将“不相关字”插入数据串116使得整个数据串116(例如，TAUC)更加不相关。

对于删除，可以定义两种类型的成本。同样，考虑从查询串110生成数据串116的情况。在删除查询串110中的项时，当该项存在于原始查询串116中时，则成本被定义为1；否则成本被定义为w2(≥1)。

另一类型的成本是位置成本。如果删除或插入发生在数据串116的第一位置处，则存在附加成本(+w3)。直观上，对在两个串(查询串110和数据串116)的开头处的匹配给出比这些串较后处的匹配更大的重要性。考虑以下示例，其中查询串110是“cnn”并且数据串116是标题＝“cnn.com-blur blur”。如果插入和删除发生在第一位置处，则可以显著地降低该解决方案的效率。

图2示出用于计算编辑距离的示例性的经修改的匹配算法200的流程图。尽管出于解释简明的目的，此处例如以流图或流程图形式示出的一个或多个方法被示出并描述为一系列动作，但是可以理解和明白，各方法不受动作的次序的限制，因为根据本发明，某些动作可以按与此处所示并描述的不同的次序和/或与其他动作同时发生。例如，本领域技术人员将会明白并理解，方法可被替换地表示为一系列相互关联的状态或事件，诸如以状态图的形式。此外，并非在一方法中示出的所有动作都是新颖实现所必需的。

在200，枚举查询串和数据(即，目标)串的各元素。这通过设查询串的程度是n(其中查询串中的每一项是s[i])并设目标(即，数据)串的程度是m(其中目标串中的每一项被表示为t[j])来实现。在202，构造包含0…m行和0…n列的矩阵(其中该矩阵中的每一项被表示为d[j，i])。在204，使用依赖于删除的不同成本的值来初始化第一行并且使用依赖于插入的不同成本的值来初始化第一列。在206，如果n＝0，则返回d[m，0]并退出，并且如果m＝0，则返回d[0，n]并退出，如在208所示。在210，检查查询串的每一字符(i从1到n)。在212，检查目标数据串的每一字符(j从1到m)。在214，如果查询串中的字符串等于数据串中的各字符，则该流程去往216，在那里成本是0并处理下一矩阵单元。换言之，如果s[i]等于t[j]，则成本是0并且d[j，i]＝d[j-1，i-1]。

如果查询串单元中的字符不等于数据串单元中的字符，则该流程从214至218，在那里将当前单元设成紧靠上方的单元或紧靠左侧的单元，加上插入或删除成本。换言之，如果s[i]不等于t[j]，则将该矩阵的单元d[j，i]设成等于紧靠上方的单元加上对应的插入成本(由d[j-1，i]+cost_insertion(插入成本)表示)或紧靠左侧的单元加上对应的删除成本(由d[j-1，i]+cost_deletion(删除成本)表示)的最小值。在220，迭代步骤210、212、214、216以及218以完成。在222，输出在单元d[m，n]中找到的最终成本。注意，在该示例中，cost_insertion和cost_deletion两者都具有两种值；例如，用于插入成本的w1＝1、w3＝4以及用于删除成本的w2＝1、w4＝26。

换言之，d[j，i]包含串s[0..i]和t[0...j]之间的编辑距离。根据定义，d[0，0]＝0(无需编辑即可使空串等于空串)。d[0，y]＝d[0，y-1]+(w2或w4).如果已知使用了多少编辑才产生了串d[0，y-1]，则d[0，y]可以计算成d[0，y-1]+从目标串删除当前字符的成本，这一成本可以是w2或w4。如果当前字符存在于s[0…n]、t[0…m]两者中，则使用成本w2；否则使用w4。d[x，0]＝d[x-1，0]+(w1或w3)。如果已知使用了多少编辑才产生了串d[x-1，0]，则d[x，0]可以计算成d[x-1，0]+从s到t插入当前字符的成本，这一成本可以是w1或w3。如果当前字符存在于s[0…n]、t[0…m]两者中，则使用成本w1；否则使用w3。

对于每一(j，i)，如果s[i]＝t[j]，则d[j，i]可以等于d[j-1，i-1]。可以计算串t[j-1]、s[i-1]之间的编辑距离，并且如果s[i]＝t[j]，则可以对这两个串附加共同字符以在不造成编辑的情况下使这些串相等。因此，使用了三个移动，其中选择提供当前d[j，i]的最小编辑距离的移动。换言之，

d[j，i]＝min(

如果s[i]＝t[j]，则d[j-1，i-1]；

d[j-1，i]+(如果s[j]存在于这两个串中，w1；否则，w3)；

d[j，i-1]+(如果t[i]存在于这两个串中，w2；否则，w4)

)

图3示出使用经修改的编辑距离和匹配算法来基于查询串和数据串处理并生成编辑距离值。该过程涉及从左至右、自顶向下、以及对角计算中的一个或多个。相对于项“C B A X”的目标数据串来处理项“A B C”查询串(其中，X表示不存在于查询串中的项)。用于计算编辑距离的过程可以用不同的方式来执行；然而，用于执行编辑距离的修改版本的具体细节在根据所公开的体系结构进行计算时是不同的。基于n×m来构造4×5矩阵300，其中对于查询串n＝3且对于数据串m＝4。查询串302沿矩阵300的水平轴放置，并且目标数据串304沿着垂直轴。

本描述将使用用四列(0-3)和五行(0-4)来表示的矩阵300。在行0列0开始，从左至右来应用图2中描述的编辑距离匹配算法，交叉单元d[0，0]接收“0”，因为查询串ABC的空单元与目标数据串CBAX的空单元的比较不造成用于使查询串与目标数据串相同的项插入或删除。“项”是相同的，所以编辑距离是0。

向右移动来将查询串302的A项与行0的空单元进行比较，使用一次删除以使这些串相同；因此，单元d[0，1]接收值“1”。再次向右移动至列2，现在进行查询串302的项AB与目标数据串列的空单元之间的比较。因此，使用查询串302中的两次删除来使这些串相同，从而使得编辑距离“2”被置于单元d[0，2]中。同样的过程应用于列3，其中将查询串302的项ABC与目标串列中的空单元相比较，使用三次删除以使得这些串相同，从而产生单元d[0，3]中的编辑距离“3”。

下降到行1并继续从左至右，将查询串行的空单元与目标数据串304的第一项C相比较。使用一次删除以使得这些串相同，其中d[1，0]中的编辑距离是“1”。向右移至列1，进行查询串302的A项与目标数据串304的C项之间的比较。使用一次删除和一次插入来使这些串相同，因此，值“2”被插入单元d[1，1]中。跳到最后单元d[1，3]，，用于将ABC与C进行匹配的匹配过程造成使用两次删除来得到单元d[1，3]中的编辑距离“2”。为简明起见，移至行4和列3并找出总体编辑距离，将项ABC与项CBAX进行匹配，造成了单元d[4，3]中的编辑距离“8”，使用目标串的第一项C中的插入/删除得到值“2”、用于B项之间的匹配的值“0”、用于第三项C和A的匹配的插入/删除得到值“2”、项X的插入得到值“1”、以及用于位置成本的值“3”，从而造成了单元d[4，3]中的最终编辑距离值“8”。

图4示出使用经修改的编辑距离和匹配算法来基于查询串和目标数据串处理并生成编辑距离值的另一示例。在此，生成矩阵400以用于基于用于插入成本的cost_insertion w1＝1，w3＝4以及用于删除成本的w2＝1以及w4＝26的权重来将查询串ABC 402与目标数据串AB 404进行比较。换言之，从左至右操作行0，将查询串402的项A与目标串404前的空单元进行匹配造成项A在目标串404中的一次插入，得到值“1”单元d[0，1]。将查询串402的项AB与目标串404前的空单元进行匹配造成项AB在目标串404中的两次插入，得到值“2”单元d[0，2]，并且将查询串402的项ABC与目标串404前的空单元进行匹配造成项AB在目标串404中的两次插入值加上项C的值w4＝26，得到单元d[0，3]中的值“28”，因为项C不在这两个串中。

从左至右操作行1(理解d[1，0]＝1)，将查询串402的项A与目标串404的项A进行匹配造成目标串404和查询串402中的等同性，得到单元d[1，1]中的值“0”，通过从d[j-1，i-1]＝d[0，0]＝“0”取得该值。将查询串402的项AB与目标串404的项A进行匹配造成项B在目标串404中的一次插入，得到最小值“1”单元d[1，2]。对于单元d[1，3]，将查询串402的项ABC与目标串404的项A进行匹配得到一最小值，该最小值关联于d[j-1，i]＝d[0，3]的值加上w3在单元d[1，3]中得到值“28”相比于d[j，i-1]＝d[1，2]的值1加上26得到27(因为项C不在这两个串中)，从而在d[1，3]中得到最小值“27”。

从左至右操作行2，将查询串402的项A与目标串404的项AB进行匹配造成目标串404中的一次删除，得到单元d[2，1]中的值“1”。对于单元d[2，2]中的距离，将查询串402的项AB与目标串404的项AB进行匹配造成等同性，从而从d[j-1，i-1]＝d[1，1]中取出值来作为单元d[2，2]的值“0”。对于单元d[2，3]，将查询串402的项ABC与目标串404的项AB进行匹配得到最小值，该最小值关联于d[j-1，i]＝d[1，3]＝27的值加上w3＝1得到值“28”(因为C不在目标串中)相比于同样基于d[i，j-1]＝d[2，2]＝0的值加上26得到26(因为C不在这两个串中)，从而得到d[2，3]中的最小值“26”。

图5示出使用神经网络502来帮助生成文档106的相关性分数504的计算机实现的相关性系统500。系统500包括用于基于查询串110从作为搜索结果108接收到的文档106提取文档信息104的处理组件102和用于计算从文档信息104导出的数据串116与查询串110之间的编辑距离114的邻近度组件112。编辑距离114被用于确定作为搜索结果108的一部分的文档106的相关性。

神经网络502可被用来接收文档信息104作为用于计算文档106的相关性分数的输入。单独地或部分地基于搜索结果108中的一些或全部的相关性分数，可以对搜索结果108中的文档进行排名。系统500使用神经网络502和代码库来生成用于搜索结果108中的相关联文档的排名的相关性分数。

以下是用于计算查询串与数据串中的每一个之间的编辑距离以获得每一对的TAUC分数的编辑距离算法的描述。

因为文档中只有一个标题，所以TAUC分数可以相对于标题如下计算：

                 TAUC(标题)＝ED(标题)

其中在应用了变换函数之后，TAUC(标题)随后用作神经网络的输入并且ED(标题)是该标题的编辑距离。

对于一文档，可以存在锚文本以及URL和点击的多个实例(其中点击是先前执行的相对于它该文档被点击的查询)。想法是这一文档对于类似查询更加相关。在索引时间，选择具有最高频率的N个锚文本。随后，为每一选定的锚计算ED分数。最后，为锚确定TAUC分数如下：

TAUC(锚)＝Min{ED(锚_i)}    i：前N个锚；

直观上，如果对于锚中的每一个都存在良好的匹配，则这是足够的。在应用了变换函数之后，TAUC(锚)被用作神经网络输入。

在计算URL串的ED之前使用特殊处理。使用一组字符作为分隔符将索引时间URL串划分成各部分。随后在每一部分中找出来自标题和锚项的字典中的项。来自字典的项的每一次出现连同以字符为单位从URL串的开头所测量的位置都被存储在索引中。

在查询时，从在索引时间存储的索引中读出查询项的所有出现，并且用“非查询”项来填充间断。在这一处理之后，计算ED。在应用了变换函数之后，ED处理的结果是神经网络输入。

可被处理的另一特性是用户对给定文档内容所输入的“点击”的数量。用户每一次点击该文档，都将一条流输入到数据库中并将该流与该文档进行关联。这一过程还可以应用于文档信息文本中的流数据，如短数据流。

索引时间URL处理算法使用一组字符作为分隔符来将整个URL划分成各部分。划分函数还将urlpart.startpos(url部分.开始位置)设成源串中的部分的位置。划分函数执行对URL的各不重要部分的过滤。

例如，“http://www.companymeeting.com/index.html”被过滤成“companymeeting/index”并被划分成“companymeeting”和“index”。

Startpos：0

Urlparts＝split(url，dictionary)

//寻找不同url部分中的项。

For each(字典中的项)

{

    Int pos＝0；

    For each(各url部分中的一url部分)

    {

        pos＝urlpart.Find(term，pos)；

        while(pos＞＝0)

        {

            //parts_separator(部分_分隔符)被用来在查询时区分不同部

分

            storeOccurrence(term，pos+urlpart.startpos*parts_separator)；

            pos＝url.Find(term，pos+term.length)；

        }

    }

    setIndexStreamLength(parts_separator*urlparts.Count)；

}

假定字典包含“company meeting comp”，则可生成以下钥匙(key)：Company：0；Meeting：7；以及Comp：0。串的总长度是parts_separator*2。

相对于ED之前的查询时间处理，在查询时间读取查询项的出现，按源URL串中的出现次序来构造查询项的串，并且用“非查询”字标记来填充各项之间的空间。例如，考虑查询串“company policy”和结果串“company”“non-query term(非查询项)”“non-query term”。

parts_separator、查询项位置、以及流长度被确定为知道原始URL串中有多少部分以及什么部分包含给定查询。不具有项的每一部分被认为包含“非查询项”。如果一部分不以查询项开始，则在该项前插入“non-query term”。查询项之间的所有空间都用“non-query term”来填充。

图6示出可以在用于确定查询串与数据串之间的编辑距离的文档信息中使用的数据的类型。文档信息104可包括供处理组件102处理以及数据(即，目标)串116的生产的TAUC数据602，例如标题文本604、锚文本606、URL 608文本或字符、以及点击信息610。文档信息104还可包括与用户点击文档内容的次数、用户(经由点击)选择的内容的类型、该内容上的点击的数量、文档总体等相关的点击信息610。

图7示出索引时间处理数据流700。在顶部，基于文档分析和提取来接收标题604、文档锚606、点击信息610等形式的文档信息。标题604通过项划分算法704来处理并随后传到字典706。字典706是在标题604、锚606、点击信息610等中找到的不同项的临时存储。字典706被用来经由URL划分算法708来划分URL 608。URL划分算法708的输出被发送到索引过程710以进行相关性和排名处理。文档锚606还可以通过管理器712来处理以得到前N个锚。点击信息610可以经由索引过程710来直接处理。可以相应地处理其他文档信息(例如，项划分、过滤，等等)。

图8示出例示来自图7的索引过程710的、用于结果排名的对神经网络的输入的框图800。索引过程710可被用于计算关于查询串110的URL编辑距离(ED)802、关于查询串110的前N个锚ED 804、关于查询串110的标题ED 806、关于查询串110的点击ED 808、以及与编辑距离不相关的其他特征810，这些(URL ED 802、前N个锚ED 804、标题ED 806、点击ED 808、以及其他特征810)中的一些或全部可以用作神经网络502的输入，最终用于找出相关联文档的相关性分数以及随后找出该文档在其他文档搜索结果之间的排名。神经网络502可以是接收至少TAUC特征作为对标识文档的相关性有贡献的输入特征的2层模型。神经网络确定如何将这些特征组合成可由搜索引擎用来进行排序的单个数字。

可以明白，神经网络502只是可用于相关性和排名处理的数学或计算模型的一个示例。可以使用其他形式的统计回归，如朴素贝叶斯、贝叶斯网络、决策树、模糊逻辑模型，并且可以使用表示不同独立性模式的其他统计分类模型，其中分类包括用于分配排名和/或优先级的各方法。

图9示出用于计算生成搜索结果的神经网络502、编辑距离输入以及原始特征输入的示例性系统900实现。关于神经网络502的输入的原始排名特征810的集合可包括BM25功能902(例如，BM25F)、点击距离904、URL深度906、文件类型908、以及语言匹配910。BM25组件可包括例如正文、标题、锚、锚文本、URL显示名称、以及所提取的标题。

图10示出确定相关性的方法。在1000，作为搜索过程的一部分来接收查询串。在1002，从在搜索过程期间返回的文档中提取文档信息。在1004，根据文档信息生成数据串。在1006，计算数据串与查询串之间的编辑距离。在1008，基于编辑距离来计算相关性分数。

该方法的其他方面可包括使用项插入来作为计算编辑距离的一部分并且评估在查询串中插入一个项以生成数据串的插入成本，该成本被表示成加权参数。该方法还包括使用项删除来作为计算编辑距离的一部分并且评估在查询串中删除一个项以生成数据串的删除成本，该成本被表示成加权参数。可以作为计算编辑距离的一部分来计算位置成本，位置成本与数据串中的项位置的项插入和/或项删除相关联。另外，在数据串的各字符与查询串的各字符之间执行匹配过程以计算用于计算编辑距离的总体成本。

划分数据串的URL的混合项可以在索引时间发生。该方法还可包括基于在文档中的出现频率来过滤数据串的锚文本以找出排名最前的一组锚文本并计算该组中的锚文本的编辑距离分数。在应用变换函数之后，从对编辑距离的计算导出的编辑距离分数可以输入到两层神经网络中，该分数是基于计算与标题信息、锚信息、点击信息、或URL信息中的至少一个相关联的编辑距离来生成的。

图11示出计算文档的相关性的方法。在1100，作为搜索过程的一部分来处理查询串以返回一组结果文档。在1102，基于从这组结果的文档中提取的文档信息生成数据串，文档信息包括来自文档的标题信息、锚文本信息、点击信息、以及URL信息中的一个或多个。在1104，基于项插入、项删除、以及项位置来计算数据串与查询串之间的编辑距离。在1106，基于编辑距离来计算相关性分数，该相关性分数用于对这组结果中的文档进行排名。

该方法还包括计算与项插入、项删除、以及项位置中的每一个相关联的成本，并将该成本包括在相关性分数的计算内，并且在索引时间划分URL信息的混合项并在索引时间基于锚文本在文档中的出现频率来过滤锚文本信息以找出排名最前的一组锚文本。可以执行查询串的各项的出现的读取以按照在源URL串中出现的次序来构造查询项的串并用字标记来填充各项之间的空间。

如在本申请中所使用的，术语“组件”和“系统”旨在表示计算机相关的实体，其可以是硬件、硬件和软件的组合、软件、或者执行中的软件。例如，组件可以是但不限于，在处理器上运行的进程、处理器、硬盘驱动器、多个(光和/或磁存储介质的)存储驱动器、对象、可执行代码、执行的线程、程序、和/或计算机。作为说明，运行在服务器上的应用程序和服务器都可以是组件。一个或多个组件可以驻留在进程和/或执行的线程内，且组件可以位于一台计算机上和/或分布在两台或更多的计算机之间。

现在参考图12，示出了根据所公开的体系结构的可用于使用TAUC特征执行编辑距离处理以进行搜索结果排名的计算系统1200的框图。为了提供用于其各方面的附加上下文，图12及以下讨论旨在提供对其中可实现该各方面的合适的计算系统1200的简要概括描述。尽管以上描述是在可在一个或多个计算机上运行的计算机可执行指令的一般上下文中进行的，但是本领域的技术人员将认识到，新颖实施例也可结合其他程序模块和/或作为硬件和软件的组合来实现。

一般而言，程序模块包括执行特定任务或实现特定抽象数据类型的例程、程序、组件、数据结构等等。此外，本领域的技术人员可以理解，本发明的方法可用其他计算机系统配置来实施，包括单处理器或多处理器计算机系统、小型计算机、大型计算机、以及个人计算机、手持式计算设备、基于微处理器的或可编程消费电子产品等，其每一个都可操作上耦合到一个或多个相关联的设备。

所示各方面也可以在其中某些任务由通过通信网络链接的远程处理设备来执行的分布式计算环境中实施。在分布式计算环境中，程序模块可以位于本地和远程存储器存储设备中。

计算机通常包括各种计算机可读介质。计算机可读介质可以是可由计算机访问的任何可用介质，且包括易失性和非易失性介质、可移动和不可移动介质。作为示例而非限制，计算机可读介质可以包括计算机存储介质和通信介质。计算机存储介质包括以存储如计算机可读指令、数据结构、程序模块或其他数据等信息的任何方法或技术来实现的易失性和非易失性、可移动和不可移动介质。计算机存储介质包括但不限于RAM、ROM、EEPROM、闪存或者其他存储器技术、CD-ROM、数字视频盘(DVD)或其他光盘存储、磁带盒、磁带、磁盘存储或其他磁存储设备、或可以用于存储所需信息并且可以由计算机访问的任何其他介质。

再次参考图12，用于实现各方面的示例性计算系统1200包括具有处理单元1204、系统存储器1206和系统总线1208的计算机1202。系统总线1208向包括但不限于系统存储器1206的各系统组件提供到处理单元1204的接口。处理单元1204可以是市场上可购买到的各种处理器中的任意一种。双微处理器和其他多处理器体系结构也可用作处理单元1204。

系统总线1208可以是若干种总线结构中的任一种，这些总线结构还可互连到存储器总线(带有或没有存储器控制器)、外围总线、以及使用各类市场上可购买到的总线体系结构中的任一种的局部总线。系统存储器1206可包括非易失性存储器(NON-VOL)1210和/或易失性存储器1212(例如，随机存取存储器(RAM))。基本输入/输出系统(BIOS)可被存储在非易失性存储器1210(例如，ROM、EPROM、EEPROM等)中，其中BIOS是帮助诸如在启动期间在计算机1202内的元件之间传输信息的基本例程。易失性存储器1212还可包括诸如静态RAM等高速RAM来用于高速缓存数据。

计算机1202还包括内置硬盘驱动器(HDD)1214(例如，EIDE、SATA)，该内置HDD 1214还可被配置成在合适的机壳中外部使用；磁软盘驱动器(FDD)1216(例如，从可移动磁盘1218中读取或向其写入)；以及光盘驱动器1220(例如，从CD-ROM盘1222中读取，或从诸如DVD等其他高容量光学介质中读取或向其写入)。HDD 1214、FDD 1216、以及光盘驱动器1220可分别由HDD接口1224、FDD接口1226和光盘驱动器接口1228连接到系统总线1208。用于外置驱动器实现的HDD接口1224可包括通用串行总线(USB)和IEEE 1394接口技术中的至少一种或两者。

驱动器及相关联的计算机可读介质提供了对数据、数据结构、计算机可执行指令等的非易失性存储。对于计算机1202，驱动器和介质容纳适当的数字格式的任何数据的存储。尽管以上对计算机可读介质的描述涉及HDD、可移动磁盘(例如FDD)以及诸如CD或DVD等可移动光学介质，但是本领域的技术人员应当理解，示例性操作环境中也可使用可由计算机读取的任何其他类型的介质，诸如zip驱动器、磁带盒、闪存卡、盒式磁带等等，并且任何这样的介质可包含用于执行所公开的体系结构的新颖方法的计算机可执行指令。

多个程序模块可被存储在驱动器和易失性存储器1212中，包括操作系统1230、一个或多个应用程序1232、其他程序模块1234和程序数据1236。一个或多个应用程序132、其他程序模块1234、以及查询时间1236可包括系统100和相关联的各框、系统500及相关联的各框、文档信息104、TAUC数据602、点击信息610、数据流700(以及算法)、以及框图800(及相关联的各框)。

操作系统、应用程序、模块和/或数据的全部或部分也可被高速缓存在易失性存储器1212中。应该明白，所公开的体系结构可以用市场上可购得的各种操作系统或操作系统的组合来实现。

用户可以通过一个或多个有线/无线输入设备，例如键盘1238和诸如鼠标1240等定点设备将命令和信息输入到计算机1202中。其他输入设备(未示出)可包括话筒、IR遥控器、操纵杆、游戏手柄、指示笔、触摸屏等等。这些和其他输入设备通常通过耦合到系统总线1208的输入设备接口1242连接到处理单元1204，但也可通过诸如并行端口、IEEE 1394串行端口、游戏端口、USB端口、IR接口等其他接口连接。

监视器1244或其他类型的显示设备也经由诸如视频适配器1246等接口连接到系统总线1208。除了监视器1244之外，计算机通常包括诸如扬声器、打印机等其他外围输出设备(未示出)。

计算机1202可使用经由有线和/或无线通信至诸如远程计算机1248等的一个或多个远程计算机的逻辑连接在网络化环境中操作。远程计算机1248可以是工作站、服务器计算机、路由器、个人计算机、便携式计算机、基于微处理器的娱乐设备、对等设备或其他常见的网络节点，并且通常包括相对于计算机1202描述的许多或所有元件，但为简明起见仅示出了存储器/存储设备1250。所描绘的逻辑连接包括到局域网(LAN)1252和/或例如广域网(WAN)1254等更大的网络的有线/无线连接。这一LAN和WAN连网环境常见于办公室和公司，并且方便了诸如内联网等企业范围计算机网络，所有这些都可连接到例如因特网等全球通信网络。

当在LAN连网环境中使用时，计算机1202通过有线和/或无线通信网络接口或适配器1256连接到LAN 1252。适配器1256可以方便到LAN 1252的有线和/或无线通信，并且还可包括其上设置的用于使用适配器1256的无线功能进行通信的无线接入点。

当在WAN联网环境中使用时，计算机1202可包括调制解调器1258，或连接到WAN 1254上的通信服务器，或具有用于诸如通过因特网等通过WAN 1254建立通信的其他装置。或为内置或为外置以及有线和/或无线设备的调制解调器1258经由输入设备接口1242连接到系统总线1208。在联网环境中，相对于计算机1202所描绘的程序模块或其部分可以存储在远程存储器/存储设备1250中。应该理解，所示网络连接是示例性的，并且可以使用在计算机之间建立通信链接的其他手段。

计算机1202可操作来使用IEEE 802标准家族来与有线和无线设备或实体进行通信，这些实体例如是在操作上安置成与例如打印机、扫描仪、台式和/或便携式计算机、个人数字助理(PDA)、通信卫星、任何一件与无线可检测标签相关联的设备或位置(例如，电话亭、报亭、休息室)以及电话进行无线通信(例如，IEEE 802.11空中调制技术)的无线设备。这至少包括Wi-Fi(即无线保真)、WiMax和蓝牙^TM无线技术。由此，通信可以如对于常规网络那样是预定义结构，或者仅仅是至少两个设备之间的自组织(ad hoc)通信。Wi-Fi网络使用称为IEEE 802.11x(a、b、g等等)的无线电技术来提供安全、可靠、快速的无线连接。Wi-Fi网络可用于将计算机彼此连接、连接到因特网以及连接到有线网络(使用IEEE 802.3相关介质和功能)。

上面描述的包括所公开的体系结构的各示例。当然，描述每一个可以想到的组件和/或方法的组合是不可能的，但本领域内的普通技术人员应该认识到，许多其他组合和排列都是可能的。因此，该新颖体系结构旨在涵盖所有这些落入所附权利要求书的精神和范围内的更改、修改和变化。此外，就在说明书或权利要求书中使用术语“包括”而言，这一术语旨在以与术语“包含”在被用作权利要求书中的过渡词时所解释的相似的方式为包含性的。