CN102750323B - 用于为具有多个书写系统的语言识别相关查询的系统和方法 - Google Patents

Abstract

本发明涉及用于为具有多个书写系统的语言识别相关查询的系统和方法。本发明的方法包括接收根据具有多个书写系统的语言的一个或多个书写系统书写的查询。识别根据该具有多个书写系统的语言的一个或多个书写系统书写的查询的候选集合。为候选集合中的一个或多个查询计算指示出该一个或多个查询与接收的查询的相似性的得分。

Description

用于为具有多个书写系统的语言识别相关查询的系统和方法

本申请是申请日为2007年2月27日、申请号为200780006965.X并且发明名称为“用于为具有多个书写系统的语言识别相关查询的系统和方法”的专利申请的分案申请。

著作权通告

本专利文献的公开内容的一部分包含受著作权保护的素材。著作权所有人不反对任何人对专利文献或专利公开以其出现在专利商标局专利文件或记录中的形式进行复制再现，但除此之外保留一切著作权权利。

相关申请的交叉引用

本申请与以下未决申请相关，特此通过引用将每个所述未决申请全部内容并入在此：

·2005年8月10日递交的题为“SYSTEMANDMETHODFORDETERMININGALTERNATESEARCHQUERIES”的美国专利申请No.11/200,851；以及

·2005年11月9日递交的题为“MODULAROPTIMIZEDDYNAMICSETS”的美国专利申请No.60/736,133。

技术领域

本发明一般地提供了用于识别与根据具有多个书写系统(writingsystem)的语言(language)书写的给定搜索查询(searchquery)相关的一个或多个查询的方法和系统。更具体而言，本发明提供了用于接收根据具有多个书写系统的语言的一个或多个书写系统的组合来书写的搜索查询并且从查询的候选集合(candidatesetofqueries)中识别一个或多个相关查询的方法和系统。

背景技术

由于因特网的出现和万维网(“web”)上用户可获得的众多网页、媒体内容、广告等等，向用户提供流线型的方法以从web获得有关信息已经成为一种需求。搜索系统和过程已经被开发出来满足用户获得这种信息的需求。这种技术的示例可通过Yahoo！、Google和其他搜索提供商网站来得到。

目前，用户可以使用能够接入广域网(例如因特网)的客户端设备(例如个人计算机(PC)、PDA、智能电话等等)来搜索和检索出内容。一般来说，用户经由客户端设备输入查询，并且搜索进程返回与查询相关的一个或多个内容项，例如链接、文档、网页、广告，等等。响应于给定查询而返回的内容项可能与用户实际在寻找的主题或题目紧密相关，也可能完全无关。给定查询的成功度可以基于所检索出的内容项与给定查询如何紧密相关来衡量，它很大程度上可能取决于对搜索查询的适当解释。

查询是由一个或多个单词和短语构成的。但是，人类用户输入的查询经常无法恰当地描述给定用户可能在寻找的内容。另外，用户可能只拥有关于其可能在寻找的内容的概括的或含糊的想法。例如，用户可能希望利用Yahoo！搜索引擎对在电视上作广告的产品进行搜索。用户可能不知道产品的名称、制造商等等，并且可能只能概括性地描述产品。因此，用户所制定的查询可能太宽泛了，从而导致所检索出的内容项与用户寻找的内容完全无关。类似地，用户所选择的查询词语(queryterm)可能无法恰当地描述产品，从而导致只检索出少量内容项，或者甚至不检索出任何内容项。

已知当前的用于生成可能与给定查询相关的查询的候选集合的技术。例如，用户可输入查询MP3player”，并且被呈现以一个或多个相关查询，例如等等。但是，搜索提供商面临着从查询的候选集合中识别在含义上与给定查询最有关或紧密相关的一个或多个查询的挑战。另外，诸如日语之类的某些语言具有多个书写系统，这进一步增大了从查询的候选集合中识别在含义上与给定查询最有关或相似的查询的复杂度。例如，提交给搜索引擎的单个日语查询可能是根据诸如汉字(Kanji)、片假名(Katakana)、平假名(hiragana)、JASCII、ASCII等等之类的一个或多个日语书写系统的不同组合来书写的。根据日语的汉字书写系统书写的查询看起来可能完全不同于根据日语的片假名和平假名书写系统书写的查询，但是两个查询可能具有非常相似或相同的含义。

此外，诸如Yahoo！、MSN或Google之类的搜索提供商可利用竞价市场(biddingmarket)，通过该市场，广告主(advertiser)可以为词语出价(bid)，以便使得一个或多个广告响应于查询而被显示。例如，一个或多个广告主可能希望显示膝上型计算机的一个或多个广告，并且相应地可为“notebookcomputer(笔记本计算机)”出价。但是，词语“notebookcomputer”可能是根据具有多个书写系统的语言(例如日语)的一个或多个书写系统来书写的。例如，词语“notebookcomputer”可能是根据日语平假名书写系统、日语片假名书写系统等等来书写的。

用户可以向给定的搜索提供商(例如Yahoo！)提交包括根据日语片假名书写系统书写的词语“notebookcomputer”的查询。具有相关联的对片假名词语“notebookcomputer”的出价一个或多个广告可被检索出并显示给用户。在竞价市场中，与为片假名词语“notebookcomputer”提供最大出价的广告主相关联的广告可以被显示在网页的最突出位置，例如，在被排名的广告列表中排名第一、显示在给定的搜索结果页面的顶部，等等。

如果用户选择了一个或多个所显示的广告，则搜索提供商可以例如通过基于广告主的出价向与所选择的广告相关联的广告主收取某一数额的货币，来使用户的选择货币化。但是，仅仅检索出和显示具有相关联的对一个或多个词语的出价的广告，可能导致给定搜索提供商的收入大受损失。例如，如果用户输入由未被一个或多个广告主出价的词语组成的查询，则搜索提供商可能无法向用户返回任何广告，从而导致搜索提供商的收入损失，因为用户将不能选择任何结果。参考上述示例，如果用户输入的查询不包括片假名词语“notebookcomputer”，而是包括平假名词语“laptopcomputer(膝上型计算机)”，则搜索提供商可能不会显示有适当针对性的广告，尽管片假名查询“laptopcomputer”和平假名查询“notebookcomputer”的含义是相似的。

虽然存在用于从查询的候选集合中识别在含义上与给定查询相同或相似的一个或多个查询的技术，但是现有技术限于根据单个书写系统书写的语言。当前的技术因而无法支持对在含义上与根据具有多个书写系统的语言的一个或多个书写系统书写的原始查询最有关或紧密相关的查询的识别。为了克服与现有技术相关联的缺点，本发明提供了系统和方法，用于从相关查询的候选集合中识别与根据具有多个书写系统的语言的一个或多个书写系统书写的给定搜索查询在含义上最相似的一个或多个查询。

发明内容

本发明涉及用于识别与给定查询相关的一个或多个查询的方法和系统。本发明的方法包括接收根据具有多个书写系统的语言的一个或多个书写系统书写的查询。根据本发明的一个实施例，所接收的查询包括根据一个或多个日语书写系统的组合来书写的查询，所述一个或多个日语书写系统包括日语平假名、片假名、假名、罗马字、JASCII和汉字书写系统。

识别与接收的查询相关联的、根据该具有多个书写系统的语言的一个或多个书写系统书写的查询的候选集合。根据本发明的一个实施例，查询的候选集合包括如一个或多个查询日志(querylog)中所指示的与接收的查询相关的一个或多个查询。

该方法还包括为候选集合中的一个或多个查询计算指示出该一个或多个查询与接收的查询的相似性的得分。为候选集合中的一个或多个查询计算的得分指示出来自候选的给定查询与接收的查询在含义上的相似性。根据本发明的一个实施例，计算得分包括在将每个查询中的一个或多个字符转换成罗马字符之后计算接收的查询和从候选集合中选择的查询之间的字符编辑距离(charactereditdistance)。根据本发明的另一个实施例，计算得分包括在将每个查询中的一个或多个字符转换成罗马字符并且从每个查询中去除空格字符之后计算接收的查询和从候选集合中选择的查询之间的字符编辑距离。根据本发明的另一个实施例，计算得分包括将接收的查询和从候选集合中选择的查询的字符转换成罗马字符，并且计算一(“1”)与下述商(quotient)之间的差：接收的查询和选择的查询中的独特空格分隔共现单词(uniquespace-separatedco-occurringwords)的数目与两个查询中的独特空格分隔单词的总数的商。

根据本发明的另一个实施例，计算得分包括识别某一数字是否是接收的查询和从候选集合中选择的查询所特有的。根据另一个实施例，计算得分包括计算值一(“1”)与下述商之间的差：接收的查询和从候选集合中选择的查询中的共现日语汉字字符的数目与接收的查询和从候选集合中选择的查询中的独特日语汉字字符的总数的商。根据本发明的另一个实施例，计算得分包括将接收的查询和从候选集合中选择的查询的一个或多个字符转换成罗马字符，并且计算这些查询共有的罗马字符的数目。根据本发明的另一个实施例，计算得分包括识别接收的查询或者从候选集合中选择的查询是否包含非罗马字符。根据本发明的另一个实施例，计算得分包括：在将每个查询的日语汉字字符转换成日语假名字符并且从每个查询中去除所有非日语字符之后，计算接收的查询和从候选集合中选择的查询之间的字符编辑距离。根据本发明的另一个实施例，计算得分包括计算在一个或多个查询日志中从候选集合中选择的查询跟随接收的查询的频率与在一个或多个查询日志中接收的查询的频率的商。

该方法还包括从候选集合的查询中选择一个或多个查询以便分发。根据本发明的一个实施例，从候选集合中选择以便分发的一个或多个查询包括具有超过给定阈值的得分的一个或多个查询。被选择以便分发的一个或多个查询可被分发。根据本发明的一个实施例，被选择以便分发的查询被嵌入在一个或多个网页中。

本发明还涉及一种用于识别与给定查询相关的一个或多个查询的系统。本发明的系统包括搜索引擎，该搜索引擎可操作以用于接收根据具有多个书写系统的语言的一个或多个书写系统书写的查询。根据本发明的一个实施例，搜索引擎可操作以用于接收根据一个或多个日语书写系统书写的查询。搜索引擎还可操作以用于识别与接收的查询相关联的、根据该具有多个书写系统的语言的一个或多个书写系统书写的一个或多个查询的候选集合。根据本发明的一个实施例，搜索引擎可操作以用于识别由如一个或多个查询日志中所指示的与接收的查询相关的一个或多个查询组成的候选集合。

转换组件可操作以用于将接收的查询和候选集合中的一个或多个查询转换成一个或多个书面格式。根据本发明的一个实施例，转换组件可操作以用于将查询转换成根据一个或多个书写系统的一个或多个书面格式。

相似性组件可操作以用于为候选集合中的一个或多个查询计算指示出该一个或多个查询与接收的查询的相似性的得分。相似性组件可操作以用于计算指示出从候选集合中选择的查询与接收的查询在含义上的相似性的得分。根据本发明的一个实施例，相似性组件可操作以用于计算接收的查询和从候选集合中选择的查询之间的字符编辑距离。根据本发明的另一个实施例，相似性组件可操作以用于计算一(“1”)与下述商之间的差：接收的查询和从候选集合中选择的查询中的独特空格分隔共现单词的数目与两个查询中的独特空格分隔单词的总数的商。根据本发明的另一个实施例，相似性组件可操作以用于识别某一数字是否是接收的查询或从候选集合中选择的查询所特有的。

根据另一个实施例，相似性组件可操作以用于计算一(“1”)与下述商之间的差：接收的查询和从候选集合中选择的查询中的共现日语汉字字符的数目与两个查询中的独特日语汉字字符的总数的商。根据本发明的另一个实施例，相似性组件可操作以用于计算接收的查询和从候选集合中选择的查询共有的字符的数目。根据本发明的另一个实施例，相似性组件可操作以用于识别接收的查询或者从候选集合中选择的查询是否包含给定书写系统的一个或多个字符。根据本发明的另一个实施例，相似性组件可操作以用于计算在一个或多个查询日志中从候选集合中选择的查询跟随接收的查询的频率与在这些查询日志中接收的查询的频率的商。

附图说明

本发明在想要为示例性而非限制性的附图中示出，在附图中类似的标号意图指代类似或相应的部件，其中：

图1是给出根据本发明一个实施例用于识别根据具有多个书写系统的语言的一个或多个书写系统的组合书写的一个或多个相关查询的系统的框图；

图2是示出根据本发明一个实施例用于选择根据具有多个书写系统的语言的一个或多个书写系统的组合书写的一个或多个相关查询的方法的一个实施例的流程图；

图3是示出根据本发明一个实施例用于计算根据具有多个书写系统的语言的一个或多个书写系统书写的两个查询之间的字符编辑距离的方法的一个实施例的流程图；

图4是示出根据本发明一个实施例用于计算根据具有多个书写系统的语言的一个或多个书写系统书写的两个查询之间的字符编辑距离的另一个实施例的流程图；

图5是示出根据本发明一个实施例用于计算根据具有多个书写系统的语言的一个或多个书写系统书写的两个查询之间的单词编辑距离的方法的一个实施例的流程图；

图6是示出根据本发明一个实施例用于识别在根据具有多个书写系统的语言的一个或多个书写系统书写的两个查询中出现的数字的差别的方法的一个实施例的流程图；

图7是示出根据本发明一个实施例用于在只考虑一个书写系统的字符的情况下计算根据具有多个书写系统的语言的一个或多个书写系统书写的两个查询之间的字符编辑距离的方法的一个实施例的流程图；

图8是示出根据本发明一个实施例用于识别在根据具有多个书写系统的语言的一个或多个书写系统书写的两个查询的前缀中重叠的字符的数目的方法的一个实施例的流程图；

图9是示出根据本发明一个实施例用于识别根据具有多个书写系统的语言的一个或多个书写系统书写的两个查询是否具有非罗马字符的方法的一个实施例的流程图；

图10是示出根据本发明一个实施例用于在根据具有多个书写系统的语言的一个或多个书写系统书写的两个查询都被转换到给定书写系统之后计算这两个查询之间的字符编辑距离的方法的一个实施例的流程图；以及

图11是示出根据本发明一个实施例用于计算根据具有多个书写系统的语言的一个或多个书写系统书写的两个查询的查询和短语替换概率的方法的一个实施例的流程图。

具体实施方式

在以下描述中，参考了形成本说明书一部分的附图，在附图中以图示方式示出了可用来实现本发明的具体实施例。应当理解，在不脱离本发明的范围的情况下，可以利用其他实施例，并且可以进行结构上的改变。

图1给出了绘出用于识别与根据具有多个书写系统的语言的一个或多个书写系统书写的给定查询相关的一个或多个查询的系统的一个实施例。根据图1的实施例，客户端设备124a、124b和124c可通信地耦合到网络122，该网络122可包括与一个或多个局域网和/或广域网(例如因特网)的连接。根据本发明的一个实施例，客户端设备124a、124b和124c是通用个人计算机，其包括处理器、暂时性和永久性存储设备、输入/输出子系统和用于在构成通用个人计算机的组件之间提供通信路径的总线。例如，具512MB的RAM、40GB的硬盘驱动器存储空间和到网络的以太网接口的3.5GHzPentium4个人计算机。其他客户端设备被认为落在本发明的范围内，包括但不限于手持式设备、机顶终端、移动手持机、PDA，等等。

可通信地耦合到网络122的客户端设备124a、124b和124c的用户可以向搜索提供商100提交包括一个或多个词语的搜索查询。用户经由网络122向搜索提供商100提交的搜索查询可包括根据具有多个书写系统的语言的一个或多个书写系统书写的一个或多个字符、词语或短语。例如，客户端设备124a、124b和124c的用户可以制定包括日语汉字字符、日语片假名字符和JASCH字符的查询。类似地，客户端设备124a、124b和124c的用户可以制定包括日语罗马字(Romaji)字符、日语平假名字符和数字的查询。例如，用户可以提交根据日语片假名、平假名、汉字和ASCII书写系统书写的以下查询：1リツトルの涙沢尻エリカ。

客户端设备124a、124b和124c的用户提交的可能包括根据具有多个书写系统的语言的一个或多个书写系统书写的字符和词语的一个或多个搜索查询可以被搜索提供商100处的搜索引擎107用来识别相关查询的候选集合。构成相关查询的候选集合的一个或多个查询可分别被维护在一个或多个本地或远程数据存储102和108中，数据存储102和108可操作以用于维护可能与给定查询相关的一个或多个查询。根据本发明的一个实施例，数据存储102和108可操作以用于维护具有标识与一个或多个查询或词语相关的一组查询的条目的索引。数据存储102和108所维护的索引可以被补充有指示出相关的词语或查询的人类编辑信息。例如，数据存储102和108中的索引条目可包括根据日语片假名、平假名、汉字和ASCII书写系统书写的查询“1リツトルの涙沢尻エリカ”，以及根据一个或多个日语书写系统书写的一个或多个相关查询或词语。

数据存储102和108可实现为数据库或能够支持对一组或多组查询的检索和存储的任何其他类型的存储结构，例如数据库、CD-ROM、磁带、数字存储库、等等。数据存储102和108中维护的查询可包括根据具有多个书写系统的给定语言的一个或多个书写系统书写的查询。例如，数据存储102和108中维护的查询可包括根据日语汉字、平假名、片假名、JASCII和罗马字书写系统书写的查询。

根据本发明的另一实施例，由搜索引擎107识别的相关查询的候选集合可包括在统计上显著地共现于一个或多个查询日志中的一个或多个有序查询对(sequentialpairofqueries)。搜索引擎107可利用查询日志来识别包括与从客户端设备124a、124b和124c接收的查询相关的一个或多个查询的候选集合。用户向搜索提供商100提交的可能根据具有多个书写系统的语言的一个或多个书写系统书写的多个查询可被维护在查询日志组件106中。查询日志组件106可实现为数据库或能够支持对根据一个或多个书写系统书写的一个或多个查询的存储的类似存储结构。

查询日志组件106可维护这样的信息：该信息标识出查询被提供给搜索提供商100的频率。类似地，查询日志组件106可维护这样的信息：该信息标识出给定查询跟随相关查询的频率。例如，在给定会话期间，进行搜索的用户可提交包括根据具有多个书写系统的语言(例如日语)的一个或多个书写系统书写的词语“intellectualproperty(知识产权)”的查询。在同一会话期间，用户可提交包括根据一个或多个日语书写系统书写的词语“patentattorney(专利代理人)”的查询。查询日志组件106可维护标识出在给定用户的会话期间查询“patentattorney”跟随查询“intellectualproperty”的频率。

搜索引擎107可利用由查询日志组件106维护的查询日志来识别候选集合，该候选集合包括与从给定的客户端设备124a、124b和124c接收的查询在统计上显著地相关的一个或多个查询。如查询日志组件106中维护的查询日志所指示的，被识别为与给定查询相关的一个或多个查询可用于补充或生成相关查询的候选集合。相关查询的候选集合可包括根据具有多个书写系统的给定语言(例如日语)的一个或多个书写系统书写的查询。用于利用查询日志来识别与给定查询相关的一个或多个查询的示例性方法在与本申请属于同一申请人的题为“SYSTEMANDMETHODFORDETERMININGALTERNATESEARCHQUERIES”的美国专利申请No.11/200,851和题为“MODULAROPTIMIZEDDYNAMICSETS”的美国临时申请No.60/736,133中有所记载，特此通过引用将上述申请的公开内容全部并入。

相似性组件104使用由搜索引擎107识别出的候选集合来为相关查询的候选集合中的一个或多个查询计算相似性得分(similarityscore)。相似性组件104可操作以用于从相关查询的候选集合中选择给定查询Q’并为Q’计算相似性得分，该相似性得分指示出Q’与从给定客户端设备124a、124b和124c接收的给定查询Q的在含义上的相似性的强度。相似性组件104可操作以用于根据这里描述的方法为搜索引擎107识别的相关查询的候选集合中的一个或多个查询中的每一个计算相似性得分。

相似性组件104可利用转换组件110来为搜索引擎107识别的相关查询的候选集合中的每个查询Q’计算相似性得分。根据本发明的一个实施例，转换组件110将给定查询转换成一个或多个书面格式(writtenformat)。由转换组件110生成的给定查询Q’的一个或多个书面格式可被递送到相似性组件104，以帮助计算相似性得分。例如，相似性组件104可针对从用户接收的给定查询Q和从相关查询的候选集合中选择的相关查询Q’执行许多比较来计算准确的相似性得分。但是，如前所述，相关查询的候选集合中的一个或多个查询可能是根据具有多个书写系统的给定语言的一个或多个书写系统来书写的。类似地，从给定的客户端设备124a、124b和124c接收的查询可能是根据具有多个书写系统的给定语言的一个或多个书写系统书写的。相似性组件104所执行的一个或多个比较可能要求从用户接收的查询Q和从相关查询的候选集合选择的给定查询Q’是根据特定的书写系统来表达的。例如，相似性组件104可能要求给定查询Q和相关查询Q’的一个或多个JASCII字符被转换成ASCII字符以便比较两个查询。

为了比较可能根据不同的书写系统书写的查询Q和查询Q’，相似性组件104可将给定的查询递送到转换组件110。根据本发明的一个实施例，转换组件110可操作以用于识别与给定查询相关联的语言和书写系统，并将该查询转换成一个或多个替代的书面格式。由搜索引擎107识别的候选集合可包括根据具有多个书写系统的给定语言的多种书写系统书写的查询，例如根据日语汉字、假名、JASCII和罗马字书写系统书写的查询。转换组件110可操作以用于识别出查询是根据一个或多个日语书写系统书写的并将该查询转换成一个或多个替代书写系统。例如，转换组件110可操作以用于识别出查询是根据日语片假名书写系统书写的并根据日语罗马字书写系统来转换该查询。类似地，转换组件110可操作以用于识别出查询包括一个或多个JASCII字符并将该一个或多个JASCII字符转换成ASCII字符，以帮助相似性组件104计算相似性得分。

根据本发明的一个实施例，由相似性组件104为相关查询的候选集合中的一个或多个查询计算的相似性得分被分发组件116用于从候选集合中选择一个或多个查询以便进行分发。基于相似性得分来选择查询使得可以选择与给定查询Q在含义上最相似的查询。例如，分发组件116可以从相关查询的候选集合中选择具有超过给定阈值的相似性得分的一个或多个查询。类似地，分发组件可从候选集合中选择具有最大相似性得分的N个查询。本领域的技术人员明白其他的用于利用相似性得分从候选集合中选择一个或多个查询的技术。

分发组件116可分发从候选集合选择的一个或多个查询。根据本发明的一个实施例，分发组件116经由网络122将从候选集合选择的查询作为“建议替代查询”或“含义相似的查询”显示给用户。作为前述内容的替代或与前述内容相结合，分发组件116可操作以用于将该选择的一个或多个查询递送给搜索引擎107，搜索引擎107可将所选择的查询嵌入在搜索结果网页中，该搜索结果网页可以被可通信地耦合到网络122的客户端设备124a、124b和124c的给定用户所查看。

由相似性组件104为候选集合中的一个或多个查询计算出的相似性得分还可用于选择一个或多个内容项(包括广告)，以便响应于给定请求而分发。根据本发明的一个实施例，广告可被维护在上述数据存储102和108中，或被维护在一个或多个不同的数据存储中(未示出)。一个或多个本地数据存储102、远程数据存储108或不同的数据存储可操作以用于维护一个或多个广告以及相关联的对与广告相对应的词语的出价。例如，给定的广告主可能希望显示针对笔记本计算机的给定广告。广告主因此可为词语“notebookcomputer”出价，并且识别出将要响应于包括词语“notebookcomputer”的查询而显示的广告。当搜索提供商100接收到查询时，搜索引擎107可搜索本地和远程数据存储102和108，或者一个或多个不同的数据存储，以判定是否有一个或多个广告主为构成所接收的查询的一个或多个词语提供了出价。如果识别出针对构成查询的词语的一个或多个出价，那么利用分发组件116，与对一个或多个词语的出价相关联的广告可被检索出并在用户的客户端设备124a、124b和124c上被显示给用户。如果用户选择了所显示的给定广告，则与所选择的广告相关联的广告主可以根据该广告主的出价而被收取某一货币金额。

但是，广告主可选择为只根据具有多个书写系统的语言的单个书写系统书写的词语出价。例如，广告主可选择为只根据日语平假名书写系统书写的词语出价。但是，如前所述，由客户端设备124a、124b和124c的用户提交的一个或多个搜索查询可包括根据一个或多个书写系统书写的词语和短语。搜索引擎107因而可利用具有超过给定阈值的相似性得分的查询来扩展响应于给定查询而检索出的广告的范围。根据本发明的一个实施例，搜索引擎107识别响应于构成具有超过给定阈值的相似性得分的一个或多个查询的词语的一个或多个广告。被识别为响应于构成具有超过给定阈值的相似性得分的查询的词语的一个或多个广告被选择以便分发到一个或多个客户端设备124a、124b和124c。

例如，客户端设备124a、124b和124c的用户可制定根据日语汉字和罗马字书写系统两者书写的日语词语组成的搜索查询Q。用户可经由网络122将该查询提交给搜索提供商100。搜索引擎107可确定没有广告主为用户所利用的汉字和罗马字词语提供了出价。作为前述内容的替代或与前述内容相结合，搜索引擎107可确定显示对应于与用户所利用的汉字和罗马字词语相关联的出价的广告将会产生很少的收入，或者甚至不产生收入。但是，搜索引擎107可利用构成从候选集合中选择的具有超过给定阈值的相似性得分的一个或多个查询的词语来识别具有相关联的出价的一个或多个词语。类似，搜索引擎107可利用构成从候选集合中选择的具有超过给定阈值的相似性得分的一个或多个查询的词语来识别具有超过给定阈值的出价的一个或多个词语。搜索引擎107然后可利用具有相关联的出价的一个或多个词语，或者具有相关联的超过给定阈值的出价的一个或多个词语，来选择响应于由用户制定的搜索查询Q的一个或多个广告。

根据另一示例，假定从候选集合中选择的具有超过给定阈值的相似性得分的给定查询Q’包括平假名词语，而上述由用户制定的查询Q包括汉字和罗马字词语。搜索引擎可利用构成查询Q’的一个或多个平假名词语来判定是否有一个或多个广告主为构成查询Q’的平假名词语出了价。类似地，搜索引擎可判定是否有一个或多个广告主为构成查询Q’的一个或多个平假名词语提供了超过给定阈值的出价。搜索引擎107可检索出具有相关联的对构成查询Q’的词语的出价的一个或多个广告，并将该一个或多个广告递送到分发组件。根据本发明的一个实施例，搜索引擎107检索出具有最大的相关联的对于构成查询Q’的一个或多个词语的出价的一个或多个广告。分发组件116随后可以将该一个或多个广告递送给提交了查询Q的用户。

虽然上述实施例描述了对查询的接收和处理，但是图1所示的搜索提供商100系统不限于接收查询并计算查询的相似性得分，而是还可用于为构成一个或多个文本串的一个或多个词语计算相似性得分。客户端设备124a、124b和124c的用户可向搜索提供商100递送包括一个或多个词语的一个或多个文本串，包括但不限于根据具有多个书写系统的语言的一个或多个书写系统书写的短语、句子、段落和文档。相应地，搜索提供商100可将这一个或多个文本串的日志记录在一个或多个日志文件中。搜索提供商100可操作以用于从其日志文件中识别出包括一个或多个项目的候选集合，其中给定项目包括与由客户端设备124a、124b和124c的给定用户递送的一个或多个词语相关的一组或多组词语。例如，候选集合中的给定项目可包括短语或句子。类似地，候选集合中的给定项目可包括段落或整个文档。搜索提供商可为候选集合中的一个或多个项目计算相似性得分，该相似性得分指示出一个项目与从客户端设备124a、124b和124c接收的一个或多个词语在含义上的相似性的强度。

图2示出了用于从候选集合中选择在含义上与给定查询Q相关的一个或多个查询Q’的方法的一个实施例，其中查询Q和Q’是根据具有多个书写系统的语言的一个或多个书写系统书写的。如图2所示，从给定用户接收搜索查询，步骤205。该查询可以是从可通信地耦合到诸如因特网之类的网络的客户端设备接收的，并且可包括根据具有多个书写系统的语言的一个或多个书写系统的组合来书写的一个或多个词语或短语。例如，从用户接收的查询可包括根据汉字、片假名和平假名书写系统书写的日语词语。

识别由与用户制定的给定查询Q相关的查询组成的候选集合，步骤210。候选集合可由根据与用户的查询相关联的语言的一个或多个书写系统书写的查询组成。例如，给定查询Q可包括根据日语片假名书写系统书写的词语，例如查询“ラクテン”。相关查询的候选集合因而可以包括根据一个或多个日语书写系统的一个或多个组合书写的一个或多个查询。例如，与上述平假名查询“ラクテン”相关的查询的候选集合可包括罗马字查询“rakuten”、汉字查询“楽天”、平假名查询“らくてん”，等等。

与给定查询Q相关的查询的候选集合可利用一个或多个查询日志来生成。根据本发明的一个实施例，查询日志可标识在给定的查询会话期间由用户制定的一个或多个查询。例如，在给定的查询会话期间，用户可以制定包括根据日语平假名和汉字书写系统书写的词语的查询。在同一查询会话期间，用户还可制定包括根据日语片假名和罗马字书写系统书写的词语的查询。可以执行分析以判定两个查询是否在统计上显著地共现于一个或多个查询日志中。根据本发明的一个实施例，统计显著性(statisticalsignificance)阈值可用于选择如一个或多个查询日志所指示的与给定查询Q最相关的一个或多个查询。

可以利用如一个或多个查询日志所指示的被识别为在统计上显著地与给定查询相关或者以超过给定阈值的统计显著性与给定查询相关的一个或多个查询来生成候选集合。构成相关查询的候选集合的一个或多个查询可根据在以上标识出的通过引用全部并入的申请中描述的用于利用查询日志来确定统计上显著相关的查询的方法来选择。

从相关查询的候选集合选择给定查询Q’，步骤215。根据图2所示的实施例，为所选择的查询Q’计算相似性得分，步骤220。为给定查询Q’计算相似性得分提供了指示出查询Q’的含义与根据具有多个书写系统的语言的一个或多个书写系统书写的给定查询Q的含义的相似性的强度的数值。表A示出了可用于为给定查询Q’计算相似性得分的式子的一个实施例。

表A中给出的式子可用于计算指示出给定查询Q’与给定查询Q在含义上的相似性的强度的得分，所述给定查询Q可以是根据一个或多个日语书写系统来书写的，所述一个或多个日语书写系统包括但不限于汉字、假名、JASCII、假名、片假名、罗马字和平假名。本领域的技术人员明白，表A中所示的式子可以被修改，以支持为其他具有多个书写系统的语言计算相似性得分。

表A

根据表A中给出的式子，Q表示根据一个或多个日语书写系统书写的给定查询。Q’表示从与查询Q相关的查询的候选集合中选择的查询。Levr是用于将所有日语字符转换成罗马字符之后计算Q和Q’之间的字符编辑距离的函数。Levrs是用于在将所有日语字符转换为罗马字符并去除空格后计算Q和Q’之间的字符编辑距离的函数。Wordr是在将所有日语字符转换成罗马字符之后Q和Q’之间的单词编辑距离。Digit是用于识别Q是否包含任何未出现在Q’中的数字以及识别Q’是否包含任何未出现在Q中的数字的函数。Kanjid是用于判定Q或Q’是否包含汉字字符并且在包含的情况下识别Q和Q’之间的汉字不一致的函数。Opr是这样一个函数，该函数用于计算在每个查询中的所有日语字符都已被转换成罗马字符之后，从每个查询的最左边字符起直到第一个字符不一致为止，Q和Q’共同具有的字符的数目。Levk是用于计算在所有汉字字符都已被转换成假名字符并且所有的非日语字符都被去除之后Q和Q’之间的字符编辑距离的函数。P12min是用于计算在用户查询会话的日志中查询Q’跟随着查询Q的查询替换概率的函数。表A中所示的相似性得分函数所利用的函数的示例在图3至图11中示出。

执行检查以判定是否已为候选集合中的一个或多个查询计算相似性得分，步骤225。如果候选集合中的一个或多个查询不具有相关联的相似性得分，则从候选集合中选择另外的查询Q’，步骤215。或者，如果已经为候选集合中的一个或多个查询计算了相似性得分，则从候选集合中选择给定查询Q’，步骤230。执行检查以判定与从候选集合中选择的查询Q’相关联的相似性得分是否超过给定的相似性得分阈值，步骤235。根据本发明的一个实施例，相似性得分阈值包括可用于执行与下述相似性得分的比较的数值：该相似性得分与给定查询Q’相关联。因为相似性得分指示出给定查询Q’与查询Q在含义上的相似性的强度，因此对相似性得分阈值的使用帮助了从候选集合中选择在含义上与查询Q最相似的一个或多个查询。

如果与给定查询Q’相关联的相似性得分超过相似性得分阈值，则查询Q’被添加到分发集合，步骤245。根据本发明的一个实施例，分发集合包括从候选集合中选择的具有超过相似性得分阈值的相似性得分的一个或多个查询。如果与给定查询Q’相关联的相似性得分不超过相似性得分阈值，则查询Q’不被添加到分发集合，步骤240。

执行检查以判定在候选集合中是否有另外的查询需要分析，步骤250。如果在候选中有一个或多个查询需要分析，则从候选集合中选择另外的查询Q’，步骤230。或者，在候选集合中的所有查询都已被分析，并且分发集合已被填充以超过相似性得分阈值的一个或多个查询之后，分发集合中的一个或多个查询被分发，步骤255。

超过相似性得分阈值的查询的分发集合中的一个或多个查询可被递送给提交了查询Q的用户。根据本发明的一个实施例，分发集合中的一个或多个查询可在结果网页中被显示给用户。例如，用户可被呈现以网页，该网页包括结果，例如指向响应于查询Q的内容项的链接，以及构成分发集合的在含义上与查询Q最相似的一个或多个Q’查询。递送给给定用户的分发集合中的一个或多个查询可根据相似性得分被显示在排名列表中，以向用户指示出给定查询Q’与查询Q在含义上的相似性的相对强度。

图3至11示出了表A中给出的可用于为从查询的候选集合选择的给定查询Q’计算相似性得分的函数的实施例。如前所述，在表A中示出并在图3至11中进一步描述的多个函数可用于计算指示出给定查询Q’与根据一个或多个日语书写系统书写的查询Q在含义上的相似性的强度的相似性得分。但是，本领域的技术人员明白，图3至11所示的函数的实施例是示例性的，而并不想要限于日语语言和书写系统，并且可以被修改以支持为其他具有多个书写系统的语言计算相似性得分。本领域的技术人员还明白，图3至11所示的函数并不限于为包括与给定查询相关的一个或多个查询的候选集合计算相似性得分，而是可用于为包括根据多个技术选择的一个或多个查询的查询候选集合计算相似性得分。此外，本领域的技术人员明白，图3至11所示的函数并不限于为包括一个或多个查询的候选集合计算相似性得分，而是可被修改以为包括但不限于短语、句子、段落和文档在内的一组或多组词语计算相似性得分。

图3示出了用于计算根据一个或多个日语书写系统书写的给定查询Q和从查询的候选集合中选择的查询Q’之间的字符编辑距离的方法的一个实施例。图3中给出的方法示出了表A所示的相似性得分函数所利用的levk函数的一个实施例。

将构成查询Q的一个或多个字符转换成罗马字符，步骤305，其中查询Q可能是根据诸如汉字、片假名、平假名等等之类的一个或多个日语书写系统书写的。从由一个或多个查询组成的候选集合中选择给定查询Q’，步骤310。从候选集合中选择的查询Q’可能是根据与查询Q相关联的语言的一个或多个书写系统来书写的。例如，Q’可能是根据与查询Q相同的书写系统书写的，或者是根据诸如日语罗马字书写系统、日语假名书写系统等等之类的一个或多个替代的日语书写系统书写的。执行检查以判定构成Q’的字符是否是罗马字符形式的，步骤315。如果查询Q’不是罗马字符形式的，则构成Q’的一个或多个字符被转换成罗马字符，步骤320。如果构成Q’的一个或多个词语已经是罗马字符形式的，或者在Q’中的所有字符都被转换成罗马字符形式之后，执行计算以识别查询Q和查询Q’之间的字符编辑距离，步骤325。字符编辑距离值可以被提供给表A中示出的相似性得分函数以为Q’计算相似性得分。

图4示出了用于计算根据一个或多个日语书写系统书写的给定查询Q和从查询的候选集合中选择的查询Q’之间的字符编辑距离的方法的一个实施例。图4中示出的实施例提供了表A所示的相似性得分函数所使用的levrs函数的一个实施例。

根据图4所示的实施例，将根据诸如汉字、片假名、平假名等等之类的一个或多个日语书写系统书写的查询Q转换成罗马字符形式，步骤405。然后，去除罗马字符形式的查询Q中出现的所有空格字符，步骤408。例如，给定查询Q可包括汉字词语“電車男”。在转换到罗马字符形式之后，查询Q可包括词语“denshaotoko”，而在去除空格之后，查询Q可包括字符“denshaotoko”。

从包括一个或多个查询的候选集合中选择给定查询Q’，步骤410。执行检查以判定Q’是否是罗马字符形式的，步骤415。如果查询Q’不是罗马字符形式的，则构成Q’的一个或多个字符被转换成罗马字符，步骤420。如果构成Q’的字符已经是罗马字符形式的，或者在构成查询Q’的字符都已被转换成罗马字符形式之后，查询Q’内的所有空格被去除，步骤425。然后，计算查询Q和Q’的罗马字符形式之间的字符编辑距离，步骤430。所计算出的查询Q和Q’之间的字符编辑距离可被表A中所示的相似性得分函数用来为Q’计算相似性得分。

图5示出了表A中所示的wordr函数的一个实施例。图5中所示的wordr函数的实施例支持计算根据一个或多个日语书写系统书写的给定查询Q和从查询的候选集合选择的查询Q’之间的单词编辑距离。根据本发明的一个实施例，给定查询Q和查询Q’之间的单词编辑距离是值一(“1”)与下述商之间的差：Q和Q’中的独特空格分隔共现单词的数目与Q和Q’两者中的独特空格分隔单词的总数的商。

将构成根据一个或多个日语书写系统书写的给定查询Q的字符转换成罗马字符形式，步骤505。然后，从查询的候选集合中选择给定查询Q’，步骤506。执行检查以判定查询Q’是否是罗马字符形式的，步骤508。如果查询Q’不是罗马字符形式的，则构成Q’的字符被转换成罗马字符，步骤510。如果构成查询Q’的字符已经是罗马字符形式的，或者在构成Q’的字符已被转换成罗马字符形式之后，识别Q和Q’中的独特空格分隔共现单词的数目，步骤515。计算Q和Q’中的独特空格分隔共现单词的数目与Q和Q’两者中的独特空格分隔单词的总数的商，步骤520。根据本发明的一个实施例，独特空格分隔共现单词的数目包括在给定查询Q和给定查询Q’两者之中都出现的独特单词的数目。此外，Q和Q’两者中的独特空格分隔单词的总数包括给定查询Q和查询Q’中的独特空格分隔单词的总和。

计算值一(“1”)和计算出的商之间的差，步骤525，并将其赋予“wordr”寄存器，步骤530。根据本发明的一个实施例，“wordr”寄存器包括用于存储给定数值的存储设备。赋予“wordr”寄存器的值可被表A中所示的相似性得分函数用来为查询Q’计算相似性得分。

例如，罗马字符形式的给定查询Q可由词语“kurumakemuri”组成。类似地，罗马字符形式的给定查询Q’可由词语“sorakemuri”组成。Q和Q’中的独特空格分隔共现单词的数目是一(“1”)，即单词“kemuri”，其中Q和Q’两者中独特空格分隔单词的总数是三(“3”)，即单词“kuruma”、“sora”和“kemuri”。因此，Q和Q’中的独特空格分隔共现单词的数目与Q和Q’两者中的独特空格分隔单词的总数的商为1/3。此外，一(“1”)与计算出的商之间的差是2/3。值2/3可被赋予“wordr”寄存器，并且可被表A中所示的相似性得分函数用来为查询Q’计算相似性得分。

图6示出了这样一个方法的一个实施例，该方法用于判定与从查询的候选集合选择的查询Q’相比，某一数字是否是根据一个或多个日语书写系统书写的给定查询Q所特有的。图6中给出的方法提供了表A所示的相似性得分函数所使用的digit函数的一个实施例。

从由根据一个或多个书写系统书写的查询组成的候选集合中选择给定查询Q’，步骤605。执行检查以判定给定查询Q中的数字是否未出现在查询Q’中。例如，给定查询Q可包含日语汉字数字“六十八”(对应于由阿拉伯数字“68”所表达的值)，并且给定查询Q’可包含日语汉字数字“九十八”(对应于由阿拉伯数字“98”所表达的值)。在步骤610执行的检查因此确定日语汉字数字“六”是查询Q所特有的，因为它未出现在查询Q’中。类似地，给定查询Q可包括日语汉字字符和阿拉伯数字“楽天2005”，并且给定查询Q’可包括日语汉字字符和阿拉伯数字“楽天2004”。在步骤610执行的检查将会确定阿拉伯数字5是查询Q所特有的，因为它未出现在查询Q’中。

如果某一数字被识别为出现在查询Q中，但未出现在查询Q’中，则“digit”寄存器被设置到值一(“1”)，表明查询Q包含不在查询Q’中的数字，步骤620。根据本发明的一个实施例，“digit”寄存器包括用于存储给定数值的存储设备。

或者，如果Q’包含出现在查询Q中的一个或多个数字中的每一个，则执行额外的检查以判定查询Q’中的数字是否未出现在查询Q中，步骤615。如果查询Q’包含未出现在查询Q中的数字，则上述“digit”寄存器被设置到值一(“1”)，表明查询Q’包含Q’所特有的数字，步骤620。或者，如果查询Q包含Q’中的一个或多个数字中的每一个，则“digit”寄存器被设置到零(“0”)，步骤625，表明查询Q’中的一个或多个数字出现查询Q中，反之亦然。赋予“digit”寄存器的值零(“0”)或一(“1”)可被表A中所示的相似性得分函数用来为查询Q’计算相似性得分。

图7给出了被表A中所示的相似性得分函数使用的kanjid函数的一个实施例。接收可能根据一个或多个日语书写系统书写的给定查询Q，步骤705。执行检查以判定查询Q是否包含一个或多个日语汉字字符，步骤710。如果查询Q不包含任何汉字字符，则“kanjid”寄存器被设置到零(“0”)，步骤708，其中“kanjid”寄存器可包括用于存储给定数值的存储设备。或者，如果查询Q包含一个或多个汉字字符，则从查询的候选集合中选择查询Q’，步骤715。

执行检查以判定从候选集合中选择的查询Q’是否包含一个或多个汉字字符，步骤720。如果查询Q’不包含任何汉字字符，则上述“kanjid”寄存器被设置到零(“0”)，步骤708。相反，如果Q’包含一个或多个汉字字符，则Q和Q’中的一个或多个非汉字字符被去除，步骤722。然后识别查询Q和查询Q’中共现的独特汉字字符的数目，步骤725。例如，如果在去除非汉字字符后查询Q由汉字字符“楽天市埸”组成，并且如果在去除非汉字字符后查询Q’由汉字字符“楽天”组成，则Q和Q’中的独特共现汉字字符的数日是二(“2”)，即“楽天”。

然后识别Q和Q’两者之中的独特汉字字符的总数，步骤727。例如，在由汉字字符“楽天市埸”组成的Q和由汉字字符“楽天”组成的Q’两者之中的独特汉字字符的总数是六(“6”)，即来自查询Q的独特汉字字符“楽天市埸”和来自查询Q’的独特汉字字符“楽天”。计算共现汉字字符的数目与总独特汉字字符的商，步骤730。将“kanjid”寄存器设置到一(“1”)与计算出的商之间的差值，步骤735。“kanjid”寄存器的值可被表A中所示的相似性得分函数用来为Q’计算相似性得分。

图8示出了用于识别根据一个或多个日语书写系统书写给定查询Q和从查询的候选集合中选择的查询Q’的前缀中重叠的字符数目的方法的一个实施例，该方法开始于比较每个查询的最左边字符，并且继续到第一个字符不一致为止。图8中给出的方法示出了被表A中所示的相似性得分函数利用的opr函数的一个实施例。

将根据一个或多个日语书写系统书写的给定查询Q转换成罗马字符形式，步骤805。从查询的候选集合中选择查询Q’，步骤810。执行检查以判定构成查询Q’的一个或多个字符是否是罗马字符形式的，步骤815。如果构成查询Q’的一个或多个字符不是罗马字符形式的，则将这些字符转换成罗马字符，步骤820。如果构成Q’的字符已经是罗马字符形式的，或者在构成Q，的一个或多个字符已被转换成罗马字符形式之后，选择查询Q和查询Q’的第一罗马字符，步骤825。

执行检查以判定从查询Q中选择的第一字符和从查询Q’中选择的第一字符是否匹配，步骤835。如果从Q和Q’选择的第一字符不匹配，则处理终止，步骤830。或者，如果选择的字符匹配，则使字符匹配计数寄存器递增，步骤850，表明识别出查询Q和查询Q’的字符匹配。根据本发明的一个实施例，字符匹配计数寄存器被初始化为值零(“0”)，并且在来自查询Q和查询Q’的字符被识别为匹配时被递增。

选择来自Q和Q’的下一字符，步骤840，并且执行检查以判定下一字符是否匹配，步骤835。如果从Q和Q’选择的字符不匹配，则字符匹配计数寄存器不被递增，并且处理结束，步骤830。当处理终止时，步骤830，字符匹配计数寄存器中的值将指示出Q和Q’中匹配的字符的数目。字符匹配计数寄存器中的值被表A中所示的相似性得分函数利用来为查询Q’计算相似性得分。

图9示出了用于识别根据一个或多个日语书写系统书写的给定查询Q或者从查询的候选集合中选择的查询Q’是否包含非罗马字符的方法的一个实施例。图9给出的实施例示出了可被表A中所示的相似性得分函数使用的japanese函数。

接收根据一个或多个日语书写系统书写的给定查询Q，步骤905。执行检查以判定查询Q是否包含一个或多个非罗马字符，步骤910。如果查询Q包含一个或多个非罗马字符，则“japanese”寄存器被设置到值一(“1”)，步骤908。根据本发明的一个实施例，“japanese”寄存器包括用于存储给定数值的存储设备。

如果查询Q不包含一个或多个非罗马字符，则从包括一个或多个查询的候选集合中选择查询Q’，步骤915。执行检查以判定查询Q’是否包含一个或多个非罗马字符，步骤920。如果查询Q’包含一个或多个非罗马字符，则“janapese”寄存器被设置到值(“1”)，步骤908。或者，如果Q’仅包含非罗马字符，则“japanese”寄存器被设置到值零(“0”)，步骤922，并且处理随后终止，步骤925。“japanese”寄存器中维护的值可被表A中所示的相似性得分函数利用来为查询Q’计算相似性得分。

图10示出了用于在所有汉字和非日语字符已被从每个相应的查询中去除之后确定给定查询Q和查询Q’之间的字符编辑距离的方法的一个实施例。图10给出的方法示出了可被表A中所示的相似性得分函数利用的levk函数的一个实施例。

如图10所示，从查询的候选集合中选择给定查询Q’，步骤1005。执行检查以判定根据一个或多个日语书写系统书写的查询Q’或给定查询Q是否包含一个或多个汉字字符，步骤1010。如果查询Q或查询Q’包含一个或多个汉字字符，则每个相应的查询中的汉字字符被转换成假名字符，步骤1015。例如，查询Q可由汉字字符和阿拉伯数字两者组成，例如“人200”。在将汉字字符转换成假名字符之后，查询Q可包括字符“ひと200”。

如果查询Q或查询Q’都不包含汉字字符，或者在每个相应查询中的所有汉字字符都已被转换成假名字符之后，执行额外的检查以判定任一查询是否包含非日语字符，步骤1020。根据本发明的一个实施例，非日语字符包括不是根据一个或多个日语书写系统书写的字符。例如，如果查询Q包括假名字符和阿拉伯数字，例如“ひと200”，则阿拉伯数字“200”可包括非日语字符。

如果查询Q或查询Q’包含非日语字符，则非日语字符被去除，步骤1025。参考上述示例，在从查询Q去除非日语字符即阿拉伯数字“200”之后，查询Q可包括假名字符“ひと”。如果查询Q或查询Q’都不包含非日语字符，或者在所有非日语字符都已被去除之后，Q和Q’之间字符编辑距离被计算，步骤1030。查询Q和查询Q’之间的字符编辑距离可被表A中所示的相似性得分函数用来为Q’计算相似性得分。

图11给出了被表A中所示的相似性得分函数利用的p12min函数的一个实施例。根据本发明的一个实施例，p12min函数计算给定查询Q’跟随给定查询Q的查询替换概率，并且也可用来计算短语P’跟随给定短语P的短语替换。例如，可以维护一个或多个查询日志，这一个或多个查询日志标识出在查询会话期间由给定用户提交的一个或多个查询和短语。查询日志例如可标识用户提交的一个或多个查询和短语的顺序，以提供关于用户如何改进查询Q、用户如何改写查询Q、用户如何利用具有多个书写系统的语言的一个或多个替代书写系统来表达查询Q等等的指示。查询日志还可指示出一个或多个用户提交一个或多个查询或短语的频率。

识别给定查询Q出现在一个或多个查询日志中的频率，步骤1105。从查询的候选集合中选择给定查询Q’，步骤1110。执行检查以判定在一个或多个查询日志中的任何一个中查询Q’是否跟随查询Q，步骤115。根据本发明的一个实施例，执行检查以判定在针对给定用户的查询会话的查询日志中查询Q’是否跟随查询Q，其中查询会话可包括在给定时间段期间由用户提交的一个或多个查询。

如果在一个或多个查询日志中的任何一个之中查询Q’都不跟随查询Q，则“p12min”寄存器被设置到零(“0”)，步骤1125，其中“p12min”寄存器可包括用于存储给定数值的存储设备。或者，如果查询Q’被识别为在一个或多个查询日志中跟随Q，则识别在查询日志中查询Q’跟随查询Q的频率，步骤1120。“p12min”寄存器被设置到在查询日志中查询Q’跟随查询Q的频率与查询日志中查询Q的频率的商的值，步骤1140。例如，如果查询Q在查询日志中出现十二(“12”)次并且在查询日志中Q’跟随查询Q七(“7”)次，则“p12min”寄存器可被设置到值“7/12”。

本领域的技术人员明白，在图3至11中示出并被表A中所示的相似性得分函数所利用的函数并不限于日语语言，而是可被修改用于一个或多个具有多个书写系统的语言。本领域的技术人员还明白，表A中所示的相似性得分函数可利用图3至11所示的函数的一个或多个组合，以为根据具有多个书写系统的语言的一个或多个书写系统书写的给定查询计算相似性得分。

虽然已经结合优选实施例描述和示出了本发明，但是在不脱离本发明的精神和范围的情况下可以进行对于本领域的技术人员来说显而易见的许多变化和修改，本发明因而不限于以上阐述的方法或构造的确切细节，因为这种变化和修改想要被包括在本发明的范围之内。

Claims (17)

1.一种用于识别与给定查询相关的一个或多个查询的方法，该方法包括：

接收根据具有多个书写系统的语言的一个或多个书写系统书写的查询；

将所述查询的一个或多个字符转换成罗马字符；

识别与所接收的查询相关联的根据所述具有多个书写系统的语言的一个或多个书写系统书写的查询的候选集合；

将所述查询的候选集合中的一个或多个查询的一个或多个字符转换成罗马字符；

计算所述查询的罗马字符形式与所述查询的候选集合中的一个或多个查询的罗马字符形式之间的字符编辑距离；

基于所述字符编辑距离来计算所述候选集合中的一个或多个查询的相似性得分，其中，所述相似性得分指示所述一个或多个查询与所接收的查询的相似性；以及

基于所述相似性得分，从所述候选集合中选择具有超过给定阈值的相似性得分的一个或多个查询以便分发。

2.如权利要求1所述的方法，其中，接收查询包括接收根据一个或多个日语书写系统书写的查询。

3.如权利要求1所述的方法，其中，计算所述字符编辑距离包括：从所接收的查询的罗马字符形式以及所述候选集合中的一个或多个查询的罗马字符形式移除空格字符。

4.如权利要求1所述的方法，其中，计算所述相似性得分包括：计算所接收的查询的罗马字符形式和所述候选集合中的一个或多个查询的罗马字符形式的公共的罗马字符的数目。

5.如权利要求1所述的方法，其中，计算所述相似性得分包括：

识别所接收的查询和所述候选集合中的一个或多个查询中的独特空格分隔共现单词的数目；

识别所接收的查询和所述候选集合中的一个或多个查询中的独特空格分隔单词的总数；

计算所述独特空格分隔共现单词的数目与所接收的查询和所述候选集合中的一个或多个查询中的所述独特空格分隔单词的总数的商；以及

计算数值1与计算出的商之间的差。

6.如权利要求1所述的方法，其中，计算所述相似性得分包括：识别所接收的查询或从所述候选集合所选择的查询是否包含非罗马字符。

7.如权利要求1所述的方法，包括：将从所述候选集合所选择的一个或多个查询提供作为建议替代查询。

8.如权利要求1所述的方法，包括：将从所述候选集合所选择的一个或多个查询提供作为在含义上与所接收的查询相似的查询。

9.如权利要求1所述的方法，包括：检索与从所述候选集合所选择的一个或多个查询相关联的一个或多个广告。

10.如权利要求1所述的方法，包括：判断一个或多个广告是否已对包括所述候选集合中的一个或多个查询的一个或多个词语出价。

11.如权利要求10所述的方法，包括：检索针对具有与所述候选集合中的一个或多个查询相关联的一个或多个出价的所述一个或多个词语的一个或多个广告。

12.一种用于识别与给定查询相关的一个或多个查询的系统，该系统包括：

数据库，该数据库包括一个或多个查询，所述一个或多个查询包括根据具有多个书写系统的语言的一个或多个书写系统书写的有关查询的候选集合；

搜索引擎，该搜索引擎用于接收根据具有多个书写系统的语言的一个或多个书写系统书写的查询，并且识别所述数据库中的有关查询的候选集合；

转换组件，该转换组件将所接收的查询以及所述有关查询的候选集合中的一个或多个查询的一个或多个字符转换成罗马字符；

相似性组件，该相似性组件用于计算所述查询的罗马字符形式与所述有关查询的候选集合中的一个或多个查询的罗马字符形式之间的字符编辑距离，并且基于所述字符编辑距离来计算所述有关查询的候选集合中的一个或多个查询的相似性得分，其中，所述相似性得分指示所述一个或多个查询与所接收的查询的相似性；

其中，所述搜索引擎能进行操作以基于所述相似性得分，从所述候选集合中选择具有超过给定阈值的相似性得分的一个或多个查询以便分发。

13.如权利要求12所述的系统，其中，所述搜索引擎能进行操作以接收根据一个或多个日语书写系统书写的查询。

14.如权利要求12所述的系统，其中，所述相似性组件能进行操作以从所接收的查询的罗马字符形式以及所述有关查询的候选集合中的一个或多个查询的罗马字符形式移除空格字符。

15.如权利要求12所述的系统，其中，所述相似性组件能进行操作以计算所接收的查询的罗马字符形式和所述有关查询的候选集合中的一个或多个查询的罗马字符形式的公共的罗马字符的数目。

16.如权利要求12所述的系统，所述搜索引擎能进行操作以判断一个或多个广告是否已对包括所述有关查询的候选集合中的一个或多个查询的一个或多个词语出价。

17.如权利要求16所述的系统，所述搜索引擎能进行操作以检索针对具有与所述有关查询的候选集合中的一个或多个查询相关联的一个或多个出价的所述一个或多个词语的一个或多个广告。