CN103870000B

CN103870000B - 一种对输入法所产生的候选项进行排序的方法及装置

Info

Publication number: CN103870000B
Application number: CN201210531929.8A
Authority: CN
Inventors: 吴先超
Original assignee: Baidu International Technology Shenzhen Co Ltd
Current assignee: Baidu International Technology Shenzhen Co Ltd
Priority date: 2012-12-11
Filing date: 2012-12-11
Publication date: 2018-12-14
Anticipated expiration: 2032-12-11
Also published as: CN103870000A

Abstract

本发明公开了一种对输入法所产生的候选项进行排序的方法及装置。其中，对输入法所产生的候选项进行排序的方法包括：利用输入法接收当前用户的当前输入信息；根据已经建立的与用户类型相关的G个不同的语言模型，获取当前用户当前输入信息的候选项集合中每个候选项所属的用户类型；按照每个候选项所属的用户类型与已获得的当前用户所属的用户类型集合中的用户类型的相关性大小，对当前用户当前输入信息的候选项进行排序；展示进行排序后的候选项。通过上述方式，本发明能够针对不同类型的用户输入相同的字符时，对不同类型的用户推送不同排序的候选项，减少用户选择候选所花费的时间，提升用户体验。

Description

一种对输入法所产生的候选项进行排序的方法及装置

技术领域

本发明涉及输入法领域，特别是涉及一种对输入法所产生的候选项进行排序的方法及装置。

背景技术

输入法是指为了将各种符号输入计算机或其他设备（如手机）而采用的编码方法。

利用输入法进行输入时，通常通过向设备发送各种字符以获取字符对应的候选项，并选择相应的候选项来完成输入。而对于输入的相同读音的字符时，获取得到的字符对应的候选项的集合中各候选项的排序通常都是一样的。对于假名“かがく”，这个读音所对应的日文汉字包括“価格、科学、化学、歌学、花岳”等众多候选，向用户推送的候选基本是一样的，或者是只按照候选项在大规模语料中出现的频次来排序。

但是，本申请的发明人在长期的研发中发现，不同的类型的用户对于同一个字符对应的候选项的排序要求也是不一样的。向所有的用户推送相同排序的候选项，大部分用户通常浪费大量的时间以选择需要的候选项，这样也降低了用户体验。

发明内容

本发明主要解决的技术问题是提供一种对候选项的排序方法及装置，能够针对不同类型的用户输入相同的字符时，对不同类型的用户推送不同排序的候选项，减少用户选择候选所花费的时间，提升用户体验。

为解决上述技术问题，本发明采用的一个技术方案是：提供一种对输入法所产生的候选项进行排序的方法，包括：利用所述输入法接收当前用户的当前输入信息；根据已经建立的与用户类型相关的G个不同的语言模型，获取所述当前用户当前输入信息的候选项集合中每个候选项所属的用户类型；按照所述每个候选项所属的用户类型与已获得的所述当前用户所属的用户类型集合中的用户类型的相关性大小，对所述当前用户当前输入信息的候选项进行排序；展示进行所述排序后的候选项。

其中，所述根据已经建立的与用户类型相关的G个不同的语言模型，获取所述当前用户当前输入信息的候选项集合中每个候选项所属的用户类型的步骤之前，还包括：使用文本分类技术，对多个用户历史输入信息进行分类整理，获得G个不同的用户类型和G类不同的与用户类型相关的语料；将所述G类不同的与所述用户类型相关的语料，分别按照各自所属的用户类型训练得到与用户类型相关的G个不同的语言模型。

其中，按照所述每个候选项所属的用户类型与已获得的所述当前用户所属的用户类型集合中的用户类型的相关性大小，对当前用户当前输入信息的候选项进行排序的步骤之前，还包括：获取当前用户的历史输入信息；根据所述当前用户的历史输入信息，用已经建立的所述与用户类型相关的G个不同的语言模型对当前用户进行分类，得到当前用户所属的用户类型集合。

其中，所述按照每个候选项所属的用户类型与已获得的所述当前用户所属的用户类型集合中的用户类型的相关性大小，对当前用户当前输入信息的候选项进行排序的步骤之前，还包括：获取多个用户的历史输入信息，所述多个用户属于所述G个不同的用户类型；从所述获取的多个用户的历史输入信息中选取部分历史输入信息；对所述选取的部分历史输入信息进行标注，获得多个用户标注的训练语料；将所述多个用户标注的训练语料和所述G个不同的用户类型，用教师指导的机器学习方法分别按照各自的用户类型训练出与用户类型相关的用户分类器；根据当前用户的历史输入信息，用所述与用户类型相关的用户分类器对当前用户进行分类，获得当前用户所属的用户类型集合。

其中，所述历史输入信息包括在输入法应用中的历史输入信息、在即时通信工具中的历史输入信息以及在社交网站中的历史输入信息中的任意一种或两种以上历史输入信息。

其中，所述按照每个候选项所属的用户类型与已获得的所述当前用户所属的用户类型集合中的用户类型的相关性大小，对当前用户当前输入信息的候选项进行排序的步骤包括：根据每个候选项所属的用户类型与所述当前用户所属的用户类型集合中的用户类型的相关性大小，获取当前用户当前输入信息的候选项集合中每个候选项的权值；根据所述候选项集合中每个候选项的权值的大小，对当前用户当前输入信息的候选项集合中的候选项进行排序。

其中，所述根据每个候选项所属的用户类型与所属当前用户所属的用户类型集合中的用户类型的相关性大小，获取当前用户当前输入信息的候选项集合中每个候选项的权值的步骤包括：获取m个用户u₁、u₂、…、u_m在输入所述当前用户当前输入信息的情况下，对同一个候选项c_i的选择次数s₁、s₂、…、s_m，其中，m个用户属于G个不同的用户类型；在G个不同的用户类型中，获取所述候选项c_i在用户类型g中的权值weight(c_i,g)，即：

其中，P_g(c_i)表示在用户类型g对应的语言模型下，候选项c_i的概率，

获取用户u_m属于一个用户类型g的权值weight(u_m,g)，即：

其中，P_g(log ofu_m)表示用户u_m的输入log文本，在用户类型g对应的语言模型下的概率；

根据所述权值weight(c_i,g)以及所述权值weight(u_m,g)以及用户所属的用户类型集合g_m,获取当前用户当前输入信息的候选项集合中每个候选项的权值weight^k(c_i,u_m)，即：

其中，k代表第k次迭代，cost(c_i，u_m)是候选项c_i对于用户u_m的成本，cost^k+1(c_i,u_m)=-weightk(c_i,u_m)。

其中，所述根据候选项集合中每个候选项的权值的大小，对当前用户当前输入信息的候选项集合中的候选项进行排序的步骤之后，还包括：根据所述候选项集合中每个候选项的权值的大小，判断候选项集合中是否有高频热词或新词。

其中，所述根据候选项集合中每个候选项的权值大小，判断候选项集合中是否有高频热词的步骤包括：若候选项的连续预定次迭代产生的所述权值均大于预设的高频热词的阈值，则确定所述候选项为高频热词。

其中，所述根据候选项集合中每个候选项的权值大小，判断候选项集合中是否有新词的步骤包括：若候选项当前迭代所产生的所述权值与前一次迭代所产生的所述权值相比的变化量大于预设的新词的阈值，则确定所述候选项为新词。

其中，所述判断候选项集合是否有高频热词或新词的步骤之后，还包括：若候选项集合中有高频热词或新词时，向所述高频热词或新词所属的用户类型的用户推送所述高频热词或新词对应的链接。

其中，所述展示进行排序后的候选项的步骤包括：展示进行排序后的候选项以及候选项的新词或热词的标识。

其中，所述展示进行排序后的候选项的步骤之后，还包括：根据当前用户的切换指令，按照所述选择次数s₁、s₂、…、s_m的求和结果对所述候选项进行排序；展示按所述求和结果进行排序的候选项以及所述求和结果。

其中，所述语言模型是n-Gram语言模型或n-Pos语言模型。

其中，所述按照每个候选项所属的用户类型与已获得的所述当前用户所属的用户类型集合中的用户类型的相关性大小，对当前用户当前输入信息的候选项进行排序的步骤包括：按照每个候选项所属的用户类型与已获得的所述当前用户所属的用户类型集合中的用户类型的相关性由大到小，对当前用户当前输入信息的候选项进行排序。

为解决上述技术问题，本发明采用的另一个技术方案是：提供一种对输入法所产生的候选项进行排序的装置，包括接收模块、第一获取模块、第一排序模块以及展示模块，其中：所述接收模块用于利用所述输入法接收当前用户的当前输入信息，并将所述当前用户的当前输入信息发送给所述第一获取模块；所述第一获取模块用于根据已经建立的与用户类型相关的G个不同的语言模型，获取当前用户的当前输入信息的候选项集合中每个候选项所属的用户类型，并将所述当前用户的当前输入信息的候选项集合中每个候选项所属的用户类型发送给所述第一排序模块，其中，G是自然数；所述第一排序模块用于按照所述每个候选项所属的用户类型与已获得的当前用户所属的用户类型集合中的用户类型的相关性大小，对当前用户当前输入信息的候选项进行排序，并将排序后的候选项发送给所述展示模块；所述展示模块用于展示来自所述第一排序模块的进行所述排序后的候选项。

其中，所述装置还包括网页语料模块和第一训练模块，其中：所述网页语料模块用于使用文本分类技术，对多个用户历史输入信息进行分类整理，获得G个不同的用户类型和G类不同的与用户类型相关的语料，并将所述获得的G个不同的用户类型和G类不同的与用户类型相关的语料发送给所述第一训练模块；所述第一训练模块用于将所述G类不同的与用户类型相关的语料，分别按照各自所属的用户类型训练得到与用户类型相关的G个不同的语言模型。

其中，所述装置还包括历史输入信息模块以及第二获取模块，其中：所述历史输入信息模块用于获取当前用户的历史输入信息，并将所述当前用户的历史输入信息输出给所述第二获取模块；所述第二获取模块用于根据所述当前用户的历史输入信息，用已经建立的所述与用户类型相关的G个不同的语言模型对当前用户进行分类，得到当前用户所属的用户类型集合。

其中，所述装置还包括第三获取模块、选取模块、标注模块、第二训练模块以及分类模块，其中：所述第三获取模块用于获取多个用户的历史输入信息，并将所述多个用户的历史输入信息发送给所述选取模块；所述选取模块用于从所述获取的多个用户的历史输入信息中选取部分历史输入信息，并将所述选取的部分历史输入信息发送给所述标注模块；所述标注模块用于对所述选取的部分历史输入信息进行标注，获得多个用户标注的训练语料，将所述获得的多个用户标注的训练语料发送给所述第二训练模块；所述第二训练模块用于将所述多个用户标注的训练语料和所述G个不同的用户类型，用教师指导的机器学习方法分别按照各自的用户类型训练出与用户类型相关的用户分类器；所述分类模块用于根据当前用户的历史输入信息，用所述第二训练模块得到的所述与用户类型相关的用户分类器对当前用户进行分类，获得当前用户所属的用户类型集合。

其中，所述第一排序模块包括权值获取单元以及排序单元，其中：所述权值获取单元用于根据每个候选项所属的用户类型与所述当前用户所属的用户类型集合中的用户类型的相关性大小，获取当前用户当前输入信息的候选项集合中每个候选项的权值，并将所述候选项集合中每个候选项的权值发送给排序单元；所述排序单元用于根据来自所述权值获取单元的所述候选项集合中每个候选项的权值的大小，对当前用户当前输入信息的候选项集合中的候选项进行排序。

其中，所述权值获取单元包括第一获取子单元、第二获取子单元、第三获取子单元以及第四获取子单元，其中：所述第一获取子单元用于获取m个用户u₁、u₂、…、u_m在输入所述当前用户当前输入信息的情况下，对同一个候选项c_i的选择次数s₁、s₂、…、s_m，其中，m个用户属于G个不同的用户类型；所述第二获取子单元用于在G个不同的用户类型中，获取所述候选项c_i在用户类型g中的权值weight(c_i,g)，即：

其中，P_g(c_i)表示在用户类型g对应的语言模型下，候选c_i的概率；

所述第三获取子单元用于获取用户u_m属于一个用户类型g的权值weight(u_m,g)，即：

所述第四获取子单元用于根据所述权值weight(c_i,g)以及所述权值weight(u_m,g)以及用户所属的用户类型集合g_m,获取当前用户当前输入信息的候选项集合中每个候选项的权值weight^k(c_i,u_m)，即：

其中，所述装置还包括判断模块，用于根据所述候选项集合中每个候选项的权值的大小，确定候选项集合中是否有高频热词或新词。

其中，所述判断模块具体用于当候选项的连续预定次迭代产生的所述权值均大于预设的高频热词的阈值时，则确定所述候选项为高频热词；或具体用于当候选项当前迭代所产生的所述权值与前一次迭代所产生的所述权值相比的变化量大于预设的新词的阈值时，则确定所述候选项为新词。

其中，所述装置还包括推送模块，用于向所述高频热词或新词所属的用户类型的用户推送所述高频热词或新词对应的链接。

其中，所述展示模块具体用于展示进行排序后的候选项以及候选项的新词或热词的标识。

其中，所述装置还包括第二排序模块，用于根据当前用户的切换指令，按照所述选择次数s₁、s₂、…、s_m的求和结果对所述候选项进行排序，并将按所述求和结果排序后的候选项发送给所述展示模块；所述展示模块具体用于展示按所述求和结果进行排序的候选项以及所述求和结果。

其中，所述语言模型是n-gram语言模型或n-pos语言模型。

其中，所述第一排序模块具体用于按照每个候选项所属的用户类型与已获得的所述当前用户所属的用户类型集合中的用户类型的相关性由大到小，对当前用户当前输入信息的候选项进行排序，并将排序后的候选项发送给展示模块。

本发明的有益效果是：区别于现有技术的情况，本发明获取当前用户所属的用户类型集合以及当前用户当前输入信息的候选项集合中每个候选项所属的用户类型，按照每个候选项所属的用户类型与当前用户所属的用户类型集合中的用户类型的相关性大小，对当前用户当前输入信息的候选项进行排序。由于用户类型是基于用户历史输入信息来进行划分得到的，根据不同类型的用户关注的候选项不同，对候选项进行排序时考虑到用户类型。通过这样的方式，对不同类型的用户推送不同排序的候选项，可以减少用户选择候选的时间，提升用户体验。

附图说明

图1是本发明对输入法所产生的候选项进行排序的方法一实施方式的流程图；

图2是本发明对输入法所产生的候选项进行排序的方法一实施方式中建立与用户类型相关的G个不同的语言模型的流程图；

图3是本发明对输入法所产生的候选项进行排序的方法一实施方式中获得当前用户所属的用户类型集合的流程图；

图4是本发明对输入法所产生的候选项进行排序的方法另一实施方式中获得当前用户所属的用户类型集合的流程图；

图5是本发明对输入法所产生的候选项进行排序的方法一实施方式中按照每个候选项所属的用户类型与已获得的当前用户所属的用户类型集合中的用户类型的相关性大小，对当前用户当前输入信息的候选项进行排序的流程图；

图6是本发明对输入法所产生的候选项进行排序的方法一实施方式中确定高频热词的流程图；

图7是某一输入法的展示界面示意图；

图8是某一输入法另一展示界面示意图；

图9是本发明对输入法所产生的候选项进行排序的装置一实施方式的结构示意图；

图10是本发明对输入法所产生的候选项进行排序的装置另一实施方式的结构示意图；

图11是本发明对输入所产生的候选项进行排序的装置又一实施方式的结构示意图；

图12是本发明的第一排序模块的结构示意图；

图13是本发明的权值获取单元的机构示意图。

具体实施方式

下面结合附图和实施方式对本发明进行详细说明。

参阅图1，本发明对输入所产生的候选项进行排序的方法一实施方式包括：

步骤S101：利用输入法接收当前用户的当前输入信息；

利用输入法接收当前用户当前输入信息，比如接收当前用户当前输入的拼音字符、假名、或者英文单词或句子等等。

步骤S102：根据已经建立的与用户类型相关的G个不同的语言模型，获取当前用户当前输入信息的候选项集合中每个候选项所属的用户类型；

语言模型(Language Model,LM)的目的是建立一个能够描述给定词序列在语言中的出现的概率的分布。即利用语言模型，可以确定哪个词序列的可能性更大，或者给定若干个词，可以预测下一个最可能出现的词语。举个音字转换的例子来说，输入拼音串为“nixianzaiganshenme”，对应的输出可以有多种形式，如“你现在干什么”、“你西安再赶什么”等等，那么到底哪个才是正确的转换结果呢？利用语言模型，我们知道前者的概率大于后者，因此转换成前者在多数情况下比较合理。再举一个机器翻译的例子，给定一个汉语句子为“李明正在家里看电视”，可以翻译为“Li Ming is watching TV at home”、“Li Mingat home is watchingTV”等等，同样根据语言模型，我们知道前者的概率大于后者，所以翻译成前者比较合理。

那么如何计算一个句子的概率呢？比如给定句子（词语序列）为：

S＝W₁，W₂，...，W_k，

那么，它的概率可以表示为：

P(S)＝P(W₁，W₂，...，W_k)＝p(W₁)P(W₂|W₁)...P(W_k|W₁，W₂，...，W_k-1)

由于上式中的参数过多，因此需要近似的计算方法。常见的方法有n-gram模型方法、决策树方法、最大熵模型方法、最大熵马尔科夫模型方法、条件随机域方法、神经网络方法等等。

与用户类型相关的G个不同的语言模型，可以确定一个句子、一个词或词组或者若干词等分别属于G个不同的用户类型的概率，概率越大，则说明该句子、词或词组或若干词属于该用户类型的可能性就越大。

用户输入信息后，会产生相应的多个候选项，这些候选项即组成候选项集合，根据与用户类型相关的G个不同的语言模型，可以知道每个候选项所属的用户类型。

本发明实施方式中，语言模型可以是n-gram语言模型或n-pos语言模型。

n-gram语言模型(n元语言模型)中当前词出现的概率仅和其左边的n-1个词有关系。当n取1、2、3时，n-gram模型分别称为unigram（一元语言模型）、bigram（二元语言模型）和trigram语言模型（三元语言模型）。n越大，语言模型越准确，计算也越复杂，计算量也越大。最常用的是bigram，其次是unigram和trigram，n取大于等于4的情况较少。当n-gram语言模型用到中文网页的时候，得到汉语n元语言模型；当n-gram语言模型用到英文网页的时候，得到英语n元语言模型。例如当n取值为2的时候，当前词的出现的概率仅和其前一个词有关系。例如对于句子：

S=张三董事长发表了四个优先重要指示的讲话。

在2元语言模型下，该句子的概率（衡量该句子的正确性的度量）为：

这里<s>和</s>，是两个人工构造的词，分别代表了句子的开始和结尾。（其目的是判断“张三”作为句子开头词的概率，和“。”句号作为句子接尾词的概率）

如果是在3元语言模型下，该句子的概率是：

这里，2元模型中一个概率的计算方法为：

P(董事长|张三)=count(张三董事长)/count(张三)

分子是，“张三董事长”在训练语料（例如大规模网络语料）中出现的频次；分母是“张三”在训练语料中出现的频次。

相应地，3元模型中一个概率的计算公式为：

P(发表|张三,董事长)=count(张三董事长发表)/count(张三董事长)

这里的分子是“张三董事长发表”在训练语料中出现的频次，而分母是“张三董事长”在训练语料中出现的频次。

在n-pos模型下，假设我们有句子S=w₁ w₂...w_K，其包含K个词，则P(S)可以写成：

区别于n-gram模型（例如bigram）中直接使用w_i-1和w_i的条件概率P(w_i|w_i-1)来刻画P(S)，我们这里引入了“隐马尔科夫模型”(HiddenMarkov Model-HMM)的思想，即把词性c_i作为“隐变量”(latent variable)。这个公式中使用了两种概率，P(w_i|c_i)代表的是从词类c_i到词w_i的“生成概率”（或者称为发射概率）；P(c_i|c_i-1)表示的是词类bigram模型，即c_i-1词类后面接c_i词类的概率。

在词类n-gram模型中，一个词类c_i出现的概率条件地依赖于前n-1个词的词类，也就是说：

P(c_i=c|history)=P(c_i=c|c_i-n+1,…,c_i-1)

n-pos模型其实是基于词的n-gram模型的一个近似。假设，我们有10000个词，10个词类，那么对于bigram的词的模型，我们需要训练10000*10000个参数。而在n-pos模型中，我们只需要训练P(w_i|c_i)和P(c_i|c_i-1)就可以了，前者的个数为10000*10，后者为10*10。这样，我们需要训练的参数的个数就会大大减少（这里从10000*10000减少到10000*10+10*10个）。

注意到一点，随着词类的数目的增加，n-pos模型越来越接近n-gram模型。极端地，如果一个词一个词类，那么n-pos模型就是n-gram模型了。另外一个极端是，如果只有一个词类，那么n-pos模型退化成uni-gram模型。

因此，n-pos语言模型的优点在于它需要训练的数据比n-gram语言模型少得多，并且模型的参数空间也要小得多；缺点在于词的概率分布依赖于词性而非词本身，显然按照词类划分词的概率分布不如词本身的划分精细。因此，在实际应用中（如语言识别）中，这类语言模型一般难以达到n-gram语言模型的精度。

步骤S103：按照每个候选项所属的用户类型与已获得的当前用户所属的用户类型集合中的用户类型的相关性大小，对当前用户当前输入信息的候选项进行排序；

如果候选项所属的用户类型属于当前用户所属的用户类型集合中的用户类型，那么候选项所属的用户类型与当前用户所属的用户类型相关性大。如果候选项所属的用户类型不属于当前用户所属的用户类型集合中的用户类型，那么候选项所属的用户类型与当前用户所属的用户类型的相关性小。上述评价相关性大小只是粗略的判断，当需要更确切一点的判断相关性大小时，具体还要看候选项在G个不同的语言模型中的概率大小，概率大的相关性就大，概率小的相关性就小。

用户所属的用户类型可能不止一个类型，可能是多个不同的用户类型，因此是一个用户类型集合。获取用户所属的用户类型集合至少可以通过两种方式：第一，系统中保存有相关用户所属的用户类型信息，该信息已经根据语言模型对用户类型进行分类，确定了用户所属的用户类型集合；第二，在用户输入信息的时，根据语言模型确定用户所属的用户类型集合。

例如，当前用户所属的用户类型分别为手表爱好者、文艺爱好者、漫画爱好者、网购爱好者，如果一个候选项所属的用户类型集合为手表爱好者、网购爱好者，那么该候选项所属的用户类型与当前用户所属的用户类型的相关性就大；如果一个候选项所属的用户类型集合为计算机爱好者、美食爱好者，那么该候选项所属的用户类型与当前用户所属的用户类型的相关性就小。

在对候选项进行排序时可以按照相关性由大到小、由小到大或者其他方式排序。当然，在实际应用过程中，候选项的排序以相关性由大到小的排序方式为优选，因为与用户所属的用户类型相关性大的候选项排在前面，当前用户选取候选项时就不需要花费过多的时间逐一查看选择，节省选择候选项的时间。

步骤S104：展示进行排序后的候选项；

对候选项进行排序后，将排序后的候选项展示给用户，以使用户能够选择自己需要的候选项。

通过上述实施方式的阐述，本发明对输入法所产生的候选项进行排序的方法，通过获取当前用户所属的用户类型集合以及当前用户当前输入信息的候选项集合中每个候选项所属的用户类型，按照每个候选项所属的用户类型与当前用户所属的用户类型集合中的用户类型的相关性大小，对当前用户当前输入信息的候选项进行排序。由于用户类型是基于用户历史输入信息来进行划分得到的，根据不同类型的用户关注的候选项不同，对候选项进行排序时考虑到用户类型。通过这样的方式，对不同类型的用户推送不同排序的候选项，可以减少用户选择候选的时间，提升用户体验。

本发明对输入法所产生的候选项进行排序的方法实施方式中，通常需要事先建立相应的与用户类型相关的G个不同的语言模型。以通过用户类型相关的G个不同的语言模型来获取当前用户当前输入信息的候选项集合中每个候选项所属的用户类型，以及获得当前用户所属的用户类型集合。

请参阅图2，本发明对输入法所产生的候选项进行排序的方法另一实施方式中，建立与用户类型相关的G个不同的语言模型的步骤包括：

步骤S201：使用文本分类技术，对多个用户历史输入信息进行分类整理，获得G个不同的用户类型和G类不同的与用户类型相关的语料；

文本分类技术就是在给定的分类体系下，让计算机根据文本内容自动确定相关类别的过程。本实施方式中使用文本分类技术，将获取的多个用户历史输入信息划分为若干个组，每个组对应一个用户类型，使得各个组别分别代表不同的用户类型，并汇集跟不同用户类型相关的语料。

用户历史输入信息可以包括在输入法应用中的历史输入信息、在即时通信工具中的历史输入信息以及在社交网站中的历史输入信息中的任意一种或两种以上历史输入信息。

例如，用户在使用日文输入法产品的时候，上传给服务器的历史输入信息；在twitter这样的即时通信工具上，按照时间的新旧顺序收集用户输入的历史信息；在facebook这样的社交网站上，同样按照时间的新旧顺序收集用户输入的历史信息。

这里的用户类型相关的语料是从各个用户的历史输入信息中获取并经过比较合并而得到。即一个用户的历史输入信息下可能包含多个用户类型的语料，通过与其他用户的历史输入信息进行比较，将相似或相同用户类型的语料汇集在一起而形成某个用户类型相关的语料。

比如某一用户的历史输入信息中包含了大量的有关“劳力士”的表述，另一个用户的历史输入信息中包含了大量有关“江诗丹顿”的表述，可以将两个用户合并为“手表爱好者”的用户类型，这时可以将两个用户的历史输入信息汇集到一起作为“手表爱好者”相关的语料。

利用文本分类技术，对多个用户历史输入信息进行分类整理，可以获得G个不同的用户类型和G类不同的与用户类型相关的语料。

步骤S202：将G类不同的与用户类型相关的语料，分别按照各自所属的用户类型训练得到与用户类型相关的G个不同的语言模型；

根据每一类与用户类型相关的语料，可以训练出一个与用户类型相关的语言模型。比如针对计算机爱好者的语言模型、针对漫画爱好者的语言模型、针对手表爱好者的语言模型以及针对网购爱好者的语言模型等等。

通过与用户类型相关的G个不同的语言模型，可以获得当前用户当前输入信息的候选项集合中每个候选项所属的用户类型。例如，以下四种语言模型：针对计算机爱好者的语言模型、针对漫画爱好者的语言模型、针对手表爱好者以及针对网购爱好者的语言模型，用户当前输入信息的候选项中的某一个候选项在四个语言模型中的概率分别为0.6、0.4、0.01、0.008，那么以概率最大的用户类型为该候选项所属的用户类型，即计算机爱好者。

另一方面，通过与用户类型相关的G个不同的语言模型，还可以获得当前用户所属的用户类型集合。

请参阅图3，本发明对输入法所产生的候选项进行排序的方法另一实施方式中，获得当前用户所属的用户类型集合的步骤包括：

步骤S301：获取当前用户的历史输入信息；

当前用户的历史输入信息可以客观的反映用户关注的与某些方面相关的信息，一个用户可以关注与多个类型相关的信息。另外，一个用户关注的与类型相关的信息经常发生变化，例如，一段时间内，当前用户关注的手表相关的、漫画相关的信息，另一段时间内，当前用户关注的可能是计算机相关的、美食相关的信息。

步骤S302：根据当前用户的历史输入信息，用已经建立的与用户类型相关的G个不同的语言模型对当前用户进行分类，得到当前用户所属的用户类型集合；

根据当前用户的历史输入信息，用已经建立的与用户类型相关的G个不同的语言模型即可实现对当前用户的分类，从而得到当前用户所属的用户类型集合。用户的历史输入信息在某一个或某几个用户类型相关的语言模型中都有相应的概率，概率越大，当前用户属于该用户类型的可能性就越大。通常情况下可以根据概率的大小来确定用户所属的用户类型，也就是说，当前用户的历史输入信息在某一个或某几个用户类型相关的语言模型中的概率相对于其在另外几个用户类型相关的语言模型中的概率都要大，这时候可以确定该当前用户属于该一个或几个用户类型。

上述对用户进行分类，主要有两个目的：1、减轻单用户的稀疏的输入日志历史信息对用户输入行为挖掘的学习算法的负影响；2、自动识别并汇集同类型的用户的输入日志信息，让同用户类型的用户互相“分享”各自输入的信息，给用户更好的用户输入体验。

请参阅图4，本发明对输入法所产生的候选项进行排序的方法又一实施方式中，获得当前用户所属的用户类型集合的步骤包括：

步骤S401：获取多个用户的历史输入信息；

获取多个用户的历史输入信息，多个用户分别属于G个不同的用户类型。

步骤S402：从获取的多个用户的历史输入信息中选取部分历史输入信息；

步骤S403：对选取的部分历史输入信息进行标注，获得多个用户标注的训练语料；

对选取的部分历史输入信息进行标注，从而可以得到比较准确的与类型相关的训练语料，对用户的分类会更加精确。

步骤S404：将多个用户标注的训练语料和G个不同的用户类型，用教师指导的机器学习方法分别按照各自的用户类型训练出与用户类型相关的用户分类器；

机器学习(Machine Learning)是研究计算机怎样模拟或实现人类的学习行为，以获取新的知识或技能，重新组织已有的知识结构使之不断改善自身的性能。它是人工智能的核心，是使计算机具有智能的根本途径，其应用遍及人工智能的各个领域，它主要使用归纳、综合而不是演绎。

教师指导的机器学习方法是指用已经标注的训练语料来训练出一个概率模型，利用该概率模型来对未知的数据（或者用户给的新的数据）进行自动分类。

举例来说，假设我们要做一个中文分词工具，即自动识别一个给定中文句子中的“词”，并用空格隔开。

这样，在使用教师指导的机器学习方法的时候，我们需要有“训练语料库”，其形式类似于：

“张三董事长发表了四个优先重要指示的讲话。”等（数以万计的）句子。

有了这些句子之后，我们可以采用若干机器学习的方法，例如CRF(conditionalrandom fields–条件自由场)模型等来训练出一个模型。该模型可以对用户新输入的句子“李四经理听取了张三董事长的重要指示。”为：

“李四经理听取了张三董事长的重要指示。”

这里，所谓的“教师”，就是指训练语料库。

在训练与用户类型相关的用户分类器时，用已经标注的与用户类型相关的训练语料，结合各个用户的个人语料，可以训练出更加精确的与用户类型相关的用户分类器。

步骤S405：根据当前用户的历史输入信息，用与用户类型相关的用户分类器对当前用户进行分类，获得当前用户所属的用户类型集合；

上述两个获得当前用户所属的用户类型集合的实施方式，其中，第一种实施方式获得的当前用户所属的用户类型集合比较粗略，第二种实施方式获得的当前用户所属的用户类型集合相对于第一种实施方式更加精确。在实际应用过程中，用户根据自己的需求，可以任意选择采用哪一种实施方式来获得当前用户所属的用户类型集合。

另一方面，请参阅图5，本发明对输入法所产生的候选项进行排序的方法另一实施方式中，按照每个候选项所属的用户类型与已获得的当前用户所属的用户类型集合中的用户类型的相关性大小，对当前用户当前输入信息的候选项进行排序的步骤包括：

步骤S501：根据每个候选项所属的用户类型与当前用户所属的用户类型集合中的用户类型的相关性大小，获取当前用户当前输入信息的候选项集合中每个候选项的权值；

得到每个候选项所属的用户类型与当前用户所属的用户类型集合中的用户类型的相关性的大小，再根据当前用户在当前用户所属的用户类型集合中每个用户类型对应的权值的大小，即可获取当前用户当前输入信息的候选项集合中每个候选项的权值的大小。

例如，当前的其中一个候选项所属的用户类型为“计算机爱好者”、而当前用户所属的用户类型集合为“计算机爱好者”、“手表爱好者”，那么，候选项所属的用户类型与当前用户所属的用户类型集合中的用户类型的相关性为1(即两者相互重叠的部分)。如果“计算机爱好者”在当前用户所属的用户类型集合中的权值为0.35，那么该候选项的权值为0.35。如果另一个候选项所属的用户类型为“手表爱好者”，那么候选项所属的用户类型与当前用户所属的用户类型集合中的用户类型相关性也是1。如果“手表爱好者”在当前用户所属的用户类型集合中的权值为0.2，那么该候选项的权值也为0.2。

上述获得权值的办法只是一种比较粗略的方法，在实际应用过程中，还可以通过以下方法得到更加精确的候选项的权值：

1、获取m个用户u₁、u₂、…、u_m在输入当前用户当前输入信息的情况下，对同一个候选项c_i的选择次数s₁、s₂、…、s_m，其中，m个用户属于G个不同的用户类型；

2、在G个不同的用户类型中，获取候选项c_i在用户类型g中的权值weight(c_i,g)，即：

3、获取用户u_m属于一个用户类型g的权值weight(u_m,g)，即：

4、根据权值weight(c_i,g)以及权值weight(u_m,g)以及用户所属的用户类型集合g_m,获取当前用户当前输入信息的候选项集合中每个候选项的权值weight^k(c_i,u_m)，即：

需要说明的是，上述获取候选项c_i在用户类型g中的权值weight(c_i,g)以及用户u_m属于一个用户类型g的权值weight(u_m,g)不严格区分先后顺序，用户在实际应该过程中，可以根据自己的实际情况选择先获取哪一个的权值。

通过上述的公式，我们可以以一种在线学习的方式，不断地根据用户输入日志信息，更新各候选项的权值，以使得更新后的各候选项的排序更加接近用户的实际需求，提升用户输入体验。

值得一提的是，上述权值的计算方法，利用了同一用户类型的用户历史输入信息，是一种用户信息、数据共享的技术方法。

步骤S502：根据候选项集合中每个候选项的权值的大小，对当前用户当前输入信息的候选项集合中的候选项进行排序；

根据候选项集合中每个候选项的权值的大小，可以按照权值由大到小、由小到大或者别的方式对当前用户当前输入信息的候选项集合中的候选项进行排序。当然，最优选的方式是按照权值由大到小的方式对候选项进行排序。

在实际应用过程中，通过上述实施方式得到的候选项的权值，可以用于确定当前输入信息的候选项集合中是否有高频热词或新词。

若候选项当前迭代所产生的权值与前一次迭代所产生的权值相比的变化量大于预设的新词的阈值，则确定该候选项为新词。

比方说，可以通过计算候选项c_i的第k次迭代所产生的weight^k(c_i,u_m)和第k-1次迭代所产生的权值weight^k-1(c_i,u_m)的变化量，若weight^k(c_i,u_m)–weight^k-1(c_i,u_m)>θ，则候选项c_i是新词。这里的θ是预设的新词的阈值，即我们可以根据整体的新词数目来调节变化的阈值θ。

例如，我们控制所有假名下一共最多允许有1000个新词，那么按照这种规格过滤下去，从而最后确定阈值。即我们按照这个阈值过滤之后，最后剩余大约1000个新词，推送给用户。

这里，我们可以根据实际情况和用户数据的更新的量，来选择一周更新一次迭代等。这样，我们可以按周为单位推出“一周新词”；当然，我们可以类似地，设定一个月，一个季度，一个迭代单元，从而推出“一月新词”，“一季度新词”等。

若候选项的连续预定次迭代产生的权值均大于预设的高频热词的阈值，则确定该候选项为高频热词。

比方说，可以通过计算候选项c_i的连续a次迭代的权值，若weight^k-a+1(c_i,u_m)>b，...,weight^k(c_i,u_m)>b，则该候选项c_i为高频热词。这里的a、b可以根据需要的高频热词的数量来设置。

比如我们需要控制所有假名下一共最多允许2000个热词，即按照这个最终热词的规模，来界定a和b的取值。另一方面需要注意的是，为了在“热词”中过滤掉那些日常经常使用的词，我们可以根据需要限定“热词”中的80%左右都来自“新词”，即有一个“新词”到“热词”的变换过程；而剩余的20%左右，将来自那些日常用语（例如，“お疲れ様です-您辛苦了”等这种日常问候语）。通过迭代次数，我们可以设定“每月热词，季度热词，年度热词”等。

事实上，热词跟新词都是跟随时间不断变化的，比如影片名《蜘蛛侠》，在电影刚开始上演的时候，“蜘蛛侠”这个词可能是新词，然后以新词持续一段时间，一段时间后，随着影片热播，人们利用输入法输入越来越多，“蜘蛛侠”可能就转变为热词了。

以下，我们来以高频热词的确定来举例说明：

请参阅图6，本发明对输入法所产生的候选项进行排序的方法另一实施方式中，确定高频热词的步骤包括：

步骤S601：判断是否有候选项的连续预定次迭代产生的权值均大于预设的高频热词的阈值；

高频热词是指出现的频次比较高，备受众多用户关注的词、词组或句子等。获取候选项的连续预定次迭代产生的权值，判断是否有候选项的连续预定次迭代产生的权值均大于预设的高频热词的阈值。高频热词的阈值可以根据需要自行设置。当有候选项的连续预定次迭代产生的权值均大于预设的高频热词的阈值时，进入步骤S602，如果没有候选项的连续预定次迭代产生的权值均大于预设的高频热词的阈值，则进入步骤S603。

步骤S602：确定该候选项为高频热词；

当有候选项的连续预定次迭代产生的权值均大于预设的高频热词的阈值时，则确定该候选项为高频热词。所得到的高频热词可以有多方面的应用，比如用来添加到一些预测词典中以提高预测的覆盖率和准确率，或者更新一些语言模型等。

优选地，可以根据所得到的高频热词或新词，向该高频热词或新词对应的用户类型的各个用户推送一些相关的网页链接或者搜索链接等。比如假设句子“元芳，你怎么看”为高频热词，当用户输入信息的候选项中出现“元芳，你怎么看”时，可以向用户推送《神探狄仁杰》的剧集链接或者剧情介绍链接，或者推送相关的背景知识介绍的链接等等，这样既能提高相关网页的点击率，也能吸引用户进一步地关注高频热词相关的信息。

步骤S603：没有高频热词；

当没有候选项的连续预定次迭代产生的权值均大于预设的高频热词的阈值时，则判定当前的候选项中没有高频热词。

另一方面，根据上述实施方式获取候选项权值的方式，在实际应用过程中，可以进一步地根据用户的切换指令，对所有用户对当前候选项集合中每个候选项的选择次数进行求和(即每个候选项历史被选择的次数)，以选择次数的求和结果对候选项集合中的候选项进行排序。

比如可以通过获取m个用户u₁、u₂、…、u_m在输入当前用户当前输入信息的情况下，对同一个候选项c_i的选择次数s₁、s₂、…、s_m，则m个用户对当前候选项集合中的候选项的选择次数求和即为E=s₁+s₂+…+s_m，以这一个求和结果对当前的候选项进行排序并展示给用户。

请参阅图7，其中A为某一输入法下依据候选项的权值进行排序的结果展示，同时还展示了候选项的历史被选择次数以及新词或热词的标识，如果用户按下按照选择次数排序的切换指令，则候选项的排序按照选择次数进行排序。其中，图7中的B为按照选择次数的降序进行排序的结果展示。

实际应用中，可以按照选择次数的升序或降序进行排序，比如用户第一次按切换指令，按照选择次数的升序进行排序并展示，再次按切换指令，按照选择次数的降序进行排序并展示，第三次按切换指令，恢复原来依据候选项的权值进行排序并展示。当然，上述的切换指令对应的排序规则只是一个举例，实际应用中可以根据需要自行设置。

根据上述实施方式，在展示候选项给用户时，可以同时展示每个候选项历史被选择的次数，候选项的热词或新词的标识等任意一种或多种信息。

其中，可参见图8，某一输入法对候选项的展示界面。如图所示，图中A部分中同时展示了候选项以及候选项的历史被选择次数和候选项的新词或热词的标识。其中，候选项“花岳”标识为新词，当用户对新词“花岳”感兴趣时，其选择焦点达到“花岳”的时候，给用户展示B部分所示的画面，即地名对应的所谓高人气的名胜古迹“花岳寺”，并在“花岳寺”后面附上一个表示超链接的箭头。当用户焦点到达箭头时，向用户呈现C部分展示的“花岳寺”的相应搜索链接地址，用户点击箭头的时候，在浏览器中展现搜索结果。

当然，上述对候选项的展示方式，只是一种举例，实际应用中不限于上述方式，比如表示新词相关的超链接标识不一定用箭头表示，可以是一个手指图标或者别的，打开链接的方式也不限于是点击超链接标识，可以通过现有的别的打开超链接的方式，比如快捷键等。

上述任何一个实施方式中所提到的语言模型是n-gram语言模型或n-pos语言模型。

需要注意的是，上述各实施方式中，涉及到用户类型分类都是围绕“个人用户”来展开的。对于企业级用户，本发明的实施方式也同样适用。简单起见，本发明这里只描述企业级用户的特有特征：

1、单个企业的各个不同主干分支，分别对应一个用户类型，而整个企业也对应一个更大的用户类型，这样分门别类地收集各个用户类型的历史输入信息，并进行汇集，训练出与用户类型相关的语言模型；

2、依据该企业的营业内容等，推送相关类型的细胞词库或相关类型的高频热词链接等。

请参阅图9，本发明对输入法所产生的候选项进行排序的装置一实施方式包括接收模块11、第一获取模块12、第一排序模块13以及展示模块14，其中：

接收模块11用于利用输入法接收当前用户的当前输入信息，并将当前用户的当前输入信息发送给第一获取模块12；

接收模块11利用输入法接收当前用户当前输入信息，比如接收当前用户当前输入的拼音字符、假名、或者英文单词或句子等等。将接收的当前用户当前输入信息发送给第一获取模块12。

第一获取模块12用于根据已经建立的与用户类型相关的G个不同的语言模型，获取当前用户的当前输入信息的候选项集合中每个候选项所属的用户类型，并将当前用户的当前输入信息的候选项集合中每个候选项所属的用户类型发送给第一排序模块13，其中，G是自然数；

语言模型(Language Model,LM)的目的是建立一个能够描述给定词序列在语言中的出现的概率的分布。即利用语言模型，可以确定哪个词序列的可能性更大，或者给定若干个词，可以预测下一个最可能出现的词语。

本发明实施方式中，语言模型包括但不限于是n-gram语言模型或n-pos语言模型。

第一排序模块13用于按照每个候选项所属的用户类型与已获得的当前用户所属的用户类型集合中的用户类型的相关性大小，对当前用户当前输入信息的候选项进行排序，并将排序后的候选项发送给展示模块14；

例如，当前用户所属的用户类型分别为“手表爱好者”、“文艺爱好者”、“漫画爱好者”、“网购爱好者”，如果一个候选项所属的用户类型集合为“手表爱好者”、“网购爱好者”，那么该候选项所属的用户类型与当前用户所属的用户类型的相关性就大；如果一个候选项所属的用户类型集合为“计算机爱好者”、“美食爱好者”，那么该候选项所属的用户类型与当前用户所属的用户类型的相关性就小。

第一排序模块13在对候选项进行排序时，可以按照相关性由大到小、由小到大或者其他方式排序。当然，在实际应用过程中，候选项的排序以相关性由大到小的排序方式为优选，因为与用户所属的用户类型相关性大的候选项排在前面，当前用户选取候选项时就不需要花费过多的时间逐一查看选择，节省选择候选项的时间。

展示模块14用于展示来自第一排序模块的进行排序后的候选项。

对候选项进行排序后，通过展示模块14将排序后的候选项展示给用户，以使用户能够选择自己需要的候选项。

请参阅图10，在本发明对输入法所产生的候选项进行排序的装置另一实施方式中，包括网页语料模块21、第一训练模块22、历史输入信息模块23、第二获取模块24、接收模块25、第一获取模块26、第一排序模块27以及展示模块28，其中：

网页语料模块21用于使用文本分类技术，对多个用户历史输入信息进行分类整理，获得G个不同的用户类型和G类不同的与用户类型相关的语料，并将获得的G个不同的用户类型和G类不同的与用户类型相关的语料发送给第一训练模块22；

网页语料模块21利用文本分类技术，对多个用户历史输入信息进行分类整理，可以获得G个不同的用户类型和G类不同的与用户类型相关的语料。并将获得的G个不同的用户类型和G类不同的与用户类型相关的语料发送给第一训练模块22。

第一训练模块22用于将G类不同的与用户类型相关的语料，分别按照各自所属的用户类型训练得到与用户类型相关的G个不同的语言模型；

第一训练模块22根据G类不同的与用户类型相关的语料，分别按照语料相应的用户类型训练得到与用户类型相关的G个不同的语言模型。

历史输入信息模块23用于获取当前用户的历史输入信息，并将当前用户的历史输入信息输出给第二获取模块24；

当前用户的历史输入信息可以客观的反映用户关注的与某些方面相关的信息，一个用户可以关注与多个类型相关的信息。另外，一个用户关注的与类型相关的信息经常发生变化，例如，一段时间内，当前用户关注的手表相关的、漫画相关的信息，另一段时间内，当前用户关注的可能是计算机相关的、美食相关的信息。历史输入信息模块23可以获取当前用户的历史输入信息，并将获取的当前用户的历史输入信息输出给第二获取模块24。

第二获取模块24用于根据当前用户的历史输入信息，用已经建立的与用户类型相关的G个不同的语言模型对当前用户进行分类，得到当前用户所属的用户类型集合；

第二获取模块24根据当前用户的历史输入信息，用已经建立的与用户类型相关的G个不同的语言模型即可实现对当前用户的分类，从而得到当前用户所属的用户类型集合。用户的历史输入信息在某一个或某几个用户类型相关的语言模型中都有相应的概率，概率越大，当前用户属于该用户类型的可能性就越大。通常情况下可以根据概率的大小来确定用户所属的用户类型，也就是说，当前用户的历史输入信息在某一个或某几个用户类型相关的语言模型中的概率相对于其在另外几个用户类型相关的语言模型中的概率都要大，这时候可以确定该当前用户属于该一个或几个用户类型。

通过第二获取模块24对用户进行分类，主要有两个目的：1、减轻单用户的稀疏的输入日志历史信息对用户输入行为挖掘的学习算法的负影响；2、自动识别并汇集同类型的用户的输入日志信息，让同用户类型的用户互相“分享”各自输入的信息，给用户更好的用户输入体验。

接收模块25用于利用输入法接收当前用户的当前输入信息，并将当前用户的当前输入信息发送给第一获取模块26；

第一获取模块26用于根据已经建立的与用户类型相关的G个不同的语言模型，获取当前用户的当前输入信息的候选项集合中每个候选项所属的用户类型，并将当前用户的当前输入信息的候选项集合中每个候选项所属的用户类型发送给第一排序模块27，其中，G是自然数；

第一排序模块27用于按照每个候选项所属的用户类型与已获得的当前用户所属的用户类型集合中的用户类型的相关性大小，对当前用户当前输入信息的候选项进行排序，并将排序后的候选项发送给展示模块28；

展示模块28用于展示来自第一排序模块的进行排序后的候选项。

请参阅图11，本发明对输入法所产生的候选项进行排序的装置又一实施方式中，包括网页语料模块31、第一训练模块32、第三获取模块33、选取模块34、标注模块35、第二训练模块36、分类模块37、接收模块38、第一获取模块39、第一排序模块40、展示模块41、判断模块42、推送模块43以及第二排序模块44，其中：

网页语料模块31用于使用文本分类技术，对多个用户历史输入信息进行分类整理，获得G个不同的用户类型和G类不同的与用户类型相关的语料，并将获得的G个不同的用户类型和G类不同的与用户类型相关的语料发送给第一训练模块32；

第一训练模块32用于将G类不同的与用户类型相关的语料，分别按照各自所属的用户类型训练得到与用户类型相关的G个不同的语言模型；

第三获取模块33用于获取多个用户的历史输入信息，并将多个用户的历史输入信息发送给选取模块34；

第三获取模块33获取多个用户的历史输入信息，多个用户分别属于G个不同的用户类型。并将获取的多个用户的历史输入信息发送给选取模块34。

选取模块34用于从获取的多个用户的历史输入信息中选取部分历史输入信息，并将选取的部分历史输入信息发送给标注模块35；

标注模块35用于对选取的部分历史输入信息进行手工标注，获得多个用户手工标注的训练语料，将获得的多个用户手工标注的训练语料发送给第二训练模块36；

标注模块35对选取的部分历史输入信息进行标注，从而可以得到比较准确的与类型相关的训练语料，对用户的分类会更加精确。

第二训练模块36用于将多个用户手工标注的训练语料和G个不同的用户类型，用教师指导的机器学习方法分别按照各自的用户类型训练出与用户类型相关的用户分类器；

机器学习(Machine Learning)是研究计算机怎样模拟或实现人类的学习行为，以获取新的知识或技能，重新组织已有的知识结构使之不断改善自身的性能。它是人工智能的核心，是使计算机具有智能的根本途径，其应用遍及人工智能的各个领域，它主要使用归纳、综合而不是演绎。教师指导的机器学习方法是指用已经标注的训练语料来对其余没有标注的语料进行自动分类，从而可以通过较少的投入而得到比较精确的分类结果。

分类模块37用于根据当前用户的历史输入信息，用第二训练模块36得到的与用户类型相关的用户分类器对当前用户进行分类，获得当前用户所属的用户类型集合；

接收模块38用于利用输入法接收当前用户的当前输入信息，并将当前用户的当前输入信息发送给第一获取模块39；

第一获取模块39用于根据已经建立的与用户类型相关的G个不同的语言模型，获取当前用户的当前输入信息的候选项集合中每个候选项所属的用户类型，并将当前用户的当前输入信息的候选项集合中每个候选项所属的用户类型发送给第一排序模块40，其中，G是自然数；

第一排序模块40用于按照每个候选项所属的用户类型与已获得的当前用户所属的用户类型集合中的用户类型的相关性大小，对当前用户当前输入信息的候选项进行排序，并将排序后的候选项发送给展示模块41；

请参阅图12，本发明对输入法所产生的候选项进行排序的装置另一实施方式中，第一排序模块还包括权值获取单元111以及排序单元112：

权值获取单元111用于根据每个候选项所属的用户类型与当前用户所属的用户类型集合中的用户类型的相关性大小，获取当前用户当前输入信息的候选项集合中每个候选项的权值，并将候选项集合中每个候选项的权值发送给排序单元112；

其中，请参阅图13，本发明对输入法所产生的候选项进行排序的装置一实施方式中第一排序模块的权值获取单元包括第一获取子单元211、第二获取子单元212、第三获取子单元213以及第四获取子单元214，其中：

第一获取子单元211用于获取m个用户u₁、u₂、…、u_m在输入当前用户当前输入信息的情况下，对同一个候选项c_i的选择次数s₁、s₂、…、s_m，其中，m个用户属于G个不同的用户类型；

第二获取子单元212用于在G个不同的用户类型中，获取候选项c_i在用户类型g中的权值weight(c_i,g)，即：

第三获取子单元213用于获取用户u_m属于一个用户类型g的权值weight(u_m,g)，即：

第四获取子单元214用于根据权值weight(c_i,g)以及权值weight(u_m,g)以及用户所属的用户类型集合g_m,获取当前用户当前输入信息的候选项集合中每个候选项的权值weight^k(c_i,u_m)，即：

排序单元112用于根据来自权值获取单元111的候选项集合中每个候选项的权值的大小，对当前用户当前输入信息的候选项集合中的候选项进行排序。

排序单元112根据候选项集合中每个候选项的权值的大小，可以按照权值由大到小、由小到大或者别的方式对当前用户当前输入信息的候选项集合中的候选项进行排序。当然，最优选的方式是按照权值由大到小的方式对候选项进行排序。

展示模块41用于展示来自第一排序模块的进行排序后的候选项。

在实际应用过程中，通过上述实施方式得到的候选项的权值，可以用于确定高频热词或新词。

请继续参阅图11，本实施方式的对输入法所产生的候选项进行排序的装置进一步包括判断模块42和推送模块43，其中：

判断模块42用于根据候选项集合中每个候选项的权值的大小，确定候选项集合是否有高频热词或新词；

判断模块42可以用于当候选项当前迭代所产生的权值与前一次迭代所产生的权值相比的变化量大于预设的新词的阈值时，则确定候选项为新词。

比方说，可以通过计算候选项c_i的第k-1次迭代和第k次迭代所产生的权值的变化量weight^k(c_i,u_m)–weight^k-1(c_i,u_m)>θ，这里的θ是预设的新词的阈值，即我们可以根据整体的新词数目来调节变化的阈值θ。

另一方面，判断模块42还可以用于当候选项的连续预定次迭代产生的权值均大于预设的高频热词的阈值时，则确定该候选项为高频热词。

比方说，可以通过计算候选项c_i的a次迭代的权值weight^k-a+1(c_i,u_m)>b，...,weight^k(c_i,u_m)>b，则该候选项c_i为高频热词。这里的a、b可以根据需要的高频热词的数量来设置。

比如我们要控制所有假名下一共最多允许2000个热词，即按照这个最终热词的规模，来界定a和b的取值。另一方面需要注意到的是，为了在“热词”中过滤掉那些日常经常使用的词，我们可以根据需要限定“热词”中的80%左右都来自“新词”，即有一个“新词”到“热词”的变换过程；而剩余的20%左右，将来自那些日常用语（例如，“お疲れ様です-您辛苦了”等这种日常问候语）。通过迭代次数，我们可以设定“每月热词，季度热词，年度热词”等。

推送模块43用于向高频热词或新词所属的用户类型的用户推送高频热词或新词对应的链接。

推送模块43可以根据所得到的高频热词或新词，向该高频热词或新词对应的用户类型的各个用户推送一些相关的网页链接或者搜索链接等。

比如假设句子“元芳，你怎么看”为高频热词，当用户输入信息的候选项中出现“元芳，你怎么看”时，可以向用户推送《神探狄仁杰》的剧集链接或者剧情介绍链接，或者推送相关的背景知识介绍的链接等等，这样既能提高相关网页的点击率，也能吸引用户进一步地关注高频热词相关的信息。

进一步地，请继续参阅图11，本实施方式的装置还可以包括第二排序模块44，用于根据当前用户的切换指令，根据选择次数s1、s2、…、sm的求和结果对候选项进行排序，并将按求和结果排序后的候选项给展示模块41。

根据上述实施方式获取候选项权值的方式，在实际应用过程中，第二排序模块44可以进一步地根据用户的切换指令，对所有用户对当前候选项集合中每个候选项的选择次数进行求和(即每个候选项历史被选择的次数)，以选择次数的求和结果对候选项集合中的候选项进行排序。

展示模块41在展示候选项给用户时，可以同时展示每个候选项历史被选择的次数，候选项的热词或新词的标识等任意一种或多种信息。

上述实施方式中提到的语言模型，可以是n-gram语言模型或n-pos语言模型。

通过上述实施方式的描述，可以理解，本发明对输入法所产生的候选项进行排序的方法及装置，通过获取当前用户所属的用户类型集合，以及获得当前用户当前输入信息的候选项集合中每个候选项所属的用户类型，按照每个候选项所属的用户类型与当前用户所属的用户类型集合中的用户类型的相关性大小，对当前用户当前输入信息的候选项进行排序。由于用户类型是基于用户历史输入信息来进行划分得到的，根据不同类型的用户关注的候选项不同，对候选项进行排序时考虑到用户类型来进行排序。通过这样的方式，对不同类型的用户推送不同排序的候选项，可以减少用户选择候选的时间，提升用户体验。

另一方面，通过候选项的权值来确定高频热词，所得到的高频热词可以有多方面的应用，比如用来添加到一些预测词典中以提高预测的覆盖率和准确率，或者更新一些语言模型等，还可以根据所得到的高频热词，向该高频热词对应的用户类型的各个用户推送一些相关的网页链接或者搜索链接等。这样既能提高相关网页的点击率，也能吸引用户进一步地关注高频热词相关的信息。

还有，可以根据用户的切换指令，根据候选项的历史被选择次数进行排序。同时，在展示候选项的时候，可以根据需要一并展示候选项的历史被选择次数、候选项的热词或新词的标识等的任意一种或多种信息，给用户更多的输入体验。

在本发明所提供的几个实施方式中，应该理解到，所揭露的系统，装置和方法，可以通过其它的方式实现。例如，以上所描述的装置实施方式仅仅是示意性的，例如，所述模块或单元的划分，仅仅为一种逻辑功能划分，实际实现时可以有另外的划分方式，例如多个单元或组件可以结合或者可以集成到另一个系统，或一些特征可以忽略，或不执行。另一点，所显示或讨论的相互之间的耦合或直接耦合或通信连接可以是通过一些接口，装置或单元的间接耦合或通信连接，可以是电性，机械或其它的形式。

所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部单元来实现本实施方式方案的目的。

另外，在本发明各个实施方式中的各功能单元可以集成在一个处理单元中，也可以是各个单元单独物理存在，也可以两个或两个以上单元集成在一个单元中。上述集成的单元既可以采用硬件的形式实现，也可以采用软件功能单元的形式实现。

所述集成的单元如果以软件功能单元的形式实现并作为独立的产品销售或使用时，可以存储在一个计算机可读取存储介质中。基于这样的理解，本发明的技术方案本质上或者说对现有技术做出贡献的部分或者该技术方案的全部或部分可以以软件产品的形式体现出来，该计算机软件产品存储在一个存储介质中，包括若干指令用以使得一台计算机设备（可以是个人计算机，服务器，或者网络设备等）或处理器（processor）执行本申请各个实施方式所述方法的全部或部分步骤。而前述的存储介质包括：U盘、移动硬盘、只读存储器（ROM，Read-Only Memory）、随机存取存储器（RAM，Random Access Memory）、磁碟或者光盘等各种可以存储程序代码的介质。

以上所述仅为本发明的实施方式，并非因此限制本发明的专利范围，凡是利用本发明说明书及附图内容所作的等效结构或等效流程变换，或直接或间接运用在其他相关的技术领域，均同理包括在本发明的专利保护范围内。

Claims

1.一种对输入法所产生的候选项进行排序的方法，其特征在于，包括：

利用所述输入法接收当前用户的当前输入信息；

根据已经建立的与用户类型相关的G个不同的语言模型，获取所述当前用户当前输入信息的候选项集合中每个候选项所属的用户类型；

按照所述每个候选项所属的用户类型与已获得的所述当前用户所属的用户类型集合中的用户类型的相关性大小，对所述当前用户当前输入信息的候选项进行排序；

展示进行所述排序后的候选项。

2.根据权利要求1所述的方法，其特征在于，所述根据已经建立的与用户类型相关的G个不同的语言模型，获取当前用户当前输入信息的候选项集合中每个候选项所属的用户类型的步骤之前，还包括：

使用文本分类技术，对多个用户历史输入信息进行分类整理，获得G个不同的用户类型和G类不同的与用户类型相关的语料；

将所述G类不同的与所述用户类型相关的语料，分别按照各自所属的用户类型训练得到与用户类型相关的G个不同的语言模型。

3.根据权利要求1所述的方法，其特征在于，按照所述每个候选项所属的用户类型与已获得的所述当前用户所属的用户类型集合中的用户类型的相关性大小，对当前用户当前输入信息的候选项进行排序的步骤之前，还包括：

获取当前用户的历史输入信息；

根据所述当前用户的历史输入信息，用已经建立的所述与用户类型相关的G个不同的语言模型对当前用户进行分类，得到当前用户所属的用户类型集合。

4.根据权利要求2所述的方法，其特征在于，所述按照所述每个候选项所属的用户类型与已获得的所述当前用户所属的用户类型集合中的用户类型的相关性大小，对当前用户当前输入信息的候选项进行排序的步骤之前，还包括：

获取多个用户的历史输入信息，所述多个用户属于所述G个不同的用户类型；

从所述获取的多个用户的历史输入信息中选取部分历史输入信息；

对所述选取的部分历史输入信息进行标注，获得多个用户标注的训练语料；

将所述多个用户标注的训练语料和所述G个不同的用户类型，用教师指导的机器学习方法分别按照各自的用户类型训练出与用户类型相关的用户分类器；

根据当前用户的历史输入信息，用所述与用户类型相关的用户分类器对当前用户进行分类，获得当前用户所属的用户类型集合。

5.根据权利要求3-4任一项所述的方法，其特征在于，所述历史输入信息包括在输入法应用中的历史输入信息、在即时通信工具中的历史输入信息以及在社交网站中的历史输入信息中的任意一种或两种以上历史输入信息。

6.根据权利要求1所述的方法，其特征在于，所述按照所述每个候选项所属的用户类型与已获得的所述当前用户所属的用户类型集合中的用户类型的相关性大小，对当前用户当前输入信息的候选项进行排序的步骤包括：

根据每个候选项所属的用户类型与所述当前用户所属的用户类型集合中的用户类型的相关性大小，获取当前用户当前输入信息的候选项集合中每个候选项的权值；

根据所述候选项集合中每个候选项的权值的大小，对当前用户当前输入信息的候选项集合中的候选项进行排序。

7.根据权利要求6所述方法，其特征在于，所述根据每个候选项所属的用户类型与所属当前用户所属的用户类型集合中的用户类型的相关性大小，获取当前用户当前输入信息的候选项集合中每个候选项的权值的步骤包括：

获取m个用户u₁、u₂、…、u_m在输入所述当前用户当前输入信息的情况下，对同一个候选项c_i的选择次数s₁、s₂、…、s_m，其中，m个用户属于G个不同的用户类型；

在G个不同的用户类型中，获取所述候选项c_i在用户类型g中的权值weight(c_i,g)，即：

其中，P_g(c_i)表示在用户群g对应的语言模型下，候选c_i的概率，

获取用户u_m属于一个用户类型g的权值weight(u_m,g)，即：

其中，P_g(log of u_m)表示用户u_m的输入log文本，在用户群g对应的语言模型下的概率；

其中，k代表第k次迭代，cost(c_i，u_m)是候选项c_i对于用户u_m的成本，cost^k+1(c_i,u_m)＝-weight^k(c_i,u_m)。

8.根据权利要求7所述的方法，其特征在于，所述根据候选项集合中每个候选项的权值的大小，对当前用户当前输入信息的候选项集合中的候选项进行排序的步骤之后，还包括：

根据所述候选项集合中每个候选项的权值的大小，判断候选项集合中是否有高频热词或新词。

9.根据权利要求8所述的方法，其特征在于，所述根据候选项集合中每个候选项的权值大小，判断候选项集合中是否有高频热词的步骤包括：

若候选项集合中候选项的连续预定次迭代产生的所述权值均大于预设的高频热词的阈值，则确定所述候选项为高频热词。

10.根据权利要求8所述的方法，其特征在于，所述根据候选项集合中每个候选项的权值大小，判断候选项集合中是否有新词的步骤包括：

若候选项集合中候选项当前迭代所产生的所述权值与前一次迭代所产生的所述权值相比的变化量大于预设的新词的阈值，则确定所述候选项为新词。

11.根据权利要求8所述的方法，其特征在于，所述判断候选项集合是否有高频热词或新词的步骤之后，还包括：

若候选项集合中有高频热词或新词时，向所述高频热词或新词所属的用户类型的用户推送所述高频热词或新词对应的链接。

12.根据权利要求8所述的方法，其特征在于，所述展示进行排序后的候选项的步骤包括：

展示进行排序后的候选项以及候选项的新词或高频热词的标识。

13.根据权利要求7所述的方法，其特征在于，所述展示进行排序后的候选项的步骤之后，还包括：

根据当前用户的切换指令，按照所述选择次数s₁、s₂、…、s_m的求和结果对所述候选项进行排序；

展示按所述求和结果进行排序的候选项以及所述求和结果。

14.根据权利要求1-4任一项所述的方法，其特征在于，所述语言模型是n-Gram语言模型或n-Pos语言模型。

15.一种对输入法所产生的候选项进行排序的装置，其特征在于，包括接收模块、第一获取模块、第一排序模块以及展示模块，其中：

所述接收模块用于利用所述输入法接收当前用户的当前输入信息，并将所述当前用户的当前输入信息发送给所述第一获取模块；

所述第一获取模块用于根据已经建立的与用户类型相关的G个不同的语言模型，获取当前用户的当前输入信息的候选项集合中每个候选项所属的用户类型，并将所述当前用户的当前输入信息的候选项集合中每个候选项所属的用户类型发送给所述第一排序模块，其中，G是自然数；

所述第一排序模块用于按照所述每个候选项所属的用户类型与已获得的当前用户所属的用户类型集合中的用户类型的相关性大小，对当前用户当前输入信息的候选项进行排序，并将排序后的候选项发送给所述展示模块；

所述展示模块用于展示来自所述第一排序模块的进行所述排序后的候选项。

16.根据权利要求15所述的装置，其特征在于，所述装置还包括网页语料模块和第一训练模块，其中：

所述网页语料模块用于使用文本分类技术，对多个用户历史输入信息进行分类整理，获得G个不同的用户类型和G类不同的与用户类型相关的语料，并将所述获得的G个不同的用户类型和G类不同的与用户类型相关的语料发送给所述第一训练模块；

所述第一训练模块用于将所述G类不同的与用户类型相关的语料，分别按照各自所属的用户类型训练得到与用户类型相关的G个不同的语言模型。

17.根据权利要求15所述的装置，其特征在于，所述装置还包括历史输入信息模块以及第二获取模块，其中：

所述历史输入信息模块用于获取当前用户的历史输入信息，并将所述当前用户的历史输入信息输出给所述第二获取模块；

所述第二获取模块用于根据所述当前用户的历史输入信息，用已经建立的所述与用户类型相关的G个不同的语言模型对当前用户进行分类，得到当前用户所属的用户类型集合。

18.根据权利要求17所述的装置，其特征在于，所述装置还包括第三获取模块、选取模块、标注模块、第二训练模块以及分类模块，其中：

所述第三获取模块用于获取多个用户的历史输入信息，并将所述多个用户的历史输入信息发送给所述选取模块；

所述选取模块用于从所述获取的多个用户的历史输入信息中选取部分历史输入信息，并将所述选取的部分历史输入信息发送给所述标注模块；

所述标注模块用于对所述选取的部分历史输入信息进行标注，获得多个用户标注的训练语料，将所述获得的多个用户标注的训练语料发送给所述第二训练模块；

所述第二训练模块用于将所述多个用户标注的训练语料和所述G个不同的用户类型，用教师指导的机器学习方法分别按照各自的用户类型训练出与用户类型相关的用户分类器；

所述分类模块用于根据当前用户的历史输入信息，用所述第二训练模块得到的所述与用户类型相关的用户分类器对当前用户进行分类，获得当前用户所属的用户类型集合。

19.根据权利要求16-18任一项所述的装置，其特征在于，所述历史输入信息包括在输入法应用中的历史输入信息、在即时通信工具中的历史输入信息以及在社交网站中的历史输入信息中的任意一种或两种以上历史输入信息。

20.根据权利要求15所述的装置，其特征在于，所述第一排序模块包括权值获取单元以及排序单元：

所述权值获取单元用于根据每个候选项所属的用户类型与所述当前用户所属的用户类型集合中的用户类型的相关性大小，获取当前用户当前输入信息的候选项集合中每个候选项的权值，并将所述候选项集合中每个候选项的权值发送给排序单元；

所述排序单元用于根据来自所述权值获取单元的所述候选项集合中每个候选项的权值的大小，对当前用户当前输入信息的候选项集合中的候选项进行排序。

21.根据权利要求20所述的装置，其特征在于，所述权值获取单元包括第一获取子单元、第二获取子单元、第三获取子单元以及第四获取子单元，其中：

所述第一获取子单元用于获取m个用户u₁、u₂、…、u_m在输入所述当前用户当前输入信息的情况下，对同一个候选项c_i的选择次数s₁、s₂、…、s_m，其中，m个用户属于G个不同的用户类型；

所述第二获取子单元用于在G个不同的用户类型中，获取所述候选项c_i在用户类型g中的权值weight(c_i,g)，即：

其中，P_g(c_i)表示在用户群g对应的语言模型下，候选c_i的概率；

22.根据权利要求21所述的装置，其特征在于，还包括判断模块，用于根据所述候选项集合中每个候选项的权值的大小，确定候选项集合中是否有高频热词或新词。

23.根据权利要求22所述的装置，其特征在于，所述判断模块具体用于当候选项集合中候选项的连续预定次迭代产生的所述权值均大于预设的高频热词的阈值时，则确定所述候选项为高频热词；或具体用于当候选项集合中候选项当前迭代所产生的所述权值与前一次迭代所产生的所述权值相比的变化量大于预设的新词的阈值时，则确定所述候选项为新词。

24.根据权利要求22所述的装置，其特征在于，所述装置还包括推送模块，用于向所述高频热词或新词所属的用户类型的用户推送所述高频热词或新词对应的链接。

25.根据权利要求22所述的装置，其特征在于，所述展示模块具体用于展示进行排序后的候选项以及候选项的新词或高频热词的标识。

26.根据权利要求21所述的装置，其特征在于，所述装置还包括第二排序模块，用于根据当前用户的切换指令，按照所述选择次数s₁、s₂、…、s_m的求和结果对所述候选项进行排序，并将按所述求和结果排序后的候选项发送给所述展示模块；

所述展示模块具体用于展示按所述求和结果进行排序的候选项以及所述求和结果。

27.根据权利要求15或16所述的装置，其特征在于，所述语言模型是n-gram语言模型或n-pos语言模型。