CN102439542B

CN102439542B - 电子设备的文本输入系统及文本输入方法

Info

Publication number: CN102439542B
Application number: CN201080022530.6A
Authority: CN
Inventors: 本杰明·威廉·麦德洛克; 乔纳森·保罗·雷诺兹
Original assignee: Touchtype Ltd
Current assignee: Microsoft Technology Licensing LLC
Priority date: 2009-03-30
Filing date: 2010-03-30
Publication date: 2016-03-09
Anticipated expiration: 2030-03-30
Also published as: US20190392034A1; US9659002B2; US20140350920A1; EP2414915A1; CN102439542A; GB0905457D0; EP2414915B1; WO2010112841A1; EP2889729A1; US11416679B2; EP2889729B1; CN105759983A; US10445424B2; US20170220552A1; US20120029910A1; US10073829B2; CN105759983B

Abstract

本发明提供了一种电子设备的文本输入系统，包括：用户界面，用于接收由用户输入的文本；具有多个语言模型的文本预测引擎，用于接收来自于所述用户界面的文本，并利用所述语言模型同时生成文本预测；其中，所述文本预测引擎还用于向所述用户界面提供文本预测，以供显示和用户选择。此外，本发明还提供了一种电子设备的文本输入方法以及在所述系统和方法中使用的一种用户界面。

Description

电子设备的文本输入系统及文本输入方法

技术领域

本发明涉及电子设备的文本输入系统及文本输入方法，特别是指用于生成文本预测以供显示和用户选择的系统以及与此相关的方法。

背景技术

时下，充斥着种类繁多的电子设备文本输入技术。标准键盘是在台式电脑和笔记本电脑上进行文本输入的标准。从1878年将标准机键盘在打字机上的布局设计成为双手操作、多指键入时起，标准键盘的布局被沿用至今。通过以往的训练和/或经验的评估，已证明标准键盘布局的高效性。尺寸缩小的标准键盘经常用于诸如PDA、移动电话等移动设备的文本输入。这样的键盘通常由双手的拇指进行操作，而其优点在于几乎所有用户都熟悉标准键盘布局。诸如黑莓、诺基亚N810等设备都使用这种键盘样式。

然而，对于移动电话的文本输入主要集中于使用9数位数字键盘输入字母字符的方法。其中，每个按键通常代表3或4个字符。现在，已开发出大量用于根据需要减少按键次数的技术。

手写识别已经广泛应用于基于手写笔进行输入的PDA的市场。虽然手写识别为用户带来基于纸张进行手写的体验。但是，与大多数基于键盘的输入方法相比，相对较慢的输入速度使手写识别技术在最近几年中逐渐衰弱。另外，还有语音识别文本输入系统应用于标准和移动电脑设备中。但是，由于受到准确度及环境噪音不利影响的限制，语音识别文本输入技术并未被广泛采用。

触摸屏式设备可以提供适用于不同类型文本输入的灵活度较高的平台，而且现在已有一些模型可供使用。传统标准键盘式“软”键盘已应用于诸如苹果iPhone和一些触摸屏式PDA等运行移动视窗的设备上。其他的设备，诸如黑莓风暴手机使用支持多种消除歧义和单词补全方法的多字符软键盘。此外，还有一些第三方系统为触摸屏式设备提供文本输入的替代方法。具体实例有(Shapwriter有限公司开发的)“ShapeWriter”，该系统基于在标准键盘背景上由字母间滑动形成的形状的识别；ExIdea开发的“MessageEase”，该系统利用经优化的键盘布局实现基于手写笔和手指的文本输入。

剑桥大学提供了一种略微不同的文本输入模型，“Dasher”系统，通过利用自然、连续的指点手势替代敲击键盘来驱动文本输入。这一系统主要依赖于基于高级语言模型的字符预测。尽管该系统能够用于移动电话和基于语音识别的应用中，但其主要致力于为残疾用户提高文本输入的使用便利性。

上述文本输入模型使用了文本预测技术。公知的用于提高文本输入的预测模型具有两种主要功能：

1)消除多字符按键的歧义；

2)尽可能地补全只有部分输入的序列。

上述文本预测技术的实例包括特捷通讯(TegicCommunications)的“T9”，摩托罗拉的“iTap”，Nuance的“XT9”，黑莓的“SureType”，以及字源公司(ZiTechnology)的“eZiType”和“eZiText”。在这些输入法中，都需要维护具有正当词条的词典，为具有正当词条的词典提供特定的输入序列，上述输入法从所述词典中选择一条(或一组)正当的词条，并将该词条作为潜在的补全候选词条呈现给用户。“T9”需要用户输入数量与目标输入序列长度相同的字符。因此，“T9”仅提供上述功能1)，而其他系统可以提供全部上述功能1)和2)。

在上述的这些技术中，都可以通过用户输入新词条来扩增基础词典。而这一扩增仅受设备的有效内存容量限制。“T9”使用静态词典，这意味着永远以同样地顺序向用户提供共享同一键序列的单词。相反地，摩托罗拉的“iTap”使用动态词典，这意味着在每次输入键序列时，给定键序列的预测首字都不相同。此外，这一方法按照近期的使用次数推荐补全。然而，这一方法并不能保证最大可能的补全，而仅能选取最近一次使用的补全。

黑莓的“SureType”，Nuance的“XT9”和字源公司的“eZiType”提供更为复杂的模型，其中，根据使用频率统计挑选出候选的补全词条。此外，字源公司的“eZiText”同样具有通过浏览用户以前的输入鉴别出高频率词组来预测多字补全候选(提供适当输入)的能力。

发明内容

本发明展现出一种由基于字符的文本输入过渡到基于词条或短语的文本输入的显著变化。

本发明提供了一种系统，包括用于接收用户文本输入的用户界面，具有多个语言模型的文本预测引擎，该文本预测引擎用于从用户界面接收输入文本并利用所述语言模型同时生成文本预测。其中，所述文本预测引擎还用于向所述用户界面提供文本预测，以供显示和用户选择。

优选地，在接收输入文本的同时从所述语言模型中实时生成所述文本预测。优选地，所述语言模型包括人类语言模型和至少一种专用语言模型。较为优选地，所述专用语言模型包括一种以上的Email、短信息、新闻电讯、学术研究、日志或产品评测的专用语言模型。可选地，所述专用的语言模型包括Email和短信息的专用语言模型，以及通过使用Email和短信息的专用语言模型的中一个或两个而生成的文本预测。所述语言模型还包括至少一个附加语言模型，例如该附加语言模型可以为用户组专用语言模型。

在本发明的一个实施例中，所述系统包括比较机构，该比较机构用于将存储在语言模型中的词条序列与存储在一个或多个其他语言模型中的词条序列进行比较，以删除重复的或多次输入的词条，仅保留概率最高的重复或多次输入的词条。

在本发明的另一实施例中，所述语言模型包括基于n元语法语言模型的用户专用语言模型。通过更新n元语法语言模型，在n元语法模型图中记录下由用户输入的n元语法模型路径出现的频率。优选地，所述用户专用语言模型用于响应未在其中出现的文本输入，以便向所述语言模型内的所述n元语法模型图中插入新路径。

在一优选实施例中，所述文本预测引擎包括用于合并由各个语言模型生成的文本预测的合并机构。优选地，所述合并机构用于将文本预测插入到有序相联结构或标准模板库(StandardTemplateLibrary，STL)“多重映射”结构中，并返回最可能词条p作为文本预测提供给所述用户界面。

优选地，在缺少任何文本输入和/或在句子结尾输入标点之后和/或在换行之后，所述语言模型利用序列起始标识确定词条或短语预测。

在本发明所述系统的一个实施例中，每个语言模型使用近似单词查找树和n元语法模型图。其中，所述近似单词查找树是标准单词查找树的扩展，在其每个节点上存储有一组用于表示各个节点之后的允许字符序列的数值。

在本发明所述系统的另一个实施例中，每种语言模型使用概率单词查找树和n元语法模型图。其中，所述概率单词查找树是标准单词查找树的扩展，在其每个节点上存储有一组用于表示各个节点之后的允许字符序列的数值。

优选地，所述语言模型用于检索所述n元语法模型图，以根据在前文本输入的n-1个词条，确定下一个词条的单词或短语预测。优选地，所述语言模型用于检索所述近似单词查找树或所述概率单词查找树，以根据至少一个输入字符确定单词预测。

此外，所述语言模型包括近似单词查找树，以及候选词过滤器，以缩小由所述近似单词查找树确定的单词预测的范围；所述候选词过滤器用于丢弃所有当前输入为非其子字符串的候选字符串。

所述语言模型还包括计算机构，该计算机构用于通过检索由所述近似单词查找树、所述候选词过滤器和所述概率单词查找树中的一种确定的单词预测集合以及由n元语法模型图确定的单词预测集合，并仅保留存在于这两个单词预测集合中的相同标识符，计算出这两个单词预测集合之间的交集。

在一个实施例中，所述语言模型还包括具有n+1元语法模型图的布隆过滤器。所述布隆过滤器用于检索所述n+1元语法模型图，并根据下列语境之一返回新的预测集合；

1)用于检索所述n元语法模型图的在先文本输入的n-1个词条的语境；

2)已确定的所述交集中预测词条的语境；以及

3)在用于检索所述n元语法模型图的n-1个词条之前的额外词条的语境。

在一个实施例中，所述语言模型还包括主题过滤器。所述主题过滤器用于预测当前输入文本的主题分类，预测所述预测集合中词条的主题分类，以及根据所述主题分类的预测调整所述预测集合中的预测的概率。

本发明还提供了一种触摸屏式界面，该界面包括单/多字符输入机构，单词预测屏面和用于显示已输入文本的打字屏面。优选地，所述触摸屏式界面包括用于切换单词预测屏面、数字和标点屏面以及标点屏面的菜单按钮。

优选地，所述触摸屏式界面包括用于向Email程序发送输入文本的发送按钮。优选地，所述用户界面用于输入依赖于给定单词序列中被选中的输入词条的单词或短语。

优选地，所述单词预测屏面包括一个或多个显示预测单词的单词键。其中，所述用户界面在所述打字屏面上显示由点击所述单词键而生成的所述单词。优选地，所述用户界面还包括删除按钮和/或撤销按钮。其中，作为对于点击撤销按钮或在所述删除按钮上做出的从左至右的手势的响应，所述用户界面通过擦除所述打字屏面上的单词来撤销上一个单词选择，并回到之前的单词预测屏面。

优选地，所述文本预测屏面包括一个或多个显示预测字的单词键；其中，所述用户界面在所述打字屏面上显示由点击所述单词键而输入的所述单词，并且将包含所述单词的当前输入序列作为语境输入传递给所述文本预测引擎。

优选地，作为对于点击单词键以及在所述单词键上做出按压或由左至右的手势的响应，所述用户界面在所述打字屏面上显示所述单词，并且将不包含所述单词的当前输入序列作为语境输入传递给所述文本预测引擎，并且将所述单词的字符作为当前单词输入传递给所述文本预测引擎。优选地，所述用户界面还包括一个或多个显示标点符号的标点键，以及回车键。其中，作为对于序列结尾标点或点击回车键的响应，所述用户界面将当前序列传递给所述文本预测引擎；其中，所述文本预测引擎包括用于拆分当前序列并将拆分后的序列传递给所述用户专用语言模型的拆分机构；其中，所述用户专用语言模型为拆分后的序列分配数字标识符，并更新其n元语法模型图。

本发明还提供了一种用于处理用户文本输入并生成供用户选择的文本预测的方法。所述方法包括以下步骤：接收输入至用户界面的文本，同时使用包括多个语言模型的文本预测引擎从所述多个语言模型中生成文本预测，然后将所述文本预测提供给所述用户界面，以供用户选择。

在一个实施例中，所述语言模型包括n元语法模型图以及近似单词查找树或者概率单词查找树。所述方法包括根据在先文本输入的n-1个词条检索所述n元语法模型图，以确定下一个词条的单词预测或短语预测的步骤。

在一个实施例中，所述语言模型包括n元语法模型图以及近似单词查找树或者概率单词查找树。所述方法包括根据至少一个输入字符检索所述近似单词查找树或者所述概率单词查找树，以确定单词预测。优选地，所述语言模型包括近似单词查找树，还包括候选词过滤器；所述方法还包括通过丢弃所有当前输入为非其子字符串的候选字符串，缩小由所述近似单词查找树确定的单词预测的范围。

优选地，所述语言模型包括计算机构，该计算机构用于计算由所述近似单词查找树、所述候选词过滤器和所述概率单词查找树中的一种以及n元语法模型图所确定的两个单词预测的交集；所述方法还包括计算这两个所述单词预测的交集的步骤。较为优选地，所述计算机构检索并仅保留存在于这两个单词预测集合中的相同标识符。

在一个实施例中，所述语言模型还包括具有n+1元语法模型图的布隆过滤器；所述方法还包括根据下列语境返回一个新的预测集合的步骤；

2)已确定的所述交集中预测词条的语境；以及

在一个实施例中，所述语言模型还包括主题过滤器；所述方法还包括预测当前输入文本的主题分类，预测所述预测集合中词条的主题分类，以及根据所述主题分类的预测调整所述预测集合中的预测概率的步骤。

在一个较优的实施例中，所述语言模型包括基于n元语法语言模型的用户专用语言模型；所述方法还包括更新在n元语法模型图中由用户输入的n元语法模型路径出现的频率的步骤。优选地，为了响应未在所述语言模型中出现的文本输入，所述方法包括向所述n元语法模型内插入新路径的步骤。

优选地，所述文本预测引擎包括用于合并由所述语言模型生成的所述预测的合并机构。所述方法还包括合并所述预测的步骤，其中所述合并优选地包括将所述预测插入到有序相联结构或标准模板库(StandardTemplateLibrary，STL)“多重映射”结构中，并返回最可能词条p提供给所述用户界面。

本发明还提供了一种计算机程序产品，包括存储有使处理器执行本发明方法的计算机程序的计算机可读介质。

本发明预测文本输入系统及方法具有能够克服上述现有技术缺点的显著优势。“T9”、“iTap”、“SureType”等是基于词条词典的系统，而本发明系统则基于自适应概率语言模型技术，顾及多种语境词条，以数学为依据利用高效的计算方式合并来自于多语言域的信息。因此，本发明的文本输入系统减少了用户文本输入的劳动量，实现了技术上的改进。

下面，将结合下述附图详细介绍本发明。

附图说明

图1为本发明的高层预测结构示意图；

图2a～d为本发明预测结构的两种不同语言模型的示意图；

图3为标准单词查找树的示意图；

图4a为被压缩的近似单词查找树的示意图；

图4b为概率单词查找树的示意图；

图4c为被压缩的概率单词查找树的示意图；

图5为n元语法模型图的示意图；

图6为动态n元语法模型图的示意图；

图7为本发明处理用户文本输入并生成文本预测以供用户选择的方法流程图；

图8为本发明用户界面的示意图；

图8a为本发明可供选择的用户界面的示意图。

具体实施方式

一般来说，可按照但不仅限于图1来实施本发明系统。图1为本发明高层文本预测结构的框图。本发明系统包括用于从多语言模型中生成文本预测20的文本预测引擎100。在一个实施例中，所述系统包括人类语言模型3(在本实施例中该语言为英语)，以及至少一个专用语言模型4(在其他实施例中仅需要人类语言模型3和专用语言模型4中的一个)。在其他实施例中，所述人类语言模型具有除英语之外的其他语言。所述语言模型从语言文本中产生。因此，英语模型3从英语文本1中产生。所述英语文本1通常但不必构成来源于种类繁多的风格和语言人口统计的庞大英语文本语料库。同样地，专用语言模型4从来自于专用语言文本2中产生。

举例来说，如果所述系统为计算机或类似设备，其中的目标应用为email，则专用语言模型4将是一种从包含大量来自于多个作者的email消息的语言文本2中生成的模型。同样地，以移动设备为例，所述专用语言模型4将从移动短信语言文本2中生成。在本系统的某些实施例中，需要使用多种专用语言模型4。例如，可以用来发送email和短信息的移动设备需要短信息专用语言模型和email专用语言模型。其他需要使用多种专用语言模型4的所述系统的实例包括用于处理文字、通过因特网向移动设备发送email和短信息的电脑需要三种专用语言模型4。当然，其他的组合还可能具有更多的专用语言模型4实例，例如包括从新闻电讯、博客、学术论文、文字处理和专利技术中生成的专用语言模型。

在某些实施例中，所述系统还包括附加语言模型6。例如，可以有效地构造一公司专用语言模型，以便在某一特定组织中使用。这包括诸如在文本输入期间能够进行首选或标准措词预测的组织专用语言模型。然而较佳地，所述附加语言模型6还可以包括任意“用户组”专用语言模型。例如，所述“用户组”专用语言模型可以包括方言或利益集团专用语言模型。

之前所述的语言模型均为静态语言模型。即，所述静态语言模型从文本代表体中生成后就不会改变。当然，可以生成并使用新的语言模型，但是已存在于本发明所述系统中的语言模型会保持不变，除非替换或删除该语言模型。

所述系统使用静态修剪机构5对所有静态语言模型进行全面的静态修剪，以减少所述系统中存储的信息量。如果检测到重复的输入或多个输入(在所述系统包括三种以上语言模型的情况下)，所述静态修剪机构5修剪所述静态语言模型，并只保留概率最高的输入。对于静态修剪的描述，参照本说明书后面部分中的单语言模型。

所述文本预测引擎100用于从现有的多个语言模型中地生成文本预测20。通过使用多语言模型8，将来自于多个语言模型中的文本预测20与生成的、供用户界面显示和用户选择的最终预测9合并。所述最终预测9为一组(即，规定的数量)概率最高的预测(预测集合)。所述多语言模型8通过将从多个语言模型中生成的文本预测20插入到可为标准模板库“多重映射”结构的有序相联结构中，生成所述最终预测9。

所述有序相联结构是一种由一些唯一键和数值构成的抽象数据类型。其中，每个键对应一个(或一组)数值。所述有序相联结构可以用来存储作为有序节点树的元素序列。其中，每个节点存储一个元素。元素由用于排序的键和映射值组成。在本系统的一个有序相联结构中，预测是一种映射到概率值的字符串值，基于所述概率执行所述该映射，即，使用所述预测字符串作为有序相联结构中的键值，使用所述概率值作为有序相联结构中的数值。在本系统中，所述有序相联结构按照所述数值(而非本身是预测字符串的所述键值)进行排序。查找与键值对应的数值的操作被称为查表或索引。

标准模板库“多重映射”结构是一种特殊的有序相联结构，其中允许存在重复键值。在本系统的标准模板库“多重映射”结构中，预测是一种映射到概率值的字符串值，基于概率执行所述该映射，使用所述概率值作为所述标准模板库“多重映射”结构中的键值，使用所述字符串值作为所述多重映射”结构中的数值。因此，使用所述键值对所述标准模板库“多重映射”结构进行排序，所述标准模板库“多重映射”结构也就是应当按照所述概率值进行排序的。

举例来说，假设由第一语言模型生成预测“a”→0.2和“the”→0.3，并由第二语言模型生成预测“an”→0.1和“these”→0.2。由所述多语言模型8将这些预测插入到有序相联结构或标准模板库“多重映射”结构，以便利用这些预测的概率为输入的这些预测进行排序((0.1→“an”)，(0.2→“a”)，(0.2→“these”)，(0.3→“the”))。随即从高值开始读取所述有序相联结构或标准模板库“多重映射”结构，并以获得一组最终概率最高的预测9结束。

在一个优选实施例中，所述系统还包括用户专用语言模型7。该用户专用语言模型7具有由用户输入逐步训练出的动态语言模型。用户输入文字串流10引用由用户生成的发展中的文本数据，然后作为逐步训练出的数据被返回给动态的用户专用语言模型，作为对于句子末尾的标点或回车符的响应，或者在其他预定时间将用户输入的文本序列传递给所述多语言模型8，并由所述多语言模型8将所述文本序列划分为将在下文描述的“标记”。然后，将标记化的序列数据12传递给所述用户专用语言模型7。将在下文参照单语言模型的结构描述动态语言模型的更新。

通过更新所述用户专用语言模型7，所述用户专用语言模型7伴随着用户输入10逐步发展，并以此形成了一个反馈循环。在该反馈循环中，由用户专用语言模型7生成的预测依赖于由所述文本预测引擎生成的或由初始阶段未在所述系统中的(由字符输入的)附加单词生成的、用户的在先预测9的选择。

因此，所述系统使用了两种语言模型，即静态语言模型和动态语言模型。所述用户专用语言模型7是动态语言模型的一个实例。

本发明的所述系统是根据预测语言模型推论原理建立的。在所述预测语言模型推论原理中，通过语言中所有词条的特定语境，来预测特定词条的概率P(词条|语境)。通过所述系统的动态应用，从训练的观测数据中预测出所述概率。此处，“语境”用来表示序列中在先出现的两个词条，不难理解“语境”还可以表示所述系统具有的关于当前词条的任意理解(例如，当前词条以特定字符或字符串开头，或者当前词条用来表示某一主题)。考虑到特定语境，所述系统通过使用概率预测P(词条|语境)，预测出随后最有可能出现的单词。

短语预测会在很大程度上增加上层计算成本。因此，所述文本预测引擎必须立刻在词条组合空间(O(n^m)，其中m为短语的长度)中进行检索。然而，所述系统使用了有效的补偿方法，使计算成本比较容易得到控制。

所述系统将词条组合的空间限制为完整n^m的很小一部分。因此，降低了计算费用。为了实现这一点，假设预测词条为t_i，即预测短语中的第i个词条，如果联合概率P(t₀，t₁，…，t_i)超出了当前预测集合中的最低概率值，则仅仅能够预测出后面的词条t_j+1。可通过将每个个体的概率相乘来取得联合概率的预测。因此，在进行短语预测之前，需要具有相当大的把握。此外，如果联合概率降到阙值之下，则不能进行短语预测。

现在，参照图2a～d本发明预测结构的两种不同的语言模型的示意图，介绍如何从单语言模型中生成预测。

有两种输入进入给定的语言模型，一种是当前词条输入11，一种是语境输入12。所述当前词条输入11包括所述系统尝试预测的所述系统的词条信息，也就是用户想要输入的词条。该词条可以是多字符按键序列，单字符按键序列或着是单、多字符按键混合的序列。例如，如果用户想要输入词条“overt”，并在多字符按键键盘上敲击两次，则当前词条输入11为集合{o/p，v/x/z}，表明使用了2-字符键“o/p”和3-字符键“v/x/z”。

如图2c、2d所示，所述系统可以由当前词条输入11生成按键响应矢量31。所述按键响应矢量表现为字符序列概率分布的指数序列形式。例如，如果用户已经使用单字符按键输入字符“i”和“m”，则所述按键响应矢量整理出用户可能打算输入的备选字符，例如im，Im或者I’m。

所述按键响应矢量31具有数量与用户按键次数相同的元素，在本实例中元素的数量为2。预留出上述备选字符的按键响应矢量的一个实例为{[(i→0.7)，(I→0.3)]，[(m→0.7)，(’m→0.3)]，}。此时，所述按键响应矢量的两个元素分别为[(i→0.7)，(I→0.3)]，[(m→0.7)，(’m→0.3)]。

其中，第一个元素表示用户打算输入字符“i”的概率为0.7，打算输入字符“I”的概率为0.3。第二个元素表示用户打算输入字符“m”的概率为0.7，打算输入字符序列“’m”的概率为0.3。

由此可知，所述按键响应矢量的实施例并不局限于单字符按键，同样也适用于多字符按键。在多字符按键的情况下，所述按键响应矢量31的第一元素包括与单次多字符按键产生的多个字符相关的概率值。如果用户将要按下代表字符g、h和i的键，则所述按键响应矢量31的第一元素包括g、h和i的概率值，所述按键响应矢量31的第一元素为[(g→0.33)]，[(h→0.33)]，[(i→0.33)]，则共享同一次按键的各个字符具有相同的概率。

可通过大量方法生成每次按键的概率分布。作为一个非限定性实例，给定标准黑莓键盘布局，假设如果用户输入了一个特定字符，则存在这样的可能，用户实际上想要输入与这个字符邻近的其他字符。通过一个非限定性实例，如果用户输入了字符“k”，则所述按键响应矢量分别为字符“j”、“i”、“l”和“m”分配一个小概率，因为这几个字符在黑莓键盘上距“k”最近。

可选地，可根据字符距触摸屏式设备上触摸点的距离向字符分配概率值。例如，假设用户触摸了“h”字符键，则从触摸点到周围键的键心的距离如下：

1)h：0.05

2)j：03.

3)g：0.25

4)y：0.5

5)n：0.45

6)b：0.7

7)u：0.7

可以使用这些距离的标准倒数(即，p＝(1/d)/D，其中p为结果概率；d为触摸点到特定字符的距离；D＝∑1/d，为所有距离值倒数之和)来生成所述按键响应矢量的概率，例如：

1)h＝20/34.41＝0.58

2)j＝3.33/34.41＝0.1

3)g＝4/34.41＝0.12

4)y＝2/34.41＝0.06

5)n＝2.22/34.41＝0.65

6)b＝1.43/34.41＝0.04

7)u＝1.43/34.41＝0.04

更为复杂、精确的生成所述按键响应矢量中概率的方法具有提高概率准确度的优点，但不利地是通常它们的计算成本比较高。字符序列诸如’t(可以用来在字符“t”前自动添加撇号“’”)的概率必须先验地建立。

每种语言模型都使用近似单词查找树13(如图2a、2c所示)或者概率单词查找树33(如图2b、2d所示)来生成基于所述当前词条输入11或所述按键响应矢量31的单词预测。近似单词查找树13或者概率单词查找树33均为标准单词查找树的扩展版本。标准单词查找树或前缀树是本领域的公知技术，是一种有序的树状数据结构，用于存储字符序列的关联数组。图3示出了一个用于存储一组小文本字符串集合的标准单词查找树的实例。每个节点21都具有指向后续节点的指针22。终端节点(即终结单词的节点)还具有当前路径值。在上述的单词查找树中，给定节点的字符按照字母表顺序排列，并根据路径的字母表顺序为节点分配值。每个节点的路径数量上限由字母表中的字符个数决定。具有高效存储能力的标准单词查找树能够促进快速检索。

图4示出了本发明中的近似单词查找树13，该近似单词查找树13用于存储与图3中标准单词查找树存储的文本字符串集合相同的文本字符串集合。所述近似单词查找树13并不在各个路径节点21上存储单值，而是存储所有后续允许序列的值的集合。从标准单词查找树演变来的这一扩展优化了计算效率和内存管理，并能够使所述文本预测引擎快速识别所有由给定前缀产生的序列。此外，这一扩展还允许所述文本预测引擎指定内部树结构的最大路径(深度)，并且对于任意给定序列还保证如果向所述近似单词查找树中添加一指定字符序列及该序列的相关值，则在检索给定序列时，返回值集合必须包括序列各自的相关值。

举例来说，将与数字标识“9”映射的词条“investigate”添加到某一语言模型的深度为4的近似单词查找树中。在所述近似单词查找树中，所述语言模型首先沿着路径到达由字符“i”表示的节点，接着将标识“9”添加到该节点上的数值集合中(因为每个节点都存储有后续允许序列的数值集合)。然后，沿着路径到达由字符“n”表示的节点并将标识“9”添加到该节点上的数值集合中。对于字符“v”、“e”进行同样的操作。在由字符“e”表示的节点上时，已到达所述近似单词查找树的最深层，由此结束上述过程。随后，如果利用某一语言模型检索“investigate”，则该语言模型将沿着路径‘i’→‘n’→‘v’→‘e’进行所述近似单词查找树的二分查找，然后返回表示‘e’的节点上的数值集合，该节点必然包含数值‘9’。然而，表示‘e’的节点上的数值集合同样还会包含其他被插入的、以“inve”开头的字符串的数值。

因此，在当前词条输入超过所述近似单词查找树的最大深度时，所述语言模型并不能够保证不返回与给定检索序列不相匹配的附加序列的数值。因为上述查询返回的是近似精确的数值集合，所以将标准单词查找树的这种扩展称为“近似单词查找树”。

图4b示出了一种可替代近似单词查找树的概率单词查找树。如图4b所示，所述概率单词查找树用于存储下列完整的词条序列：“I”，“Ill”，“I’ll”，“I’m”，以及诸如“Il”，“I’l”等子字符串。图中箭头阐明的是：假设一特定的按键响应矢量31，如何查询所述概率单词查找树。在图4a中，所述按键响应矢量具有与三个按键对应的三个元素：

1)[(I→1.0)]

2)[(l→0.5)，(‘l→0.5)]

3)[(l→0.2)]

注意，在本实施例中为了简单起见，所述按键响应矢量的第三个元素由概率为0.2的单一元素组成。实际上，每个元素都是由一个共计为1的真实概率分布构成。此外，为了简单起见，本实施例描述了一个单字符输入按键。

图4b中的每个箭头表示的是对于所述按键响应矢量(与由按键输入的字符有关)中的序列的识别，而且查询过程试图遍历所述按键响应矢量中每条可能路径，因此所述查询过程向下遍历了整个概率单词查找树。如果找到了匹配，则将所述序列的概率值与当前累积概率值相乘，然后继续处理。所述概率单词树查询的输出结果是一个标识符映射到概率值的词条序列。每个词条标识符代表一个词条，所述按键响应矢量的单一路径为(可能不恰当的)该词条的子字符串。

在本实施例中，如果以所述按键响应矢量查询所述概率单词查找树，则所述系统将在根节点40处开始尝试沿包含在所述按键响应矢量第一元素的第一项中的序列(在本例中为字符“I”)而行进。离开所述根节点40的唯一路径包含字符“I”，因此所述系统沿这条路径而行并将概率状态(累计概率值)更新为1.0。因为所述按键响应矢量的第一元素中不存在其他项，因此所述系统移动至下一元素，先尝试沿字符“l”行进，然后沿序列“’l”行进。这两种选择都匹配所述概率单词查找树结构，因此沿着这两条路径行进，并将概率状态分成需要进行相关乘法运算的两份。分别将这两条路径的当前概率状态(累计概率值)乘以0.5，得到结果为0.5。注意，所述系统在所述概率单词查找树中沿着“’l”路径横跨两个概率状态，但仅被当做由所述按键响应矢量指定的单一概率进行处理，因为用户并没有输入撇号“’”。然后，所述系统移至所述按键响应矢量中的结尾元素，并尝试从两种当前概率状态中匹配字符“l”。所述匹配是成功的，在字符“l”和序列“’l”这两条路径上都进行了相关的概率乘法运算，最终得到的当前概率状态为0.1。因为在所述按键响应矢量中不存在其他元素，因此所述系统将各个末端节点上的值连同这些值各自的概率状态值一起返回。在本例中，系统返回各个末端节点上的值为映射概率值均为0.1的标识符2和4。

为了提高存储效率，所述系统使用本领域公知技术压缩整个概率单词查找树，并以同样的方式压缩如图4a所示的近似单词查找树。通过将相邻的非分叉点连接在一起来压缩所述概率单词查找树33。图4c示出了图4b中的概率单词查找树的压缩过程。这样的话，所述概率单词查找树中的路径就包含了多个字符，而且有些箭头在同一节点上起始和终结。

优选地，本发明的所述系统使用的是概率单词查找树33，而非近似单词查找树13。所述概率单词查找树33具有将概率值映射到字符串的优点。此外，所述概率单词查找树33并不受指定的最大深度的限制。然而，对于单词查找树的选择取决于诸如可用内存大小等因素。

由此可知，本发明中的所述按键响应矢量31和概率单词查找树33除了可以用来纠正遗漏标点符号的错误之外，还可以用来纠正单词字符输入中的错误。与用户遗忘插入标点符号的实例相似，本系统可以用来插入被用户遗漏的重复的字符。例如，如果用户想要输入‘accommodation’，但仅输入了‘a-c-o’，则本系统将通过插入字符‘c’来解决遗漏字符‘c’的问题。举例来说，该字符序列的按键响应矢量31可以是[(“a”→1)，(“c”→0.9，“cc”→0.1)，(“o”→1)]。该按键响应矢量对于单辅音字母输入的这种特殊情况按照单辅音字母输入对应双单辅音字母进行编码，例如c→cc，d→dd，m→mm等。

可以将所述按键响应矢量31归纳成：在将每个字符输入系统后对遗漏的字符进行负责。例如可将所述按键响应矢量归纳为[(“a”→0.9，“a*”→0.1)，(“c”→0.9，“c*”→0.1)，(“o”→0.9，“o*”→0.1)]。在按键响应矢量31的这一实例中，每个单字符都与一潜在的双字符输入联系在一起，但是双字符输入中的第二个字符是不确定的。通过在概率单词查找树中沿来自于当前节点的具有一定概率的所有可能路径行进，来补充不确定字符的符号“*”。因此，在上述例子中，假设第一元素为(“a”→0.9，“a*”→0.1)，与字符“a”对应的所述路径的概率为0.9；所有与身后跟随有其他字符的字符“a”对应的现有路径的概率为0.1，这样的路径实例包括“ab”、“ac”、“ad”、“a-”等。

使用类似的方法插入空字符，即忽略用户输入的字符。例如，如果在用户想要输入‘necessary’时，插入了字符‘n-e-c-c’，此时所述系统可以忽略掉重复输入的单辅音字母，即只检索出序列‘n-e-c’。因此，对于字符输入‘n-e-c-c’的按键响应矢量31的一个实例可以为[(“n”→1，“e*”→1)，(“c”→1，“c”→0.9，“”→0.1)]，其中“‘”→0.1’相当于匹配(假设)概率为0.1的“空”字符串。通过在每个已输入的字符后面插入具有一定概率的空字符，将所述按键响应矢量归纳成“忽略”由用户输入的每个字符。经过归纳的按键响应矢量31可以是[(“n”→0.9，“”→0.1)，(“e”→0.9，“”→0.1)，(“c”→0.9，“”→0.1)，(“c”→0.9，“”→0.1)]。在概率单词查找树中，由保留在当前节点上的按键响应矢量来实施所述空字符“”。上述方法的使用范围可以扩及至一些例如由用户输入的序列中的每个字符完成输入后，用户遗漏了字符或插入了一个错误的字符等小概率事件。

很明显，上述操作将增加所述系统的运算成本(所述符号“*”会明显影响被跟随路径的数量)。然而，上述操作会使所述系统更善于纠正用户拼写或输入的错误。

再回到图2a或2c，所述语言模型可以通过使用候选词过滤器15来缩小由所述近似单词查找树返回的预测集合的范围，以使所述预测集合仅仅包含完全由当前字输入允许的候选标识符。仅在当前输入的长度超过近似单词查找树的最大深度时，候选过滤才是必需的。而此时在任意候选过滤的应用中，至少要使用一次候选过滤，而使用3～5次候选过滤通常是比较适当的。除此之外，不必使用候选过滤。为每个语言模型指定先验的近似单词查找树的深度。所述候选词过滤器查找出由近似单词查找树返回的数字标识符集合中的数字标识符表示的实际候选词条字符串值后，通过将各个实际候选词条字符串值与当前输入进行比较，逐个处理这些实际候选词条字符串值。对于一个给定的候选字符串s，如果当前输入不是该候选字符串s的子字符串，则丢弃这个不是真候选的候选字符串s。

由此可知，并不需要使用候选词过滤器缩小由概率单词查找树33(参见图2b、2d)返回的预测的范围，因为所述概率单词查找树33不受指定的最大深度的限制。

所述语境输入12包括截至到目前由用户输入的、在当前单词之前的序列。由所述多语言模型8将所述序列拆分为多个“标记”，其中的标记可以是单个词条、标点符号、数字等。所述多语言模型8将标记化的序列数据作为语境输入提供给各个语言模型。如果所述系统为第n个词条生成预测，则所述语境输入12包含已被选中且由用户输入系统的在先的n-1个词条。

所述语言模型使用n元语法模型图14生成基于所述语境12的单词和/或短语预测。如图5所示，n元语法模型图14是一种相关映射结构。在所述n元语法模型图14中，词汇表中的词条带有数字标识符(短整型)，这些带有概率值的数字标识符存储在n元语法模型图14中。单个父节点的子节点合并概率之和总是为1。将作为从用于训练语言模型的训练数据中估计出的标识符分配给词条，以便产生由最高频率至最低频率的排序结果。因此，所述标识符由P(词条)定义排序，其中，P为语言模型中词条的一元语法模型概率。所述标识符由P定义排序是十分重要的，因为这样可以优化文本预测引擎通过将P(词条|语境)近似为P(词条)来进行n元语法模型图检索的效率。通过为在给定的n元语法模型图层级上的词条排序来进行所述近似操作。所述n元语法模型图层级是由P(词条)给定的，而非词条概率排序P(词条|语境)。

在所述系统中，以压缩方式存储n-元语法模型概率，以便帮助有限的存储设备实现广泛的作用范围和快速的存取速度。优选地，由离散(衰减)过程来压缩概率值，其中，离散化所述概率值，并将所述概率值散布于单字节内存中有效的概率值范围。假设概率值为p，使用下列公式将概率值p映射到单字节内存：b＝int(abs(log(p))*10)，其中int(x)求出具有小数位的数值x的整数部分，abs(x)求出数值x的绝对值。

还可以通过将字符串数值表示为短整型数值，并将高层级输入存储在低层级输入之上，来压缩所述n元语法模型图。因此，例如三元语法模型“inthemorning”存储在与二元语法模型“inthe”相同的位置上，但是该三元语法模型与额外的n元语法模型首词条“morning”链接，也就是，将后续允许序列的一组数字值(标识符)存储在所述n元语法模型图中的每个节点上。

为了由n元语法模型图14生成预测，在每个图节点21上，语言模型执行二分查找以定位指定的后续子节点。例如，如果上下文包括词条1和词条2，则语言模型先定位词条1的节点，然后指定词条2的、将被检索的子节点。为了帮助该检索，在每个父节点上，利用子节点的标识符对所述子节点进行数字排序。需要检索的节点可能包含大量子节点，但仅对高概率候选感兴趣。因为，这些子节点是由P(词条)自动排序的，所述语言模型仅仅返回第一批k个子节点，其中k为预设值。本方法假设：只要k足够大，P(词条|语境)下的最大概率候选存在于P(词条)下的具有k个最大概率候选的集合中。利用P(词条|语境)为子节点排序并不可行，因为利用P(词条|语境)为每个子节点排序需要使用不同的n元语法模型图，由此会极大地增加内存管理费用。

下面将进一步描述如何由n元语法模型图14生成预测。如果语言模型正在检索最大概率词条候选，假设两个语境词条为“in”和“the”，则所述语言模型将检索最大化3元语法模型概率P(t|inthe)的词条t。所述语言模型首先查找“in”的标识符，然后在所述n元语法模型图的第一层级中进行二分查找以定位标识符(如果存在的话)。从“in”节点下来，所述语言模型查找“the”的标识符，然后在所述n元语法模型图的下一层级中进行二分查找以定位标识符。由于“inthe”是一种普通前缀，因此这个节点很可能有许多子节点。因此，所述语言模型返回可能与“morning”、“first”、“future”、“next”、“same”等词条对应的第一批k个子节点(由P(词条)反向排序)。

上述n元语法模型图结构目前应用于静态语言模型。一旦静态语言模型被构建，并存储了被压缩的n元语法模型图概率后，静态语言模型就是不可改变的。静态语言模型由已有数据生成，然后被编译成在运转时间为可读的二进制格式的文件。

相反地，可以在任何时候更新例如所述用户专用语言模型7的动态语言模型，并且从动态语言模型中成的预测经常变为被加工处理的新数据。

更新动态语言模型的两种方式之一为：将之前不在动态语言模型词汇表中的词条列入；然后更新特定n元语法模型语境中已存在词条的频率。动态n元语法模型图存储由用户出入的n元语法模型路径的频率，其中“n元语法模型路径”引用一特定词条，以及多达n-1个在先语境词条。

对于当前词条t，当前语境c以及动态语言模型D，如果当前词条t不在动态语言模型D的词汇表中，则所述动态语言模型D将所述词条t映射到一个新标识符后将其插入所述近似单词查找树或所述概率单词查找树。为了输入一个不在所述动态语言模型D词汇表中的词汇，用户可以在所述系统的用户界面通过依次输入该词条字符的方式插入该词条。然后，所述动态语言模型D沿着由当前词条t以及当前词条t在n元语法模型图中的当前语境c表示的路径行进。如果没有新节点，则建立新节点。由此，根据所述当前词条t的在先语境c，在所述动态语言模型D中建立新n元语法模型图路径。将这些路径加入到所述动态n元语法模型图中，用于在从零语境词条到n-1个语境词条范围内改变语境的长度。其中，n是所述动态语言模型的最大n元语法模型次序。当用户在过一段时间后输入所述词条t时，所述动态语言模型D将存储在用于表示该词条t的所述n元语法模型图节点上的计数值加1，并将该节点父节点上的总计数值也加1。这样，就完成了包括词条t和词条t的在零语境词条到n-1个语境词条之间变化的语境的n元语法模型路径输入频率在所述n元语法模型图中的更新。

不直接存储动态语言模型的n元语法模型概率，而是存储频率统计。图6示出了动态n元语法模型图的实例。每个节点存储有包括其子节点组合频率(表示为“T＝”)的频率值，而非概率。从所述频率值中，通过将特定词条的计数值除以特定词条父节点上的总计数值，高速计算出概率。优选地，将平滑常数加入每个父节点中以避免不合理地过高估计稀疏事件。平滑常数值选择得越高，用户专用语言模型中的概率就会虚增得越慢(因为特定词汇的概率是通过将特定词条的计数值除以其父节点上的总计数值而得到的)。在一优选实施例中，选择的平滑常数为500。然而，这个平滑常数值仅是选择之一。

所述动态语言模型的优点是允许快速更新。然而，此类语言模型的缺点是：相对于静态语言模型，具有更高的内存和计算要求。

由上所述，每种语言模型都具有两个输入源，当前词条输入11和语境输入12。其中，当前词条输入11可以用来生成按键响应矢量31。为了生成给定语言模型的单组文本预测20，所述语言模型必须计算出由所述近似单词查找树12、可选的候选词过滤器15返回的候选集合与由所述n元语法模型图14返回的候选集合之间的交集。可选地，所述语言模型必须计算出由所述概率单词查找树33返回的候选集合与由所述n元语法模型图14返回的候选集合之间的交集。候选集合由一组数字标识符表示。

为了计算出分别由所述近似单词查找树和所述n元语法模型图返回的候选集合之间的交集，逻辑乘法机构16首先确定所述两个集合中哪个集合较小。将较小的标识符集合作为基本集合。所述逻辑乘法机构16遍历所述标识符基本集合，并在另一集合中找出还存在于该基本集合中的每个标识符。如果找到了问题中所述标识符的匹配，则所述逻辑乘法机构16将该标识符放入一个用来表示所述两集合之间交集的新集合中。在本实施例中，所述新集合中的标识符的概率就是存储在所述n元语法模型图中的概率。这是因为由所述近似单词查找树返回的候选并没有相关的概率值。通过查询所述近似单词查找树仅返回合适的候选。

为了计算出分别由所述概率单词查找树33和所述n元语法模型图返回的候选集合之间的交集，所述逻辑乘法机构16使用了与上述近似单词查找树相关的相同步骤。然而，在计算分别由所述概率单词查找树33和所述n元语法模型图返回的候选集合之间交集的这种情况下，由所述概率单词查找树33返回的候选包含概率值。因此，如果在由所述n元语法模型图返回的候选和由所述概率单词查找树33返回的候选之间找到匹配，则所述逻辑乘法机构16计算出两个概率的结果，并将映射到结果概率的标识符放入一个用来表示所述两集合之间交集的新集合中。

所述语言模型使用一个或多个过滤器过滤由所述逻辑乘法机构16生成的预测。在一个实施例中，使用的第一过滤器为布隆过滤器17，其后为主题过滤器18和可选的附加过滤器19，以生成给定语言模型的输出预测20。然而，在其他实施例中，可以改变所使用过滤器的次序或类型。

布隆过滤器17是一种随机化数据结构，用于以高效方式使用位数组及散列函数组合来存储对象集合。本系统通过操作多位数组布隆过滤器17来为预测候选重新排序。该预测候选是在所述逻辑乘法机构16上根据出于内存原因不能存储在所述n元语法模型图14中的高层级n元语法模型统计生成的。本系统使用了在所述布隆过滤器中将n元语法模型图14与概率值结合在一起的技术。将布隆过滤器的输入词条与概率值结合在一起的技术已在塔伯特和奥斯本编著的《2007年自然语言处理和计算学自然语言学习中经验方法联合会议的会议记录》，第468至479页(TalbotandOsborne，2007，Proceedingsofthe2007JointConferenceonEmpiricalMethodsinNaturalLanguageProcessingandComputationalNaturalLanguageLearning，pp.468-479.)中公开。

对于给定的一组预测候选和一定数量的语境词条，所述布隆过滤器17为所述预测重新排序以反映新概率。本系统采用了将一组n元语法模型输入词条映射到各自频率概数上的对数式频率布隆过滤器(塔伯特和奥斯本)。在本系统中，所述语言模型根据一组数量为n-1的语境词条C生成了预测集合P。将n+1元语法模型词条序列与概率概数结合在一起的对数式频率布隆过滤器F用于生成新预测集合。在先预测在新预测集合被重新排序。对于预测集合P中的每个词条预测t，所述语言模型根据c+C+t的语境检索F，以生成新概率值v。其中C包含用于检索n元语法模型图的在先输入文本的n-1个词条；t包含预测集合P中的词条预测(在已确定的交集中)；c包含在n-1个用于检索所述n元语法模型图的词条之前的语境的额外词条。因此，通过检索所述布隆过滤器的n+1元语法模型图获取每个n+1元词条序列、c+C+t，以便确定是否存在n+1元语法模型路径。如果存在n+1元语法模型路径，则将概率与n+1元语法模型路径结合。然后，使用新概率构造新预测集合。一般地，如果p是要求的预测的最终数量，则执行过滤过程的次数超过p(先验确定的)次，以使重新排序过程能够产生返回给用户的、不同的预测集合。

在一些实施例中，所述语言模型还使用了主题过滤器18。N元语法模型统计根据局部语境生成了预测候选概率概数，但全局语境任辉影响候选概率。本系统使用能够积极识别给定书写片段的最可能主题、并相应地重新排列候选预测的主题过滤器18。

所述主题过滤器18能够顾及主题语境会影响词条使用率的这一事实。例如，给定序列“wasawardeda”，随后的词条“penalty”或“grant”出现的可能性很大程度上取决于讨论的题目是“足球”还是“金融”。在主题过滤器考虑整个文本片段有可能出现的语境时，局部n元语法模型语境却经常无法阐明这一事实。

所述主题过滤器的作用是接收预测集合，并生成改变了预测词条的概率值的该集合的变体。因此所述主题过滤器必然能够改变该预测集合中预测的排序。给定一输入预测集合P和当前输入文本T，所述主题过滤器执行下列操作：预测在当前输入文本T中表示最可能主题的分类的加权集合；预测在预测集合P中词条/短语主题分类的加权集合；并修改预测集合P，以便相对于同当前输入文本T主题分类不相同的预测，提高与当前输入文本T主题分类相似的预测的概率。

通过由某一结构构成的分类的机器学习范型，完成文本任意片段的主题分类预测。在该结构内，一机械“学习者”归纳出在特定样本空间中抽取的元素与指定目标类集合之间的函数映射(更多关于分类概念和方法的详细介绍，参考B.Medlock编写的、VDMVerlag于2008年出版的《自然语言处理任务的调查分类》，“B.Medlock，″InvestigatingClassificationforNaturalLanguageProcessingTasks″，VDMVerlag2008”)。

根据必须首先收集大量训练数据并为训练数据分配用于表示主题分类的标签的监督式学习原理，在所述主题过滤器18中使用分类器。从训练数据中，所述分类器学习推断新数据的可能主题分类标签。在本例中，个体数据样本为文本片段。例如，在构建分类器以在新闻域中标注数据时，必须要有一些新闻报道，其中各个新闻报道已被预先分配了表示其主导主题的主题分类标签，例如“体育”、“金融”、“娱乐”等。预先定义主题分类集合，并且该主题分类集合是分层次等级的，例如“足球”是“体育”的子类。

一旦所述分类器通过已有数据的训练，它就能够预测出文本新闻片段最有可能的主题分类。所述最有可能的主题分类连同每个预测的用于构成该预测的表示置信度的数字值一起构成所述预测。例如，给定如下文本片段，“DavidBeckhamwillstayatACMilanuntiltheendoftheseasonaftera‘timeshare’dealwasfinallyagreedwithLosAngelesGalaxy”，经过训练的分类器可以生成如下分类预测‘sport’→0.8；‘finance’→0.3，其中，数字值用于表示在上述预测中各分类的置信度。可将所述数字值解释为对于给定文本片段中特定主题表达程度的估计。

可通过使用所述分类器输入文本片段，完成来自于预测集合P的个体词条/短语的主题分类的预测。由此生成预测集合P中每个词条/短语预测的加权主题分类预测集合。

预测集合P中预测概率的修改需要在主题分类预测集合之间定义“相似度标准”。如此得到函数形式：sim(S，S’)＝v，其中S和S’为主题分类预测集合；v为函数sim产生的实数值，用来表示S和S’之间的相似度。执行函数sim的方法有多种，并且每种方法都很合适。例如，可将主题分类预测集合解释为m维空间中的矢量，其中m为主题分类的数量。在这种解释之下，由所述分类器分配给特定分类c的权重为c维空间矢量的外延。可使用完善的技术例如通过应用量级标准化和采用内(点)积矢量运算，来估计矢量的相似度。

一旦确定了相似度标准，所述主题过滤18内运行的最后阶段是通过使用相似度数值来修改预测集合P中的概率。可选用一些技术来实现这一修改，但是会有这样一种可能，即在预测集合P中的概率由带有频率值T的主题相似度排序时，会与预测集合P中的概率的排列次数成反比地少量虚增所述概率。以公式p_final＝P_initial+k/r为例，其中p为从预测集合P中取得的预测概率；当以sim(S_p，S_T)(rank1＝最高相似度)进行排序时，r为与p有关的词条的排列次数；k为预先定义的常数。

本系统的语言模型的结构便于使用许多附加过滤器19来为候选概率重新排序。在各个阶段中，所述语言模型已具有一候选预测集合，并且如果超过计算时间阙值，则所述候选预测集合会被返回，并且附加过滤器19会被轻易地绕过。

所述语言模型返回其作为映射到概率值的词条/短语集合的预测20。如图1中所阐明的，通过多语言模型8聚集由各个语言模型输出的预测20，以生成提供给用户界面以供显示和用户选择的最终预测集合10。

从图2a～2d中可以看出，缺少了当前词条输入11并同样缺少了按键响应矢量31，所述预测仅仅建立在输入的语境12的基础之上。

在一些实施例中，所述系统在不存在任意在先用户输入的情况下，使用序列的起始标记来生成单词或短语9的列表，以使用户能够通过选择单词或短语来着手句子的输入。所述系统还可以使用“序列起点”(beginningofsequence，BOS)标记确定在句子末尾标点和/或在换行之后的单词或短语预测。

所述语言模型在缺少任意在先用户输入的情况下使用作为语境12的BOS标记。在缺少在先用户输入的情况下，所述语言模型会生成某些词条，例如“Hi”、“Dear”、“How”、“I”等，因为这些词条的出现概率要比高概率的一元语法模型词条诸如“of”、“to”、“a”等更高。在BOS标记的基础上从各个语言模型20中生成预测。在所述n元语法模型图第一层级上的其中一个输入为所述BOS标记，并且以和标准输入词条相同的方式将该BOS标记作为语境来使用。例如，如果所述BOS标记为‘^’，则所述n元语法模型图可以包括(除其他)如下路径：“^Dear”→0.2；“^Hi”→0.25；“^How”→0.1；以及“^I”→0.15。优选地，在用户输入句子结尾标点(句号、感叹号、问号)或输入“回车”符时，可将BOS标记自动插入到语境中。

在用户指定语言模型7为动态语言模型时，随着时间的流逝，语言模型7将学习用户的语言风格，由此生成更有可能反映特殊用户语言风格的预测。然而，如果文本预测引擎生成了未能列入用户想要词的单词或短语列表，则用户可以利用所述用户界面输入字符11来调整由所述文本预测引擎生成的所述词条或短语列表。然后，所述语言模型利用近似单词查找树13会或概率单词查找树33，连同n元语法模型图一起生成基于当前单词输入11的单词预测列表。

如上所述，参考图1，本系统使用静态修剪机构5对所有静态语言模型进行全面的静态修剪，以减少所述系统中存储的信息量。下文中描述的静态修剪涉及到单语言模型的修剪。

给定两个语言模型L1和L2，通过与参考语言模型L2进行比较来完成对于语言模型L1的修剪。每个语言模型包括n元语法模型图，在该n元语法模型图中，词汇表中的词条具有存储在n元语法模型图中、与概率值联系在一起的数字标识符。因为将所述数字标识符分配给词条便于产生由最高频率至最低频率的排序结果，分配给在某一语言模型中的指定词条的标识符不必与分配给在其他语言模型中的同一指定词条的标识符相匹配。因此，为了完成静态修剪，所述静态修剪机构5在语言模型L1的词汇表标识符与语言模型L2的词汇表标识符之间生成一转换表。所述转换表将语言模型L1中的给定词条t的标识符映射到语言模型L2中的给定词条t的标识符。例如，如果在语言模型L1中词条“the”由数字标识符1标识，在语言模型L2中词条“the”由数字标识符2标识，则给定语言模型L1的数字标识符为1，所述转换表将为语言模型L2生成数字标识符2。

所述静态修剪机构5遍历语言模型L1的n元语法模型图，以便使每个节点都被确切地访问过一次。对于语言模型L1中的每条跟随路径，尝试将语言模型L2中的对应路径通过使用所述转换表将语言模型L1中的路径标识符转换为语言模型L2中的路径标识符。所述静态修剪机构5进行二分查找以找出指定的后续子节点。例如，如果语境包括词条1和词条2，所述静态修剪机构5首先找到词条1的节点。词条2是接下来需要检索的指定子节点。通过在语言模型L2中执行上述检索，可识别出同样的路径。如果在所述语言模型L2中没有同样的路径，则所述静态修剪机构5在语言模型L2中查找与语言模型L1中的下条路径相同的路径。如果在语言模型L2中存在同样的路径，则所述静态修剪机构5对各节点上的概率进行比较。如果语言模型L1中词条1、词条2所在各节点上的概率小于语言模型L2中词条1、词条2所在各节点上的概率，并且词条1所在的节点为末节点，则所述静态修剪机构5将从语言模型L1中移除该节点。

现在参照为本发明处理用户文本输入并生成文本预测以供用户选择的方法流程图的图7，详细介绍本发明提供的电子设备的文本输入方法。在上述方法中，第一步骤包括接受文本输入。与之前本发明提供的电子设备的文本输入系统的讨论类似，所述文本输入包括当前单词输入11(可被表示为按键响应矢量31)和/或语境输入12。因此，所述输入流可以包含字符、单词和/或短语输入和/或标点输入。在具体实施例中，预测文本引擎同样用于预测存储在n元语法模型图中伴随文本词条出现的标点、标点项。将单标点项(′！′，′？′)以及一组标点(′！！！！！！！′，′…′)作为一个预测单元进行处理。

所述方法还包括通过使用包含多个语言模型的文本预测引擎从多语言模型中生成文本预测；并为用户提供文本预测选择的步骤。如图7中的方法流程所示，在用户输入序列时，因为该包含从在先预测集合中选择的词条的序列用于更新促成下一组预测9的动态语言模型，由此形成一循环。例如，可通过在序列末尾插入标点符号或“回车”符形成该循环。因此，基于上述在先序列输入可以不断地更新预测。

举例来说，加入用户已经输入了序列“Hopetoseeyou”，并想要以如下词条顺序输入词条“very”以及“soon”。由文本预测引擎100提供给用户界面以供显示和用户选择的最终预测集合9包括‘all’、‘soon’、‘there’、‘at’、‘on’、‘in’。

想要输入的下一词条“very”并不在当前预测出的词条列表里。用户可以输入多字符‘v/x/z’以提示所述文本预测引擎100提供更贴切的预测。将与当前语境“Hopetoseeyou”有关的信息和当前输入的多字符‘v/x/z’一并转给所述文本预测引擎100，由所述文本预测引擎100中的多语言模型8将所述语境拆分，并加入序列起始标记“^”：“Hopetoseeyou”→“^”“Hope”“to”“see”“you”。

然后，所述多语言模型8将被拆分的序列数据12以及多字符当前单词输入11传递给各个语言模型。每个语言模型接收到所述当前词条输入11和被拆分语境12的副本。

在各个语言模型内，将所述当前单词输入(可表示为按键响应矢量31)送入近似单词查找树13或概率单词查找树33。在这种情况下，近似单词查找树13或概率单词查找树33会返回所有以‘v’、x’或‘z’开头的词条的标识符集合。这一过程是由如下步骤完成的：通过沿着初始路径到达字符v’、x’和‘z’相应的节点；合并在各个所述节点上找到的标识符数值集合并返回合并后的集合。在由近似单词查找树13返回标识符的情况下，可使用候选词过滤器15来缩小标识符集合的范围。然而在本例中并不需要过滤器，这是因为当前词条输入的长度小于所述近似单词查找树的最大深度。因此，仅在使用近似单词查找树13、且所述当前词条输入的长度超过所述近似单词查找树的最大深度时，才有使用候选过滤的必要。如之前记载的，在所有应用之中，所述近似单词查找树的最大深度至少为1，通常为3～5。各个语言模型的近似单词查找树深度是先验指定的。

使用被拆分的语境12，由所述语言模型查询所述n元语法模型图14以获取给定的n元语法模型的阶次，即若干语境词条。各个语言模型都包括取决于n的最大值的n元语法模型。例如，某一特定语言模型包括1、2、3元语法模型，其最高n元语法模型阶次为3。所述系统先取得语境的最大可能数量并查询所述n元语法模型，以查看是否存在用于表示语境的路径输入。因此，例如，如果给定语言模型的n元语法模型最高阶次为3，则在本例中所述系统先查询与语境短语“seeyou”对应的路径。然后，所述系统摘取出对应于该路径的第一批k个子节点。其中，k为所述系统的先验参数。在静态语言模型中，每个子节点包含有词条标识符和被压缩的概率数值。可将该被压缩的概率数值提取出来以便在预测排序中使用。在动态语言模型中，每个子节点包含有频率值。必须使用子节点所属父节点上的频率总值规范化该频率值以生成概率。

给定一组来自于所述近似单词查找树13的标识符的集合或映射到来自于所述概率单词查找树33的概率值的标识符的集合，以及一组映射到来自于n元语法模型图14的概率值的标识符的集合，由逻辑乘法机构16计算上述集合间的交集。如果结果集合中的预测数量小于p，或为p的一定倍数(其中，p为必需的预测数量)，所述系统则返回所述n元语法模型图14并考虑更小的语境继续查询其他预测。在本例中，如果语境“seeyou”没有生成足够的预测，所述系统则考虑语境“you”(所述n元语法模型中的第二层级)，而且如果仍然没有生成必需的预测数量，所述系统则将语境还原成空白语境(所述n元语法模型中的第一层级)。

在本例中，所述系统在先检索与所述语境短语“seeyou”对应的路径。在这一步骤中，所述语言模型获得了与所述语境和当前单词输入(可表示为按键响应矢量31)相匹配的、并按照来自于所述n元语法模型图的预测词条的各自概率值排列的预测词条集合。例如，所述预测集合可以包括与词条“very”、“visit”和“x”对应的标识符。通过使用布隆过滤器17对在先预测进行重新排序，生成新预测集合。在这种情况下，所述布隆过滤器包括与概率估计有关的4元语法模型序列。所述语言模型使用包含用于检索n元语法模型图的在先语境(“seeyou”)、当前预测集合(“very”、“visit”和“x”)以及可选的附加语境词条(在本例中为“to”)的新语境来查询所述布隆过滤器。因此，在本例中可使用如下序列：“toseeyouvery”、“toseeyouvisit”和“toseeyoux”来查询所述布隆过滤器。

然后，可使用由所述布隆过滤器返回的概率值替换在当前预测集合中映射到词条“very”、“visit”和“x”的概率值，因此上述词条必然会被重新排序。附加过滤器以相同述的方式进行工作。一般地，如果p是必需预测的最终数量，则需要执行的过滤过程次数需要大于p(先验指定的)，从而使重新排序过程能够产生不同的预测集合以返回给用户。

一旦应用了所有过滤器，预测集合(词条+概率值)20由各个单语言模型返回给所述多语言模型8。接着由所述多语言模型8通过将所有的预测插入有序相联结构或STL多重映射结构来使所述预测聚合，并且选择最可能词条p作为最终的预测集合9返回。在本实例中，显示给用户的预测集合9为‘very’、‘via’、‘view’、‘x’。

想要输入的词条“very”现出现在预测列表中，并可被选中。一旦选中该词条，则包含词条“very”的语境变为“Hopetoseeyouvery”，而当前词条输入为空。接着除绕过所述近似单词查找树或概率单词查找树(因为此时无字符输入，即无当前词条输入)，以及从所述n元语法模型图中单独摘出预测候选集合这两步骤之外，以相同方式重复前述方法步骤。如此将会生成下列预测集合‘much’、‘soon’、‘good’、‘many’、‘well’。

词条“soon”出现在预测集合中，因此用户可以选择这一词条.而当再次更新语境时，此时包含新词条的所述语境为“Hopetoseeyouverysoon”，并设置当前词条输入为空。随着输入进展，连续重复这一过程。

当用户通过点击‘回车’或输入序列结尾标点符号结束序列时，所述用户界面将当前序列传递给所述文本预测引擎100，其中，所述多语言模型8拆分当前序列，然后将被拆分后的序列传递给所述用户专用语言模型7。动态语言模型7为被拆分的输入12分配数字标识符，并更新所述n元语法语言模型图14。利用相同的例子，认为用户随后在所述序列结尾加入了感叹号，从而生成“Hopetoseeyouverysoon！”。下面的步骤包括：所述多语言模型8拆分了所述序列，并且插入了BOS标记，例如“Hopetoseeyouverysoon！”变为“^”、“Hope”、“to”、“see”、“you”、“very”、“soon”、“！”；对于所述序列中的每一词条(及其各自的语境)，所述动态语言模型将n元语法模型路径加入到所述动态n元语法模型图中，构成不同的语境长度，从空语境词条到n-1个语境词条。其中，n为所述语言模型的最高n元语法模型阶次。举例说明上述情况，假n＝4，加入下列路径：

“^”

“Hope”

“^”“Hope”

“to”

“Hope”“to”

“^”“Hope”“to”

“see”

“to”“see”

“Hope”“to”“see”

“^”“Hope”“to”“see”

“you”

“see”“you”

“to”“see”“you”

“Hope”“to”“see”“you”

“^”“Hope”“to”“see”“you”

“very”

‘you”“very”

“see”“you”“very”

“to”“see”“you”“very”

“soon”

“very”“soon”

‘you”“very”“soon”

“see”“you”“very”“soon”

“！”

“soon”“！”

“very”“soon”“！”

“you”“very”“soon”“！”

对于每条n元语法模型路径，所述动态语言模型7将相应节点的频率值加1，同时还将相应节点所属父节点上的频率总值加1。如果一给定词条未存在于所述动态语言模型的词汇表中，则由所述语言模型将该词条加入其词汇表并为该词条分配新标识符。

本发明还涉及一种用户界面。特别涉及一种触摸屏式用户界面。可通过该界面来操作本发明系统。图8示出了普通用户界面。图8a示出了可供选择的普通用户界面。如图8所示，基本用户界面包括打字屏面23，可位于所述界面中央的文本预测屏面25，以及位于所述文本预测屏面25两侧的两个相同的、用于单/多字符、标点或符号输入的侧屏面24、26。在一可选实施例中，如图8a所示，所述基本用户界面包括打字屏面27、预测屏面28以及用于单/多字符、标点或符号输入的单屏面29。所述预测屏面28优选地包括实际字符输入按钮38，最可能单词按钮48以及可选单词按钮58。

在如图8示出的实施例中，所述预测屏面25包括一组按钮，每个按钮显示一来自于由文本预测引擎预测出的单词或短语集合的单词。所述打字屏面23包括一可以显示用户输入文本的屏面。所述侧屏面24、26包括一组与字符、标点或数字按键对应的按钮。在默认设置屏幕的情况下，所述侧屏面24、26包括字符按钮。然而，在其他配置条件下，屏面24、25、26全部用作字符、标点和数字按钮，而且可切换所述屏幕以使用户能够在预测、数字和标点屏幕之间往来。

上述实施例中两种用户界面的区别点在于预测屏面25、28。在可选实施例中，所述预测屏面28包括能使用户输入他们实际录入所述系统的字符序列(并非向系统中输入由系统的文本预测引擎预测出的词条)的实际字符输入按钮38。这一特点能够使用户输入那些并非由系统识别出的、因此也不是由所述系统预测出的单词。所述预测屏面28还包括用于显示由文本预测引擎预测出的单词或短语集合中具有最大概率的单词的最可能单词按钮48，所述预测屏面28还包括用于显示除最大概率词条之外的其他单词的可选单词按钮58(即具有第二高概率的单词)点击所述按钮48或58将输入相关的词条。

在用户界面的这两个实施例中，所述打字屏面23显示由用户输入的文本。用户可以向上或向下滚动显示于所述打字屏面上的在先输入文本，以便用户查看和编辑所述文本。所述打字屏面还包括可移动的、以帮助编辑输入文本的光标。

设置用户界面，以便在点击预测屏面25、28上的文本按钮时，使被选中的文本呈现在所述打字屏面23、27上。将已更新的、包括选中文本及选中文本在先语境的输入序列传递给所述文本预测引擎，以生成新的预测。优选地，在图8a示出的实施例中，用户可通过点击最可能单词按钮48或输入空格来输入最可能单词。

在图8示出的实施例中，在按住文本按钮(一定时间)或对于由左至右的手势进行响应时，将除问题词条之外的当前输入序列传递给所述文本预测引擎，并将当前输入序列中的无问题词条显示在打字屏面上。这时的文本并不是完整的(即每个词条后面并没有自动输入空格)，但是可将字母作为用于进一步预测的输入。例如，如果按住单词‘not’，则所述文本预测引擎生成包括诸如‘note’、‘nothing’等单词的单词预测9列表。将该列表提供给所述用户界面以供显示和在所述预测屏面25中选择。如果语言模型预测出了标点，则标点项会呈现在与预测出的单词或短语在所述预测屏面25底部相同的位置上，由此保证用户使用的一致性。在图8a示出的可选的用户界面中，当前输入序列实时显示在所述打字屏面27上。所述实际字符输入按钮38同样显示所述当前输入序列，并将所述当前输入序列显示在所述最可能单词按钮48和可选单词按钮58的旁边。如果用户想要选择已输入的所述当前输入序列，而非预测词条，则用户可点击实际字符输入按钮38输入作为已完成单词的所述当前输入序列。

图8示出的用户界面可以用于输入多词条(短语)。下面，以预测短语“andthe”为例，讨论双词条短语输入。在所述预测屏面25中部，包含词条“and”的按钮在包含词条“the”的按钮左侧紧邻该包含词条“the”的按钮。如果用户选择了词条“the”，则输入序列“andthe”输入。然而，如果用户选择了词条“and”，则仅输入词条“and”。同样的原理可以应用于任意长度短语的预测中。所述同样的原理可以应用于图8a示出的用户界面，其中所述最可能单词按钮48可以用来显示短语输入。例如，如果最可能预测为具有两个以上词条的短语，并且所述可选单词按钮58可以显示下一条最可能短语预测，则可将所述最可能单词按钮48分成两个以上按钮。

字符按钮可显示于两个侧屏面24、26或者单主屏面29。所述字符按钮可以具有二元或三元字符行为。这意味着，会出现两个或三个字符同时提交给预测器(即文本预测引擎)的情况(例如，如果点击‘A|B’按钮，则同时提交了‘A’和‘B’)。在一个实施例中，在默认设置的屏幕上，上述情形是一种默认的行为。将双字符按钮设计有多区域行为。例如，点击‘A|B’按钮的左侧将输入‘A’；点击‘A|B’按钮的中部将输入‘A’和‘B’；点击‘A|B’按钮的右侧将输入‘B’(这种组合能够获得更大、更容易使用的多字符按键，与此同时，允许经验丰富的用户从单字符输入中获得准确度更高的预测)。在一个实施例中，在默认设置的屏幕上，上述情形为一种可选的行为。在需要毫无迟疑地输入字符时(例如，输入一个未列入语言模型词汇表中的新词条)，可以使用多字符按钮。在一个需要毫无迟疑地输入字符的实施例中，用户点击切换按钮进入数字/标点屏幕，其中所有的按钮都是多字符按钮。

所有数字或标点按钮都是多字符按钮。以三字符按钮为例，用户点击一次该按钮可以输入(三字符按钮中的)第一项，点击两次该按钮可以输入第二项，或者点击三次该按钮以输入第三项。

所述用户界面还包括下面全部或其中一个附加技术特征：用于切换预测屏面、数字和标点屏面以及标点屏面的菜单按钮；用于文本换行的回车按钮；用于在被单击时输入空格或在被按住时不停输入空格的空格按钮；用于在被单击时删除单个字符或在被按住时不停删除字符或词条的删除按钮；用于切换“Abc”(仅首字母为大写字母)、“ABC”(所有字母都是大写字母)和“abc”(所有字母都是小写字母)的大写按钮；以及用于向诸如电子邮件程序(针对于电子邮件应用)发送输入文本的发送按钮。

此外，所述用户界面还包括撤销按钮，或者所述用户界面能够对在删除按钮上做出的“撤销”手势(例如，在删除按钮上从左至右的动作)进行响应。对于所述手势或者按钮点击动作的响应，所述用户界面会撤销在先词条选择，并使用户返回至先前的词条选择位置。

例如，如果用户通过字符输入，输入了‘us’，则将会基于这一输入为用户呈现出词条预测选择。假设用户意外选择了词条“usually”而非想要的词条“useful”，那么所述撤销手势允许用户撤销先前的词条选择，并返回初始基于‘us’的词条预测。由此可使用户选择‘useful’。这一撤销过程可将用户从不停地点击删除按钮以删掉意外输入的非正确词条选择中解放出来。

所述系统包括序列首字母自动大写功能。然而，在“ABC”、“Abc”和“abc”之间进行切换意味着语言模型仅能预测适当形式的词条，即如果大写切换键设置为“Abc”，则所述文本预测引擎将按照下列诸如‘Jon’、‘Ben’、‘Cambridge’等大写格式来检索词条。

以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。

Claims

1.一种电子设备的文本输入系统，包括：

用户界面，用于接收由用户输入的文本；

具有多个语言模型的文本预测引擎，用于接收来自于所述用户界面的文本，并利用所述语言模型同时生成文本预测；

其中，所述文本预测引擎还用于向所述用户界面提供文本预测，以供显示和用户选择；

其中，所述多个语言模型包括：人类语言模型，以及应用程序专用语言模型、公司专用语言模型、用户组专用语言模型和用户专用语言模型中的至少一个。

2.根据权利要求1所述的系统，其特征在于，从所述多个语言模型中实时生成所述文本预测。

3.根据权利要求1所述的系统，其特征在于，所述应用程序专用语言模型至少为以下之一：

电子邮件专用语言模型，短信息专用语言模型，新闻电讯专用语言模型，学术专用语言模型，博客专用语言模型，产品评测专用语言模型。

4.根据权利要求1所述的系统，其特征在于，所述应用程序专用语言模型包括电子邮件专用语言模型和短信息专用语言模型，由电子邮件专用语言模型和短信息专用语言模型或者两者之一生成所述文本预测。

5.根据权利要求1所述的系统，其特征在于，所述多个语言模型包括至少一个附加语言模型。

6.根据权利要求5所述的系统，其特征在于，所述附加语言模型包括用户组专用语言模型。

7.根据权利要求1至6中任意一项所述的系统，其特征在于，还包括：

比较机构，用于将存储在语言模型中的词条序列与存储在一个或多个其他语言模型中的词条序列进行比较，以删除重复的或多次输入的词条，仅保留概率最高的重复或多次输入的词条。

8.根据权利要求1所述的系统，其特征在于，所述多个语言模型包括基于n元语法语言模型的用户专用语言模型，通过更新n元语法语言模型，在n元语法模型图中记录下由用户输入的n元语法模型路径出现的频率。

9.根据权利要求8所述的系统，其特征在于，所述用户专用语言模型用于响应未在其中出现的文本输入，以便向所述多个语言模型内的所述n元语法模型图中插入新路径。

10.根据权利要求1所述的系统，其特征在于，所述文本预测引擎包括：合并机构，用于合并由各个语言模型生成的文本预测。

11.根据权利要求10所述的系统，其特征在于，所述合并机构用于将所述文本预测插入到有序相联结构或标准模板库多重映射结构中，并返回最可能词条作为文本预测提供给所述用户界面。

12.根据权利要求1所述的系统，其特征在于，在缺少任何文本输入和/或在句子结尾输入标点之后和/或在换行之后，所述多个语言模型利用序列起始标识确定词条或短语预测。

13.根据权利要求1所述的系统，其特征在于，所述多个语言模型使用近似单词查找树和n元语法模型图；其中，所述近似单词查找树是标准单词查找树的扩展，在其每个节点上存储有一组用于表示各个节点之后的允许字符序列的数值。

14.根据权利要求1所述的系统，其特征在于，所述多个语言模型使用概率单词查找树和n元语法模型图；其中，所述概率单词查找树是标准单词查找树的扩展，在其每个节点上存储有一组用于表示各个节点之后的允许字符序列的数值。

15.根据权利要求13所述的系统，其特征在于，所述多个语言模型用于检索所述n元语法模型图，以根据在前文本输入的n-1个词条确定下一个词条的单词或短语预测。

16.根据权利要求14所述的系统，其特征在于，所述多个语言模型用于检索所述n元语法模型图，以根据在前文本输入的n-1个词条确定下一个词条的单词或短语预测。

17.根据权利要求13所述的系统，其特征在于，所述多个语言模型用于检索所述近似单词查找树，以根据至少一个输入字符确定单词预测。

18.根据权利要求14所述的系统，其特征在于，所述多个语言模型用于检索所述概率单词查找树，以根据至少一个输入字符确定单词预测。

19.根据权利要求17所述的系统，其特征在于，包括近似单词查找树的所述多个语言模型具有候选词过滤器，以缩小由所述近似单词查找树确定的单词预测的范围；所述候选词过滤器用于丢弃所有当前输入为非其子字符串的候选字符串。

20.根据权利要求15所述的系统，其特征在于，所述多个语言模型包括：

计算机构，用于通过检索由所述近似单词查找树确定的单词预测集合以及由n元语法模型图确定的单词预测集合，并仅保留存在于这两个单词预测集合中的相同标识符，计算出这两个单词预测集合之间的交集。

21.根据权利要求16所述的系统，其特征在于，所述多个语言模型包括：

计算机构，用于通过检索由所述概率单词查找树确定的单词预测集合以及由n元语法模型图确定的单词预测集合，并仅保留存在于这两个单词预测集合中的相同标识符，计算出这两个单词预测集合之间的交集。

22.根据权利要求20或21所述的系统，其特征在于，所述多个语言模型还包括：

具有n+1元语法模型图的布隆过滤器，用于检索所述n+1元语法模型图，并根据下列语境之一返回新的预测集合；

用于检索所述n元语法模型图的在先文本输入的n-1个词条的语境；

已确定的所述交集中预测词条的语境；以及

在用于检索所述n元语法模型图的n-1个词条之前的额外词条的语境。

23.根据权利要求22所述的系统，其特征在于，所述多个语言模型还包括：

主题过滤器，用于预测当前输入文本的主题分类，预测所述预测集合中词条的主题分类，以及根据主题分类的预测调整所述预测集合中的预测的概率。

24.根据权利要求1所述的系统，其特征在于，所述用户界面是一种触摸屏式界面，包括：

单/多字符输入机构；

单词预测屏面；以及

用于显示已输入文本的打字屏面。

25.根据权利要求24所述的系统，其特征在于，所述单词预测屏面包括一个或多个显示预测单词的单词键；其中，所述用户界面在所述打字屏面上显示由点击所述单词键而输入的所述单词。

26.根据权利要求25所述的系统，其特征在于，还包括：

删除按钮和/或撤销按钮；其中，作为对于点击撤销按钮或在所述删除按钮上做出的从左至右的手势的响应，所述用户界面通过擦除所述打字屏面上的单词来撤销上一个单词选择，并回到之前的单词预测屏面。

27.根据权利要求24所述的系统，其特征在于，所述用户界面还包括：

菜单按钮，用于切换单词预测屏面、数字和标点屏面以及标点屏面。

28.根据权利要求24所述的系统，其特征在于，所述用户界面还包括：

发送按钮，用于向电子邮件程序发送输入的文本。

29.根据权利要求24所述的系统，其特征在于，所述用户界面用于输入依赖于给定单词序列中被选中的输入词条的单词或短语。

30.根据权利要求24所述的系统，其特征在于，所述单词预测屏面包括一个或多个用于显示预测单词的单词键；其中，所述用户界面在所述打字屏面上显示由点击所述单词键而输入的所述单词，并且将包含所述单词的当前输入序列作为语境输入传递给所述文本预测引擎。

31.根据权利要求24所述的系统，其特征在于，所述单词预测屏面包括一个或多个用于显示预测单词的单词键；其中，作为对于点击所述单词键以及在所述单词键上做出按压或由左至右的手势的响应，所述用户界面在所述打字屏面上显示所述单词，并且将不包含所述单词的当前输入序列作为语境输入传递给所述文本预测引擎，并且将所述单词的字符作为当前单词输入传递给所述文本预测引擎。

32.根据权利要求24所述的系统，其特征在于，所述用户界面还包括一个或多个显示标点符号的标点键，以及回车键；

其中，作为对于序列结尾标点或点击回车键的响应，所述用户界面将当前序列传递给所述文本预测引擎；

其中，所述文本预测引擎包括用于拆分当前序列并将拆分后的序列传递给所述用户专用语言模型的拆分机构；

其中，所述用户专用语言模型为拆分后的序列分配数字标识符，并更新其n元语法模型图。

33.一种用于处理用户文本输入并生成供用户选择的文本预测的方法，其特征在于，包括以下步骤：

接收输入至用户界面的文本；

同时使用具有多个语言模型的文本预测引擎从所述多个语言模型中生成文本预测；以及

将所述文本预测提供给所述用户界面，以供用户选择；

34.根据权利要求33所述的方法，其特征在于，所述多个语言模型包括n元语法模型图和近似单词查找树或概率单词查找树；所述方法还包括：

根据在先文本输入的n-1个词条检索所述n元语法模型图，以确定下一个词条的单词预测或短语预测。

35.根据权利要求33所述的方法，其特征在于，所述多个语言模型包括n元语法模型图和近似单词查找树或概率单词查找树；所述方法还包括：

根据至少一个已输入的字符检索所述近似单词查找树或所述概率单词查找树，以确定单词预测。

36.根据权利要求35所述的方法，其特征在于，所述多个语言模型包括近似单词查找树和候选词过滤器；所述方法还包括：

通过丢弃所有当前输入为非其子字符串的候选字符串，缩小由所述近似单词查找树确定的单词预测的范围。

37.根据权利要求34至36中任意一项所述的方法，其特征在于，所述多个语言模型包括：

计算机构，用于计算由所述近似单词查找树和所述概率单词查找树中的一种以及n元语法模型图所确定的两个单词预测的交集；所述方法还包括：

计算这两个所述单词预测的交集。

38.根据权利要求37所述的方法，其特征在于，所述计算机构检索并仅保留存在于这两个所述单词预测集合中的相同标识符。

39.根据权利要求37所述的方法，其特征在于，所述多个语言模型包括具有n+1元语法模型图的布隆过滤器；所述方法还包括：

根据下列语境返回一个新的预测集合；

已确定的所述交集中预测词条的语境；以及

40.根据权利要求38所述的方法，其特征在于，所述多个语言模型包括具有n+1元语法模型图的布隆过滤器；所述方法还包括：

根据下列语境返回一个新的预测集合；

已确定的所述交集中预测词条的语境；以及

41.根据权利要求39所述的方法，其特征在于，所述多个语言模型还包括主题过滤器；所述方法还包括：

预测当前输入文本的主题分类，预测所述预测集合中词条的主题分类，以及根据所述主题分类的预测调整所述预测集合中的预测的概率。

42.根据权利要求33所述的方法，其特征在于，所述多个语言模型包括基于n元语法语言模型的用户专用语言模型；所述方法还包括：

更新在n元语法模型图中由用户输入的n元语法模型路径出现的频率。

43.根据权利要求42所述的方法，其特征在于，为了响应未在所述多个语言模型中出现的文本输入，所述方法还包括：

向所述n元语法模型内插入新路径的步骤。

44.根据权利要求33所述的方法，其特征在于，所述文本预测引擎包括：

合并机构，用于合并由所述多个语言模型生成的预测：所述方法还包括：

合并所述预测。

45.根据权利要求44所述的方法，其特征在于，所述合并预测的步骤包括：

将所述预测插入到有序相联结构或标准模板库多重映射结构中，并返回最可能词条提供给所述用户界面。