T9输入法实现原理和步骤(T9输入法的实现

T9输入法，好像不知道名字，大家都很常用。可以说T9输入法在输入法历史上是一场革命。至少从T9输入法开始，输入法有了很大的进步。

就像手机上的九个数字键。 26个字母被分配给8个数字键，从2到9。以前想输入英语单词时，为了得到目标文字需要多次连续按键。例如，如果要输入“hello”，则需要按4次、3次、5次、5次、6次和2次。输入一个单词需要几十次键，更不用说经常按错。编辑邮件很麻烦。

T9输入法很好地解决了这个问题。用户使用9个数字键输入非常复杂的英语单词，不需要多次按某个字符。系统根据现有词典找出最有可能的单词。例如，如果目标单词为” hello “，则只要输入4、3、5、5和6，就会自动过滤错误的单词，如” gdjjm “。通过排除非法单词，只考虑合法单词，大大提高了输入速度。

但是，这是第一步。因为每次输入数字时，多个候选单词的前缀都可能匹配。这需要根据可能性提供可能性最大(最常用)的英语单词。例如，两个单词“idea”和“hello”是已知的。 idea是最常用的。那么，如果依次输入4、3、5、5和6，则每个关键系统提供的候选词语应该如下：

I(4) )。

id(3) )。

赫尔(5)。

光晕(6)。

这样，用T9输入法可以大大提高输入法的输入法速度和简洁度。

怎么实现T9输入法？

(1)词典的编写

储存大量的单词，很快就能找到。词典树确实是个好选择。每个节点存储此前缀的可能性，如下所示：

/* *词典树* /公共类树{ publicnoderoot=new node (； //词典根节点public class node { publicintprobablity；公共节点[ ]下一步； public Node () {this.probablity=0； next=new Node[26]； }publicvoidinsert(stringstr，int probablity ) {Node p=root； int i=0； for(I=0； i str.length (； I ) if(p.next[str.charat(I )- ‘a’]！=null () p=p.next[str.charat(I )- ‘a’]； p.probablity =probablity； } else {Node q=new Node ()； q.probablity=probablity； p.next[str.Charat(I )- ‘a’]=q； p=p.next[str.charat(I )- ‘a’]； } }公共内搜索(stringstr ) {Node p=root； int i=0； for(I=0； i str.length (； I ) if(p.next[str.charat(I )- ‘a’]！=null () p=p.next[str.charat(I )- ‘a’]； } else {return 0； }}return p.probablity； }

)2)寻找

在每个节点上最多有26个孩子分别创建表示以下字符的词典树：如果给出搜索字符串“43556”，则使用宽度优先扫描来搜索长度为x的所有前缀的可能性。找到最大的就行了。广搜索时使用排队。

模拟过程示例：

4 )输入g、h、I )后，通过遍历词典树，找到仅找到’ h ‘、’ I ‘、最大可读输出) I )，并将h、I全部入队。

3 )输入d、e、f )后，取出队列中的’ h ‘，分别组成’ hd ‘、’ he ‘、’ hf ‘，去词典树查询，其中放入合法字符串，记录最大可能对应字符串。又把h推出队伍。对“I”也进行同样的操作。最终找到最大的可能性读最大的字符串。

在搜索过程中可以发现树枝被大量修剪，以及常用单词的长度最多不过十几个字。所以词典树的深度也只有十几棵树，加上大量的剪枝，性能很好。

static int[][] ref={//手机键盘数字-字符映射表{0}，{0}，{ 3，0，1，2 }，/按钮2，3个字符的a，b，c { 3，3，4，} //大小优先的遍历中的队列公共静态三树； //词典树publicstaticvoidBFS(stringstr ) {queue.clear )； queue.offer (‘ )； int i=0； for(I=0；’ 1 ‘！=str.Charat(I； I ) {int max_probablity=0； //最大可能值String probaStr=’ ‘； int pre_amount=queue.size (； //队列中前一个字符串的数量int j=0； for(j=0； j pre_amount； j () {int k=0； String preStr=queue.peek (； for(k=1； k=ref[str.Charat(I )- ‘0’][0]； k ({ string tempstr=prestr.concat ((char ) ) ref[str.charAt(i ) I )-‘0) ][k]97 ) ‘)； if(trie.search(Tempstr )0) queue.offer ) Tempstr )； }if(trie.search(tempstr ) max_probablity ) max_probablity=trie.search ) tempstr )； probaStr=tempStr； }}queue.poll (； }if(”.equals(probastr ) ) {break； } else { system.out.println (probastr )； }while(1)！=str.Charat(I ) ) system.out.println(‘manually )； }

思考：

1 .虽然以上的模拟过程是提供最大可能性的串，但是也可以对每个可能性依次提供所有的匹配串，由用户选择。

2.t9输入法似乎打破了此前输入法的僵局。我只需要用手机输入。但我个人认为，目前流行的智能键盘输入法也采用了同样的处理。例如，在Sogou输入软件中依次输入“hao”“缓慢的魔镜”“Wei”“zhi”

最大的候选人依次是“好”“老鼠”“味道好”“自作自受”。有点T9输入法的味道吗？如果你感兴趣，可以交换讨论！