用于本地字轮/WEB搜索的基于人口统计的分类

摘要

提供了创建一种语言中的句子分类，并基于地理位置和/或人口统计准则进一步构造语言模型的相关联的本地版本的各种系统和方法，其中这些本地语言模型根据所选人口统计准则可以是不同的粒度水平。本发明利用形成句子分类(例如，树结构)的分类编码器组件和利用该句子分类来构造本地化语言模型的本地语言模型编码器组件。解码器组件可随后通过混合来自匹配用户人口统计的不同人口统计粒度的本地语言模型的k个最佳答案来启用本地字轮和/或本地web搜索。因此，对于在一个人口统计地点的用户的输入数据的k个最佳匹配可不同于对于在另一个地点的其他用户的相同输入的k个最佳匹配。

说明书

背景

计算机硬件、软件和联网方面的技术进步已提供了能够从世界上的任何地 方彼此通信的高效的、节省成本的计算系统。使用这些系统来访问、浏览和搜 索因特网，撰写、发送和接收电子邮件消息，查看和编辑文档，发送和获得文 本消息、即时消息等。例如，用户可利用蜂窝电话、个人数字助理(PDA)来 在因特网上搜索电影时间并且通过发送电子邮件、文本消息或即时消息来邀请 朋友观看特定的放映。

已经利用了各种技术来将信息输入到这些设备中，诸如通过使用键盘、鼠 标、触敏屏幕、笔设备、光学字符识别、语音识别等来输入数据。例如，常规 的系统通常利用大小可取决于主机设备类型(个人计算机还是膝上型计算机 等)而变化的键盘，这些设备可利用基于QWERTY布局的键盘，其中每一字 母数字字符可以与一相应的键相关联，而蜂窝电话可包括更少的键，使得多个 字母字符与一数字字符共享单个键。例如，蜂窝电话键区上的“2”键通常与字 母“A”、“B”和“C”相关联。

此外，通常利用多种技术来用有限的键盘输入文本一但是当多于一个字母 数字字符与一特定键相关联时会出现歧义。例如，可实现多击(multiple-tap) 方法，其中用户按压一数字键多次以输入所需的字母或数字。因此，可按压“2” 键一次来输入数字2，按压两次来输入字母A，按压三次来输入字母B，而按 压四次来输入字母C。暂停和/或按下移动光标的键(例如，箭头键)可以帮助 在不同的字母数字字符之间作出区分。然而，这一技术通常是耗时的，且对于 用户而言是低效的，因为要按压单个键多次来输入单个字母数字字符。用数字 键输入文本的另一常见的方法是单击(single-tap)方法，其中用户按下与一所 需字母相关联的数字键一次。之后，所输入的字符例如通过将与一单词相对应 的字符序列匹配到储存在存储器中的序列来消除歧义。因此，为了输入单词 “cell”，用户可按压序列2-3-5-5，该序列可以与储存在存储器中的序列进行比 较。即使单击方法提供了输入文本的更高效方式，但是它也有缺陷。

通常，常规的web搜索和多字字轮(用于协助输入搜索查询)都是基于 可根据流行度准则和/或预定度量来对网页和查询排名的语言模型(或索引)的。 一般而言，这些应用程序的非本地版本将与一个通用语言模型交互，并且搜索 或字轮因此将向同一输入提供相同的答案而不管位置(例如，无论用户从西雅 图还是纽约启动相同的查询，都获得相同的结果)。语言模型组件通常可利用 任何语言模型(例如，在单词序列上定义的概率分布)。例如，可以利用三元 语法(trigram)语言模型。另外，可采用受限语言模型。根据一个示例，用于 web查询的语言模型可以基于查询以及与其相关联的概率的列表。根据另一示 例，可将基于音节元素构建的语言模型用于扩充隐式和/或显式通配符。

概述

以下提出了简化概述以便提供对在此描述的某些方面的基本理解。本概述 并不是对所要求保护的主题的全面综述。它既不旨在标识出所要求保护的主题 的关键或重要的要素，也不描绘其范围。其唯一的目的是以简化的形式来介绍 一些概念，作为稍后提出的更为详细的描述的序言。

本发明提供了基于人口统计对来自一语言的句子分类(例如，树结构形式 的查询日志及其基于时间、空间、其他用于人口统计等的平滑)以通过采用以 下组件来允许与预定人口统计准则相关联的本地字轮和本地web搜索，这些组 件包括：分类编码器组件(根据人口统计来形成句子分类，例如，树结构)； 本地语言模型编码器组件(产生对本地语言模型的相关联的编码)；以及解码 器组件，其基于分类结构和本地语言模型高效地找出对于用户给出的输入数据 (例如，搜索查询的一部分)的人口统计相关匹配。句子在语言模型中可具有 与不同的人口统计(例如，空间、时间等)相关联的的不同的概率。因此，对 于在一个地点的用户的输入数据的k个最佳扩充可不同于对于在另一个地点的 其他用户的相同输入的k个最佳扩充。这可允许基于人口统计准则执行高效的 查询或搜索，同时有效地使用系统资源。

编码器组件通过选择性地获得或挖掘句子(例如，基于诸如用户位置、时 间、其他人口统计信息等准则挖掘来自日志的查询)来利用存储在句子日志(例 如，查询日志)中的信息，并且基于分类格式(例如，采用具有根节点和叶的 树结构的形式，其中节点或叶可表示从可由定义诸如矩形形式的区域的经度和 纬度来标识的区域发出的查询)来归纳这些数据。这样的分类随后可通过将句 子移至与该分类相关联的不同层次来平滑，其中大多数用户感兴趣的句子移至 比特定人口统计的用户感兴趣的句子更高的层次，而后者移至该分类的较低层 次(例如，将诸如一个洲或一个国家的用户等绝大多数用户感兴趣的查询上移 至树的顶端；而诸如一个城市的用户、城市中的街坊的用户等少得多的用户感 兴趣的查询移至树的较低部分)。

根据一个特定方面，分类树结构可以是具有根据重要性准则的增强的平滑 的Kd树的形式。解码器组件然后可将这种树结构用于字轮和/或搜索以产生例 如本地、全国、或国际上感兴趣的结果。因此，每个节点可具有基于地点而对 其特制的语言模型，以便为由用户输入的显式/隐式通配符提供k个最佳扩充。

以下描述和附图详细阐明了所要求保护的主题的某些说明性方面。然而， 这些方面仅指示了可采用该主题的原理的各种方法中的几种，且所要求保护的 主题不旨在包括所有这些方面及其等效方面。结合附图阅读下面的详细描述， 则其他优点和新颖特征将变得清楚。

附图简述

图1示出了一示例性系统的框图，该示例性系统将来自句子的查询(例如， 查询日志)编码为分类树状结构并且将这一句子分类进一步编码为与该树结构 中的节点相关联的本地语言模型。

图2示出了根据本发明的一个方面的平滑的树结构。

图3示出了根据本发明的一个方面的一种编码以获得树结构的特定方法。

图4示出了根据本发明的一个方面的一种解码树结构的进一步的方法。

图5示出了可利用人工智能组件以便于平滑树结构的示例性编码器/解码 器系统。

图6示出了基于本地化语言模型组件的扩充输入数据的系统。

图7示出了根据本发明的一个方面的基于本地化语言将隐式通配符插入 到输入数据中的系统。

图8示出了一种帮助基于本地兴趣扩充输入数据的方法。

图9示出了根据所要求保护的主题的可被采用的示例性操作环境。

图10示出了其中可采用所要求保护的主题的各新颖方面的示例性联网环 境。

详细描述

现在参考附图描述本发明的各个方面，在全部附图中，用相同的附图标记 来指代相同的或相应的元素。然而应该了解，附图以及与其相关的详细描述并 非旨在把所要求保护的主题局限于所公开的具体形式。相反，其意图是覆盖落 在所要求保护的主题的精神和范围内的所有修改、等效和替换方案。

图1示出了系统100，该系统创建一种语言中的句子的分类，并基于地理 位置和/或人口统计准则进一步构造语言模型的相关联的本地版本，其中这些本 地语言模型根据所选人口统计准则可以是不同的粒度水平。一般而言，语言是 由语法生成的一组句子(也被称为字符串)。这样的语法可作为以下各种语法 而存在：有限状态语法；无上下文的语法；或仅仅一个列表(诸如来自查询日 志的查询列表等)。此外，语言模型将概率与该语言中的每句句子相关联。系 统100提供语言模型110的本地版本(1到n，n为整数)。语言模型的这一本 地版本(本地化语言模型110)是其中句子的概率取决于人口统计(例如，时 间、空间、其他用户人口统计等)的语言模型。如图1所示，不同人口统计粒 度的本地语言模型的构造通过由分类编码器组件104从句子102(例如，查询 日志)中创建的分类106(例如，树结构)的形式的编码，并通过使用句子分 类106以构造本地化语言模型的本地语言模型编码器108来促进。

通过利用经编码的分类结构和相关联的本地语言模型，解码器组件(未示 出)随后可通过混合来自不同人口统计粒度的本地语言模型的答案来允许本地 字轮和/或本地web搜索，如将在以下详述的。这一解码器组件能够根据分类 结构和利用该系统的用户的人口统计来混合特定语言模型以启用本地化字轮 和/或web搜索。例如，由位于西雅图的用户启动的对于“动物园”的搜索查询 可检索诸如西雅图动物园等答案(除了在离西雅图更远的地点的其他结果之 外)，这与利用非本地化语言模型的常规的搜索系统形成对比，其中这一常规 的搜索可能返回美国和/或世界上最受欢迎的动物园(并且通常不是位于西雅图 的动物园)。因此，本发明使对于在一个地点的用户的输入数据的k个最佳扩 充能够不同于对于在另一个地点的其他用户的相同输入的k个最佳扩充。这可 允许执行高效的查询或搜索，同时有效地使用系统资源。编码器组件104通过 从句子102中选择性地获得或挖掘查询(例如，基于诸如用户位置、时间、其 他人口统计信息等准则)来利用存储在这些句子102(例如，查询日志)中的 信息，并且以分类106(树结构)的形式来归纳这些数据。如图1所示，(示 出特定分类的)示例性树结构能够允许任意扇出和/或非叉分枝和深度。可以理 解，也可利用其他分类结构(除了树结构之外)并且这些结构也在本发明的范 围之内。

图2示出了根据本发明的一个特定方面的树结构200形式的分类的一个特 定方面。该结构中的任一节点可表示从可由定义该区域(例如，矩形形式的区 域)的经度和纬度来标识的区域发出的查询。节点出现在树200中的越下方， 该节点就覆盖越具体的区域。树结构200随后可通过基于重要性准则在节点之 间移动查询(例如，从节点207到其父节点204，然后从204到203，并且从 203到202)来平滑，其中最一般的查询/元素移向树200的根(例如，诸如一 个洲或一个国家的用户等相当大的人口统计用户组感兴趣的查询)，而小得多 的人口统计用户组(例如，一个城市、城市中的街坊的用户等)感兴趣的查询 驻留在树的较低部分。

树结构200可以是具有根据重要性准则的增强的平滑的Kd树的形式，如 将在以下详述的。查询的树结构可被本地语言模型组件用来基于地点构造语言 模型。因此，每个节点都可具有基于地点对其特制的语言模型。解码器组件因 此可将这种具有相关联的本地语言模型的树结构用于字轮以产生或混合例如 本地、全国、或国际上感兴趣的结果。结果可以是对于具有由用户输入的显式 /隐式通配符的文本串的k个最佳扩充的形式。

根据本发明的一个特定方面，可提供元素列表，其中每个元素可包含：频 率、查询、纬度、经度和其他人口统计。位置树可以是将世界(或将要覆盖的 预定区域)分成小块的二叉树的形式。本发明可在位于树中的不同层次的纬度 和经度上拆分之间交替。可创建拆分以使得对于元素的频率总和在该拆分的两 侧保持相同。因此，元素可根据对于这些元素的元素纬度和经度来被分成树中 的叶。

例如，叶210可对应于西雅图地区，而叶207可以是迈阿密地区。叶210 因而可包含与这一位置相关的所有查询及其频率。在理论上，语言模型可在每 个位置处构建，并且然后可根据输入文本的用户的位置来选出合适的语言模型 以加以利用。这一方法可通过创建经调整的位置树来增强，其中叶上分布的元 素通过(递归地)在树中向上提升类似的元素来变稀少。如果对于两个兄弟节 点(例如，206、207)中的相同查询的频率类似，但不一定相等，则这两个元 素将都被提升至其位置树中各自的父节点。因此，对于这种情况，提升通过删 除兄弟节点中的元素(等同于将频率设置为0)，并且然后改为将该元素插入 (仍然具有与兄弟节点中的实际频率的总和相等的频率的)父节点中来执行。 否则，如果频率不类似，则具有最低频率的兄弟节点可通过将该元素插入具有 等于这两个频率中的最小者的两倍的频率的父节点中，并且然后从这两个兄弟 节点中减去这一频率(将最低频率兄弟节点的频率设为0，从而实际上从这一 兄弟节点删除该元素)来提升。可以理解，一般而言，当决定兄弟节点的提升 时可采用对于频率相似性的任何合理的测试，并且这一选择可部分取决于例如 应用。

此外，可以实现“符号测试”，其返回分配给较低的频率在它们是等可能的 假设下比较高的频率低的替换假设的(单方面的)重要性等级。这一假设(H0) 因此可规定具有p＝0.5的二项式分布，并且重要性等级等于可对于较低频率(例 如，<＝50)计算的(单方面的)二项式拖尾。对于较高的频率，该二项式分布 可由正态分布来高效地逼近。因此，该重要性等级可决定元素从较局部节点(例 如，206、207)向较全局节点(例如，204)(从叶向根)的提升程度。在较 低重要性等级的情况下更难以违犯两个频率是相似的H0假设，并且在这种情 况下元素更有可能在位置树中向上移动。单个重要性等级可用于通常位置树中 的所有测试。或者，重要性等级可通过采用重要性等级调整以类似于Bonferroni 的样式来调整，其中：

$\alpha \left(D\right)=1-{0.95}^{\left(\frac{1}{2^{(D-1)}}\right)}$

其中α是所选的重要性等级，且D是树的深度，例如：

α(1)＝0.05

α(2)＝0.0253

α(15)＝3.13e-6

给定根据以上提升模式的元素的重新分布，可对于位置树中的每个节点创 建一语言模型。对于低重要性等级，位于该结构中的许多叶节点处的语言模型 通常小得多并且只包含真正的本地信息。随着一个节点在树中上移，语言模型 覆盖更大的区域并且根将包含在不考虑位置的情况下等可能的信息。例如，查 询“pizza”将很可能出现在根节点，而一地点特有的“Joe’s pizza joint”将出现在 对应于这个非常具体的匹萨地方的位置的叶中。

位置树200可具有位于树中每个节点处的本地化语言模型。这些本地化语 言模型中的每一个可以是相同类型的；因为对于一般/非本地通配物 (WildThing)(或搜索)，还有各个模型所采用的类型通常相当小。因此， 解码器可利用语言模型的位置树来检索对于文本输入的k个最佳匹配。例如， 给定一特定位置，本发明能够在从(与该特定人口统计位置相关联的)树的叶 节点到该树的根节点的路径上的每个节点中找出k个最佳匹配及其频率。可采 用与对于一般通配物(或搜索)相同的方法来在位于特定节点的模型中找到匹 配，该方法是通过引用结合于此的，2006年1月17日提交的第11/332,954号 和第11/333,846号专利中的方法。k个最佳匹配中的某一些在不同的节点中可 以是相同的，而其他最佳匹配不是。对于出现在一个节点而不是另一个节点中 的k个最佳匹配中的匹配，这些匹配及其相关联的频率必须在它们没有出现在 k个最佳匹配中的节点中逐一查找。对于所有唯一的匹配，在该组匹配中，现 在可添加每个节点中的匹配的频率，且在本地化树中的中间节点获得的频率具 有折扣，以便反映对该特定位置的平均贡献。这些折扣频率可按照

Frequency<-frequency/(2^L)来计算，

其中L是从中间节点到叶节点的路径长度。

如早先所解释的，本发明并不限于地理位置，并且还可采用诸如时间、时 间和空间、及其他人口统计准则等其他准则。因此最一般的查询可移至树的顶 端，诸如将大多数人口统计用户组感兴趣的查询(例如，一个洲或一个国家的 用户所感兴趣的查询等)上移至树结构的顶端；而诸如一个城市、城市中的街 坊的用户等少得多的人口统计用户组感兴趣的查询移至树的较低部分。

图3示出了根据本发明的一个方面的相关方法300。虽然在此将该示例性 方法图示并描述为代表各种事件和/或动作的一系列框，但是本发明不受所示的 这些框的次序的限制。例如，根据本发明，除了在此示出的次序之外，某些动 作或事件可以按不同的次序发生和/或与其他动作或事件同时发生。此外，不是 所有示出的框、事件或动作都是实现根据本发明的方法所必需的。此外，将会 认识到，根据本发明的该示例性方法和其他方法可以与在此图示并描述的方法 相关联地实现，也可与未示出或描述的其他方法和装置相关联地实现。最初， 在302处，可从语言(例如，从查询日志中收集的查询)中收集句子，其中随 后在304处基于人口统计对于这些句子进行分类(例如，基于发出这些查询的 地理位置来将这些句子分布在节点中以形成树结构)。可以理解，基于地理位 置的查询分布表示示例性准则，并且也可采用其他人口统计准则来进行这种节 点中的分布和树形成。在306处，可基于这一分类来归纳来自句子的数据(例 如，以树结构的形式归纳查询日志)。随后在308处，然后可通过基于重要性 准则在不同层次之间移动句子(例如，将查询从位于树的较低部分的节点移至 较高部分)来平滑这一分类(例如，树结构)。

图4示出了根据本发明的一个方面的平滑树形式的特定分类的特定方法 400。最初在402处，可标识子节点。随后在404处，基于预定准则(例如， 重要性测试准则)比较共享一父节点的子节点，以便验证这些节点中的查询中 的某一些是否应被提升到树的上方。在406处，确定一个节点中的查询频率是 否比兄弟子节点中的查询频率大得多。如果对于一查询的计数在两个子节点中 的一个中大得多，(如基于预定准则所计算的)，则在410处，可部分地提升 对于这一查询的计数，诸如从两个兄弟节点提升对于兄弟节点中的查询的最低 计数。例如，如果最左边的兄弟节点获得对于一特定查询的计数3并且最右边 的兄弟节点具有对于相同查询的计数13，则计数3从这些兄弟节点中的每一个 上移至父节点，因此将计数6留在与兄弟节点相关联的父节点中。这样的部分 提升导致最右边的兄弟节点随后包括10个计数，而最左边的兄弟节点具有计 数0。或者，如果子节点中的查询的比较指示相对相等的计数(或低于预定阈 值的差值)，则将对于该查询的计数从这两个子节点提升至父节点。因此，用 于上移节点的重要性准则可类似于例如用户之间的流行度准则。一般而言，最 上面的根节点将覆盖对于所有用户都流行的查询(例如，不管用户人口统计如 何)。可以理解，当确定兄弟节点的提升时可采用对于频率相似性的任何合理 的测试(例如，取决于应用)。

在一相关方面中，可使用人工智能(AI)组件来帮助从查询日志中创建经 平滑的树。如此处所使用的，术语“推断”通常指的是根据经由事件和/或数据捕 获的一组观察结果来推出或推断系统、环境、和/或用户状态的过程。例如，推 断可用于标识特定的上下文或动作，或可生成状态的概率分布。推断可以是概 率性的，即，基于对数据和事件的考虑计算所关注状态的概率分布。推断也可 以指用于从一组事件和/或数据合成更高级事件的技术。这类推断导致从一组观 察到的事件和/或储存的事件数据中构造新的事件或动作，而无论事件是否在相 邻时间上相关，也无论事件和数据是来自一个还是若干个事件和数据源。

图5示出了人工智能组件510，它可与(帮助根据其在节点的分类结构中 的位置来移动句子以及构造相关联的本地语言模型的)编码器组件502和(如 将在以下详细描述的，帮助根据所构造的编码来扩充用户的输入的)解码器组 件504交互。例如，可经由自动分类器系统和过程来促进用于确定何时将句子 提升至分类(例如，树结构)的上方的过程。分类器是将输入属性矢量x＝(x1， x2，x3，x4，xn)映射到该输入属于一个类的置信度的函数，即f(x)＝ confidence(class)。这一分类可采用基于概率和/或基于统计的分析(例如，分解 成分析效用和成本)来预测或推断用户期望自动执行的动作。

支持矢量机(SVM)是可采用的分类器的一个示例。SVM通过找出可能 输入空间中的超曲面来操作，其中，超曲面试图将触发准则从非触发事件中分 离出来。直观上，这使得分类对于接近但不等同于训练数据的测试数据是正确 的。可采用其它定向和非定向模型分类方法，包括，例如，朴素贝叶斯、贝叶 斯网络、决策树、神经网络、模糊逻辑模型以及提供不同独立性模式的概率分 类模型。此处所使用的分类也包括用于开发优先级模型的统计回归。

如从本说明书中可以容易地理解，本发明可以使用显式训练(例如，经由 一般训练数据)以及隐式训练(例如，经由观察用户行为、接收外来信息)的 分类器。例如，SVM经由分类器构造器和特征选择模块内的学习或训练阶段 来配置。因此，可使用分类器来自动地学习和执行多个功能，包括但不限于根 据预定准则来确定何时更新或细化先前推断的模式，基于正在处理的数据种类 使关于推断算法的准则更严格，以及一天中何时实现更严格的准则控制。

图6示出了基于本地化语言模型组件606的扩充输入数据的系统600。本 地化语言模型组件606通常能够将一般答案与本地用户相当感兴趣的本地答案 相混合。这样的本地化语言模型组件606包括其中句子的概率取决于人口统计 (例如，时间、空间、其他用户人口统计等)的一系列语言模型。一般而言， 本地语言模型组件中的语言模型全都能够遵照给定的人口统计，但仍能够在其 人口统计地点/通用性中有所变化，以便允许混合具有不同的地点程度的答案。 例如，对于树结构形式的分类，本地语言组件通常可涉及与从树中的叶(特定 人口统计位置)到树的根(全部节点所共享的一般人口统计位置)的路径上的 节点相关联的所有本地化语言模型。

系统600可包括获得输入数据的接口602以及利用该输入数据来生成候选 扩充数据列表的扩充组件604。接口602可以从任何类型的输入设备(未示出) 接收输入数据。例如，输入数据可由个人计算机、膝上型计算机、手持式计算 机、蜂窝电话、服务器等生成。可以理解，接口602和/或扩充组件604可以耦 合到输入设备、可以全部或部分地包括在输入设备中、和/或可以是独立的组件。

一般而言，任何类型的输入数据都可由接口602接收。例如，当用户采用 个人计算机时，接口602可以获得与用户按下的键相关联的字母数字字符。另 外，可采用语音识别来分析用户的口头输入和/或可利用手写识别来标识书面数 据；由此，接口602可以接收听觉和/或视觉数据。作为进一步的说明，接口 602可以接收与蜂窝电话键区相关联的数字字符，其中每一数字字符可以与多 个字母数字字符相关。

输入数据可以包括一个或多个显式通配符。通配符可以由“^*”来表示；然 而，通配符的任何完全不同的表示也落入所要求保护的主题的范围之内(例如， 除了^*，任何其它字符可以被用作通配符，如声音、记号、……)。显式通配 符可以被包括在输入数据内的任何地方。由此，例如，如果用户希望输入单词 “Lincoln”，则输入“Linc^*n”可以用与个人计算机相关联的键盘来键入并提供给 接口602。根据另一说明，用户可发出“m-星号-t”的声音，并且该输入数据可 被提供给扩充组件604，后者还可利用语音识别来将输入数据标识为“m^*t”。

在获得了输入数据之后，接口602可以将输入数据提供给扩充组件604。 如早先所解释的，扩充组件604可包括允许采用基于人口统计提供与输入数据 相关联的通配符的可能扩充的语言模型的语言模型组件606。由此，通过利用 该本地化语言模型及其分类结构，扩充组件604可以扩充与输入数据相关联的 显式通配符以生成候选扩充数据列表。此外，扩充组件604可以将隐式通配符 插入到输入数据中，其中可以类似地扩充这些隐式通配符。可采用作为本地化 语言模型组件606的一部分的本地化语言模型及其分类结构来找到k个最佳扩 充，其中对于在一个地点的用户的输入数据的k个最佳扩充可不同于对于在另 一个地点的用户的相同输入的k个最佳扩充。此外，可频繁地更新本地化语言 模型组件606所使用的本地化语言模型以允许及时地标识出突发新闻报导。

尽管接口602被描绘为与扩充组件604分开，但是可以构想扩充组件604 可包括接口602或其一部分。并且，接口602可以提供各种适配器、连接器、 通道、通信路径等以便允许与扩充组件604交互。

扩充组件604产生之后可被利用的候选扩充数据列表的本地兴趣。例如， 该候选列表的本地兴趣可以被显示给用户(例如，经由接口602)，和/或用户 可从这些本地兴趣中作出选择。从该候选列表中所选的扩充可以用于执行搜 索、可被输入到所撰写的文档或消息中、可被插入到地址栏中等等。可以构想， 接口602可以提供如图所示的候选扩充数据列表(例如，提供给用户、给输入 设备......)。扩充组件604或一完全不同的组件(未示出)可以输出该候选列 表。例如，该本地化候选列表可包括k个最佳扩充。

图7示出了将隐式通配符插入到输入数据中的系统700。系统700包括接 收输入数据并将输入数据提供给扩充组件702的接口704。扩充组件704可以 扩充输入数据以产生一本地扩充数据候选列表。例如，可用扩充组件704来生 成k个最佳扩充。扩充可以至少部分地利用由本地化语言模型组件706提供的 语言模型及其分类结构来实现。

扩充组件704还可以包括可将一个或多个隐式通配符插入到输入数据中 的通配符插入组件708。可以理解，通配符插入组件708可以将隐式通配符定 位在输入数据中的任何地方。在插入了隐式通配符之后，可以基于本地化语言 模型来扩充输入数据中的隐式通配符以及任何显式通配符。

在一相关方面，通配符插入组件708可以标识输入数据中的期望单词的末 尾。例如，通配符插入组件708可以在这一标识的位置处插入一通配符。可以 理解，可以确定多个这样的位置，并且因此可以随输入数据包括任何适当数量 的隐式通配符。通配符插入组件708可以通过标识空格以及输入数据的末尾来 定位期望单词的末尾，并在输入数据内的这些位置的每一个之前插入一隐式通 配符。

通配符插入组件708和/或扩充组件704可允许字轮。例如，用户可在诸 如蜂窝电话或PDA等具有有限键盘能力的移动设备上输入数据，其中该有限 的键盘能力可能与字母数字字符的低效和/或耗时输入相关联。另外，字轮可以 补偿用户不知道期望输入的正确拼写。此外，字轮可以帮助对于对输入的查询 仅有模糊概念(例如，在web搜索的上下文中)或对当前什么是流行的感到好 奇的用户，并且因此匹配一部分输入。

图8示出了帮助基于本地兴趣来扩充输入数据的方法800。最初，在802 处，可获得输入数据，其中，例如，可以对任何类型的输入设备(例如，台式 计算机、膝上型计算机、手持式计算机、蜂窝电话、服务器......)接收这些输 入数据。另外，输入数据可以与搜索查询、文本消息(例如，短消息服务(SMS) 消息)、即时消息、所生成和/或编辑的文档等有关。此外，这些输入数据可包 括例如字母字符、数字字符、手写数据、口头数据、其组合。在804处，可将 一个或多个隐式通配符插入到输入数据中。例如，隐式通配符可以被插入到输 入数据的末尾处。

此外，隐式通配符可以被插入到输入数据内的一个或多个期望单词的末尾 处。例如，隐式通配符可以被插入在输入数据中的每一空格之前。在806处， 可采用本地化语言模型及其分类结构。本地化语言模型中的句子的概率取决于 人口统计(例如，时间、空间、其他用户人口统计等)。因此，对于在一个地 点的用户的输入数据的k个最佳扩充可与对于在另一个地点的其他用户的相同 输入的k个最佳扩充不同。随后，可生成与输入数据相关联的通配符的k个最 佳扩充，它能够与本地兴趣相关。例如，在808处，给定一特定位置，本发明 能够确定在从(与该特定人口统计位置相关联的)树的叶节点到该树的根节点 的路径上的每个节点中k个最佳匹配及其频率，且随后组合这k个最佳匹配。

在此使用词语“示例性”意指用作示例、实例或说明。在此被描述为“示例 性”的任何方面或设计并不一定要被解释为相比其他方面或设计更优选或有 利。类似地，在此提供的示例只是出于清楚和理解的目的并且并不意味着以任 何方式限制本发明或其部分。可以理解，本可呈现多个其他或替换示例，但已 出于简明的目的而省略了。

此外，本发明的全部或部分可以使用产生控制计算机以实现所公开的本发 明的软件、固件、硬件或其任意组合的标准编程和/或工程技术而被实现为于系 统、方法、装置或制品。如在本申请中所使用的，术语“组件”旨在表示计算机 相关的实体，它可以是硬件、硬件和软件的结合、软件、或者执行中的软件。 例如，计算机可读介质可以包括但不限于磁存储设备(例如，硬盘、软盘、磁 带......)、光盘(例如，紧致盘(CD)、数字多功能盘(DVD)......)、智 能卡和闪存设备(例如，卡、棒、钥匙驱动器......)。另外可以理解，可以采 用载波来承载计算机可读电子数据，例如那些用于发送和接收电子邮件或用于 访问如因特网或局域网(LAN)等网络的数据。当然，本领域的技术人员将会 认识到，在不背离所要求保护的主题的范围或精神的前提下可以对这一配置进 行许多修改。

为给所公开的主题的各方面提供上下文，图9和10以及下列讨论旨在提 供可以在其中实现所公开的主题的各方面的合适的计算环境的简要、概括的描 述。尽管前面已经在运行在一个和/或多个计算机上的计算机程序的计算机可执 行指令的一般上下文中描述了本发明，然而本领域内的技术人员将认识到，本 发明也可以和其他程序模块结合实现。一般而言，程序模块包括执行特定任务 和/或实现特定抽象数据类型的例程、程序、对象、数据结构等等。此外，本领 域内的技术人员将会理解，本发明的方法可以与其他计算机系统配置一起实 施，包括单处理器或多处理器计算机系统、小型计算设备、大型计算机以及个 人计算机、手持式计算设备(例如，个人数字助理(PDA)、电话、手表……)、 基于微处理器的或可编程的消费性或工业电子产品等等。所示各方面也可以在 其中任务由通过通信网络链接的远程处理设备执行的分布式计算环境中实践。 然而，所要求保护的本发明的一些方面，如果不是全部方面，可以在独立计算 机上实施。在分布式计算环境中，程序模块可以位于本地和远程存储器存储设 备中。

参考图9，用于实现在此公开的各方面的示例性环境910包括计算机912 (例如，台式计算机、膝上型计算机、服务器、手持式计算机、可编程消费或 工业电子产品……)。计算机912包括处理器单元914、系统存储器916、以 及系统总线918。系统总线918把包括但不限于系统存储器916的系统组件耦 合到处理单元914。处理单元914可以是各种可用处理器中的任意一种。双微 处理器和其它多处理器体系结构(例如，多核)也可用作处理单元914。

系统总线918可以是几种类型的总线结构中的任意一种，包括存储器总线 或存储器控制器，外围总线或外部总线，和/或利用下述可用总线结构中的任意 一种的局部总线，包括但不限于，11位总线、工业标准体系结构(ISA)、微 通道体系结构(MCA)、扩展ISA(EISA)、智能驱动器电子接口(IDE)、 VESA局部总线(VLB)、外围部件互连(PCI)、通用串行总线(USB)、 高级图形端口(AGP)、个人计算机存储卡国际联合会总线(PCMCIA)、以 及小型计算机系统接口(SCSI)。

系统存储器916包括易失性存储器920以及非易失性存储器922。基本输 入/输出系统(BIOS)包含诸如在启动期间在计算机912的元件之间传送信息 的基本例程，其存储在非易失性存储器922中。作为说明而非限制，非易失性 存储器922可以包括只读存储器(ROM)、可编程ROM(PROM)、电可编 程ROM(EPROM)、电可擦除ROM(EEPROM)或者闪存。易失性存储器 920包括用作外部高速缓冲存储器的随机存取存储器(RAM)。

计算机912还包括可移动/不可移动、易失性/非易失性计算机存储介质。 例如，图9示出了大容量或辅助存储924。大容量存储924包括但不限于诸如 磁盘驱动器、软盘驱动器、磁带驱动器、Jaz驱动器、Zip驱动器、LS-100驱 动器、闪存卡、或者记忆棒之类的设备。此外，大容量存储924可以包括独立 的或者与其它存储介质结合的存储介质，包括但不限于诸如紧致盘ROM设备 (CD-ROM)、可记录CD驱动器(CD-R驱动器)、可重写CD驱动器(CD-RW 驱动器)或者数字多功能盘ROM驱动器(DVD-ROM)这样的光盘驱动器。 为了便于将大容量存储设备924连接到系统总线918，通常使用诸如接口926 等可移动或不可移动接口。

可以理解，图9描述了在用户和在合适的操作环境910中描述的基本计算 机资源之间担当中介的软件。这样的软件包括操作系统928。可存储在大容量 存储928上并加载到系统存储器916的操作系统928用于控制并分配计算机系 统912的资源。系统应用程序930通过存储在系统存储器916中或大容量存储 924上的程序模块932和程序数据934来利用操作系统928对资源的管理。可 以理解，本发明可用各种操作系统或操作系统的组合来实现。

用户通过输入设备936把命令或信息输入到计算机912中。输入设备936 包括但不限于，诸如鼠标、跟踪球、指示笔、触摸垫等定点设备、键盘、话筒、 操纵杆、游戏手柄、圆盘式卫星天线、扫描仪、TV调谐卡、数码相机、数码 摄像机、网络摄像头等等。这些以及其它输入设备通过系统总线914经由接口 端口938连接至处理单元918。接口端口938包括，例如串行端口、并行端口、 游戏端口、以及通用串行总线(USB)。输出设备940利用和输入设备936相 同类型的某些端口。因此，例如，USB端口可用于向计算机912提供输入，以 及将来自计算机912的信息输出到输出设备940。提供输出适配器942是为了 说明除了输出设备940之外还有一些像显示器(例如，平板、CRT、LCD、等 离子……)、扬声器、以及打印机这样的需要专用适配器的输出设备940。输 出适配器942包括，作为说明而非局限，提供输出设备940和系统总线918之 间的连接手段的显卡和声卡。应该注意到，其它设备和/或设备系统同时提供了 输入和输出能力，诸如远程计算机944。

计算机912可以使用至诸如远程计算机944等一个或多个远程计算机的逻 辑连接在网络化环境中操作。远程计算机944可以是个人计算机、服务器、路 由器、网络PC、工作站、基于微处理器的电器、对等设备或者其它常见的网 络节点等，且通常包括相对于计算机912所描述的很多或者全部元件。为了简 明起见，对远程计算机946仅示出了存储器存储设备944。远程计算机944经 由网络接口948被逻辑地连接到计算机912，并且然后经由通信连接950物理 地连接(例如，有线或无线地)。网络接口948涵盖诸如局域网(LAN)和广 域网(WAN)这样的通信网络。

通信连接950指的是用于把网络接口948连接到总线918的硬件/软件。 虽然为了清楚地举例说明，通信连接950被示为在计算机916的内部，但其也 可以在计算机912的外部。连接到网络接口948所需要的硬件/软件包括(仅为 了举例说明)内部和外部技术，诸如包括常规电话级调制解调器、电缆调制解 调器、电源调制解调器以及DSL调制解调器的调制解调器、ISDN适配器、和 以太网卡或组件。

图10是本发明可与其交互的示例计算环境1000的示意框图。系统1000 包括一个或多个客户机1010。客户机1010可以是硬件和/或软件(例如，线程、 进程、计算设备)。系统1000也包括一个或多个服务器1030。因此，系统1000 可以对应于两层客户机服务器模型或多层模型(例如，客户机、中间层服务器、 数据服务器)以及其他模型。服务器1030也可以是硬件和/或软件(例如，线 程、进程、计算设备)。服务器1030可以容纳各线程以通过例如利用本发明 执行转换。在客户机1010和服务器1030之间的一种可能的通信能够采用在两 个或多个计算机进程之间传输的数据分组的形式。

系统1000包括可以用来使客户机1010和服务器1050之间通信更容易的 通信框架1030。客户机1010操作上被连接到一个或多个可以用来存储对客户 机1010本地的信息的客户机数据存储1060。同样地，服务器1030操作上被连 接到一个或多个可以用来存储对服务器1040本地的信息的服务器存储1030。 作为示例而非限制，如上所述的匿名化系统及其变体可作为对于至少一个服务 器1030的web服务来提供。该web服务也可与多个其他服务器1030以及相 关联的数据存储1040通信地耦合，使其可用作对于客户机1010的代理。

以上所已经描述的内容包括所要求保护的主题的各方面的例子。当然，出 于描绘所要求保护的主题的目的而描述每一个可以想到的组件或方法的组合 是不可能的，但本领域内的普通技术人员应该认识到，所要求保护的主题的许 多进一步的组合和排列都是可能的。因此，所公开的主题旨在涵盖落入所附权 利要求书的精神和范围内的所有这些改变、修改和变动。此外，就在说明书或 权利要求书中使用术语“包含”、“具有”或“含有”及其形式上的变体而言，这 些术语旨在以与术语“包括”在被用作权利要求书中的过渡词时所解释的相似 的方式为包含性的。