编者注: X-MOVE是作者在业余时间于2010年6月份启动的以运动传感开发,算法和应用的平台,目前已经发展了三个版本,第四版的开发接近尾声。发布在博客园仅为交流技术,不存在商业目的,作者保留一切权利。
一. 综述
所谓T9,指的是在手机上广为流传的九宫格输入法。中文输入法大家每天都在使用,那么多大的空间才能承载一个输入法呢?搜狗安装包已经20M了,手机版本的也有2M。但我会告诉你,实现中文输入法仅需要14KB的存储空间和不到100byte的内存。虽然没有联想,并只支持拼音,但已经足够surprising了~
输入法的词组和数据结构定义是我大三时从某个不知名的网站上巴拉下来并移植到我的XMOVE平台下的嵌入式手持终端上的,现在实在想不起其真实来源了。我对它做了必要的改进,并优化了存储结构,想必算法的原作者也会乐于接受的吧。
以下是它的运行时实物截图:
它具有如下特点:
- 低内存和低CPU占用
- 支持摇动系统旋转输入字符(需陀螺仪支持)
- 支持中英文混合输入
- 由于物理按键不足,因此采用了屏幕虚拟键盘
与XMOVE手持终端相关的介绍文章列表如下:
系统综述: 自制的彩屏手持动作感应终端
软件介绍(一):精简型嵌入式系统的菜单实现和任务切换
软件介绍(二):在2KB内存单片机上实现的彩屏GUI控件库
软件介绍(三):在2KB内存单片机上实现的俄罗斯方块
软件介绍(四):在2KB内存单片机上实现的超精简五子棋算法
软件介绍(五):在2KB内存的单片机上实现的T9中文输入法
二. 数据结构和数据
从直觉来说,实现输入法的必要条件是建立索引,因为中文常用词就已经两三千。同时,应该在没有完成拼音输入之前就能获得可能的结果,例如,输入zhua,那么系统会提供来自zhua,zhuang,zhuan的汉字显示,而并非仅仅提供zhua。
通常的手机输入功能是这样的:
我们可以朴素的思考,我们建立一组拼音字符串(如"zhua")与相应汉字列表(如“抓爪...”),那么每次更新拼音字符串后,就只需要搜索匹配的汉字列表了。但实际上问题并非这么简单,这个表可能有200多条(可能的拼音字符串就有200种,没有仔细统计过),每次都在这里搜索,无疑会很慢。为了提升速度,应该将该表进行分割,通常可以根据按下的第一个键分割成10个拼音索引表。这样每组表只有20多个,大大提升了搜索速度。
数字按键组合,组合成16进制,比如按键246则为0x246。
通过这些基本思想,我们确定如下的数据结构。
1. 必要的结构体定义
相关信息都在注释上解释清楚了。
struct t9PY_index //拼音索引结构 {const unsigned long t9PY; //对应的索引号const unsigned char *PY; //显示的拼音字符串const unsigned char *PY_mb; //对应的汉字排列表 };struct t9py_struct {unsigned char pysrf; //输入法选项unsigned char firstno; //输入的第一个数字按键unsigned char mblen; //查出码表的长度unsigned char mbtimes; //码表切换的次数unsigned long t9py; //数字按键组合,组合成16进制,比如按键246则为0x246const struct t9PY_index *t9PY_addr; };
2. 汉字排列表
const unsigned char PY_mb_space []={""}; const unsigned char PY_mb_a []={"啊阿呵吖嗄腌锕"}; const unsigned char PY_mb_ai []={"爱矮挨哎碍癌艾唉哀蔼隘埃皑呆嗌嫒瑷暧捱砹嗳锿霭"}; const unsigned char PY_mb_an []={"按安暗岸俺案鞍氨胺厂广庵揞犴铵桉谙鹌埯黯"}; const unsigned char PY_mb_ang []={"昂肮盎仰"}; const unsigned char PY_mb_ao []={"袄凹傲奥熬懊敖翱澳嚣拗媪廒骜嗷坳遨聱螯獒鏊鳌鏖"}; const unsigned char PY_mb_ba []={"把八吧爸拔罢跋巴芭扒坝霸叭靶笆疤耙捌粑茇岜鲅钯魃"}; const unsigned char PY_mb_bai []={"百白摆败柏拜佰伯稗捭呗掰"}; const unsigned char PY_mb_ban []={"半办班般拌搬版斑板伴扳扮瓣颁绊癍坂钣舨阪"}; ///省略....
//下面是英文对应的排列表
const unsigned char PY_mb_abc []={"abc"};
汉字排列表较容易理解,就是某拼音下对应的汉字数组,注意加上了const。在单片机环境中它会默认存储在flash中而不是内存,这样可以优化存储。
3. 拼音索引表
const struct t9PY_index t9PY_index0[] ={0x00," ",PY_mb_bd}; //1 const struct t9PY_index t9PY_index1[] ={0x20," ",PY_mb_space}; //1 const struct t9PY_index t9PY_index2[] ={{0x2,"a",PY_mb_a}, //55 {0x22,"ba",PY_mb_ba}, {0x22,"ca",PY_mb_ca}, {0x224,"bai",PY_mb_bai}, {0x224,"cai",PY_mb_cai}, {0x226,"ban",PY_mb_ban}, {0x226,"bao",PY_mb_bao}, {0x226,"can",PY_mb_can}, {0x226,"cao",PY_mb_cao}, {0x226,"cen",PY_mb_cen}, {0x2264,"bang",PY_mb_bang}, {0x2264,"cang",PY_mb_cang}, {0x23,"ce",PY_mb_ce}, {0x234,"bei",PY_mb_bei}, {0x236,"ben",PY_mb_ben}, {0x2364,"beng",PY_mb_beng}, {0x2364,"ceng",PY_mb_ceng}, {0x24,"ai",PY_mb_ai}, {0x24,"bi",PY_mb_bi}, {0x24,"ci",PY_mb_ci}, {0x242,"cha",PY_mb_cha}, {0x2424,"chai",PY_mb_chai}, {0x2426,"bian",PY_mb_bian}, {0x2426,"biao",PY_mb_biao}, {0x2426,"chan",PY_mb_chan}, {0x2426,"chao",PY_mb_chao}, {0x24264,"chang",PY_mb_chang}, {0x243,"bie",PY_mb_bie}, {0x243,"che",PY_mb_che}, {0x2436,"chen",PY_mb_chen}, {0x24364,"cheng",PY_mb_cheng}, {0x244,"chi",PY_mb_chi}, {0x246,"bin",PY_mb_bin}, {0x2464,"bing",PY_mb_bing}, {0x24664,"chong",PY_mb_chong}, {0x2468,"chou",PY_mb_chou}, {0x248,"chu",PY_mb_chu}, {0x24824,"chuai",PY_mb_chuai}, {0x24826,"chuan",PY_mb_chuan}, {0x248264,"chuang",PY_mb_chuang}, {0x2484,"chui",PY_mb_chui}, {0x2484,"chun",PY_mb_chun}, {0x2486,"chuo",PY_mb_chuo}, {0x26,"an",PY_mb_an}, {0x26,"ao",PY_mb_ao}, {0x26,"bo",PY_mb_bo}, {0x264,"ang",PY_mb_ang}, {0x2664,"cong",PY_mb_cong}, {0x268,"cou",PY_mb_cou}, {0x28,"bu",PY_mb_bu}, {0x28,"cu",PY_mb_cu}, {0x2826,"cuan",PY_mb_cuan}, {0x284,"cui",PY_mb_cui}, {0x286,"cun",PY_mb_cun}, {0x286,"cuo",PY_mb_cuo} };
//还有大量省略
所谓拼音索引表一共有10个,本节的第一部分就介绍了拼音索引表的用途。以及如下的表:
const unsigned char t9PY_indexlen[10] = {1,1,55,33,38,57,44,79,19,74}; //以每个数字键开始的拼音代码组合数量
三. 主流程实现
1. 输入法任务初始化
初始化主要设置为默认拼音,输入的拼音字符串和长度默认归零。
struct t9py_struct t9pyfun; void py_init() {t9pyfun.pysrf=T9PY;t9pyfun.t9PY_addr=t9PY_index1;t9pyfun.t9py=0; t9pyfun.firstno=' ';t9pyfun.mblen =0;}
2. 查找索引
void py_index_sub(void) {uchar i;uchar flag = 0x55;unsigned long temp;uchar mblentemp;mblentemp = t9pyfun.mblen;t9pyfun.mblen = 0x00;if ((t9pyfun.pysrf == T9PY) && (t9pyfun.firstno != ' ')) //拼音输入法{for (i=0;i<t9PY_indexlen[t9pyfun.firstno];i++) {if (t9pyfun.t9py == (*(t9PY_index_headno[t9pyfun.firstno]+i)).t9PY){t9pyfun.mblen++;flag = 0xaa;t9pyfun.t9PY_addr = (t9PY_index_headno[t9pyfun.firstno]+i);for (i++;i<t9PY_indexlen[t9pyfun.firstno];i++){if (t9pyfun.t9py == (*(t9PY_index_headno[t9pyfun.firstno]+i)).t9PY)t9pyfun.mblen++;else break;}break;}}if (flag == 0x55) //没有查找完全对应的拼音组合,{for (i=0;i<t9PY_indexlen[t9pyfun.firstno];i++){temp = (*(t9PY_index_headno[t9pyfun.firstno]+i)).t9PY;while (temp > t9pyfun.t9py){temp >>= 4;if (temp == t9pyfun.t9py){t9pyfun.t9PY_addr = t9PY_index_headno[t9pyfun.firstno]+i;t9pyfun.mblen++;i = t9PY_indexlen[t9pyfun.firstno];flag = 0xaa;break;}} }if (flag == 0x55){t9pyfun.t9py >>= 4;t9pyfun.mblen = mblentemp;}}}else if(t9pyfun.pysrf == T9SZ) //数字输入{t9pyfun.mblen++;t9pyfun.t9PY_addr = &t9PY_sz[t9pyfun.firstno];}else if(t9pyfun.pysrf == T9BD) //标点输入{t9pyfun.mblen++;t9pyfun.t9PY_addr = t9PY_index0;} else if(t9pyfun.pysrf == T9DX) //大写英文字母输入{if ((t9pyfun.firstno>1)&&(t9pyfun.firstno<10)){t9pyfun.mblen++;t9pyfun.t9PY_addr = &t9PY_ABC[t9pyfun.firstno];}} else if(t9pyfun.pysrf == T9XX) //小写英文字母输入{if ((t9pyfun.firstno>1)&&(t9pyfun.firstno<10)){t9pyfun.mblen++;t9pyfun.t9PY_addr = &t9PY_abc[t9pyfun.firstno];}} }
3. 通过用户输入标识(input_data)实现判断和相关操作:
由于不同的平台,用户输入是完全不同的,因此本部分仅供参考。
u8 T9InputChoose(u8 x,u8 y,u8 input_data,u8 *buff,u8 *buffin,uchar bufflen) {if (input_data==0) // 输入法切换{if ((++t9pyfun.pysrf) > T9SZ)t9pyfun.pysrf = T9DX; dispsrf(x,y);}else if (input_data==KEYLEFT_UP+20) // 输入标点符号,{t9pyfun.mblen++;t9pyfun.t9PY_addr = t9PY_index0;}else if ((input_data>0&&input_data<9)||input_data==10||input_data==KEYDOWN_UP+20) //输入内容{if (t9pyfun.pysrf == T9PY){if (input_data>0&&input_data<9) //输入内容{t9pyfun.mbtimes = 0;PY_index = 0;if (t9pyfun.firstno == ' ')t9pyfun.firstno = input_data+1;t9pyfun.t9py = ((t9pyfun.t9py<<4) | DecToHexFunc(input_data+1) );py_index_sub();}else if (input_data== 10||input_data==KEYDOWN_UP+20) //索引切换.{t9pyfun.t9PY_addr++;t9pyfun.mbtimes++;PY_index = 0;if (t9pyfun.firstno != ' '){if (t9pyfun.mbtimes >= t9pyfun.mblen){t9pyfun.mbtimes = 0;t9pyfun.t9PY_addr -= t9pyfun.mblen;}}}}else if (t9pyfun.pysrf == T9SZ) //输入数字{buff[(*buffin)++] =0x30+input_data+1;clrindex(x,y,0);}else if ((t9pyfun.pysrf == T9DX) || (t9pyfun.pysrf == T9XX)) //输入字母{if (input_data>0&&input_data<9) //输入内容{if (t9pyfun.firstno == ' '){t9pyfun.mbtimes = 0;PY_index = 0; t9pyfun.firstno = input_data;t9pyfun.t9py = ((t9pyfun.t9py<<4) | DecToHexFunc(input_data+1));py_index_sub();} }} }else if (input_data==11||input_data==KEYRIGHT_UP+20) // 删除键{if (t9pyfun.mblen > 0){ if (PY_index == 0) //删除索引拼音 {if ((t9pyfun.t9py > 0) && (t9pyfun.pysrf == T9PY)){t9pyfun.t9py >>= 4;if (t9pyfun.t9py == 0)clrindex(x,y,1);else{ py_index_sub();clrindex(x,y,0);};}else {clrindex(x,y,1);} }}else if (bufflen > 2) //删除输入的汉字.{buff[--(*buffin)] = 0;buff[--(*buffin)] = 0;} }else if (input_data==9||input_data==KEYUP_UP+20) //确认键{if (t9pyfun.mblen>0){if (*buffin < bufflen){ select_data(x,y,buff, buffin, bufflen);}else {clrindex(x,y,1);} }}else if (input_data==10) //跳出{return 0;}return 1; }
4. 选择汉字函数
本部分是用户在输入拼音字符串后,在选取输入汉字时的函数。由于系统采用了虚拟键盘,因此必须读取外部的“旋转数据”,选择相应的输入字符。
系统有在汉字列表下有一红色光标,当左右旋转设备时,光标会随之移动,当您需要翻到上一页或下一页时,上下稍微用力摇晃设备即可。当然,这一切也可以通过物理的上下左右按键完成。
void select_data(u8 x,u8 y,uchar *buff,uchar *buffin,uchar bufflen) //选择汉字函数 {InnerFuncState=1;u8 FlagSet=0;u8 GyroKey; while(InnerFuncState==1){ key_data=KEYNULL;SetPaintMode(0,COLOR_Red);Circle(x+108+FlagSet*X_Witch_cn,y+7*Y_Witch_cn+5,4,1); if(GyroControlEN==1){ITG3200ReadData();ITG3200ShowData();delay_ms(150);}elseInputControl();GyroKey=GyroKeyBoardInputMethod(0,1,200,1000);if(GyroKey!=KEYNULL)key_data=GyroKey;GyroKey=KEYNULL;SetPaintMode(0,COLOR_White);Circle(x+108+FlagSet*X_Witch_cn,y+7*Y_Witch_cn+5,4,1);switch(key_data){case KEYUP_UP:if(PY_index>8)PY_index-=9;dispsf(x,y,buff,*buffin);break;case KEYDOWN_UP:if((strlenExt(t9pyfun.t9PY_addr->PY_mb)-(2*(PY_index+8)))>0){PY_index+=9;dispsf(x,y,buff,*buffin);}break;case KEYCANCEL_UP:InnerFuncState=0;break;case KEYLEFT_UP:if(FlagSet>0)FlagSet--;break;case KEYRIGHT_UP:if(FlagSet<8)FlagSet++;break;case KEYENTER_UP:PY_index+=(FlagSet);if (*(*t9pyfun.t9PY_addr).PY_mb > 0x80) //输入汉字{buff[(*buffin)++] = *((*t9pyfun.t9PY_addr).PY_mb+PY_index*2);buff[(*buffin)++] = *((*t9pyfun.t9PY_addr).PY_mb+PY_index*2+1);InnerFuncState=0;clrindex(x,y,1);}else //输入字符{buff[(*buffin)++] = *((*t9pyfun.t9PY_addr).PY_mb+PY_index);//buff[(*buffin)++] = ' '; InnerFuncState=0;clrindex(x,y,1);}break;}}}
5. 主函数流程
这是系统整个的输入流程,在主循环中,VirtualNumKeyBoardInput函数接收用户输入,用户输入的字符可通过形参的指针传递,返回值作为状态。但返回0时,表明用户选择放弃输入直接退出;返回1时,跳出循环保存,返回2时,继续输入,加20的偏移量,仅仅是为了前后的输入键值匹配。
u8 T9InputTask(u8 x,u8 y, u8 *Buff,u8 *BuffFlag,u8 Max) {u8 VnKbX=1,VnKbY=1,VnKey;TaskBoxGUI_P(x,y,x+100+9*Y_Witch_cn,y+Y_Witch_cn+108,"中文输入程序",0);PutBitmap(x,y+Y_Witch_cn,VKNUM,0);FontMode(1,COLOR_White);py_init();dispsrf(x,y);OS_func_state=1;while (OS_func_state==1){dispsf(x,y,Buff,*BuffFlag);switch(VirtualNumKeyBoardInput(x,y-Y_Witch_cn,&VnKbX,&VnKbY,&VnKey,0,1)){case 0:return 0;case 1:break;case 2:VnKey+=20; //加20偏移量break;}T9InputChoose(x,y,VnKey,Buff,BuffFlag,Max);}return 1;}
四. 总结
这些代码也是我在大三时移植和完成的,因此存在大量的C语言印记。
我的最大感受,即使是嵌入式C语言,也应该尽可能的将功能模块化,输入函数仅处理用户输入,显示函数和搜索算法都应该分离。当然,由于C语言没有事件,只能通过返回值确定系统状态,在传递参数较多时,要么传递结构体,要么通过长长的形参表传递,这都是不利于程序维护,也是我的代码需要改进的地方。
整个输入法模块移植起来依旧是需要时间,精力和耐心的。我承认在一篇文章中完整的表述中文输入法算法有些困难,附件将提供完整的源代码供大家参考。
以下是完整源代码。