具有表意文字和音标字符的语言的自动输入完成的方法和系统

摘要

当用户在文本输入框(例如浏览器或工具条)中输入文本时，包括表意文字串的排序预测输入完成字符串集被呈现给用户。用户输入的文本可包括零个或多个表意文字跟随一个或多个音标字符，或者输入的文本可以是一个或多个。预测完成的字符串可以是URL或查询字符串。排序可以基于任意数量的因素(例如用户群体所提交查询的频率)。URL可基于URL的重要性值来分级。可通过将用户输入字符串的指纹与包含该排序预测输入完成字符串集的指纹-表映射进行匹配来获得排序预测完成字符串的集。排序预测的字符串的产生考虑了某个表意文字串的多种语音表示。

权利要求

1.一种用于为具有表意文字和音标字符的语言建议查询输入完成的方法，包括：从搜索请求者接收部分查询，该部分查询包括一个或多个表意文字，所述一个或多个表意文字跟随有至少一个音标字符，其中所述至少一个音标字符是表意文字的部分音标字符输入；

根据所述一个或多个表意文字和所述至少一个音标字符，从用户群体提交的各查询获取对应于该部分查询的预测完整查询集，该预测完整查询集依照分级标准排序，该集包含表意文字；以及将该排序的预测查询集传送给该搜索请求者。

2.如权利要求1所述的方法，其中所述预测包括预测与所述部分音标字符输入相一致的至少一个或多个表意文字。

3.如权利要求1所述的方法，还包括根据用户群体提交的查询来建立预测查询集。

4.如权利要求1所述的方法，其中所述预测查询集包括至少一个不是由该搜索请求者以前提交的查询。

5.如权利要求1所述的方法，其中所述集包括搜索查询和至少一个URL。

6.如权利要求1所述的方法，其中所述预测包括识别两个或多个对应于该部分查询的集并且合并这些集。

7.如权利要求6所述的方法，还包括以交织方式合并所述的各集。

8.如权利要求6所述的方法，其中所述各集的至少第一集在客户机上产生，以及所述各集的第二集在服务器上产生。

9.如权利要求1所述的方法，包括：

接收输入，该输入用于标识从所述排序的预测查询集中选择的查询；以及产生与所接收查询相关的搜索结果。

10.如权利要求1所述的方法，包括产生与至少一个预测查询相关的搜索结果，以及将所述搜索结果传送到该请求者。

11.如权利要求1所述的方法，还包括：

从所接收的查询信息中确定相关查询信息；

识别与该相关查询信息相关的至少一个预测查询；以及把与该相关查询信息相关的所述至少一个预测查询包含在子集中。

12.如权利要求1所述的方法，其中所述预测包括依照预测查询的时间/日期值排序所述各预测查询。

13.如权利要求1所述的方法，还包括基于与用户相关的特性来修改所述集。

14.如权利要求1所述的方法，还包括：

判定在预定时段内没有从该搜索请求者接收到对应于所传送的该集中查询的选择；以及将根据分级标准排序的随后的预测查询集传输给该搜索请求者。

15.如权利要求1所述的方法，还包括：

从所述搜索请求者接收对于随后的预测查询集的请求；

识别随后的预测查询集；以及

将根据分级标准排序的随后的预测查询集传输给该搜索请求者。

16.如权利要求2所述的方法，包括：

在接收所述部分查询之前：

识别由用户群体先前提交的历史查询集，该历史查询集中的每个查询包括提交频率并包括至少一个表意文字；以及根据识别的历史查询集产生多个排序子集，每个排序子集包括来自依照相应提交频率排序的所识别的历史查询集中的一个或多个历史查询。

17.如权利要求16所述的方法，其中所述产生包括：将来自多个历史查询的一个或多个表意文字的字符串映射到一个或多个表示，所述表示包括一个或多个音标字符的字符串。

18.如权利要求16所述的方法，其中所述产生包括将来自多个历史查询的一个或多个表意文字的字符串映射到一个或多个表示，其中至少一个映射包括至少一个表意文字和一个或多个音标字符的字符串。

19.如权利要求1所述的方法，包括：

识别由用户群体先前提交的历史查询集，该历史查询集中的每个查询具有提交频率并包括至少一个表意文字；以及从识别的历史查询集中产生多个排序子集，每个排序子集包括依照相应提交频率排序的来自所识别的历史查询集中的一个或多个历史查询。

20.如权利要求19所述的方法，其中所述产生包括将来自多个历史查询的一个或多个表意文字的字符串映射到包括一个或多个音标字符的字符串的一个或多个表示。

21.如权利要求1所述的方法，包括：

在接收所述部分查询之前：

识别多个集，每个集与一个部分查询单元相关，并且包括用户群体先前提交的多个查询，每个查询具有相应的分级值；

对于所述多个集的至少一部分，根据相应分级值来排序所述集中的查询；以及其中所述预测包括从所述多个集中识别第一集，其中所选择的集对应于该部分查询。

22.如权利要求21所述的方法，其中所述预测包括识别第二集并合并所述第一集和所述第二集。

23.如权利要求22所述的方法，其中所述预测还包括：从第一存储器中识别所述第一集；以及

从第二存储器中识别所述第二集。

24.一种用于为具有表意文字和音标字符的语言建议查询输入完成的系统，包括：一个或多个处理器；以及

存储器，用于存储由所述一个或多个处理器执行的一个或多个程序，该系统还包括：查询处理模块，用于从搜索请求者接收部分查询，该部分查询包括一个或多个表意文字，所述一个或多个表意文字跟随有至少一个音标字符，其中所述至少一个音标字符是表意文字的部分音标字符输入；

预测模块，用于根据所述一个或多个表意文字和所述至少一个音标字符从用户群体提交的查询中获取对应于该部分查询的预测完整查询集，该预测完整查询集依照分级标准排序，该集包含表意文字；以及通信模块，用于将该排序的预测查询集传送到该搜索请求者。

25.如权利要求24所述的系统，其中所述预测查询集中的至少一个预测查询包括与所述部分音标字符输入相一致的至少一个或多个表意文字。

26.如权利要求24所述的系统，其中所述预测查询集根据由用户群体提交的查询来建立。

27.如权利要求24所述的系统，其中该预测查询集包括至少一个不是由该搜索请求者以前提交的查询。

28.如权利要求24所述的系统，其中该预测查询集包括搜索查询和至少一个URL。

29.如权利要求24所述的系统，还包括根据分级标准排序的至少第二个预测查询集，该第二集包含具有一个或多个表意文字的字符串的至少一个查询，以及所述预测模块还配置为至少识别所述的预测查询的第一集和第二集并且合并该两个集。

30.如权利要求29所述的系统，其中所述预测模块还配置为按交织方式合并所述第一集和第二集。

31.如权利要求29所述的系统，其中所述第一集位于所述第二集的远程位置。

32.如权利要求24所述的系统，还包括：用于接收输入的接收模块，该输入用于识别从该排序预测查询集中选择的查询；以及查询服务器，用于产生与所接收查询相关的搜索结果。

33.如权利要求24所述的系统，其中所述查询服务器进一步配置成用于产生与至少一个预测查询相关的搜索结果，并且将所述搜索结果传送给该请求者。

34.如权利要求24所述的系统，还包括：概念模块，用于根据所接收的查询信息来确定相关查询信息；以及子集，包括与该相关查询信息相关的至少一个预测查询。

35.如权利要求24所述的系统，其中所述预测模块还被配置为根据预测查询的时间/日期值来排序所述预测查询。

36.如权利要求24所述的系统，还包括基于与用户相关的特性修改所述集。

37.如权利要求24所述的系统，其中预测模块还配置为：将所述集传送给该搜索请求者；

从该搜索请求者接收对于随后的预测查询集的请求；

识别随后的预测查询集；以及

将根据分级标准排序的该随后的预测查询集传输给搜索请求者。

38.如权利要求24所述的系统，其中所述预测模块还被配置为：在接收所述部分查询之前：

识别由用户群体先前提交的历史查询集，该历史查询集中的每个查询具有提交频率并包括至少一个表意文字；以及从所识别历史查询集产生多个排序子集，每个排序子集包括来自根据相应提交频率排序的所识别历史查询集中的一个或多个历史查询。

39.如权利要求38所述的系统，其中所述预测模块还被配置为：将来自多个历史查询的一个或多个表意文字的字符串映射到包括一个或多个音标字符的字符串的一个或多个表示。

40.如权利要求38所述的系统，其中所述预测模块还被配置为将来自多个历史查询的一个或多个表意文字的字符串映射到一个或个表示，其中至少一个映射包括至少一个表意文字和一个或多个音标字符的字符串。

41.如权利要求24所述的系统，其中所述预测模块还被配置成：识别由用户群体先前提交的历史查询集，该历史查询集中的每个查询具有提交频率并包括至少一个表意文字；以及从所识别的历史查询集中产生多个排序子集，每个排序子集包括来自根据相应提交频率排序的所识别的历史查询集中的一个或多个历史查询。

42.如权利要求41所述的系统，其中所述预测模块还被配置为将来自多个历史查询的一个或多个表意文字的字符串映射到包括一个或多个音标字符的字符串的一个或多个表示。

43.如权利要求24所述的系统，其中所述预测模块还被配置成：在接收所述部分查询之前：

识别多个集，每个集与某个部分查询单元相关，并且包括用户群体先前提交的多个查询，每个查询具有相应的分级值；

对于所述多个集的至少一部分，根据相应的分级值排序集中的查询；以及从所述多个集中预测第一集，其中所选择的集对应于所述部分查询。

44.如权利要求43所述的系统，其中所述预测模块还被配置为用于预测第二集，且合并所述第一集和第二集。

45.如权利要求44所述的系统，其中所述预测模块还被配置为：从第一存储器中识别所述第一集；以及

从第二存储器中识别所述第二集。

说明书

具有表意文字和音标字符的语言的自动输入完成的方法和

系统

技术领域

[0001] 本发明一般地涉及用于在计算机网络(例如计算机系统的分布式系统)中定位文档的搜索引擎的领域，以及特别涉及通过在包括非音标字符的语言中预测用户查询来加速期望搜索的系统和方法。

背景技术

[0002] 搜索引擎提供了一种强有力的工具，可在大的文档数据库、比如万维网(WWW)的文档或存储在企业内部网的各计算机中的文档中定位某些文档。响应于用户所提交的搜索查询来进行定位这些文档。一个搜索查询可包括一个或多个搜索词项(search term)。

[0003] 在一种输入查询的方式中，用户通过添加相继的搜索词项直到输入所有搜索词项来输入查询。一旦用户明确表示已经输入了该查询的所有搜索词项，该查询就被发送给搜索引擎。用户可通过可替换的方法，例如通过按下键盘上的回车键或点击图形用户界面上的“搜索”按钮来输入回车字符，从而告知查询输入完成。一旦查询被搜索引擎接收，搜索引擎处理该搜索查询，响应于该搜索查询来搜索文档，并且将文档列表返回给用户。

[0004] 在主要不是基于字母书写系统的语言中，通常要从键盘输入字符序列来建立查询的语言成分。按这种方式输入查询是非常耗时间的。

[0005] 因为典型情况下直到用户已经告知查询输入完成时，该查询才被发送到搜索引擎，在用户完成整个搜索查询输入的时候，时间在流逝。因此需要一种加速该过程的系统和方法。

发明内容

[0006] 在一个实施例中，一种为具有表意文字和音标字符的语言建议查询输入完成的方法包括从搜索查询者接收部分查询。该部分查询是完整查询的一部分。预测查询集被预测，其包括至少一个字符串，所述字符串具有根据一种分级标准来排序的一个或多个表意文字。该经排序的预测查询集被传送到搜索查询者。

[0007] 搜索查询者可从该排序的预测查询集中选择相应的查询并随后指示查询输入完成。搜索引擎处理该查询来产生一组搜索结果。作为替换，搜索查询者可继续输入查询信息直到输入了完整查询，或者直到新的预测查询集被传输并提供给搜索查询者。

附图说明

[0008] 本发明的上述实施例和其它实施例将通过对本发明结合附图的以下各个方面的详细描述的变得清楚易懂。在所有附图中对相应的部分采用相同的附图标记。其中：

[0009] 图1描述了根据本发明一些实施例用于预测查询的过程；

[0010] 图2描述了根据本发明一些实施例的搜索系统的框图；

[0011] 图3描述了根据本发明一些实施例的搜索助手中的过程；

[0012] 图4描述了根据本发明一些实施例用于接收查询输入和建立对该查询的响应的过程；

[0013] 图5描述了根据本发明一些实施例的与建立和使用指纹-表映射相关联的信息流图；

[0014] 图6描述了根据本发明一些实施例的输入字符串的相关性的例子；

[0015] 图7描述了根据本发明一些实施例用于处理历史查询的过程；

[0016] 图8描述了根据本发明一些实施例用于处理历史查询的示例表的一部分；

[0017] 图9描述了根据本发明一些实施例的与使用后缀的查询完成表相关联的数据结构；

[0018] 图10描述了根据本发明一些实施例的示例查询完成表的一部分；

[0019] 图11描述了根据本发明一些实施例的示例屏幕快照；

[0020] 图12描述了适用于实施本发明一些实施例的搜索引擎；

[0021] 图13描述了适用于实施本发明一些实施例的客户机；

[0022] 图14描述了根据本发明一些实施例的用于处理包括表意文字和音标字符的历史查询的过程；

[0023] 图15描述了根据本发明一些实施例的用于所选择表意文字的多个音标表示；

[0024] 图16描述了根据本发明一些实施例的包括音标字符和表意文字的示例查询完成表的一部分。

具体实施方式

[0025] 在本发明的一个实施例中，在用户完成输入完整查询之前，用户查询的一部分被传输给搜索引擎。搜索引擎使用所传输的部分查询来预测用户的最终查询。这些预测被传送给用户。如果其中一个预测是用户想要的查询，那么用户可选择该预测的查询，而无需继续完成查询的输入。在一些实施例中，所选择的查询被传输到搜索引擎，搜索引擎返回与所选择查询相对应的一组查询结果。

[0026] 图1说明了包括客户机系统104和搜索引擎106的本发明的一个示例实施例。当用户输入搜索查询时，用户的输入被客户机系统监视(108)。在用户通知搜索查询输入完成之前，用户查询的一部分从客户机系统104被发送到搜索引擎106(110)。该部分查询可以是少量字符、搜索词项或不止一个搜索词项。在一些实施例中，部分输入是采用内容定位标识符的形式，通常被称为统一资源定位符(URL)，比如在由因特网工程特别工作组(Internet Engineering Task Force)发布的RFC 1738中所描述的，可被用于在计算机和计算机网络中识别资源。URL还可被用于识别在计算机上本地可用的资源，比如文档、文件夹或服务。在此使用的术语“URL”意味着任一形式的内容定位标识符，包括但是不限于因特网地址、符合RFC 1738的地址以及文件路径名比如在很多计算机系统和局域网中使用的。搜索引擎108接收部分查询来处理(112)并且对用户想要的完整查询进行预测(或URL)(114)。根据一个分级标准来排序预测。例如，在一些实施例中具有较高提交频率的查询被排在具有较低提交频率的查询之前。搜索引擎106使用多个查询完成表(将在以下详细描述)来协助得到排序的预测。使用搜索引擎106所接收的以前输入的搜索查询来建立查询完成表。在一些实施例中，以前的查询包括来自用户群体的搜索查询。预测的查询被发送回到客户机系统106(116)并且随后呈现给用户(118)。如果其中一个预测查询是用户想要的查询，用户可选择该预测查询并继续，而不必完成输入该想要的查询。如果预测查询没有反映出用户所想，那么用户可接着输入想要的搜索查询。

[0027] 图2说明了根据本发明一些实施例的搜索系统200并且示出了各个功能组件，在下面的详细讨论中将参考图中内容。搜索系统200可包括一个或多个客户机系统202。每个客户机系统202具有搜索助手204。客户机系统202被连接到通信网络206。通信网络206将客户机器系统202连接到搜索引擎208。搜索引擎208包括连接到通信网络206的查询服务器210、预测服务器212和查询处理控制器214。

[0028] 查询服务器210包括客户机通信模块216、查询接收、处理和响应模块218、部分查询接收、处理和响应模块220、用户信息处理模块222和查询日志224，它们都彼此相连。在一些实施例中，更少和/或另外的模块和功能被包括在查询服务器210中。图2所示的作为查询服务器210一部分的模块表示在示例实施例中执行的功能。预测服务器212与部分查询接收、处理和响应模块220、排序集建立器242和查询日志224相连接。排序集建立器242根据查询日志和URL请求来建立多个排序的预测查询集，并且与查询日志224连接。在一些实施例中，排序集建立器242还与URL数据库225耦合，并且在一些实施例中它还与语言词典244耦合。语言词典244可提供关于某些语言成分的信息，比如用于各种字符语言成分的音标表示，并提供相关单词和概念给查询或查询词项。在一些实施例中，排序集建立器242和语言词典244是预测服务器212的一部分。在这种实施例中，预测服务器212直接与查询日志224和URL数据库225相连。

[0029] 查询处理控制器214与倒排文档索引228、文本数据库230、查询缓存232和URL数据库225相连。缓存232可包括索引234，其功能是在缓存结果236中定位条目。缓存结果236可包括用于已识别查询238的缓存条目以及用于预期查询240的缓存条目。倒排文档索引228和文档数据库230有时被共同称为文档数据库。在一些实施例中，“搜索文档数据库”意味着搜索倒排文档索引228来识别与特定搜索查询或词项匹配的文档。

[0030] 尽管在图中示出的是离散的模块，图2的目的在于作为本发明实施例的功能描述而不是功能部件的结构映射。本领域技术人员将认识到实际实施方式会将多个功能聚集或将多个部件分开。例如，查询日志224可以与查询服务器210分离。在一些实施例中查询日志224可存储在其主要功能是存储和处理查询日志信息的一个或多个服务器中。类似的，URL数据库225可以被存储在其主要目的是存储和处理有关已知URL的信息的一个或多个服务器上。

[0031] 图3说明了将被实施在客户机系统202(图2)的搜索助手204中的本发明的实施例。搜索助手204监视在客户机系统104上的搜索查询的用户输入(302)。在一些实施例中，搜索助手204监视统一资源定位符(URL)输入字符串的用户输入，比如在浏览器窗口的地址栏中。用户可通过多种方式包括浏览器窗口、搜索工具或任何其它输入机构来输入搜索查询或URL。搜索助手204可识别两个不同情景。首先，当用户已经指示输入字符串完成或选择了一个所提供的预测时，搜索助手204接收或识别最终输入(302-最终输入)。第二，当在用户指示输入字符串完成之前输入被识别时(如下所述)，搜索助手204接收或识别部分输入(302-部分输入)。在第三中可选的场景中(将在以下更详细描述)，搜索助手204在一个规定时间段内确定或接收用户没有选择预测之一的通知。

[0032] 当最终输入或选择(302-最终输入)被识别为搜索查询时，输入被传输到搜索引擎208(304)用于处理。搜索引擎208返回一组搜索结果，其由搜索助手204或客户机应用程序比如浏览器应用程序接收(306)。搜索结果的列表被呈现给用户使得用户可选择一个文档用于进一步的检查(例如视觉的或听觉的)。当最终输入是URL时，请求被传输到适当的文档主机(304)，并且如果可用的话，文档被返回(306)。在接收响应之后(306)，用户的输入活动再次被监视(302)。在一些实施例中，URL请求被发送到搜索引擎208用于记录到日志，并且该请求被重新定向到合适的文档主机。

[0033] 最终输入可由搜索助手204通过多种方式来识别，比如当用户输入回车或等同字符、在搜索查询的输入期间在呈现给用户的图形用户界面(GUI)上选择搜索按钮、或可能在搜索查询的输入期间从呈现给用户的可能查询集中选择一个。本领域技术人员将认识到有多种方式来通知搜索查询的最终输入。

[0034] 在用户通知最终输入之前，可识别部分输入(302-部分输入)。部分输入可通过多种方式识别。对于搜索查询，部分输入包括搜索查询的单个搜索词项、多个搜索词项或搜索词项的预定数量的字符。

[0035] 在一些实施例中，可通过检测分隔符或其它字符的输入(例如但不限于引号、句号、括号、斜杠、箭头按键检测或tab输入)来识别部分输入。分隔字符的输入可指示用户已经完成了想要词项或输入一部分的输入，并且将进行到下一个搜索词项或部分。

[0036] 在一些实施例中，可通过检测预定数量字符的条目来识别部分输入。在这些实施例中，输入包含若干字符，虽然少于全部输入但是仍然可以用于在用户输入全部字符之前识别部分输入。在例如当搜索词项或URL包含大量字符或者当预定数量的字符足够大能形成有用的预测时，希望采用这种技术。

[0037] 在一些实施例中，可通过在一段时间内检测输入字符的不出现来识别部分输入，不出现表示用户的停顿。停顿意味着用户已经输入一个搜索词项或整个字符串的部分但是没有输入空格键(或其它分隔字符)来开始输入另一个词项，或者意味着搜索查询实际上是完整的但是用户还没有发出通知。

[0038] 不管部分输入是通过什么方式来识别，其被传输到搜索引擎208(308)用于处理。响应于部分搜索查询，搜索引擎208返回排序的预测搜索查询和/或URL(310)的集合，根据某种分级标准排序并呈现给用户(312)。预测可以通过多种方式显示给用户。例如，预测可以在下拉窗口、持久或非持久窗口或其它方式显示。在一些实施例中，用户先前提交的查询可以被可视地指示给用户(例如通过高亮显示用户自己先前输入的查询)。

[0039] 在一些实施例中，预测的搜索请求根据用户群体的提交频率来排序。在一些实施例中，搜索查询至少部分地根据查询被提交的最晚时间/日期值来排序。在一些实施例中，搜索查询根据个人信息比如用户个人信息或群体信息来排序。例如用户个人信息可包括关于用户感兴趣的信息的主题、概念或类型信息。用户个人信息可由用户直接提供，或可从在用户许可时从用户先前的搜索或浏览活动中推断，或可至少部分基于关于与用户相关联或用户所属(例如作为成员或雇员)的组群的信息。该预测搜索查询集可最初根据第一分级标准比如预定通行标准来最初排序，并且随后如果任何一个预测搜索查询与用户的用户个人信息匹配时重新排序，从而将匹配的预测搜索查询置于或更接近排序预测搜索查询集的顶部。

[0040] 本领域技术人员将认识到可有多种方式将预测搜索查询和/或URL呈现给用户。例如，预测搜索查询和/或URL可被呈现在下拉菜单中。不管预测查询和/或URL是通过何种方式呈现给用户，如果用户确定预测之一与想要的输入匹配时，用户可选择查询和/或URL之一。在一些例子中，预测可将用户没有考虑的附加信息提供给用户。例如，用户在脑子里有一个查询作为搜索策略的一部分，但是通过查看预测结果可使得用户改变输入策略。
一旦该预测集被呈现(312)，用户的输入再次被监视。如果用户选择了预测之一(302-最终)，该请求被作为搜索请求传输到搜索引擎208或如果可用，作为URL请求传输到资源主机(304)。在该请求被传输之后，用户的输入活动被再次监视(302)。如上所述，在一些实施例中，URL请求被传输到搜索引擎208用于日志目的。

[0041] 另一方面，如果用户在一个特定时间段内没有选择预测之一，那么有可能用户在最初返回的预测中没有找到满意的预测。例如，用户想要的输入没有足够高的分级值，因此没有被包括在该排序的预测集中。这样，在一些优选实施例中，如果用户在一个特定时间段(例如5或10秒)内没有选择预测之一(302-到期)，那么请求被发送到搜索引擎208用于另一预测集(318)。随后该预测集可包括具有比先前提交的那个集更低的分级值。可替换的，第二组标准可被用于在第二集中识别预测，其中第二组标准不同于被用于选择和分级第一预测集的第一组标准。例如，两组之一可使用考虑有关请求者个人信息的选择标准，而另一组不考虑。在一些优选实施例中，其它触发器可被用于请求一组或多组随后的预测。例如，用户发起的活动(例如按下“tab”键、箭头键、功能键等)可引起对于后续集的请求。
在一些实施例中，与搜索请求者相关联的信息被保持在服务器中用于识别哪些预测结果已经被传送到搜索请求者。在一些实施例中，客户机可在请求中包括对于随后请求的信息，其指示哪些结果已经被传送到搜索请求者。在一个这种实施例中预测服务器212使用该信息从随后预测的结果中排除所有先前预测的结果或者先前预测结果的子集。在另一种实施例中，只要预测服务器212能够识别与请求者的部分请求匹配的附加预测结果，关于先前预测结果的信息被预测服务器212用来产生另外的或不同的结果。在一些实施例中，触发随后一个预测集使得使用搜索请求者的查询作出的预测被本地存储，而在其它实施例中随后一个预测集包括基于用户群体的历史查询产生的预测，以及如果有的话，则包括与请求者的部分查询匹配的搜索请求者的历史搜索查询。

[0042] 在一些实施例中，一个或多个预测结果集在客户机本地缓存。当搜索请求者修改当前查询来反映较早的部分输入(例如通过后退键(backspace)来删除一些字符)，与较早部分输入相关联的该预测集结果从客户机缓存中被重新获得，并且代替被发送到搜索引擎的部分输入被再次呈现给用户。

[0043] 在一些实施例中，搜索引擎208可优选返回预测结果(320)。该活动可与接收预测(310)重叠并且由图3的虚线320指示。预测结果被呈现(320)并且恢复对用户的监视(302)。对用户的呈现可通过多种方式完成。例如，结果可在非持久窗口的一部分、弹出窗口或在当前显示器的一部分或用户界面的一部分显示。用于输入查询以及用于呈现预测结果的网页可包括JavaScript或其它嵌入码或指令来提供预测结果的显示并响应用户对于任一预测结果的选择。其它方式也是可以想到的。预测结果对应于可基于作为一个或多个预测查询或URL的请求被返回的文档或信息。在一些实施例中，预测结果包括在对应于预测结果的一个或多个位置的内容文本摘录。在一些实施例中，预测结果包括一个或多个网页的一个或多个缩略图或在对应于预测结果的一个或多个位置的其它文本。在一些实施例中，结果是基于一个或多个预测查询的搜索结果。例如，在一些实施例中，呈现的结果(320)可以是与一个或多个预测查询或预测URL相关的一个或多个文档。因此，可在用户完成输入请求(例如搜索请求或URL请求)之前把与想要请求匹配的预测结果呈现给用户。在这种情况下，用户观看的处理等待时间被有效减小为零，因为用户无需完成输入就获得想要的结果。

[0044] 图4说明了当根据本发明一些实施例接收输入时搜索引擎208中发生的活动。搜索引擎208接收输入并确定该输入是否指示了是最终输入还是部分输入(402)。如果搜索引擎208确定接收的输入是最终输入(402-最终查询)，则确定关于该查询的相关搜索结果是否存在于缓存203中(404)。如果相关搜索结果在缓存232中(404-是)，那么这些结果被返回到客户机104(406)。另一方面，如果搜索结果没有在缓存中(404-否)，那么获得关于查询的搜索结果(408)，并且随后返回到客户机104(406)。在一些实施例中，一些URL在完成时不由搜索引擎208接收，而由搜索助手发送该请求到资源主机。在一些实施例中，URL请求由搜索引擎208接收用于追踪目的(比如存储在URL数据库中)并且搜索引擎208将该请求重定向到资源主机。

[0045] 如果搜索引擎208确定接收的输入是部分输入(402-部分)，那么其确定对应于该部分输入的排序匹配集(410)，并且将该预测集传输到客户机104(412)。如下所述，在一些实施例中，发送到客户机104的该排序匹配集是多个预计算的排序匹配集之一。尽管以下操作根据部分查询来描述，同样的技术对于URL的部分输入也同样可用。在一些实施例中，返回的该排序匹配集仅与查询相关。在一些实施例中，该排序匹配集仅与URL相关。以及在一些实施例中，该排序匹配集与查询和URL都相关。

[0046] 为了帮助理解根据一些实施例的搜索引擎208怎样确定返回哪一排序匹配集，从描述怎样建立和使用这些排序集来开始是有帮助的。图5示出了与用于预测对应于部分输入查询的预测查询的历史查询(例如先前提交的查询)相关联的一组数据结构。搜索引擎或用户输入预测系统还可包括与用于预测对应于部分输入URL的预测URL的历史URL(例如先前提交的URL)相关联的一组类似的数据结构。

[0047] 参考图5，历史查询日志502被一个或多个过滤器504过滤来建立认可历史查询列表506。排序集建立器508依照认可历史查询列表506基于某个标准来建立一个或多个指纹-表映射510。当部分查询被传输时(图3，308)，其在搜索引擎208作为部分查询513接收。一个散列函数514被应用到部分查询513来建立指纹，即一个b位二进制值(例如一个64位数)。为该指纹(例如515)搜索一个可应用的指纹-表映射510(例如510-1)来识别与该指纹相关联的查询完成表516。查询完成表516提供与该部分查询513相关的预测查询的一个排序集。

[0048] 一个可用的指纹-表映射510可根据与用户或请求相关联的多个不同因素来选择。被用于选择可用指纹-表映射510的信息可来自用户或搜索助手204提供的档案(profile)信息、从请求本身收集的信息(例如语言)、与用户信息处理模块222中的用户相关联的信息或其它来源。例如，指纹-表映射可基于与用户或搜索请求者相关联的某个连接信息(例如设备类型、连接速度、连接类型等等)来选择。在一些实施例中，预测的数量或每个查询预测的长度是依赖于这些连接信息的。具有小用户界面的设备可接收较少数量的预测和/或具有较少数量词项的查询。查询词项可具有与其相关联的重要性因子，并且具有较低重要性因子的词项可先于具有较高重要性因子的词项从查询中被截去。在一些实施例中，指纹-表映射510的不同组可被用于各个种类的用户，从而提供根据与用户相关联的一个或多个种类或主题而有所偏重的预测结果。例如，从特定网站接收的部分搜索查询可通过使用从相同网站或者从一组被认为与特定网站类似的网站中接收的历史查询所产生的一组指纹-表映射来被映射到预测结果。类似的，在他/她许可的情况下，单独的用户可具有用户档案，用于说明关于用户或与用户相关联的组群的信息，并且该“个人信息”可被用于当为该用户预测结果时识别为该用户识别各个组的指纹-表映射。应注意的是，与增加多组指纹-表映射510相关联的开销是适度的，因为多组指纹到表映射510可以指向一些查询完成表516，并且查询完成表516比指纹-表映射516占据更多的存储空间。

[0049] 在一些实施例中，在指纹被建立之前对部分查询进行一些预处理。在一个实施例中，识别部分查询中明显拼错的单词并且通过比较一个或多个完整搜索词项与词典中的条目来校正。来自包括正确拼写单词的查询的一个或多个预测结果与返回到用户的预测结果合并。在另一个例子中，普通的前缀信息可被去除(例如“http://”或者“www.”)。在一些实施例中，分析查询中的词项来提取体现在搜索词项中指示信息特定类型的概念(例如“技术”，“食物”，“音乐”或“动物”)。来自与一个或多个提取的概念相关的查询的一个或多个预测结果与返回到用户的预测结果合并。

[0050] 历史查询日志502包含搜索引擎208在一段时间内接收的先前提交的查询的日志。在一些实施例中，查询是来自特定用户的。在一些实施例中，查询是来自共享至少一个类似特征比如属于相同公司、使用相同语言、具有与相同国家或地区相关联的因特网地址等等的用户群体。对群体的选择确定了先前提交查询的集合，从中可提取预测。不同的群体将会产生不同的预测集。

[0051] 历史查询日志502还可包含与每个提交查询相关联的信息。在一些实施例中，查询信息包括查询提交或接收的日期和时间。在一些实施例中，查询信息包括查询被提交的地址的网际协议(IP)地址。在一些实施例中，查询信息包含对于查询的唯一源标志符(例如来自存储在用户机器上的cookie的值，该值与特定搜索助手204相关联)。当唯一标识符没有直接识别任何特定用户时，其可以与浏览器或工具栏的特定安装相关联。在一些实施例中，用户可允许用对某些个人特征的唯一标识符来直接识别，该特征可以使用用户信息处理模块222来存取。

[0052] 在一些实施例中，指纹值与查询相关联。指纹值可通过对查询字符串应用散列函数来计算。在一些实施例中，其它类型的元数据与查询相关联并被存储，比如查询语言或可由用户或搜索助手根据用户喜好提供的其它信息(例如指示用户的某些喜好的标识符或档案信息)。在一些实施例中，元信息包括从分析查询中的词项获得的类型或概念信息。对查询做日志的时间段是可变的，并且表现了存储容量于预测的可能准确度之间的折中。更长的时间段将更精确地反映在整个群体上的查询的流行性，然而这需要更大的存储空间。另一方面，在长时间段上的流行性分级可能不会反映对于当前事件的暂时的流行性。

[0053] 使用一个或多个过滤器504来确定被认可做进一步处理的查询。例如，过滤器可基于各种标准来去除某些查询。在一些实施例中，私密性过滤器504防止那些没有从多于某个数量的可唯一识别提交者接收的查询被包括在认可历史查询列表506中。这可通过检查与每个查询相关联的唯一标识符来完成(如果该标识符存在)，并且仅识别已经被至少n个可唯一识别提交者提交的那些查询，其中n是基于私密性考虑的数字(例如三个或四个可唯一识别提交者)。在一些实施例中，过滤器504包括去除不经常被提交的查询，因不大可能被用户选择。在一些实施例中，过滤器504包括适当性过滤器504，其基于多个不同因素比如查询中一个或多个特定关键字的存在，和/或基于对应于查询的搜索结果或文档的内容来从内部阻止某些查询。其它类型的过滤器也可容易地想到。例如，过滤器可以阻止在一个特定历史时间点之前提交的查询，使得认可历史查询列表506表示最近提交的查询。哪些被认为是最近的，要基于具体实施例(例如根据时、日、周、月或年)。在另一个例子中，反欺骗过滤器504可被用于防止查询/URL预测系统被大量虚假产生的查询或URL提交而欺骗。例如，反欺骗过滤器504可过滤从相同用户或从相同客户计算机接收的相同查询或URL的多个提交。

[0054] 在历史查询日志502被一个或多个过滤器504过滤后，则产生认可历史查询列表506，即易于被返回到用户作为建议查询输入完成的查询列表。认可历史查询列表506包括历史查询506-1到历史查询506-q，其中q表示包括在认可历史查询列表506中的查询数量。q的值可等于或小于从历史查询日志502中过滤的查询的总数量。例如，具有小于预定阈值的频率的过滤查询可被忽略。在一些实施例中，新的认可历史查询列表506被定期建立，比如每小时、每天、每周或其它周期。在一些实施例中，当前认可历史查询列表506在可用过滤后根据查询日志224的最近输入来更新。

[0055] 认可历史查询列表506中的每个查询(例如506-1)包括查询、其频率以及可选的元信息。查询可以是一个字符串。频率信息指示在一个时间段内该查询被提交的次数。如上所述，唯一标识符可被用于对可唯一识别搜索者提交的查询的次数进行计数。因为不同的用户可使用多个搜索助手或其它查询可不包括唯一标识符，频率数量可不表示可唯一识别用户提交搜索查询的实际数量。但是，查询的频率可作为查询的流行性的代理。在一些实施例中，认可历史查询列表506基于查询按字母排序。在其它实施例中，认可历史查询列表506基于查询频率来排序。

[0056] 元信息可包括类似于以上讨论的关于历史查询日志502的元信息(例如位置或语言信息)。在一些例子中，相同的查询可在历史查询日志502中具有条目，它们不是查询的字符串不同，而是元信息不同。因此，对于特定认可历史查询506-1的元信息可对于相同查询指示不同的元信息。例如，对于从两个不同位置提交的查询的元信息，比如欧洲或亚洲，将指出这两个位置作为查询的源位置。元信息还指示用户档案信息来指示用户已经提交的查询的类型。本领域技术人员能够理解，各种类型的元信息可被用于分类或分组由共同的特征集(例如语言或位置)关联的查询。在一些实施例中，查询被分析并且与信息的某些类型相关联。例如，包括“狗”和“饲养”的搜索查询被与“狗”或“动物”类型相关联。在一些实施例中的元信息包含这种类型信息。在一些实施例中，对于认可历史查询列表506中的单独条目的元信息从多个查询中产生，例如通过提供查询的日期/时间作为查询被提交的最近的日期/时间。

[0057] 排序集建立器508使用认可历史查询列表506来建立一组指纹-表映射510-1到510-t，其中t表示建立的指纹-表映射510的数量。任意数量的指纹-表映射510可基于期望用于分类预测查询的方式的数量来建立。每个指纹-表映射510包含经排序的预测集，每一预测集映射到特定的部分查询。指纹-表映射510基于比如在元信息中找到的信息的特征而不同。例如，对于每种语言可以有一个指纹-表映射510(例如一个用于英语查询，一个用于法语查询，一个用于日语查询)。类似的，可为地区建立不同的指纹-表映射510。
作为另一个例子，不同的指纹-表映射510可以从来自特定IP地址或地址群的查询建立，比如来自特定网络或特定个体群的那些(例如公司)。使用元信息来建立不同的指纹-表映射510，使得预测基于具有类似于搜索者的特征的各用户，并且增加正确预测的可能性。
在一些实施例中，不同的指纹-表映射510基于用于查询的不同分级标准(例如频率、最近日期/时间、个人类型或特征等等)。在一些实施例中，不同的指纹-表映射510基于用户输入的类型(例如查询字符串或URL)。

[0058] 使用指纹-表映射510-1作为例子，每个指纹-表映射510包括多个条目512-1到512-f，其中f表示指纹-表映射510-1中的条目数量。在任何特定指纹到表映射510中的条目数量基于预测服务器212将为其返回预测的不同部分查询的数量。

[0059] 指纹-表映射510-1中的每个条目(例如512-2)包括指纹(例如指纹(2)515)以及查询完成表(例如查询完成表(2)516)。指纹-表映射510用于将指纹(例如指纹(2)515)与查询完成表(例如查询完成表(2)516)相关联。

[0060] 指纹(2)515表示用于特定查询的指纹值。指纹(2)515可例如通过对部分查询应用散列函数建立b位二进制值(例如64位数)来计算。因此，可对与部分查询513的指纹(例如指纹5151)匹配的指纹搜索指纹-表映射510-1。

[0061] 查询完成表(2)516包含查询完成指纹518-1到518-n的列表，其中n表示在查询完成表(2)516中的查询完成指纹的数量。在一些实施例中，n表示返回到搜索助手的预测查询的数量(例如10个预测查询)。在其它实施例中，返回小于n个。在一些实施例中，n大于在排序查询中被返回的结果的数量。在一些实施例中，n是被返回的结果的两倍，并且第一n/2个被提供作为第一排序预测查询集以及第二n/2个被提供作为第二排序预测查询集(例如基于某些条件，第二集中10个预测查询在第一集中10个之后发送)。在一些实施例中，查询完成表516包括用于每个查询完成指纹518的分数。该分数用于在查询完成表516中按分数的降序对词项排序。在一些实施例中，分数是查询完成表的持久部分，而在其它实施例中分数被删除或在查询完成表516的形成完成后不再保持。

[0062] 每个查询完成指纹518是与完整查询相关联的指纹值。查询完成指纹518(例如518-2)被映射到相关联的查询记录520。查询记录520包括查询字符串522，其包含用于完整查询的查询字符串。该方式便于多个查询完成表512中的条目参考相同的查询字符串
522，而仅要求实际查询字符串被存储在单一的位置(例如查询字符串522)中。然而在一些实施例中，查询字符串522可被存储在查询完成表512中的查询完成指纹518的位置。在一些实施例中，用于URL字符串的查询记录包括表示与URL相关联的标题的URL标题524。
在一些实施例中，与URL相关联的附加信息被提供在信息526中。

[0063] 在一些实施例中，查询完成表512-2是关于与指纹515相关联的部分查询的n个查询的排序列表。该列表可根据各种分级标准排序，比如(频率、提交的日期/时间等等)。在一些实施例中，分级标准可考虑两个或多个因素，比如同时考虑频率和提交的日期/时间，通过为每个查询考虑两个或多个因素中的每个而产生分数或分级。在简单的例子中，其日期/时间大于过去的24小时的历史查询可对查询的分级分数贡献一个“1”的值，而其日期/时间在过去24小时之内的历史查询可对查询的分级分数贡献一个“2”的值。在该例子中，在确定每个认可历史查询的分级时，近期的历史查询比较早的历史查询被更高地加权。

[0064] 在一些实施例中，排序集建立器506定期地(例如每小时、每天、每周)建立或更新指纹-表映射510以及相关联的查询完成表512和/或910(图9)，使得由预测服务器产生的查询和/或URL预测与可应用群体客户近期提交的查询和/或URL保持一致。

[0065] 参考图6，部分查询“ho”602可具有与该部分查询602相关的一组完整查询604。该组完整查询604的第一位置包括具有最高频率值的查询(例如“hotmail”)，其随后的第二位置是具有第二高频率值的查询(例如“hot dog”)等等。在该例子中，完整查询与给定部分查询的相关性通过部分查询在完整查询的开头的出现来确定(例如字符“ho”在“hotmail”和“hotels in San Francisco”)。在其它实施例中，相关性通过部分查询在完整查询的任何位置的搜索词项的开头来确定，如完整查询集606所示(例如字符“ho”在“hotmail”的开头以及在“cheap hotels in Cape Town”的第二个搜索词项的开头)。

[0066] 为了建立查询完成表的集512，选择认可历史查询506中的一个查询(图7，702)。在一些实施例中，仅处理具有所期望元信息的查询(例如英语的查询)。从所选的查询中识别第一部分查询(704)。在一种实施例中，第一部分查询是所选查询的第一个字符(即对于查询字符串“hot dog ingredients”是“h”)。在一些实施例中，在部分查询被识别之前应用预处理(例如去除“http://”或者“www”)。在表中做出条目，来指示该部分查询、对应于该部分查询的完整查询以及其频率。在其它实施例中，存储用于分级的其它信息(例如日期/时间值、或基于两个或更多因素而计算的分级分数)。如果该部分查询不表示整个查询，那么查询处理没有完成(708-否)。因此，识别接下来的部分查询(710)。在一些实施例中，通过添加随后的附加字符到先前识别的部分查询来识别随后的部分查询(即对于查询字符串“hot dogingredients”是“ho”)。识别处理(710)和对查询完成表的更新处理(706)一直持续，直到整个查询被处理(708-是)。如果全部查询还没有被处理完(712-否)，那么选择随后的查询并进行处理，直到所有的查询都被处理(712-是)。在一些实施例中，当词项被添加到查询完成表，词项就被插入，使得表中的词项根据分级或分数来排序。在另一种实施例中，所有的查询完成表在表建立过程的最后被分级，使得每个查询完成表中的词项根据该词项在查询完成表中的分级或分数来排序。此外，一个或多个查询完成表可被截去，使得表包含不大于预定数量的条目。

[0067] 参考图8，查询字符串“hot dog ingredients”的前五个字符的示例处理在表802中从804到812示出。查询字符串“hotmail”的前四个字符的示例处理在814至820示出。

[0068] 在一些实施例中，对于给定部分查询，通过从表中识别与该给定部分查询相关的最常被提交的n个查询来建立查询完成表，并且将它们按分级次序放置，使得具有最高分级的查询(例如最高分级分数或频率)在列表的顶端。例如，对于部分查询“hot”的查询完成表可包括808和818的完整查询字符串。当分级基于频率时，对于“hotmail”的查询字符串可出现在查询字符串“hot dog ingredients”的上面，因为818中查询字符串的频率(即300,000)大于808中查询字符串的频率(即100,000)。在一些实施例中，URL的流行性可以是指定给特定网页的给定值，其提供一组网页中的重要性指示(例如页面分级)。因此，当排序的预测集返回到用户时，具有较高被选择可能性的查询被首先呈现。如上所述，其它从元信息获得的值可被用于分级(例如日期/时间值、或个人信息)。

[0069] 参考图9和10，在一些实施例中，通过将历史查询字符串分割为预定尺寸C的“块”，比如4个字符，来减小查询完成表的数量。对于长度小于C的部分查询的查询完成表保持不变。对于长度大于等于C的部分查询，部分查询被分为两个部分：前缀部分和后缀部分。后缀部分的长度S等于部分查询的长度(L)模C：

[0070] S＝L mod C

[0071] 其中L是部分查询的长度。前缀部分的长度P是部分查询的长度减去后缀长度：P＝L-S。因此，例如，对具有10个字符长度的部分查询(例如“hot potato”)，当块尺寸C为4时，可具有后缀长度S为2以及前缀长度P为8。

[0072] 当执行图7所示的过程时，步骤706识别或建立对应于部分查询的查询完成表，对此在图9中进行概念性的说明。图9示意性说明了用于产生查询完成表的处理以及当处理用户输入部分查询时的查找处理。当部分查询的长度小于一个“块”的尺寸C时，部分查询被映射到查询指纹515，例如通过使用散列函数514(图5)。指纹515通过指纹-表映射510被映射到查询完成表516，查询完成表516又包含查询完成指纹518或指向一组查询记录520的指针(查询记录520包含查询字符串522，图5)。

[0073] 当部分查询的长度大于等于一个块的尺寸C时，部分查询902被分解为前缀904和后缀906，其长度由块尺寸控制，如上面所解释的。对前缀904产生指纹908，例如通过对前缀904应用散列函数514，并且指纹908随后通过指纹-表映射510映射到“分块”的查询完成表910。分块查询完成表910的结构不同于图5所示的查询完成表516，其中分块查询完成表910的每个条目911具有后缀条目914和查询完成指纹912。每个查询911还可可选地包括一个分数916，用于排序查询完成表910中的条目。后缀具有长度S，其可以是零到C-1的任何长度，并且包括没有被包括在前缀904中的部分查询的零个或多个字符。在一些实施例中，当产生历史查询的查询完成表条目911时，在每个分块查询完成表910中仅作出一个条目对应于历史查询。特别的，该个条目911包含历史查询的最长可能后缀，最长是C-1个字符的长度。在其它实施例中，在每个分块查询完成表910中为特定历史查询作出直到C个条目，每个条目用于每个不同的后缀。

[0074] 图10示出了包含对应于历史查询“hot potato”的条目911的一组查询完成表。该例子假设块尺寸C等于四。在其它实施例中块尺寸可以是2、3、5、6、7、8或其它合适的值。
块尺寸C可基于经验信息来选择。图10所示的查询完成表的前三个516-1到516-3是分别用于部分查询“h”、“ho”和“hot”的。接下来的两个查询完成表910-1和910-2分别对应于部分查询“hot pot”和“hot potato”，具有部分查询长度为7和10。再次参考图7的步骤710，通过部分由步骤710构形成的循环的每次重复，部分查询的长度最初按1个字符的步长增加，直到达到C-1的长度，并且随后部分查询的长度按C个字符的步长增加，直到达到历史查询的整个长度。

[0075] 每个分块查询完成表的条目911根据通过查询完成指纹912在条目911中识别的查询字符串的分级值(由分数916表示)来排序。对于具有小于C个字符的部分查询，在相关查询完成表516中的查询的数目是第一值(例如10或20)，其可表示作为预测被返回的查询数量。在一些实施例中，在每个分块查询完成表910中的条目911的最大数量(例如在1000和10,000之间的数量)大大超过第一值。每个分块查询完成表910可占用几十或几百个普通查询完成表。因此，每个分块查询完成表910被调整大小来包含若干(p)条目，对应于其前缀部分对应该分块查询完成表的所有或几乎所有认可历史查询，从而在为用户指定的部分查询产生预测查询的列表时不至于产生不能忍受的等待时间。

[0076] 在已经根据历史查询集产生查询完成表516、910和指纹-表映射510之后，这些相同的数据结构(或其副本)被用于识别对应于用户输入的部分查询的查询预测集。如图9所示，对用户输入的部分查询，首先通过对整个部分查询902或部分查询的前缀部分904应用散列函数514，如由该部分查询的长度所确定的，将该部分查询映射到查询指纹515或
908。随后通过在指纹-表映射510中执行查询指纹的查找，把查询指纹515或904映射到查询完成表516或910。最后，从识别的查询完成表中提取直到N个预测查询的排序集。当部分查询的长度小于块尺寸时，预测查询的排序集是识别的查询完成表中的前N个查询。
当部分查询的长度等于或大于块尺寸时，在识别的查询完成表中搜索与部分查询的前缀匹配的前N个词项。因为查询完成表910中的条目按降序排列，对于匹配条目的搜索从顶端开始并且继续，直到获得了想要返回的预测数量(N)(例如10个)，或直到达到了查询完成表
910的末端。当部分查询的前缀906与条目911中的前缀914的相应部分相同时就存在“匹配”。例如，参考图10，一个字母的前缀

与分别具有前缀和的条目911-3和911-4匹配。具有长度零的空前缀(也被称为空字符串)与查询完成表中的所有条目匹配，并且因此当部分查询的前缀部分是空字符串时，表中前N个词项被作为预测查询返回。

[0077] 如上所述，用于识别对应于部分URL的预测URL的排序集的数据结构和过程与上述用于识别对应于用户输入的部分查询的预测查询的排序集的数据结构和过程相同。尽管URL和查询字符串具有不同的用途，但在用户的部分输入之后，它们都可被看作其值可被预测的字符或符号的字符串。在一些实施例中，“历史URL”集可包括特定用户或一组用户或用户群体输入的URL，由此建立一组URL完成表1234(图12)和URL指纹-表映射1236(图12)。在另一种实施例中，“历史URL”集可包括存储在文档数据库中的URL文档，比如搜索引擎的文档数据库，由该“历史URL”集可建立一组URL完成表和URL指纹-表映射。

[0078] 图11说明了当使用根据本发明某些实施例的浏览器和工具栏的用户视图。浏览器1102包括工具栏1104，该工具栏包括文本输入框1106，示出了部分查询的输入。响应于检测到部分查询以及最终从查询服务器接收预测查询，预测被显示在显示区域1108，用于用户的可能选择。类似的，尽管未示出，响应于检测到用户在地址栏1110的部分URL的输入，预测URL的一个排序集显示在地址栏1110的紧下方或邻近的显示区域中(未示出)用于用户的可能选择。

[0079] 参考图12，实施上述方法和数据结构的搜索引擎1202的实施例包括一个或多个处理单元(CPU)1204，一个或多个网络或其它通信接口1206，存储器1208，以及一个或多个用于互联这些部件的通信总线1210。搜索引擎1202可选地包括含有显示设备1214和键盘1216的用户接口1212。存储器1208可包括高速随机读取存储器并且还可包括非易失性存储器，比如一个或多个磁盘或光盘存储器。存储器1208可包括远离CPU的1204的海量存储器。存储器1208可存储以下要素，或这些要素子集或超集：

[0080] ●包括用于处理各种基础系统服务和用于执行硬件依赖任务的程序的操作系统1218；

[0081] ●用于将搜索引擎1202通过一个或多个通信接口1206(有线或无线地)比如因特网、其它广域网、局域网、城际网等等连接到其它计算机的网络通信模块(或指令)1220；

[0082] ●用于接收完整查询或部分查询并返回搜索结果和预测查询以及预测搜索结果的查询服务器210；以及

[0083] ●用于接收部分查询并返回查询或URL的排序预测集的预测服务器212。

[0084] 在一些实施例中，查询服务器210包括以下部件或这些部件的子集：用于接收和传输信息的客户机通信模块216；用于接收和响应完整搜索查询的查询接收、处理和响应模块218；用于接收和相应完整搜索查询的部分查询接收、处理和响应模块220；用于存取用户信息数据库1226中用户信息的用户信息和处理模块222，其包括用于多个用户的各用户档案(profile)；用于存储关于先前提交查询的信息的查询日志224，以及URL日志或数据库225。在一些实施例中，查询服务器210包括这些模块的子集。在一些实施例中，查询服务器210包括附加模块。

[0085] 在一些实施例中，预测服务器212包括以下部件，或这些部件的子集：

[0086] ●用于接收部分查询的查询接收模块(或指令)1230；

[0087] ●用于产生查询完成表516、910和查询指纹-表映射510的查询/URL完成表建立器(或指令)1232；在一些实施例中，查询/URL完成表建立器1223还可产生URL完成表1234和URL指纹-表映射1236；以及

[0088] ●用于获得一预测集查询或URL的预测模块(或指令)1238。

[0089] 在一些实施例中，预测服务器212还可包括以下一个或多个：

[0090] ●用于至少部分地基于某些用户档案信息选择一预测集查询的个性化模块(或指令)1240；

[0091] ●用于确定与特定查询相关联概念的概念模块(或指令)1242；

[0092] ●用于确定与用户群体相关联的一组特性的群体特性模块(或指令)1244；

[0093] ●用于识别接收查询或查询词项的可替换拼写的拼写模块(或指令)1246；以及[0094] ●为各种符号语言成分提供音标表示的语言词典1248。

[0095] 在一些实施例中，用户信息处理模块222、个性化模块1240、概念模块1242。、群体特性模块1244和拼写模块1246中的一个或多个没有实现。当实现时，用户信息处理模块222的用户档案1228可包含适用于选择排序预测查询或URL的信息。例如，用户档案1228可识别特定用户感兴趣的信息类型。用户档案1228还可包含用户所属于的、或用户与其相关联的用户群体的相关信息。用户信息处理模块222可将个人信息和群体信息结合来产生用户档案1228。

[0096] 当实现时，概念模块1242可将历史查询映射到概念或信息类别，适用于与用户档案1228中的信息匹配。类似的，概念模块1242可被配置为映射历史URL到概念或信息类别，例如通过在对应于历史URL的文档内容中确定一组主要概念、主题或信息类型。由概念模块1242识别的概念、主题或信息类型可被存储在查询完成表或URL完成表的条目中，或者存储在通过查询/URL完成表识别的查询记录或URL记录中。当处理部分查询或URL时，可记录该预测集查询或URL，使得其概念、主题或信息类型与请求用户的用户档案中的信息相匹配的预测查询或URL在预测查询或URL的列表中被置于较之其概念、主题或信息类型与请求用户的用户档案中的信息不匹配的预测查询或URL更高的位置。

[0097] 在另一种实施例中，概念模块1242可被配置为根据词项的概念的或类别映射将部分查询中的一个或多个词项映射到一个或多个替代词项。为部分查询产生包含一个或多个替代词项的预测查询的排序集，并且随后将这些预测查询传输给用户，单独地或者与使用用户输入的部分查询产生的结果相结合地传输。

[0098] 图12描述了在一种实施例中的搜索引擎1202的内部结构。应当理解的是，在一些其他实施例中搜索引擎1202可使用多个服务器来实施从而提高其吞吐量和可靠性。例如查询日志224可在与搜索引擎1202中的其他服务器之一通信并共同工作的独立服务器上实施。在另一个例子中，查询/URL完成表建立器1232和/或语言词典1248可在单独的服务器或计算设备上实施(例如图2中的排序集建立器242和语言词典244)。

[0099] 尽管此处的讨论是参考为位于搜索请求者远程位置的文档所设计的搜索引擎而做出的，应当理解的是，在此公开的概念对于其他搜索环境也是可用的。例如，在此描述的同样技术可被应用到对于任何类型的对于查询或搜索被运行的信息贮藏库(例如地址簿、产品信息数据库、文件服务器、网站等等)。因此，术语“搜索引擎”可被广义地理解为覆盖所有这些用途。

[0100] 参考图13，实施上述方法的客户机系统1300地实施例包括一个或多个处理单元(CPU)1302、一个或多个网络或其它通信接口1304、存储器1306和用于互联这些部件的一个或多个通信总线1308。搜索引擎1300可选的包括带有显示设备1312和/或键盘1314的用户接口1310。存储器1306可包括高速随机读取存储器并且还可包括非易失性存储器，比如一个或多个磁盘或光盘存储器。存储器1306可包括远离CPU 1302的海量存储器。存储器1206可存储：

[0101] ●包括用于处理各种基础系统服务和用于执行硬件依赖任务的程序的操作系统1316；

[0102] ●用于将客户机系统1300通过一个或多个通信网络接口1304以及一个或多个通信网络比如因特网、其它广域网、局域网、城际网等等连接到其它计算机的网络通信模块(或指令)1318；

[0103] ●用于与用户交互来输入搜索查询以及显示搜索结果的浏览器或工具1320；以及

[0104] ●搜索助手1322。

[0105] 在一些实施例中，搜索助手1322独立于浏览器/工具1320，而在其他实施例中搜索助手结合在浏览器/工具1320中。

[0106] 搜索助手1322可包括以下部件或这些部件的子集：用于监视搜索查询的输入并选择部分查询用于传输到搜索引擎的输入和选择监视模块(或指令)1324；用于传输部分搜索查询和最终搜索查询至搜索引擎的传输模块(或指令)1326；用于接收预测查询的预测查询接收模块(或指令)1328；用于接收预测搜索结果的预测搜索结果接收模块(或指令)1330；用于显示预测和结果的显示模块(或指令)1332；以及可选的，用于接收搜索结果的搜索结果接收模块(或指令)1334。最终(即完整的)查询的传输、完整查询的搜索结果的接收以及这些结果的显示可被浏览器/工具1320、搜索助手1322或其结合来处理。搜索助手1322还可提供用于处理部分和完整URL的对应功能集，其可由相同部件或上述部件的并行组来处理。搜索助手1322可通过多种方式实施。例如，搜索助手1322可作为浏览器的一部分、工具栏的一部分、桌面应用程序的一部分或使用可执行指令的网页(比如JavaScript)来实施。至少，搜索助手把部分查询信息传送给搜索系统。搜索助手还可实现预测结果的显示，以及所显示预测结果的用户选择。

[0107] 尽管在图12和13中作为独立的模块或部件来示出，但各个模块或组件可位于或共同位于搜索引擎或客户机中。例如，在一些实施例中，预测服务器312的部分、和/或各个查询完成表512和/或910位于客户机系统202中或形成搜索助手204的一部分。例如，在一些实施例中，对于最流行搜索的查询和指纹-表映射可被定期下载到客户机系统202中，从而对至少一些部分输入的查询或URL提供完全基于客户机的查询或URL输入预测。

[0108] 在另一种实施例中，搜索助手204可包括预测服务器312的本地版本，用于至少部分地基于用户的先前搜索和URL输入来做出搜索或URL预测。可替换的或附加，本地预测服务器312可基于从搜索引擎或远程预测服务器下载的数据来产生预测。此外，客户机助手204可把本地产生和远程产生的预测集结合起来呈现给用户。结果可通过多种方式中的任何一种结合，例如通过交织两个集或结合两个集并偏向于用户先前提交的查询，使得那些查询可被置于或插入到偏向于预测查询的结合列表的顶部。在一些实施例中，客户机助手204把对于用户很重要的查询插入到预测集中。例如，用户经常提交的但是没有包括在从搜索引擎所获得的集中的查询可被插入到预测中。

[0109] 可通过改变产生指纹-表映射510的处理，将上述技术应用到不同于主要基于字母书写系统的其它语言。例如，上述技术可被应用到具有符号或象形文字(pictograms)比如缩记符(表示文字的部分或全部文字的符号)、表意字符(用图形表示抽象意思的符号)、音标字符(就像在字母表或字音表中的字母中表示特定声音的符号)以及意音结合(包括语义部分表示或提示符号的意思，以及音标部分指示或提示发音)的语言中。为此，符号或象形文字，即不是字母的字符被称为“表意文字(ideographs)”。

[0110] 日本语被用于说明将上述技术应用到主要不是字母的语言中的实施例。日语使用一种混合书写系统，并且包括汉字、假名、罗马字、阿拉伯数字和中国数字。汉字是源自多个来源的“字符”：一些汉字从中文派生(典型地具有多于一个发音，其中发音是基于意思或语义的)；一些从中文改写(通常具有“标准”发音)；以及一些单独地为日本语中创建的。假名是两种日本字音表地音标字符：平假名(主要用于表示日本本土文字或古代从中国的借字)以及片假名(主要用于书写外语或拟声文字，或给文本一个“漂亮”的外观)。在一些例子中，汉字表示包括一个或多个拖尾假名字符来指示某个结合和/或帮助发音。罗马字是罗马的字母符号。

[0111] 平假名和片假名各包括46个字符，并且主要由元音和元音-辅音组合来组成。通常通过输入用于一个或多个汉字字符的假名语音表示来把日语文本输入到计算机，这些假名随后将会转化为汉字表示。根据一种输方法，罗马字字符的序列(通过键盘)被输入或显示到中间文本输入区域。当用来产生假名字符的每个罗马字字符序列被识别，假名字符代替显示的罗马字字符，或显示在中间文本输入区域。例如，键入罗马字序列“ti”产生平假名“ㄘ”。在输入期望数量的假名字符之后，用户可将假名表示直接置于想要的文本范围或可通过用户启动的操作选择性的将全部或部分假名表示转化为汉字表示。例如，输入罗马字序列“ti”和“ke”，产生平假名“ちけ”，是英文单词“salmon”的平假名表示。可通过用户启动的操作，比如按下“空格键”或按下功能键，将该假名字符串转化为“salmon”的汉字表示或“鮭”。在一些例子中，将假名转化为汉字的尝试是自动的。尽管通常这种转化需要用户的某种干预。用户典型的被要求从多个汉字表示中选择一种，因为平假名中相同的语音表示会映射到多种汉字表示。例如，语音序列“ほし”(通过罗马字字符序列“ho”和“si”所产生的)可对应以下三个汉字：“端”(表示tip或end)；桥(表示bridge)以及“箸”(表示chopsticks)。此外，单个汉字表示可具有多种语音表示。例如“鮭”(表示salmon)至少有语音表示“さけ”(通过输入罗马字字符序列“ti”和“ke”来产生)以及“しやけ”(通过输入罗马字序列“si”、“ya”和“ke”来产生)。

[0112] 用户输入查询，典型地通过将音标字符序列输入到查询输入区域来输入每个查询词项。音标序列通常在查询形成时被转化为表意文字。查询通常包括理想顺序的一个或多个表意文字和/或一个或多个音标字符。希望预测服务器不仅基于由一个或多个表意文字组成的部分查询来预测搜索查询，而且在用户输入语音表示时使用表意文字的部分音标字符输入来做出预测。因此，并且除了其他组合之外，根据由零个或多个表意文字跟随一个或多个音标字符所组成的部分查询输入来做出预测。在一些实施例中，这些预测可通过修改图7的过程来实现，该过程用于建立指纹-表映射，来考虑语言的特定书写系统。修改的过程考虑通过一个或多个音标字符来输入表意文字。参考图14，描述了考虑包括表意文字和音标字符的语言书写系统来建立指纹-表映射的这种过程，并且其中在表意文字和语音表示之间可存在多个映射。本领域技术人员将认识到图14描述的方法可扩展到其它语言。

[0113] 从认可历史查询列表中选择查询(例如图5的认可历史查询列表506)，该列表包含有被处理语言的查询(1402)。在一些实施例中，这个认可历史查询列表根据参考图5讨论的方法产生。识别初始查询单元(1404)。查询单元可通过多种方式来确定。在一些实施例中，查询单元包括按可识别顺序表示词语或意思的一个或多个汉字字符(以及用于变形和发音的可应用平假名)。在一些例子中，表示不同词语或意思的汉字字符被表示成没有间隔字符(例如空格符)的汉字字符的单个字符串。在一些例子中，查询单元是一个单个的汉字字符。在一些例子中，查询单元是一个或多个汉字和/或一个或多个音标字符。在一些实施例中，在表意文字被识别之前应用预处理(例如去除“http://”)。在表中做条目来指示任何先前查询单元和当前查询单元，完整查询对应于当前查询单元和查询频率(1406)。在其它实施例中，用于分级的其它信息被存储(例如日期/时间值或基于两个或多个因素计算的分级分数)。

[0114] 如果当前查询单元是表意文字，则识别与该表意文字相一致的语音表示(1408)。在一种实施例中，查阅词典(例如图2的语言词典242)来返回与该表意文字相一致的至少一个可能的语音表示。根据每个语音表示，确定增量式查询字符串，表示语音字符的增量式增加，就像通过将当前字符附加到先前字符来输入这些字符以建立完整的语音表示(1410)。例如，如果“鮭”已经被识别作为当前查询单元，一种语音表示是“さけ”(如上所述)。因为语音表示“さけ”包括两个音标字符(即“さ”和“け”)，第一增量式查询字符串可以是“さ”，由第一语音字符组成，以及第二增量式查询字符串可以是“さけ”，由第一和第二字符组成。在表中对每个增量式查询字符串做条目(并且包括任何先前表意文字和查询单元(如果有的话))，完整查询对应于增量式查询字符串和查询频率(1412)。在一些例子中，查询单元包括不止一个表意文字或一个或多个表意文字跟随一个或多个音标字符。随着每个增量式查询字符串的建立，音标字符的完整序列由它们对应的表意文字代替。例如，当查询单元是“認める”时(意为acknowledge，并且其中假名字符“める”提供变形词尾)，一种可能的完整音标序列是“みとめる”(其中“みと”是汉字“認”的假名表示)。随着增量式查询字符串被建立(例如“み”和“みと”)，当识别特定音标序列时(例如“みと”)，其被适用的表意文字(例如“認”)代替，得到随后的增量式查询字符串(例如“認め”和“認める”)。

[0115] 如果查询没有被完全处理(1414-否)，那么识别下一个查询单元，按如上所述处理。如果当前的查询被完全处理(1414-是)，但是还有更多的查询没有处理(1418-否)，那么选择另一个查询并且进行上述处理。处理一直持续，直到所有待处理的查询都被处理完(1418-是)。

[0116] 上述过程可通过参考图15和16被更好地理解。示例查询字符串1502表示具有第一表意文字1504(即鮭鱼的汉字表示“鮭”)和第二表意文字1506(即日本的汉字表示“日本”)的查询。第一表意文字1504具有第一语音表示1508(即发音为“sake”的“さけ”)以及第二语音表示1510(即发音为“Sha-ke”的“しやけ”)。类似的，第二表意文字1506具有第一语音表示1512(即发音为“nohon”的“にほん”)以及第二语音表示1514(即“发音为“nippon”的“につほん”)。

[0117] 图16描述了处理图15的查询字符串1502的一种方式。最初，查询字符串1502的第一查询单元被识别(即“鮭”)，并且在表1604中做出对应的条目1602来指示该部分查询单元1606、完整查询1608和查询频率1610。在一些实施例中，与该查询相关联的其它或附加信息可被包括在其中，以支持查询分级。“鮭”的语音表示被识别(即“さけ”和“しやけ”)，增量式查询字符串被确定并且在表1604中做出对应的条目。例如，第一语音表示“さけ”包括增量式字符串“さ”和“さけ”。因此。对应于增量式查询字符串“さ”的条目1612被建立，并且对应于增量式查询字符串“さけ”的条目1614被建立。用于与第二语音表示相关联的增量式查询字符串的条目也被建立(例如1616、1618和1620)。然后，识别下一个查询单元(即“日本”)并且在表1604中做出包括两个表意文字的对应条目1622(并且不包括该第一表意文字的语音表示)。最后，“日本”的语音表示被确定并且建立对应条目(例如条目1624)。注意，当查询单元包括一个或多个表意文字时，同样可应用上述处理。
当在查询中遇到音标字符时(例如附加到表意文字之后)，在遇到时就将其包括在部分查询中(并且在表1604中做出相应的条目)。当输入是部分输入URL时，以上过程可同样应用。URL等同于查询词项的字符串，其包括预定分隔字符(例如“＞”和“/”)但是不包括空格。

[0118] 在查询的处理期间或之后，各种想要的查询完成表和指纹-表映射可被建立，如参考图7和8所述。

[0119] 通过考虑各种可被输入来得到查询的表意文字的音标字符串，可在语音表示的序列完成之前做出预测。根据从搜索请求者接收的部分查询来识别查询完成表，该部分查询包括零个或多个表意文字和一个或多个音标字符。

[0120] 尽管本发明的各个实施例已经使用英语和日语描述，本领域技术人员将认识到将在此描述的概念扩展到其它语言的方法。例如，输入字符的可能序列可根据认可历史查询和各种查询完成表以及基于这些可能的输入字符串建立的指纹-表映射来确定。

[0121] 尽管一些附图说明了特定顺序的一些逻辑阶段，不依赖顺序的阶段可被重新排序并且其它阶段可被结合或拆开。当提到一些重新排序或其它组合时，其它的情况对于本领域技术人员来说是显见的，并且不再给出这些替换方式的穷尽列表。而且，应当认识到这些阶段可通过硬件、固件、软件或其结合的方式实施。

[0122] 为了解释的目的，上述说明已经参考特定实施例描述。然而，上述说明性的讨论并不是穷举或将本发明限制到这些具体形式。根据上述的说明，可做出很多修改和变形。选择和描述实施例是为了按最好的方式解释本发明的原理和其实际应用，从而使得本领域技术人员最好地利用适于特定用途的具有各种变形的本发明和各种实施例。