使用概括的句子搭配的检索的制作方法
专利名称：使用概括的句子搭配的检索的制作方法
使用概括的句子搭配的检索对相关申请的交叉引用本申请要求于2008年11月3日提交的名称为“RETRIEVAL USING A GENERALIZED SENTENCE COLLOCATION(使用概括的句子搭配的检索)，，的第61/110，892号美国临时专利申请的利益，该申请的全部内容通过引用结合于此。
背景技术：
因特网、特别是万维网(“web”)已经通过其因特网浏览器使海量的信息对用户可用。尽管这些信息对用户而言是可容易访问的，但是信息多得以至于在用户尝试标识什么信息与其需求相关时出现问题。该问题被称为信息爆炸问题。已经开发出搜索引擎服务以帮助用户找出与其需求相关的信息。这些搜索引擎服务允许用户搜索用户可能感兴趣的显示页面，比如网页。在用户提交包含搜索项的搜索请求(即查询)之后，搜索引擎服务标识可能与这些搜索项相关的网页。为快速标识相关的网页，搜索引擎服务可以维护关键词到网页的映射。该映射可以通过对web进行爬寻(crawling)以标识出每个网页的关键词来生成。为了对web进行爬寻，搜索引擎服务可以使用根网页列表来标识出可通过这些根网页来访问的所有网页。任一特定网页的关键词都可以使用各种公知的信息检索技术来标识，比如标识标题行的文字、在网页的元数据中所提供的文字、突出显示的文字等等。搜索引擎服务基于网页的关键词与查询的文字的匹配程度来标识可能与搜索请求相关的网页。 搜索引擎服务随后将到所标识出的网页的链接以基于排名的顺序向用户显示，该排名可以由所标识出的网页与查询的相关度、流行度、重要性和/或其它度量来确定。
尽管，这种搜索感兴趣的信息的通用方法在许多情况中都有用，但在某些情况中， 它们还是存在问题。一种这样的情况在以一种语言为母语的人在以另一种语言进行书写时寻求帮助的时候出现。例如，以中文为母语的人在以英语书写文档时可能会发现难以识别表达他们意图的最适当的英文词。虽然，这些人可以向搜索引擎服务提交查询以检索网页， 这些网页具有可能有助于确定合适的词的句子，但这些人可能甚至不知道任何在意思上类似的英文词，这导致关键字搜索变得困难。例如，如果这些人想要表达“they are happy with life”(他们生活得很快乐)，这些人可能知道句子应该具有词“I”(我)和“life”(生活)，但可能不知道词“enioy”(享受)和“like”(喜欢)可能是用于形成句子“I enjoy life”(我享受生活)或“I like life”(我喜欢生活)的句子的合适的词。如果这些人向搜索引擎服务提交查询“I life”(我生活)，搜索结果很可能包括有关“iLife”软件产品、“life(生活)”的定义、life-skills(生存技巧)训练等等的引用。然而，这些结果未必包括将有助于用户识别用于表达其意思的合适的词的样本句子。
另一种情况在一个人搜索有关某个话题的文档，但使用了可能不能精确表达他们的意图的一系列简单的关键字的时候出现。例如，正在研究政府实体的收入的来源的人可能想要编纂用于不同类型的税(tax)的通用名字列表，例如所得税、房地产税、遗产税、车船禾兌、销售禾兌(income tax, real estate tax, death tax, vehicle tax, sales tax)等等。 此人可以提交看上去精确描述其兴趣的查询“税的通用名称”。在这种情况，搜索引擎服务很可能返回有关通用法律婚姻(common law marriages)的名字和税问题的文档、以包括税的价格出售的有关通用名和学名的书等等。然而，这样的文档并不是对税的通用名字感兴趣的人所在意的。
发明内容
提供了一种用于识别有关指定词类的查询的文档的方法和系统。一种检索系统从用户接收包括词和词类的输入查询。一旦接收到包括词和词类的输入查询，所述检索系统识别具有包括该词的句子的文档，该词与作为该词类的一词相搭配。所述检索系统向用户显示所识别的文档的指示。所述检索系统允许用户在输入查询时将词类适当用作通配符以指定他们的意图。
提供本发明内容是为了以精简的形式介绍将在以下详细描述中进一步描述的一些概念。本发明内容并不旨在标识出所要求保护的主题的关键特征或必要特征，也不旨在用于帮助确定所要求保护的主题的范围。
图1是在检索系统的一些实施例中说明使用输入查询的句子搜索的显示页面，所述输入查询使用词类作为通配符。
图2是在检索系统的一些实施例中说明使用输入查询的网页搜索的显示页面，所述输入查询使用词类作为通配符。
图3是示出一些实施例中的检索系统的组件的框图。
图4是示出一些实施例中的检索系统的搭配存储的组件的框图。
图5是例示一些实施例中检索系统的生成搭配存储组件的处理的流程图。
图6是例示一些实施例中检索系统的更新搭配索引组件的处理的流程图。
图7是例示一些实施例中检索系统的查找匹配句子组件的处理的流程图。
具体实施例方式提供了一种用于识别有关指定词类的查询的文档的方法和系统。在一些实施例中，一种检索系统从用户接收包括词和词类的输入查询。例如，输入查询可以指定为 “(adjeCtiVe)taX”((形容词)税)。这个输入查询可以表示一个人查找税的通用名字的意图，它通常具有其后跟随有词“tax”(税)的形容词。检索系统使用术语“ (adjective) ”(形容词)来表示用于用作在词“tax”(税)之前的形容词的任意词的通配符。一旦接收到包括词和词类的输入查询，所述检索系统识别具有包括所指定的词的句子的文档，所指定的词与作为词类的词相搭配。例如，检索系统可以识别包含下述句子的文档 Most Americans pay their income tax on April 15(大多数美国人在 4 月 15 日支付他们的所得税)。
Congress voted to limit the death tax (国会投票限制遗产税)。
第一个句子包括与词“tax”(税)相搭配的形容词“income”(所得)，并且，第二个句子包括与词“tax”(税)相搭配的形容词“death”(遗产)。然而，检索系统不会基于下述句子来识别文档
5 Many levels of government tax small businesses unfairly(多级政府对小商业团体不公平地征收税)。
It is our obligation to pay upon his death tax for his estate (一旦ftk去世了，为他的财产付税是我们的责任)。
这两句句子中任一一个都不包括与词“tax”(税)相搭配的形容词。虽然，词 “government”(政府)和“death”(去世)可以在某些上下文中用作形容词，但在这些句子中它们被用作名词，而非描述词“tax”(税)的形容词。作为另一个实例，用户可以输入查询“I v. life，”(我动词生活)，其中“V.”表示用于作为动词的词的通配符。在这种情况下，检索系统对包含其后跟随有动词的词“ I ”(我)，所述动词后面跟随有词“ life”(生活)的文档中的句子进行搜索。例如，检索系统可以识别包含下述句子的文档 I enjoy life (我享受生活)。
I like life (我喜欢生活)。
在这两个句子中，词“enjoy”(享受)和“like”(喜欢)是动词。所述检索系统向用户显示所识别的文档的指示。通过这种方式，用户可以将词类适当用作通配符以指定他们的意图。
在一些实施例中，检索系统可以用于在人们以其母语以外的语言书写文档时帮助人们搜索词。例如，以中文作为母语的人可能想要找到表达他们生活快乐(their happiness with life)的英文动词。以英文为母语的人知道动词“enjoy”(享受)和 “like”(喜欢)可能是合适的动词——但以中文作为母语的人却可能并不知道这点。检索系统允许人们输入包括将词类作为通配符和一个或多个词(例如"Iv. life"(我动词生活))的输入查询，并返回匹配该输入查询的句子(例如“I enjoy life”(我享受生活)和“I like life”(我喜欢生活))。以中文作为母语的人随后可以基于这个动词的定义决定合适的动词，所述动词的定义是从该句子中围绕该词的上下文中或从字典中推断出来的。
在一些实施例中，检索系统可以生成搭配词和词类的映射以帮助识别匹配输入查询的句子。检索系统可以使用自然语言处理器来处理句子集合中的句子以识别每个句子中的词的词类。例如，自然语言处理器可以将句子"I enjoy life"(我喜欢生活)中的词分别识别为代名词、动词和名词。自然语言处理器可以通过识别主语、谓语、宾语等来最初确定每个句子的结构。自然语言处理器随后可以基于句子的结构识别该句子的每个词的词类。词的词类被认为是该词的概括。检索系统随后识别每个句子中的搭配词对。例如，句子〃 I enjoy life"(我喜欢生活)包括搭配词(Lenioy)和(enjoy, life), BP (我，享受)和(享受，生活)。检索系统随后为每个搭配词对生成两对词类和词。例如，检索系统可以为搭配词(I，enioy)生成(pronoun，enjoy)和(I，verb)的词类和词对，即为搭配的词 (我，享受)生成(代名词，享受)和(我，动词)的词类和词对，并为搭配词(enjoy，life) 生成(verb，life)和(enjoy，noun)的词类和词对，即为搭配的词(享受，生活)生成(动词，生活)和(享受，名词)的词类和词对。检索系统可以创建包括所生成的每个词类和词的对的条目的索引。每个条目识别集合中包括该词类和词的对的句子。通过这种方式，检索系统可以快速地识别包含匹配输入查询的词类和词的对的句子。
图1是说明在检索系统的一些实施例中使用输入查询的句子搜索的显示页面，所述输入查询使用词类作为通配符。显示页面100包括输入查询文本框101、执行按钮102和结果区域103。用户将具有用于词类的通配符的查询输入到文本框中并选择执行按钮来提交该查询。检索系统识别与查询匹配的句子并将结果显示在结果区域中。在本实例中，用户输入查询“I v. life”(我动词生活)以搜索包括有词“I”(我)其后是一个动词随后是词“life”(生活)的句子。结果区域中的每个句子使用不同的动词(即enjoy (享受)， like(喜欢)，love(爱)，hate(恨))与查询匹配。在一些实施例中，检索系统可以允许用户从结果区域中选择一词以查看该词的定义。例如，如果用户选择了词"enjoy"(享受)， 检索系统可以显示词"enjoy"(享受)的定义。在一些实施例中，检索系统可以允许用户从结果区域中选择整句句子以在从中提取该句子的文档的上下文中(如果存在的话)查看该句子。
图2是说明在检索系统的一些实施例中使用输入查询的网页搜索的显示页面，所述输入查询使用词类作为通配符。显示页面200包括输入查询文本框201、执行按钮202 和结果区域203。用户将具有用于词类的通配符(例如“v. ”(动词))的查询输入到文本框中并随后提交该查询。检索系统识别包含匹配该查询的句子的网页并将到所识别的网页的链接显示在结果区域中。每个链接可以由匹配该查询的网页中的短语来标识。每个链接还可以由取自该网页的附加上下文来标识。在本实例中，用户输入查询"attorneys v. client"(代理人动词客户)以搜索包括有词“attorneys”(代理人)其后是一个动词随后是词“client”(客户)的句子。在结果区域中所识别的每个网页包括使用不同动词 (即“advise(建议)，bill(开帐单)，trust(相信)以及fire(解雇)”)匹配该查询的句子。
在一些实施例中，检索系统可以基于所识别的网页与查询的相关性、流行性、重要性和/或一些其他的度量来对它们进行排名。用户可以选择结果区域中的链接以查看包含与查询匹配的句子的网页。检索系统可以允许使用词类作为通配符，例如形容词、副词、 连接词、感叹词、名词、介词、代名词和动词。例如，用户可以输入查询“adj. tax”(形容词税)来寻找其后跟着词“tax”(税)的形容词。在一些实施例中，检索系统可以允许用户在查询中指定词和其词类两者。检索系统将搜索包括将该词作为该词类的句子。例如，查询〃 buildingfc.)"(建筑(名词))将产生对包括将词"building"(建筑)作为名词的句子的识别，但不识别将词"building"(建筑)作为动词的句子。检索系统可以识别句子“The building is old”(这个建筑是旧的)，但不会识别句子“The old are building relationships"(老人们正在建立关系)。这样的词和词类的组合可以用于定义复杂的查询，例如“bUilding(V.)hOUSe”(建筑(动词)房屋)以查找有关建造房屋的网页。通常， 可以将任何搜索引擎服务调整为包括词类通配符。例如，搜索引擎可以被调整为包括词类作为用于指定查询的另一类型的正规表达式的量词。
图3是示出一些实施例中的检索系统的组件的框图。检索系统310可以通过通信链路330连接到web服务器340和用户计算设备350。检索系统可以包括搭配存储320、输入查询组件311、自然语言处理器组件312、生成搭配存储组件313、更新搭配存储组件314 以及查找匹配句子组件316。当检索系统用于搜索网页时，检索系统还可以包括排名网页组件317和爬寻网站组件318。搭配存储包括句子存储321、搭配索引322和位置索引323。 句子存储包含要搜索的句子，而索引提供了句子的词类和词的对的映射。
生成搭配存储组件用于填充搭配存储。生成搭配存储组件选择句子存储中的每个句子并使用自然语言处理器组件识别句子的词类和词的对。生成搭配存储组件调用更新搭配存储组件以更新搭配和位置索引。输入查询组件从用户输入包括将词类作为通配符的查询。查找匹配句子组件查找句子存储中匹配输入查询的句子。爬寻网站组件对各个网站进行爬寻，并将网页的句子和对包含该句子的网页的引用一起添加到句子存储。排名网页组件生成包含匹配该输入查询的句子的网页的排名。
图4是示出一些实施例中的检索系统的搭配存储的组件的框图。搭配存储402包括搭配索引410、位置索引420和句子存储430。搭配索引包含从句子存储中识别的每个词类和词的对的条目。在本实例中，搭配索引包括下述词类和词的对(noim，enjoy), (I, verb), (verb, life), (enjoy,noun), (noun, like)禾口(like,noun),艮口“(名词，享受)，(我， 动词)，(动词，生活)，(享受，名词)，(名词，喜欢)和(喜欢，名词)”。搭配索引的每个条目识别了对的第一和第二项并且包括了对位置索引420的引用。例如，(noun，enjoy)的条目((名词，享受)的记录)包含对位置索引421的引用。每个位置索引的条目识别了词对的第一项在句子中的位置以及该词对的第二项在该句子中的位置。每个条目还包括对于对应的句子的引用。例如，位置索引422中的第三条目指示了在句子2的第二位置处的词 (即‘‘like”(喜欢))是动词，并且在句子2的第四位置处的词(即“life”)是“life”(喜欢)。(注意句子中的第一词可以被认为是在位置0，第二词可以被认为是在位置1，以此类推)。
为了查找匹配查询例如〃 I v. life"(我动词生活)，的句子，检索系统生成词类和词的对(I，verb)和(verb，life)，即(我，动词)和(动词，生活)。检索系统随后使用搭配索引来找到包括(I，verb)，g卩(我，动词)的句子集合和包括(verb，life)，即(动词，生活)的句子集合。随后，检索系统取这些句子集合的交集，即那些既包含(I，verb)即 (我，动词)又包含(verb，life)，即(动词，生活)的句子。在一些实施例中，检索系统可允许查询指定(I，verb)和(verb，life)，即(我，动词)和(动词，生活)，中的动词应该表示相同的动词或可以表示不同的动词。例如，查询"I v. life"(我动词生活)可以指示该用户想要表示相同动词的动词，而查询“I v.&v. life”(我动词&动词生活)可以表示用户不在乎所述动词是不同的。
在一些实施例中，检索系统可以认为在同一句子中的任意词对是搭配词对，而不考虑它们是否相邻。例如，句子"I enjoy life"(我喜欢生活)包括搭配词(I，enioy)、 (I，life)和(enjoy, life)，即(我，享受)、(我，生活)和(享受，生活)。位置索引识别了搭配对中的每个词在句子中的位置。例如，这些搭配词的位置为(0，1)，(0，2)和(1，2)。 检索系统可以使用这些位置来识别何时通配符表示相同的词。例如，句子1的(I，enioy) 和(enjoy，life)，即(我，享受)和(享受，生活)，的位置(0，1)和(1，2)指示了动词是相同的，因为这两个动词都在位置1。相对地，句子2的(I, verb)和(verb, life)，即(我， 动词)和(动词，生活)，的位置(0，1)和(7，9)指示了动词是不同的，因为位置1和位置7 是不同的。
在其上面实现了检索系统的计算设备可包括中央处理单元、存储器、输入设备 (例如，键盘和指示设备)、输出设备(例如，显示设备)，以及存储设备(例如，磁盘驱动器)。存储器和存储设备是可以用实现该检索系统的计算机可执行指令来编码的计算机可读介质，这意味着包含该指令的计算机可读介质。此外，指令、数据结构和消息结构可被存储或通过诸如通信链路上的信号之类的数据传输介质发送。可以使用各种通信链路，如因特网、局域网、广域网、点对点拨号连接、蜂窝电话网络等等。
该检索系统的实施例可以在各种操作环境中实现，这些操作环境包括个人计算机、服务器计算机、手持式或膝上型设备、多处理器系统、基于微处理器的系统、可编程消费电子产品、数码相机、网络PC、小型计算机、大型计算机、包括任何上述系统或设备中任一种的计算环境等。
可以在由一台或多台计算机或其他设备执行的诸如程序模块之类的计算机可执行的指令的一般上下文中来描述本检索系统。一般而言，程序模块包括执行特定任务或实现特定抽象数据类型的例程、程序、对象、组件、数据结构等等。通常，程序模块的功能可以按需在各个实施例中进行组合或分布。例如，检索系统可以被实现在向用户计算设备提供用户界面以搜索句子的服务器上。或者，检索系统可以在每个用户计算设备上实现。还有， 搭配存储的生成可以在服务器上执行，并随后下载到用户计算设备以帮助搜索句子。
图5是例示一些实施例中检索系统的生成搭配存储组件的处理的流程图。所述组件处理句子存储的每个句子以填充搭配和位置索引。在框501，组件选择句子存储的下一个句子。在判定框502，如果所有句子都已被选择，则该组件完成，否则该组件在框503继续。在框503，组件识别所选句子中的搭配词对。在框504，组件生成搭配词的词类和词的对。组件调用自然语言处理器以识别句子的结构以及句子中的词的词类。在框505-507，组件循环地将每个词类和词的对添加到搭配存储。在框505，组件选择下一词类和词的对。在判定框506，如果已经选择了所有词类和词的对，则该组件循环至框501以选择下一句子， 否则该组件继续至框507。在框507，组件调用更新搭配存储组件，并随后循环至框505以选择下一词类和词的对。
图6是例示一些实施例中检索系统的更新搭配索引组件的处理的流程图。向该组件传递词类和词的对并更新搭配索引和位置索引。在判定框601，如果词类和词的对已经在搭配索引中，则该组件在框604继续，否则该组件就在框602继续。在框602，该组件将条目添加到搭配存储中。在框603，该组件创建对应于搭配索引中新的条目的位置索引。在框 604，该组件将条目添加到位置存储中并随后返回。
图7是例示一些实施例中检索系统的查找匹配句子组件的处理的流程图。向该组件传递第一对、第二对和距离，第一对将通配符作为其第二元素，而第二对将通配符作为其第一元素。组件识别匹配第一对和第二对且其通配符在指定的距离内的句子。距离0指示了通配符表示句子中的相同的词。在框701，组件从搭配索引中检索匹配第一对的第一搭配条目。在框702，组件从搭配索引中检索匹配第二对的第二搭配条目。在框703-710，组件循环地确定是否有任何由第一搭配条目所识别的并还被第二搭配条目所识别的句子(即， 句子的交集)满足该距离。在框703，组件选择第一搭配条目的位置索引的下一条目。在判定框704，如果已经选择了位置索引的所有条目，则该组件返回结果，否则该组件在框705 处继续。在框705，组件从位置索引中所选的条目中检索句子标识符。在框706，组件检索具有匹配的句子标识符的第二搭配条目的位置索引的条目。在判定框707，如果检索到了具有匹配的句子标识符的条目，则组件继续至框708，否则，组件循环至框703来选择位置索引的下一条目。在框708，组件计算由条目所表示的词类和词的对之间的距离。在判定框709，如果计算的距离小于或等于传递的距离，则组件继续至框710，否则，组件循环至框 703来选择位置索引的下一条目。在框710，组件将句子标识符加入到结果中并随后循环至框703以选择位置索引的下一条目。
尽管用专门描述结构特征和/或方法动作的语言描述了主题，但是应当理解，在所附权利要求书中限定的主题并不一定局限于上述特定的特征或动作。例如，向用户显示的句子可以是基于各种特性例如可读性排名的。作为另一个实例，输入查询可以包括多个词类作为通配符。例如，输入查询可以是"adv.(副词)adj.(形容词)work(工作)"，它可被短语“really hard work”(真正艰苦的工作)匹配。通常，句子可以被认为是仅包含一个句子的文档。更确切而言，上述具体特征和动作是作为实现权利要求的示例形式公开的。相应地，本发明不受限制，只受所附的权利要求书的限制。
权利要求
1.一种在计算设备中用于搜索句子的方法，所述方法包括 提供(301)句子的集合；对于集合中的每个句子 识别(503)句子中的搭配词对； 对于每个所识别的搭配词对 识别(504)该对的每个词的词类；生成(504)第一词类和包括所识别的第一词的词类的词对，以及第二词类和包括所述第一词和所识别的第二词的词类的词对；以及为所述句子从第一词类和词对以及第二词类和词对中生成(504)映射； 接收(311)包括第一词、词类和第二词的输入查询；从映射中识别句子(701-710)，所述句子包括搭配有所述输入查询的词类的一词的所述输入查询的第一词以及搭配有所述输入查询的第二词的具有所述词类的一词。 向用户显示所识别的句子。
2.如权利要求1所述的方法，其特征在于，所述识别句子包括识别一句子，使得具有输入查询的词类的相同的词与所述输入查询的第一词和第二词两者搭配。
3.如权利要求1所述的方法，其特征在于，所述映射包括每个唯一的词类和词对的条目，所述条目识别了包含具有该词类和词对的搭配词的句子。
4.如权利要求3所述的方法，其特征在于，所述映射的每个条目识别了包含搭配词的每个句子中所述词类的位置和所述词的位置。
5.一种包含用于控制计算设备来通过一种方法来识别有关查询的文档的指令的计算机可读存储介质，所述方法包括从用户接收(311)包括词和词类的输入查询；识别(701-710)具有包括所述词的句子的文档，其中所述词搭配有所述词类的一词。对所识别的文档进行排名；以及以文档的排名顺序向用户显示所识别的文档。
6.如权利要求5所述的计算机可读存储介质，其特征在于，所述文档是句子。
7.如权利要求6所述的计算机可读存储介质，包括 提供句子的集合；对于集合中的每个句子识别句子的搭配词对；对于每个所识别的搭配词对识别在所述句子中使用时所述对中的每个词的词类；生成第一词类和包括所识别的第一词的词类的词对，以及第二词类和包括所述第一词和所识别的第二词的词类的词对；以及为所述句子从第一词类和词对以及第二词类和词对中生成映射。
8.如权利要求7所述的计算机可读存储介质，其特征在于，对文档的识别使用所生成的映射。
9.如权利要求5所述的计算机可读存储介质，其特征在于，所述文档是由爬寻网站识别的网页。
10.如权利要求9所述的计算机可读存储介质，其特征在于，所述文档的排名包括基于句子与所述输入查询的相关性来对网页排名。
11.如权利要求9所述的计算机可读存储介质，其特征在于，包括为所述网页生成搭配词及其词类的映射。
12.如权利要求11所述的计算机可读存储介质，其特征在于，文档的识别使用所生成的映射来识别包括所述输入查询的所述词的网页，其中所述词搭配有所述输入查询的词类的一词。
13.一种用于识别具有指定词类的词的句子的计算设备，包括组件(311)，从用户输入具有词和词类的查询；组件(316)，识别具有所述查询的所述词的句子，所述词搭配有用作所述查询的词类的一词；以及向用户显示所识别的句子的组件。
14.如权利要求13所述的计算设备，其特征在于，所述查询的所述词和用作所述词类的词是同一词。
15.如权利要求13所述的计算设备，其特征在于，所述查询的所述词和用作所述词类的词是不同的词。
全文摘要
提供了一种用于识别有关指定词类的查询的文档的方法和系统。检索系统从用户接收包括词和词类的输入查询。一旦接收到包括词和词类的输入查询，所述检索系统识别具有包括该词的句子的文档，该词搭配有用作该词类的一词。所述检索系统向用户显示所识别的文档的指示。
文档编号G06F17/26GK102203774SQ200980143730
公开日2011年9月28日 申请日期2009年11月3日 优先权日2008年11月3日
发明者X·刘, M·周, H·魏, J·赵, M·R·斯格特, L·蒋, G·陈 申请人:微软公司
使用概括的句子搭配的检索对相关申请的交叉引用本申请要求于2008年11月3日提交的名称为“RETRIEVAL USING A GENERALIZED SENTENCE COLLOCATION(使用概括的句子搭配的检索)，，的第61/110，892号美国临时专利申请的利益，该申请的全部内容通过引用结合于此。
背景技术：
因特网、特别是万维网(“web”)已经通过其因特网浏览器使海量的信息对用户可用。尽管这些信息对用户而言是可容易访问的，但是信息多得以至于在用户尝试标识什么信息与其需求相关时出现问题。该问题被称为信息爆炸问题。已经开发出搜索引擎服务以帮助用户找出与其需求相关的信息。这些搜索引擎服务允许用户搜索用户可能感兴趣的显示页面，比如网页。在用户提交包含搜索项的搜索请求(即查询)之后，搜索引擎服务标识可能与这些搜索项相关的网页。为快速标识相关的网页，搜索引擎服务可以维护关键词到网页的映射。该映射可以通过对web进行爬寻(crawling)以标识出每个网页的关键词来生成。为了对web进行爬寻，搜索引擎服务可以使用根网页列表来标识出可通过这些根网页来访问的所有网页。任一特定网页的关键词都可以使用各种公知的信息检索技术来标识，比如标识标题行的文字、在网页的元数据中所提供的文字、突出显示的文字等等。搜索引擎服务基于网页的关键词与查询的文字的匹配程度来标识可能与搜索请求相关的网页。 搜索引擎服务随后将到所标识出的网页的链接以基于排名的顺序向用户显示，该排名可以由所标识出的网页与查询的相关度、流行度、重要性和/或其它度量来确定。
尽管，这种搜索感兴趣的信息的通用方法在许多情况中都有用，但在某些情况中， 它们还是存在问题。一种这样的情况在以一种语言为母语的人在以另一种语言进行书写时寻求帮助的时候出现。例如，以中文为母语的人在以英语书写文档时可能会发现难以识别表达他们意图的最适当的英文词。虽然，这些人可以向搜索引擎服务提交查询以检索网页， 这些网页具有可能有助于确定合适的词的句子，但这些人可能甚至不知道任何在意思上类似的英文词，这导致关键字搜索变得困难。例如，如果这些人想要表达“they are happy with life”(他们生活得很快乐)，这些人可能知道句子应该具有词“I”(我)和“life”(生活)，但可能不知道词“enioy”(享受)和“like”(喜欢)可能是用于形成句子“I enjoy life”(我享受生活)或“I like life”(我喜欢生活)的句子的合适的词。如果这些人向搜索引擎服务提交查询“I life”(我生活)，搜索结果很可能包括有关“iLife”软件产品、“life(生活)”的定义、life-skills(生存技巧)训练等等的引用。然而，这些结果未必包括将有助于用户识别用于表达其意思的合适的词的样本句子。
另一种情况在一个人搜索有关某个话题的文档，但使用了可能不能精确表达他们的意图的一系列简单的关键字的时候出现。例如，正在研究政府实体的收入的来源的人可能想要编纂用于不同类型的税(tax)的通用名字列表，例如所得税、房地产税、遗产税、车船禾兌、销售禾兌(income tax, real estate tax, death tax, vehicle tax, sales tax)等等。 此人可以提交看上去精确描述其兴趣的查询“税的通用名称”。在这种情况，搜索引擎服务很可能返回有关通用法律婚姻(common law marriages)的名字和税问题的文档、以包括税的价格出售的有关通用名和学名的书等等。然而，这样的文档并不是对税的通用名字感兴趣的人所在意的。
发明内容
提供了一种用于识别有关指定词类的查询的文档的方法和系统。一种检索系统从用户接收包括词和词类的输入查询。一旦接收到包括词和词类的输入查询，所述检索系统识别具有包括该词的句子的文档，该词与作为该词类的一词相搭配。所述检索系统向用户显示所识别的文档的指示。所述检索系统允许用户在输入查询时将词类适当用作通配符以指定他们的意图。
提供本发明内容是为了以精简的形式介绍将在以下详细描述中进一步描述的一些概念。本发明内容并不旨在标识出所要求保护的主题的关键特征或必要特征，也不旨在用于帮助确定所要求保护的主题的范围。
图1是在检索系统的一些实施例中说明使用输入查询的句子搜索的显示页面，所述输入查询使用词类作为通配符。
图2是在检索系统的一些实施例中说明使用输入查询的网页搜索的显示页面，所述输入查询使用词类作为通配符。
图3是示出一些实施例中的检索系统的组件的框图。
图4是示出一些实施例中的检索系统的搭配存储的组件的框图。
图5是例示一些实施例中检索系统的生成搭配存储组件的处理的流程图。
图6是例示一些实施例中检索系统的更新搭配索引组件的处理的流程图。
图7是例示一些实施例中检索系统的查找匹配句子组件的处理的流程图。
具体实施例方式提供了一种用于识别有关指定词类的查询的文档的方法和系统。在一些实施例中，一种检索系统从用户接收包括词和词类的输入查询。例如，输入查询可以指定为 “(adjeCtiVe)taX”((形容词)税)。这个输入查询可以表示一个人查找税的通用名字的意图，它通常具有其后跟随有词“tax”(税)的形容词。检索系统使用术语“ (adjective) ”(形容词)来表示用于用作在词“tax”(税)之前的形容词的任意词的通配符。一旦接收到包括词和词类的输入查询，所述检索系统识别具有包括所指定的词的句子的文档，所指定的词与作为词类的词相搭配。例如，检索系统可以识别包含下述句子的文档 Most Americans pay their income tax on April 15(大多数美国人在 4 月 15 日支付他们的所得税)。
Congress voted to limit the death tax (国会投票限制遗产税)。
第一个句子包括与词“tax”(税)相搭配的形容词“income”(所得)，并且，第二个句子包括与词“tax”(税)相搭配的形容词“death”(遗产)。然而，检索系统不会基于下述句子来识别文档
5 Many levels of government tax small businesses unfairly(多级政府对小商业团体不公平地征收税)。
It is our obligation to pay upon his death tax for his estate (一旦ftk去世了，为他的财产付税是我们的责任)。
这两句句子中任一一个都不包括与词“tax”(税)相搭配的形容词。虽然，词 “government”(政府)和“death”(去世)可以在某些上下文中用作形容词，但在这些句子中它们被用作名词，而非描述词“tax”(税)的形容词。作为另一个实例，用户可以输入查询“I v. life，”(我动词生活)，其中“V.”表示用于作为动词的词的通配符。在这种情况下，检索系统对包含其后跟随有动词的词“ I ”(我)，所述动词后面跟随有词“ life”(生活)的文档中的句子进行搜索。例如，检索系统可以识别包含下述句子的文档 I enjoy life (我享受生活)。
I like life (我喜欢生活)。
在这两个句子中，词“enjoy”(享受)和“like”(喜欢)是动词。所述检索系统向用户显示所识别的文档的指示。通过这种方式，用户可以将词类适当用作通配符以指定他们的意图。
在一些实施例中，检索系统可以用于在人们以其母语以外的语言书写文档时帮助人们搜索词。例如，以中文作为母语的人可能想要找到表达他们生活快乐(their happiness with life)的英文动词。以英文为母语的人知道动词“enjoy”(享受)和 “like”(喜欢)可能是合适的动词——但以中文作为母语的人却可能并不知道这点。检索系统允许人们输入包括将词类作为通配符和一个或多个词(例如"Iv. life"(我动词生活))的输入查询，并返回匹配该输入查询的句子(例如“I enjoy life”(我享受生活)和“I like life”(我喜欢生活))。以中文作为母语的人随后可以基于这个动词的定义决定合适的动词，所述动词的定义是从该句子中围绕该词的上下文中或从字典中推断出来的。
在一些实施例中，检索系统可以生成搭配词和词类的映射以帮助识别匹配输入查询的句子。检索系统可以使用自然语言处理器来处理句子集合中的句子以识别每个句子中的词的词类。例如，自然语言处理器可以将句子"I enjoy life"(我喜欢生活)中的词分别识别为代名词、动词和名词。自然语言处理器可以通过识别主语、谓语、宾语等来最初确定每个句子的结构。自然语言处理器随后可以基于句子的结构识别该句子的每个词的词类。词的词类被认为是该词的概括。检索系统随后识别每个句子中的搭配词对。例如，句子〃 I enjoy life"(我喜欢生活)包括搭配词(Lenioy)和(enjoy, life), BP (我，享受)和(享受，生活)。检索系统随后为每个搭配词对生成两对词类和词。例如，检索系统可以为搭配词(I，enioy)生成(pronoun，enjoy)和(I，verb)的词类和词对，即为搭配的词 (我，享受)生成(代名词，享受)和(我，动词)的词类和词对，并为搭配词(enjoy，life) 生成(verb，life)和(enjoy，noun)的词类和词对，即为搭配的词(享受，生活)生成(动词，生活)和(享受，名词)的词类和词对。检索系统可以创建包括所生成的每个词类和词的对的条目的索引。每个条目识别集合中包括该词类和词的对的句子。通过这种方式，检索系统可以快速地识别包含匹配输入查询的词类和词的对的句子。
图1是说明在检索系统的一些实施例中使用输入查询的句子搜索的显示页面，所述输入查询使用词类作为通配符。显示页面100包括输入查询文本框101、执行按钮102和结果区域103。用户将具有用于词类的通配符的查询输入到文本框中并选择执行按钮来提交该查询。检索系统识别与查询匹配的句子并将结果显示在结果区域中。在本实例中，用户输入查询“I v. life”(我动词生活)以搜索包括有词“I”(我)其后是一个动词随后是词“life”(生活)的句子。结果区域中的每个句子使用不同的动词(即enjoy (享受)， like(喜欢)，love(爱)，hate(恨))与查询匹配。在一些实施例中，检索系统可以允许用户从结果区域中选择一词以查看该词的定义。例如，如果用户选择了词"enjoy"(享受)， 检索系统可以显示词"enjoy"(享受)的定义。在一些实施例中，检索系统可以允许用户从结果区域中选择整句句子以在从中提取该句子的文档的上下文中(如果存在的话)查看该句子。
图2是说明在检索系统的一些实施例中使用输入查询的网页搜索的显示页面，所述输入查询使用词类作为通配符。显示页面200包括输入查询文本框201、执行按钮202 和结果区域203。用户将具有用于词类的通配符(例如“v. ”(动词))的查询输入到文本框中并随后提交该查询。检索系统识别包含匹配该查询的句子的网页并将到所识别的网页的链接显示在结果区域中。每个链接可以由匹配该查询的网页中的短语来标识。每个链接还可以由取自该网页的附加上下文来标识。在本实例中，用户输入查询"attorneys v. client"(代理人动词客户)以搜索包括有词“attorneys”(代理人)其后是一个动词随后是词“client”(客户)的句子。在结果区域中所识别的每个网页包括使用不同动词 (即“advise(建议)，bill(开帐单)，trust(相信)以及fire(解雇)”)匹配该查询的句子。
在一些实施例中，检索系统可以基于所识别的网页与查询的相关性、流行性、重要性和/或一些其他的度量来对它们进行排名。用户可以选择结果区域中的链接以查看包含与查询匹配的句子的网页。检索系统可以允许使用词类作为通配符，例如形容词、副词、 连接词、感叹词、名词、介词、代名词和动词。例如，用户可以输入查询“adj. tax”(形容词税)来寻找其后跟着词“tax”(税)的形容词。在一些实施例中，检索系统可以允许用户在查询中指定词和其词类两者。检索系统将搜索包括将该词作为该词类的句子。例如，查询〃 buildingfc.)"(建筑(名词))将产生对包括将词"building"(建筑)作为名词的句子的识别，但不识别将词"building"(建筑)作为动词的句子。检索系统可以识别句子“The building is old”(这个建筑是旧的)，但不会识别句子“The old are building relationships"(老人们正在建立关系)。这样的词和词类的组合可以用于定义复杂的查询，例如“bUilding(V.)hOUSe”(建筑(动词)房屋)以查找有关建造房屋的网页。通常， 可以将任何搜索引擎服务调整为包括词类通配符。例如，搜索引擎可以被调整为包括词类作为用于指定查询的另一类型的正规表达式的量词。
图3是示出一些实施例中的检索系统的组件的框图。检索系统310可以通过通信链路330连接到web服务器340和用户计算设备350。检索系统可以包括搭配存储320、输入查询组件311、自然语言处理器组件312、生成搭配存储组件313、更新搭配存储组件314 以及查找匹配句子组件316。当检索系统用于搜索网页时，检索系统还可以包括排名网页组件317和爬寻网站组件318。搭配存储包括句子存储321、搭配索引322和位置索引323。 句子存储包含要搜索的句子，而索引提供了句子的词类和词的对的映射。
生成搭配存储组件用于填充搭配存储。生成搭配存储组件选择句子存储中的每个句子并使用自然语言处理器组件识别句子的词类和词的对。生成搭配存储组件调用更新搭配存储组件以更新搭配和位置索引。输入查询组件从用户输入包括将词类作为通配符的查询。查找匹配句子组件查找句子存储中匹配输入查询的句子。爬寻网站组件对各个网站进行爬寻，并将网页的句子和对包含该句子的网页的引用一起添加到句子存储。排名网页组件生成包含匹配该输入查询的句子的网页的排名。
图4是示出一些实施例中的检索系统的搭配存储的组件的框图。搭配存储402包括搭配索引410、位置索引420和句子存储430。搭配索引包含从句子存储中识别的每个词类和词的对的条目。在本实例中，搭配索引包括下述词类和词的对(noim，enjoy), (I, verb), (verb, life), (enjoy,noun), (noun, like)禾口(like,noun),艮口“(名词，享受)，(我， 动词)，(动词，生活)，(享受，名词)，(名词，喜欢)和(喜欢，名词)”。搭配索引的每个条目识别了对的第一和第二项并且包括了对位置索引420的引用。例如，(noun，enjoy)的条目((名词，享受)的记录)包含对位置索引421的引用。每个位置索引的条目识别了词对的第一项在句子中的位置以及该词对的第二项在该句子中的位置。每个条目还包括对于对应的句子的引用。例如，位置索引422中的第三条目指示了在句子2的第二位置处的词 (即‘‘like”(喜欢))是动词，并且在句子2的第四位置处的词(即“life”)是“life”(喜欢)。(注意句子中的第一词可以被认为是在位置0，第二词可以被认为是在位置1，以此类推)。
为了查找匹配查询例如〃 I v. life"(我动词生活)，的句子，检索系统生成词类和词的对(I，verb)和(verb，life)，即(我，动词)和(动词，生活)。检索系统随后使用搭配索引来找到包括(I，verb)，g卩(我，动词)的句子集合和包括(verb，life)，即(动词，生活)的句子集合。随后，检索系统取这些句子集合的交集，即那些既包含(I，verb)即 (我，动词)又包含(verb，life)，即(动词，生活)的句子。在一些实施例中，检索系统可允许查询指定(I，verb)和(verb，life)，即(我，动词)和(动词，生活)，中的动词应该表示相同的动词或可以表示不同的动词。例如，查询"I v. life"(我动词生活)可以指示该用户想要表示相同动词的动词，而查询“I v.&v. life”(我动词&动词生活)可以表示用户不在乎所述动词是不同的。
在一些实施例中，检索系统可以认为在同一句子中的任意词对是搭配词对，而不考虑它们是否相邻。例如，句子"I enjoy life"(我喜欢生活)包括搭配词(I，enioy)、 (I，life)和(enjoy, life)，即(我，享受)、(我，生活)和(享受，生活)。位置索引识别了搭配对中的每个词在句子中的位置。例如，这些搭配词的位置为(0，1)，(0，2)和(1，2)。 检索系统可以使用这些位置来识别何时通配符表示相同的词。例如，句子1的(I，enioy) 和(enjoy，life)，即(我，享受)和(享受，生活)，的位置(0，1)和(1，2)指示了动词是相同的，因为这两个动词都在位置1。相对地，句子2的(I, verb)和(verb, life)，即(我， 动词)和(动词，生活)，的位置(0，1)和(7，9)指示了动词是不同的，因为位置1和位置7 是不同的。
在其上面实现了检索系统的计算设备可包括中央处理单元、存储器、输入设备 (例如，键盘和指示设备)、输出设备(例如，显示设备)，以及存储设备(例如，磁盘驱动器)。存储器和存储设备是可以用实现该检索系统的计算机可执行指令来编码的计算机可读介质，这意味着包含该指令的计算机可读介质。此外，指令、数据结构和消息结构可被存储或通过诸如通信链路上的信号之类的数据传输介质发送。可以使用各种通信链路，如因特网、局域网、广域网、点对点拨号连接、蜂窝电话网络等等。
该检索系统的实施例可以在各种操作环境中实现，这些操作环境包括个人计算机、服务器计算机、手持式或膝上型设备、多处理器系统、基于微处理器的系统、可编程消费电子产品、数码相机、网络PC、小型计算机、大型计算机、包括任何上述系统或设备中任一种的计算环境等。
可以在由一台或多台计算机或其他设备执行的诸如程序模块之类的计算机可执行的指令的一般上下文中来描述本检索系统。一般而言，程序模块包括执行特定任务或实现特定抽象数据类型的例程、程序、对象、组件、数据结构等等。通常，程序模块的功能可以按需在各个实施例中进行组合或分布。例如，检索系统可以被实现在向用户计算设备提供用户界面以搜索句子的服务器上。或者，检索系统可以在每个用户计算设备上实现。还有， 搭配存储的生成可以在服务器上执行，并随后下载到用户计算设备以帮助搜索句子。
图5是例示一些实施例中检索系统的生成搭配存储组件的处理的流程图。所述组件处理句子存储的每个句子以填充搭配和位置索引。在框501，组件选择句子存储的下一个句子。在判定框502，如果所有句子都已被选择，则该组件完成，否则该组件在框503继续。在框503，组件识别所选句子中的搭配词对。在框504，组件生成搭配词的词类和词的对。组件调用自然语言处理器以识别句子的结构以及句子中的词的词类。在框505-507，组件循环地将每个词类和词的对添加到搭配存储。在框505，组件选择下一词类和词的对。在判定框506，如果已经选择了所有词类和词的对，则该组件循环至框501以选择下一句子， 否则该组件继续至框507。在框507，组件调用更新搭配存储组件，并随后循环至框505以选择下一词类和词的对。
图6是例示一些实施例中检索系统的更新搭配索引组件的处理的流程图。向该组件传递词类和词的对并更新搭配索引和位置索引。在判定框601，如果词类和词的对已经在搭配索引中，则该组件在框604继续，否则该组件就在框602继续。在框602，该组件将条目添加到搭配存储中。在框603，该组件创建对应于搭配索引中新的条目的位置索引。在框 604，该组件将条目添加到位置存储中并随后返回。
图7是例示一些实施例中检索系统的查找匹配句子组件的处理的流程图。向该组件传递第一对、第二对和距离，第一对将通配符作为其第二元素，而第二对将通配符作为其第一元素。组件识别匹配第一对和第二对且其通配符在指定的距离内的句子。距离0指示了通配符表示句子中的相同的词。在框701，组件从搭配索引中检索匹配第一对的第一搭配条目。在框702，组件从搭配索引中检索匹配第二对的第二搭配条目。在框703-710，组件循环地确定是否有任何由第一搭配条目所识别的并还被第二搭配条目所识别的句子(即， 句子的交集)满足该距离。在框703，组件选择第一搭配条目的位置索引的下一条目。在判定框704，如果已经选择了位置索引的所有条目，则该组件返回结果，否则该组件在框705 处继续。在框705，组件从位置索引中所选的条目中检索句子标识符。在框706，组件检索具有匹配的句子标识符的第二搭配条目的位置索引的条目。在判定框707，如果检索到了具有匹配的句子标识符的条目，则组件继续至框708，否则，组件循环至框703来选择位置索引的下一条目。在框708，组件计算由条目所表示的词类和词的对之间的距离。在判定框709，如果计算的距离小于或等于传递的距离，则组件继续至框710，否则，组件循环至框 703来选择位置索引的下一条目。在框710，组件将句子标识符加入到结果中并随后循环至框703以选择位置索引的下一条目。
尽管用专门描述结构特征和/或方法动作的语言描述了主题，但是应当理解，在所附权利要求书中限定的主题并不一定局限于上述特定的特征或动作。例如，向用户显示的句子可以是基于各种特性例如可读性排名的。作为另一个实例，输入查询可以包括多个词类作为通配符。例如，输入查询可以是"adv.(副词)adj.(形容词)work(工作)"，它可被短语“really hard work”(真正艰苦的工作)匹配。通常，句子可以被认为是仅包含一个句子的文档。更确切而言，上述具体特征和动作是作为实现权利要求的示例形式公开的。相应地，本发明不受限制，只受所附的权利要求书的限制。
权利要求
1.一种在计算设备中用于搜索句子的方法，所述方法包括 提供(301)句子的集合；对于集合中的每个句子 识别(503)句子中的搭配词对； 对于每个所识别的搭配词对 识别(504)该对的每个词的词类；生成(504)第一词类和包括所识别的第一词的词类的词对，以及第二词类和包括所述第一词和所识别的第二词的词类的词对；以及为所述句子从第一词类和词对以及第二词类和词对中生成(504)映射； 接收(311)包括第一词、词类和第二词的输入查询；从映射中识别句子(701-710)，所述句子包括搭配有所述输入查询的词类的一词的所述输入查询的第一词以及搭配有所述输入查询的第二词的具有所述词类的一词。 向用户显示所识别的句子。
2.如权利要求1所述的方法，其特征在于，所述识别句子包括识别一句子，使得具有输入查询的词类的相同的词与所述输入查询的第一词和第二词两者搭配。
3.如权利要求1所述的方法，其特征在于，所述映射包括每个唯一的词类和词对的条目，所述条目识别了包含具有该词类和词对的搭配词的句子。
4.如权利要求3所述的方法，其特征在于，所述映射的每个条目识别了包含搭配词的每个句子中所述词类的位置和所述词的位置。
5.一种包含用于控制计算设备来通过一种方法来识别有关查询的文档的指令的计算机可读存储介质，所述方法包括从用户接收(311)包括词和词类的输入查询；识别(701-710)具有包括所述词的句子的文档，其中所述词搭配有所述词类的一词。对所识别的文档进行排名；以及以文档的排名顺序向用户显示所识别的文档。
6.如权利要求5所述的计算机可读存储介质，其特征在于，所述文档是句子。
7.如权利要求6所述的计算机可读存储介质，包括 提供句子的集合；对于集合中的每个句子识别句子的搭配词对；对于每个所识别的搭配词对识别在所述句子中使用时所述对中的每个词的词类；生成第一词类和包括所识别的第一词的词类的词对，以及第二词类和包括所述第一词和所识别的第二词的词类的词对；以及为所述句子从第一词类和词对以及第二词类和词对中生成映射。
8.如权利要求7所述的计算机可读存储介质，其特征在于，对文档的识别使用所生成的映射。
9.如权利要求5所述的计算机可读存储介质，其特征在于，所述文档是由爬寻网站识别的网页。
10.如权利要求9所述的计算机可读存储介质，其特征在于，所述文档的排名包括基于句子与所述输入查询的相关性来对网页排名。
11.如权利要求9所述的计算机可读存储介质，其特征在于，包括为所述网页生成搭配词及其词类的映射。
12.如权利要求11所述的计算机可读存储介质，其特征在于，文档的识别使用所生成的映射来识别包括所述输入查询的所述词的网页，其中所述词搭配有所述输入查询的词类的一词。
13.一种用于识别具有指定词类的词的句子的计算设备，包括组件(311)，从用户输入具有词和词类的查询；组件(316)，识别具有所述查询的所述词的句子，所述词搭配有用作所述查询的词类的一词；以及向用户显示所识别的句子的组件。
14.如权利要求13所述的计算设备，其特征在于，所述查询的所述词和用作所述词类的词是同一词。
15.如权利要求13所述的计算设备，其特征在于，所述查询的所述词和用作所述词类的词是不同的词。
全文摘要
提供了一种用于识别有关指定词类的查询的文档的方法和系统。检索系统从用户接收包括词和词类的输入查询。一旦接收到包括词和词类的输入查询，所述检索系统识别具有包括该词的句子的文档，该词搭配有用作该词类的一词。所述检索系统向用户显示所识别的文档的指示。
文档编号G06F17/26GK102203774SQ200980143730
公开日2011年9月28日 申请日期2009年11月3日 优先权日2008年11月3日
发明者X·刘, M·周, H·魏, J·赵, M·R·斯格特, L·蒋, G·陈 申请人:微软公司
最新回复(0)