CN1194391A - 具有键多义性的文本输入设备和方法 - Google Patents

Abstract

一种用于输入文本的数据输入方法和装置,其中存在键多义性并需得到解决。数据输入设备的小键盘的键被激活,其中一个键表示多个字符,以提供输入数字流。数字流的列表被保存,该表表示所需语言的字符和对应于该数字流的字符地址。搜索列表以找到对应于输入数字流的数字流并获得一个相应的字符地址。另一方面,存储字符和字符有序排序的字符的相对地址的表,并且字符的相对地址依据所选择的字符被重新排列。

Description

具有键多义性的文本输入设备和方法

本发明一般涉及一种数据输入方法和设备，尤其涉及一种用于从输入设备如小键盘，特别是从存在键多义性并且需要解决的数字小键盘上输入文本，例如文本信息的方法和装置。

随着要求携带越来越小的具有优化功能的个人通信设备，如，寻呼机，蜂窝式电话，和其它个人通信设备需求的增加，及要求通过远程通信和电缆的连接使得家庭自动化的需求的增加，其中一个小房间将有一个或更多个能够执行各种应用程序或控制各种应用程序的小型设备；要求从非字母小键盘或从数字小键盘输入字母数字文本的需求也不断地增加。

在美利坚合众国，对于每个电话小键盘，键盘上显示出数字和字母是一项标准。因此，表示数字＂2 ＂的键上显示有A，B，和C并且表示字母＂3＂的键上显示有D，E，和F等。由对应于小键盘上数字的字母来表示电话号码是很普遍的。因此，例如，名称为＂Amtrack＂的铁道公司可有一电话号码2687225并且该公司可告知客户该公司电话号码可通过激活有字母A-M-T-R-A-C-K的键来拨打。拨打这些字母将只产生一个数字序列，但是一个数字序列可由多个字母序列表示。

在远程通信领域，对于使用数字小键盘的人来讲用名称选择的方法是众所周知的。例如，众所周知，在一个语音邮件系统中通过从远程电话键入用户名的头几个字母来选择用户的语音信箱，作为结果，一个短数字流被发送到此语音邮件系统。此语音邮件系统把所输入的数字流同查找表中的有限选项集作比较。必须输入足够的数字以唯一的标识所期望的用户。类似地，自动客户服务系统可使用这种文本输入格式。例如，一个航空公司信息系统能够请求目的地机场的头三个字母，尽管存在由所传送的数字所表示的字母的多义性，还是能够仅由这三个字母来唯一地标识机场，这是因为它有一个用于搜寻匹配的机场名的限“字典”。同样的方法可用于电话快速拨号查找方案中。可从存储在电话终端的受限名字列表中选择一个名字并且拨打与所选名字相关联的号码。

各种其它的用于从非字母小键盘、只有数字的小键盘、或其它类型的比相应字母少的多的键或按钮的小键盘输入字母数字输入的方法已经被发展起来或已经被周知。这些方法中多数受益于在标准US电话小键盘上所显示的字母。但是，与小键盘的字母数字文本相关的方法常常很麻烦而且难以编辑。另外，一般，必须限制输入或者以一种特定的方式输入从而使得每一输入序列只有一个选项。更具体地来讲，特定的输入同字母表中特定的字母或符号有着直接的联系。例如，如果一个用户想要从非字母小键盘输入单词＂call＂，则用户必须输入一特定的数字和/或符号的组合以表示单词“call”。在用户要输入单词“call”的例子中，该用户必须如下输入：2***；2*；5***；5***；#。这样一种输入的方法是非常受限的，费时的，并且编辑困难且慢。

以上所描述的数据输入的方法并不适合于中文。中文中有几千个字符。例如，由在中国的GB编码标准所支持的汉字就有近7000个，而且在台湾和香港由BIG5编码标准所支持的汉字约有13000个。对于建立一个能从如此巨大的字典中使用少数键例如只是一个有12个键的电子小键盘来选择字符的设备来讲，如此多的汉字是主要的挑战。

因此，需要提供给用户一个简单直接的用于从具有比所需字母少的键的小键盘上输入文本的方法和设备；并且需要提供一种不需借助于很大的计算能力或存储要求的系统。

现在通过示例的方式，参照附图来描述本发明的各种较好的实施方式。

图1是一个说明依据本发明适合于接收输入的文本输入设备的前视图。

图2是一个详细描述图1中设备的内部电路的框图。

图3是一个说明存储在图2的存储器设备中的一级列表的数据结构图，其中该表中存储了地址信息。

图4是一个说明存储在图2的存储器设备中的二级列表的数据结构图，其中该表中存储了字符信息。

图5是一个说明存储在图2中设备的存储器中的三级列表的数据结构图，其中该表中存储了双字组信息。

图6是一个说明图2中处理器操作的流程图。

图7是一个详细描述图6中用于查找数据流ID的子程序100的流程图。

图8是一个详细描述图6中用于选择字符的子程序400的流程图。

图9是一个用于查找单字组和双字组共用的汉字的流程图。

一般地，现在所描述的方法包括以下步骤在存储器中保存一张一级列表，该表保存的是以所希望的语言表示的数字流或数字序列及对应于数字流的字符地址；激活数据输入设备(例如一个小键盘，但也可为一键盘或一查寻数字化装置和输入笔)的键，其中一个键可表示多个用于提供输入数字流的字符；搜寻存储器中的一级列表以查找对应于输入数字流的数字流并获得相应的字符地址。在这里，＂字符＂一般指字母或象形文字或语义符字符。

从十九世纪五十年代中期开始，一种汉字的标准语音表示方式被作为＂拼音＂接受了下来。每一个汉字的拼音，像每一英语单词一样，由罗马字母a-z的26个字母混合而成。这26个字母可映射到电话小键盘或其它的例如只有12个键的小键盘上，其中每一键上显示有3-4个字母。假设有适当的方法来解决多义性问题，这种小键盘可被用于利用拼音的书写系统来输入中文文本。现在描述这样一种方法。

现在参考附图，图1说明了一种根据本发明的装置的一般且优选的实施方式。一个有小键盘的蜂窝式电话(或其它数据输入设备如无线电话，寻呼机或个人数字辅助设备或远程通信设备)的例子一般由参考数字10描述。所描述的蜂窝式电话10包括外壳12，显示器14和用于接受输入的小键盘16。显示器14有一文本显示区15和一用于显示可选择字符的区域17。小键盘16有12个以标准格式显示数字0-9的键，而且拼音字母a-z也以标准格式显示。这些字母可以其它方式排列，例如为求得更高的人机工程效率，但是如果考虑所建立的用途则所说明的格式是较好的。表示数字＂1＂的键上显示有标点＂，＂，＂。＂，＂？＂和＂！＂。该键左下方的键18上显示有符号＂《＂(如下面所说明的，表示＂回退键＂或＂向左滚动键＂)及“*”(表示“星”)。该键右下方的键19上显示有符号＂》＂(如下面所说明的，表示＂回车键＂或＂向右滚动键＂)和＂#＂(表示＂击打＂)。

作为一种可选的小键盘输出格式，数字0-7可分别表示<prs>，<tuv>，<wxy>，<qz>或数字7-9和数字1可分别表示<prs>，<tuv>，<wxy>，<qz>。

在所提及的实施方式中，用到了拼音表。可选的是，根据本发明所提及的实施方式可用多种其它的字母表，如另一种中文语音字母表(注音)或基于笔画的字母表或英语、俄语或亚洲语字母表。在附图中所说明的本发明所提及的一种实施方式中，输入设备为具有字母数比字母表中的字母数少的单独键的小键盘。因此，字母表被分成多个序列，其中一个单独的数字和一系列的字母或符号表示在一个单独的键上，或小键盘或其它输入设备的输入块上。按下一个键会输送一个数字，但是该数字可表示一个字母或字符。

参照图2，蜂窝式电话被描述为具有一个微处理器30，该微处理器利用技术上周知的标准的输入和输出驱动器连接到输入板16和显示器14上。还可连接到该微处理器30上的为一个一级存储器31和一个二级存储器32，其中一级存储器最好是电可擦性只读存储器(EEPRM)或闪速存储器，二级存储器最好是有序存取存储器(RAM)。在EEPR0M存储器中至少存有三个表一表一(33)，表二(34)，表三(35)。相应地分别参照图3，4和5，更详细地描述了表33-35。一个可选的扬声器38被连接到该微处理器上。

参看附图3，图中显示了图2的表1的数据，该表包括存储了对应于所有可能汉字的可能的拼音的数字串的第一列101。对应于408个可能的拼音存在219个可能的数字串(序列)。(一个数字串可能对应几个拼音，因为三个或四个罗马字母映射到一个电话数字上)。多种可能的拼音对应于几千个字符。第一列的宽度为4个字节。图中第一列101的左边为每一个数字串的标识号(ID)。该号并不存储在存储器中。数字串以它们值的顺序存储，即，值越小，其索引越小。第二列102的宽度为2个字节并且存储有具有相同数字串的汉字的起始地址(在表二中)(有相同的数字串的汉字总数可由第二列的相邻二个项间的差来得到；例如第一个项和第二个项之间的差(7-1＝6)表示有6个汉字有相同的数字串2)。第二列102的右边显示了映射到相应数字串上的拼音。

为了定位对于可能对应于一给定数字串的所有实际上的汉字在表2中的开始(和结束)地址，用到了表1，这在后面将会更详细地描述。

图4中显示了表2并且表2包括四列110-113。在第一列中显示了字符(每项2个字节)的十六进制GB编码表示。对于字典中的每个汉字，表中都有一条记录。图中该表的左边显示了当其被书写时或在显示器14的文本显示区15和较下方的显示区17中出现时实际上的汉字图形。这种表示方式不需存储在表2中(但是可存在表2中)。有相同数字串的汉字被顺序存储在字典中，然后依据十六进制编码值被排序，即，其值越小，其索引越小。图的最左边(但是并不存在存储器中)所显示的为表示具有相同数字流的每一汉字组中汉字的相对地址的索引。第二列111存储了具有相同数字串的每一字符的单字组索引相对地址(每项1个字节)。它根据与其相应的汉字的频率(单字组)排序。即，频率越高，其索引越小。频率被显示在图4的右方，但是并未存在存储器中。第三列112(每一项3个字节)存储了具有同一首字符的两字组在表3中的开始地址。第四列存储了表3中具有同一首字符的两字组数。

为了说明，图4的1到6行左边表示具有同一数字串＂2＂的汉字的相对地址，并且同一列的7到9行表示具有同一数字串＂3＂的汉字的相对地址。

列111表示每组中以其频率次序排序的汉字的相对地址。例如，在第一组中(1到6行)，第二行的频率最高(频率＝11574)，因此其相应汉字的相对地址＂2＂被存在第一位(参看第一行，列111)。第三列112和第四列113分别表示表3中的开始地址和表3中具有同一首字符的两字组的数目。

现在参看图5，图5中显示了存储有汉字两字组数据的表3。两字组为两个字符的组合，该两字组是由所讨论的语言中该组合所出现的频率标识的。例如两字组＂qu＂在英语中很普遍而两字组＂qa＂就很罕见。这一信息被用来识别相似的和不相似的字符组合，字符组合反过来被用于解决数据输入中的多义性问题。

在图5中，第一列和第二列表示两字组的汉字对的列表(用中文和＂十六进制＂GB编码格式并由＂：＂分隔开来)。第三列表示这两个汉字同时出现的频率。第四列表示在汉字对中第二个汉字的数字串。这四列并不存在存储器中。图5中的第5列160和第六列161作为表35存在存储器中。

列160包括表示表1中数字流位置的相应的数字串ID。例如，在第三行上，数字串＂22＂的ID为＂4＂。列161包括表2的汉字字典中第二个汉字的相对地址。

选取具有同一首字符＂b0a2＂的组作为示例，列160按其项(element)值排序(数字串ID)。如果列160中连续的项具有同一数字串ID，则它们在列161中的相应项以其在列160中同时出现的频率排序。由此看来，数字流ID-相对地址对可唯一地定位存储在表2的汉字字典中的汉字。

在每一具有同一两字组首字符的组中，各组均首先依据数字ID排序，然后依据两字组概率排序。

在表2和表3中并不存储频率数据。而是，频率由表2中列111的索引相对地址所表示的单字组和由表3中列160和161的索引数字流ID-相对地址对所表示的两字组的存储顺序来标识。这是一种存储该扩展数据的有效方式。

已介绍过数据输入设备的结构和存储器中的表结构。现在描述设备的操作。

在标准数据输入模式中，用户通过使用标有a，b，c，d等的电话键来输入每一个他想要输入的汉字的拼音，同样的方式也描述在美国专利申请No.08/754,453中，该申请于11/21/96递交，并转让给了本申请的受让人，该专利在此被作为参考文献。

用户输入拼音字母到小键盘16并且这些字母被送到微处理器30。微处理器担负有识别由拼音输入所表示的一组可能的字符和从一组可能的字符中识别最可能的候选字符的任务。这一处理过程在图6中说明。

从步骤200开始，用户在步骤210中输入数字串并且所输入的数字串首先在步骤210中通过使用一种快速二叉搜索方法在第一级表33(图3所示的表1)中搜索。由于数字按其项值顺序被排序并且对于基于拼音的方法只有219个项，因此只需8次匹配。这是一种识别所输入数字流的快速有效的方法。步骤210的细节在下面将参照图7被描述。

继续参看图6，对于一个新数字流的输入，该处理在步骤215中判定这一新的数字流输入是否标识先前所输入的数字流正是用户所选择的字符，如果是这样，则该处理得出结论：单字组和两字组模式的匹配作为该用户选择的结果是合适的。该匹配在步骤211和212中完成并且将在下面描述。

如果不存在语言模式的匹配，则该处理跳转到步骤311。这种情况是，例如，先前所输入的数字流的输入不正确且已被删除并且不应该被用于匹配。为了说明的简明性，现在将描述这种情况。

把数字串ID作为索引，微处理器30从二级表34(图4中所示的表2)中查找具有相同数字串的汉字的起始地址和数目。在步骤311中，候选汉字的初始列表从表2中读出。通过使用在步骤210中所获得的地址和数目，所有具有相同数字串的候选汉字可从表2中所描述的汉字字典数组中找到。它们组成了候选汉字的初始列。

紧接着步骤311，步骤312使得两字组的列表从图5的表3中读得。通过使用已被用户选中的先前的字符，处理器30从表2的列112和113中找到具有同一首字符的两字组的起始地址和数目。然后该处理器从表3中所描述的两字组数组中定位所有具有相同的首字符的两字组。

由于两字组在每一具有相同首字符的组中按数字串ID的顺序进行排序，因此处理器可在步骤313中利用快速二叉搜索法来查找对应于由用户所输入的数字串的实际上的数字ID。由于有相同数字ID的两字组也以两字组概率的顺序依次存储，因此通过在两字组的第一数组中搜索相邻项可很容易地找到其它有相同数字ID的两字组。一旦找到所有具有相同数字ID的项，则处理器30还从两字组的第二数组中找到有相同数字ID的字符的相对地址。

在步骤314中创建了候选汉字的最终列表。通过使用在步骤313中所获得的相对地址(依据两字组概率存储)，处理器30从在步骤311中所获得的候选汉字列表中获得字符并且把它们放在最终候选汉字列表的前端。由于表2存储了依频率(单字组)排序的字符的相对地址，因此它可被用来从初始候选列表中获取其它的汉字并把它们放入最终列表中。然后该处理器在显示器14的显示区17中按照最终候选列表的顺序显示汉字。

至此，已描述了一种把文本输入到设备的方法，该方法包括以下步骤：在存储器中保存一个用所需要的语言表示的字符的数字流和对应于该数字流的字符地址的一级列表；在内存中保存位于对应于一级表中的字符地址的地址处字符的二级表；激活数据输入设备的键，其中一个键表示多个字符以提供输入字符流；在存储器中搜索一级表以找到对应于输入数字流的数字流并获得一个相应的字符地址；并从二级表中至少读取一个位于此字符地址上的字符。已描述了搜索步骤如何执行二叉搜索及读取步骤如何从位于相对于字符地址的预定位置处的二级表查找多个分类有序字符。而且还描述了如何利用语言模式数据(如两字组和单字组数据)来解决多个字符的字符间的多义性。

接下来是一种选择字符并在存储器中依据所选字符重排字符的相对地址的软件的描述和方法。现在将要描述对应于同一数字流的字符标识如何被存储在多个连续的地址上及以最佳方式有序排序的字符的相对地址如何存储在连续的地址上，而并不依赖于相对地址所被存储的连续地址。

语言模式的匹配为快速在线匹配。图6的步骤211通过对存储在表2的列111中数据的操作来完成单字组模式的匹配，并且步骤212通过对存储在表3的列161中数据的操作来完成两字组模式的匹配。

参看这些匹配步骤的开始处，前面已描述过，表2的第二列111中存储了具有相同数字串的每一字符的相对地址。它按每一汉字的频率(单字组)排序。步骤211完成把上次所选择字符的相对地址放置在列111的最前位置114处并把该相对地址从其在列中的先前位置处移走的操作。随着地址被移走，有相同位流的字符的相对地址(在位置115处)在列111中被向下移动。

该过程是一个总是把上次所选的字符放置在可选列表顶端的过程。表2中字符的存储顺序是不变的，但是相对地址的存储顺序改变了。如果这样，则真正的频率信息就丢失了，但是该排列的实用性却增强了，因为对于用户来说最近使用的字符信息被保留了(真正的频率数据表示被所有的用户所用的历史频率)。

例如，假设对应于一个数字串有三个汉字A，B和C。它们的值和概率有如下关系：B＜A＜C和Prob{A}＞Prob{B}＞Prob{C}。这三个汉字在字典中以其值的顺序被存储：

1    B    2

2    A    1

3    C    3在该表中，第一列表示它们的相对地址(并不存储在存储器中)，第二列(表2的列110)表示存储在字典中的这三个汉字，第三列为表2的列111，其中以其概率顺序存储了这三个字符的相对地址。当用户输入对应于这三个字符的数字串时，则设备将会以ABC的顺序显示它们，因为字符A的相对地址存储在字符B的相对地址之前，且字符B的相对地址存储在C的相对地址之前。如果用户选择了字符C作为他想要输入的字符，则只需修改第三列

1    B    3

2    A    2

3    C    1因此下次，当用户输入相同的数字串时，则系统将以CAB的顺序把这三个字符显示给用户，因为现在字符C的相对地址存储在A的相对地址之前并且字符A的相对地址存储在B的相对地址之前。

也假设表112和113中的字符被重新排列并假设相对地址数据为用于互相参照而被保存，因为表2为完整字符字典且为了定位实际上的字符必须保存信息。则代替保持表2中字符的存储的顺序不变并改变相对地址的存储顺序，字符的存储顺序可重新排列，

步骤212中的匹配两字组的过程与步骤211中匹配单字组的过程相似。而且，当在两字组中对应于一数字串并具有同一个前面字符D有三个汉字A，B，C时也可考虑这个例子。它们的两字组概率有如下关系：

Prob{D，A}＞Prob{D，B}＞Prob{D，C}。它们以

4    2    A

4    1    B

4    3    C的顺序存储在两字组中。第一列(表3的列160)的第一行到第三行表示汉字A，B，和C各自的数字串ID，在此我们假设汉字A，B和C有同一数字串ID＂4＂。第二列(表3的列161)以其两字组概率的顺序表示它们各自的相对地址。第三列的项为由其相应的数字ID-相对地址对所表示的中文两字组字符对中的第二个汉字。当用户输入有数字串ID＂4＂的数字串＂22＂时，系统将会以ABC的顺序把这些字符显示给用户，因为字符A的相对地址存储在B的相对地址之前，且字符B的相对地址存储在C的相对地址之前。如果用户选择了字符C作为他想要输入的字符，则只需修改第二列

4    3    C

4    2    A

4    1    B因此下次，当用户输入相同的数字串时，则系统将以CAB的顺序把这些字符显示给用户，因为现在字符C的相对地址存储在A的相对地址之前并且字符A的相对地址存储在B的相对地址之前。

在这一语言模式的匹配中，两字组比单字组具有更高的优先权。如果由用户所选择的汉字可在其两字组中找到，则只需修改其两字组。否则，需修改其单字组。

为了完全描述，现在描述图6的步骤210和400的细节。

参照图7，所显示的流程图以一种更详细的方式描述了在步骤210中所执行的查找数字流ID的处理过程。这一过程在步骤700中以数字输入开始。当已经输入了一个完整字符的数字后，用户按下键19(图1)并且步骤701识别键＂#＂的输入。当要删除一个数字时，用户按下键18且步骤702识别键＂*＂的输入并在步骤703中删除上一个数字。对于每一个数字输入，该过程返回循环704，直至按下了键19。

按下键19后，该处理执行步骤710，该步骤表示用于单一字符的拼音输入的结束并开始字符的识别。在步骤711中对表1执行快速二叉搜索以定位所输入的字符。如果该搜索没有发现与所输入数字流的匹配则步骤712使得处理过程向前执行步骤720并从扬声器28(图2)或由其它指示器给出一个＂蜂鸣＂或其它的错误信号。如果步骤711成功地找到了一个匹配，则步骤715使得该处理过程向前执行图6的步骤215。

参照图8，步骤400(图6)的子程序在显示器14的显示区17中显示匹配所输入数字流的候选字符的头十个(或少些)。用户在步骤801中按下一个键。

如果用户在列表中没有看到他想要输入的字符，则他可按下键19或键18并且步骤802和803将会相应地使得步骤803和805显示它们相应的下十个或前十个字符。

如果键19和18均未被按下(即指在步骤801中按下了一个数字键)，步骤810使得对应于所输入的数字的字符被选中。例如如果所需字符被显示在列表中编号为1的位置处并且用户输入了＂1＂，则该字符被选中。所选字符为该设备的最终输出。所选字符被显示在显示器14的文本显示区15中并且被送到操作中的任一应用程序，例如被送到一个字处理程序。在步骤812程序返回到图6的步骤200处。现在程序将要利用所选择的字符在上面所描述的步骤211和212中修改单字组和两字组模式。

作为一种用于搜索两字组的可选方法，存在下述问题，即存储两字组需要大量的存储器。上述的两字组和两字组搜索方法是为一种特别的输入方法所设计的，即用于中国大陆的基于拼音的方法。然而，如果其它的输入方法如基于汉字笔画的方法，与基于拼音的方法共享两字组，则需以增加计算能力为代价给双方提供更通用的两字组和两字组搜索方法。

可选的两字组存储器只存储了两字组的第二个字符(每单位两个字节)。具有相同首字符的字符被连续地存储，然后如同对表2的列110中所存储汉字的处理一样，按其值进行排序。由于需要由两字组进行模型化的汉字不到8000个，因此存储一个汉字只需1 3位。其它3位可被用于给基于其两字组概率的两字组的第二个字符排序。

而且，假设对应于一个数字串并有同一首字符D的两字组中有三个汉字A，B和C。它们的值和两字组概率有以下关系：

B＞A＞C和

Prob{D，A}＞Prob{D，B}＞Prob{D，C}。它们以

C    5

A    7

B    6的顺序存储在两字组中。第一列表示存储在2字节存储器的前13位中的汉字，第二列表示存储在2字节存储器的后3位中的其两字组概率索引。因此存储一个两字组只需2字节存储器(16位)。

获得候选汉字的初始列表和刚才所述的两字组列表的过程同前面所描述的相同。由于这两个列表均按其项值的顺序被搜索，因此它们可彼此间相互比较以查找对于两个列表共同的汉字。

图9是一个用于查找两个列表共有的汉字的流程图。在该图中：u_list[M]和b_list[N]为相应的用于在初始列表和两字组列表中存储汉字的数组；M和N为这两个列表中各自的项的个数；并且chin_lists[N]为存储两个表共用的汉字的数组。

在图9中，步骤900为一初始化步骤。索引计数K1和K和n分别被置为1，1和0。在步骤901中，执行一匹配以决定单字组数组u_list[K1]中的项与两字组数组b_list[K2]中的项是否相同。如果项是相同的，则该处理执行分支910，接下来执行步骤911，步骤912设置数组chin_list[N]的首(或下一个)项与数组b_list[K2]的项相同。然后在步骤913中，单字组数组u_list[K1]的项被设置为0，实际上从单字组数组中删除了该项。在步骤914中增量索引计数K1和K2。

如果，步骤901中数组项不相等，则，步骤920，921和922使得这两个项中较小的索引计数被增量。以这种方式，步骤901可以以增值顺序完成所有项的比较，直到步骤930中两个列表的最后一个项已进行了比较。当比较结束时，步骤931以对于单字组和两字组相同的汉字的列表(chin_list[N])方式给出结果。

比较所需的最多次数为M+N-1，其中M和N为这两个列表中相应项的个数。然后，结果列表hin_list[N]中的汉字依据其两字组概率索引被重新排序并且被放置到最终候选汉字列表的前端。

利用上述的同一的例子，这三个汉字将会以A，B，C的顺序列出，因为A的索引(＝7)比B(＝6)的索引大，并全B的索引(＝6)比C(＝5)的索引大。

在匹配之前，两字组如下列出：

C    5

A    7

B    6如果用户选择了字符C作为他想要输入的字符，则只需修改第二列

C    7

A    6

B    5在匹配之后，C的索引被改为7，且A和B的索引相应地被改为6和5。

现在更描述一种用于产生字符两字组概率的新方法。

传统的用于产生汉字两字组概率的方法只是盲目地对在一个大的中文文本语言资料库中两个汉字同时出现的次数进行计数。然后两字组以同时出现的频率被排序。由于用于存储字符的存储单元的限制，系统只选择有最高同时出现频率的头N个两字组。

在这种新方法中，用以产生汉字两字组的过程被分成三步骤：汉字单字组和两字组的产生；产生汉字的词内(in-word)和词间(cross word)两字组；并且通过合并汉字的词内和词间两字组来产生汉字的最终两字组。

一个中文词有1至6个汉字组成。但是，多数中文词由两个汉字组成。例如，中文词＂人民＂包括两个汉字，＂人＂和＂民＂。一个包括60,000个中文词的中文词典被提供。用于产生语言模式的中文文本语言资料库中的中文句子首先利用中文词典被分解成中文词序列。然后计算词单字组(词出现的次数)和两字组(两个词同时出现的次数)。

中文词单字组首先被汉字字典中的汉字分段。然后两个汉字同时出现的次数被计数并被计算以得到汉字的词内两字组。对于一个60K的词典来说，大约有50K个汉字的词间两字组。显然，词间两字组包括中文词典中所有中文单词的大多数最重要的信息。

汉字的词间两字组仅通过计数第一个单词中的最后一个字符和第二个单词中的第一个字符同时出现的次数就可产生。实验证明所产生的汉字词内两字组的数目为1340K。但是，该列表在分类排序之后被截短了，使得只有出现频率最高的50K个词间两字组被选中以形成汉字的最终两字组列表。此词间两字组包括一些未被包括在中文词典中的新词的信息和一些通常只包括一个汉字的常用功能词的用法的信息。

在汉字的词内和词间两字组之间存在着一些重叠。因此通过合并汉字的词内和词间两字组而产生最终汉字两字组。

已描述了一种数据输入的方法，这种方法容许从有限键或其它输入设备上，如从一12个键的电话小键盘上，快速输入数据，并且对于用户和人机工程效果来讲这是自然的。键输入的多义性由语言建模解决了。本发明描述了用单字组和两字组语言模式，但是可用其它的模式。例如如果存储器可用或如果利用这些模式可取得更高的效率则可使用三表模式和n表模式。这种方法对于处理项是有效的并有一个有效的数据结构。这些特征可使得操作速度变快并且降低成本，从而使得这种方法可用于简单廉价的客户设备。在不超出本发明的精神和实质范围内本领域技术熟练人员可作种种修改。

Claims (12)

1.一种把文本输入具有键多义性设备的方法，包括步骤：

在存储器中保存一个用所需要的语言表示的字符的数字流和对应于该数字流的字符地址的一级列表；

激活数据输入设备的键以提供一个输入数字流，其中一个键表示多个字符；并且

搜索存储器中的一级列表以找到对应于输入数字流的数字流并获得相应的字符地址。

2.权利要求1所述的方法，其中搜索步骤包括执行二叉搜索。

3.一种把文本输入设备的方法，包括步骤：

在存储器中保存一个用所需要的语言表示的字符的数字流和对应于该数字流的字符地址的一级列表；

在存储器中保存一个位于对应于一级列表中字符地址的地址处的字符的二级列表；

激活小键盘上的键，其中一个键表示多个字符以提供输入数字流；

搜索存储器中的一级列表以找到一对应于输入数字流的数字流并获得相应的字符地址；并

从二级列表中至少读取一个位于字符地址上的字符。

4.权利要求3所述的方法，其中搜索步骤包括执行二叉搜索。

5.权利要求3所述的方法，其中读取步骤包括从二级列表中定位多个有序排列的字符，其中这些字符位于对应于字符地址的预定位置处。

6.权利要求5所述的方法，进一步骤包括了使用语言模式数据解决多个字符的字符间多义性的方法。

7.一种字符识别的方法，包括步骤：

在存储器中保存一个字符和字符的有序排列的相对地址的表；

选择一个字符；并

依据所选择的字符重新排列存储器中的字符的相对地址。

8.权利要求7所述的方法，其中保存步骤包括：

当从数据输入设备输入时，在多个连续地址上存储对应于共同数字流的字符标识；并

在连续地址上存储按序排列的字符的相应地址，最好独立于相对地址所被存储的连续地址。

9.一个文本输入设备，包括：一个具有一组键的小键盘，每一个键表示多个字符；一个存储器，该存储器存储了表示所需要的语言字符的数字流及对应于该数字流的字符地址的一级列表和一个位于对应于一级列表中字符地址的地址处的字符的二级列表的存储器；一个输出设备；和一个连接到小键盘、存储器和输出设备上的处理器，

该处理器被编程为，接收对应于所激活的键的数字流输入，搜索存储器中的一级列表以找到一对应于输入数字流的数字流，获得相应的字符地址，从存储器的二级列表中读取一个位于该字符地址上的字符标识并提供给输出设备一个对应于该字符标识的字符。

10.一个文本输入设备包括：一个有一组键的小键盘，每个键表示多个字符；一个存储了字符和字符的有序排列的相对地址的表的存储器；一个输出设备；和一个连接到小键盘、存储器和输出设备上的处理器，

该处理器被编程为，接收一对应于所激活的键的数字流输入，依据数字流输入从存储器的表中的多个字符中进行选择；从小键盘上接收一个字符选择输入并依据字符选择输入重新排列存储器中字符的相对地址。

11.一个计算机可读存储器，存储有指令和数据，用于：

保存字符地址及表示所需语言字符的数字序列的一级列表；

接收表示多个字符的输入数字序列；

搜索一级列表以找到对应于该输入数字序列的数字序列；并

获得一个相应的字符地址。

12.一个计算机可读存储器，存储指令和数据，用于：

保存字符和字符的有序排序的相对地址的表；

接收一个字符选择输入；并

依据该字符选择输入重新排列字符的相对地址。

Images