李文涛，戴 永，彭喻杰，谢建斌

（湘潭大学智能计算与信息处理教育部重点实验室，湖南湘潭411105）

多文种融合文字书写教学知识及其自动生成方法

李文涛，戴 永，彭喻杰，谢建斌

（湘潭大学智能计算与信息处理教育部重点实验室，湖南湘潭411105）

多文种融合文字书写教学系统的教学资源具有多语源的特点，但存在知识点数据类型多、计算结构复杂等不足。为此，依据不同文种文字书写的异性与共性规律，提出基于文字书写过程计算的知识点自动生成方法。将多文种的笔画、笔画关系、部件关系等计算元按共享、分类，给出各类计算元编码空间的计算方法，定义面向各文种通用的文字书写过程计算模型，设计并实现计算模型中各计算元编码的自动生成算法。实验结果表明，该方法能准确识别各种知识要素，笔画及各类关系的识别正确率达到98.3%，与人工编码相比，录入速率提高15%，冗码率降低23%。

多文种融合；文字书写教学；知识点；文字书写过程计算模型；计算元；自动编码

1 概述

作为文字书写自动教学系统［1-2］，文字书写教学知识是实现系统教学功能的必备资源。教学知识研究包括两方面内容，即知识库结构与知识点。知识库结构研究已趋成熟［3-4］，单文种知识点的构造方法已进入实用阶段，如文献［5］采用笔画以及笔画书写顺序作为知识点结构来指导英文字母书写；文献［9］按笔画与笔画关系知识点结构设计了基于关系图的汉字匹配算法指导汉字书写。知识点构建方法分手动和自动两大类，知识面窄、量少时可以采用手动，多文种融合使得知识点数据类型多、计算结构复杂及知识量大等，为提高工作效率与知识正确率应采用自动方法。本文依据不同文种书写过程所具备的公共与独特形态、公共与独特规则，提出多文种文字书写教学的通用教学知识点结构及其自动生成的方法。将各文种的笔画与关系分为共享及独特两大类；设计综合两类的编码结构；给出各类计算元编码空间的计算方法，定义文字书写过程计算模型，实现知识点主导笔顺、错交笔顺、错离笔顺等的自动编码，缺省的融合文种含汉字、英文、汉语拼音。

2 文字结构分析

笔画、笔画关系、部件关系是文字结构的要素，也是文字书写教学的基本内容。不同文种有各自的笔画、笔画关系、部件关系集合，在形态及书写过程等方面虽独具特色但也不可避免会形成相交内容。

其中，α（·）表示多文种共享的笔画数目；β（·）表示由“·”个文种的共享笔画构成的集合，记共享笔画数量为：

用f（us）表示A个文种的独特笔画数目：

A种文种融合后的笔画全集记为：

各笔画子集之间无交集。

同理可计算融合后总的笔画关系子集数量F（sr）、部件关系子集数量F（pr）。分别用λ（·），χ（·）依次表示共享笔画关系、部件关系的数目，用φ（·），φ（·）分别依次表示共享笔画关系、部件关系元素构成的集合，共享笔画关系数量f（ssr）和共享部件关系数量f（spr）计算结构与式（2）相同。独特笔画关系数量f（usr）和独特部件关系数量f（upr）计算结构与式（3）相同。A种文种融合后的笔画关系、部件关系全集分别依次记为φ，φ，各子集关系描述类同β。用L表示文种，表1给出A种文种笔画的共享与独特情况分析，笔画关系、部件关系分析结构类同，即将笔画子集的β，w分别依次用φ，r*和φ，rρ替代便可。

表1 A种文种融合笔画共享与独特情况

为适用多文种通用的部件描述，部件分割采用定制法，即当紧邻前后2条笔画的空间位置关系超出所在系统设置的分析能力，称其为具有不可计算性，并认为此2条笔画处于2个相邻的部件中，在2条笔画间插入部件关系符。

3 知识结构设计

教学知识点通用的基本内容与结构如图1所示。

图1 通用的文字书写教学知识点结构

第2字段为被教学文字的标准编码，如汉字采用国标GB2312-80编码（区位码），英文字母采用ASCII码等；第3字段、第4字段用于文字书写质量分析［7］；第5字段用于产生文字语音码［8］。第1字段是被练习文字书写过程的计算结构，计算元为笔画、笔画关系、部件关系等要素，为本文的重点研究对象。

3.1 元编码计算

对计算元编码应满足的基本要求为：（1）不同计算元有明显的数值段；（2）能体现不同文种共享与独特计算元的区别；（3）具有能自动适用于文种增加和计算元补充的编码变换机制等。

采用10进制数字编码。以笔画编码为基准编码，单粒度占用编码范围为1～（f（ss）+f（us）），当粒度为m时，编码范围为1～m×（f（ss）+f（us）），考虑笔画的扩充，设置编码裕量。记ε（ss），ε（us）分别依次为共享、独特笔画编码裕量，则确认的笔画编码范围为1～m×（f（ss）+ε（ss）+f（us）+ε（us）），最大值需j位表示，个位为1高位为j-1个0是首条共享笔画的编码。编码数目为m×（f（ss）+ε（ss）+f（us）+ε（us））。w的最高位位值用bitmax表示，令B1为对应于笔画关系r*类编码，当w（bitmax）+b≤9，b∈｛1，2，…，8｝，B1取j位，且w（bitmax）＜B1（bitmax）≤w（bitmax）+b，低j-1位编码全取0；否则B1取j+1位，B1（bitmax）=1，低j位编码全取0。确认的r*类编码范围为B1（bitmax）×10（j-1 orj）～［B1（bitmax）× 10（j-1∩or∩j）+（f（ssr）+ε（ssr）+f（usr）+ε（usr））］，ε（ssr），ε（usr）分别依次为共享、独特笔画关系编码裕量。B1（bitmax）×10（j-1 or j）为首个共享笔画关系的编码。从文字书写教学的角度出发，笔画关系编码需进行多层次空间关系描述。设建立e层空间关系，r*编码的完整结构定义为B1（B2B3…Be+1），B2B3…Be+1为空间关系细分描述码，Bi是对Bi-1的进一步细分（i∈｛2，3，…，e+1｝，Bi∈｛0，1，…，9｝），e+1越大，空间关系描述越精细。设b2b3…be+1依次分别对应B2B3…Be+1的取码数量，笔画关系编码数目为（f（ssr）+ε（ssr）+f（usr）+ε（usr））×b2× b3…×be+1。部件关系与笔画关系的接码及其编码原理基本类似笔画关系与笔画，不同之处在于部件关系编码的结尾码字标注的该部件与后续多少部件构成该关系编码所标注的关系，用x表示结尾码，其缺省值为1，x无当前空间标识作用，因此不影响编码数量。

算法1 编码空间生成

输入 m，f（ss），f（us），ε（ss），ε（us），f（ssr），f（usr），ε（ssr），ε（usr），e（sr），f（spr），f（upr），ε（spr），ε（upr），e（pr）

3.2 结构计算

文字书写过程的计算内容及其关系定义为：主导笔顺||错交笔顺||错离笔顺。

图2 文字示例

以Q表示文字的书写过程计算结构，书写过程中的定制部件记为M，Q定义为：

为便于式（5）各计算元的分类输入与库存管理、笔顺跟踪及逆跨分析等，按后缀波兰式结构重排计算元。去掉“+”号，用Q（B）表示Q的后缀波兰式，于是：

4 知识码的自动生成

将式（6）表示为向量，即有：

通过对文字标准书写结构的跟踪生成W，R，WEC，WEL。

4.1 主导笔顺码链的生成

主导笔顺码链生成是基础。跟踪主导笔顺不但要给出W，R，还要为生成WEC，WEL准备笔画数据。R中既有r*，也有rρ，两者的生成方法有较大区别。4.1.1 笔画与笔画关系编码

借鉴已有成果［9-10］对当前书写笔画wi（i=2，3，…，k）进行识别，将识别结果的笔画编码有序存入W。在wi，wi-1之间进行e+1次计算分析，将r*i-1的属性编码有序存入R。当wi，wi-1之间无法在系统中找到相应的计算模型分析时，在wi，wi-1之间预置部件分割的通用标志。写完文字最后一条笔画，即i=k，W生成结束；R中r*有确定的代码，但其中需进一步分析；提供k行笔迹数据阵列S［k， lmax］，lmax为该字最长的笔画笔迹点数量。

4.1.2 部件关系编码

部件关系依托R，S［k，lmax］分析。设R中存在m个。在R中搜素到（j=1，2，…，m），在S［k，lmax］中获取Mj，Mj+1所含w，利用φ元素所适用的计算模型分析关系，将分析结果对应的编码有序存于位置。第1轮均按x=1建立部件关系，第2轮进行跨部件关系分析，即如果关系与关系相同，则x+1。依次类推，直至j=m-2。

4.2 错交笔顺向量的生成

文字书写主导笔顺正确，进行错交码对偶预测。在S［k，lmax］中，对于wi，wj（i＞j+1，i，j∈｛1，2，…，k｝），将wi两端点的笔段按其形态进行延伸，对所有的wj（j∈｛i-2，i-3，…，1｝）进行十字交关系分析，形成初选笔画书写序号构成的十字交序号对偶序列，借助共享工作容器进行对偶元素去留分析，分析模型为S［k，lmax］。

即将wi端点到wi，wj交点距离最短的那一对（i，j）有序填入WEC。dis（wi-endp，w iw j-Inters）为wi端点到wi，wj十字交点的距离计算函数。

4.3 错离笔顺向量生成

对于书写结构确认正确的W，设其存在q对有可能产生错离的笔画，在S［k，lmax］中取第τ对可能产生错离的wi，wj（i＞j+1，i，j∈｛1，2，…k｝），记为wiτ，wjτ，τ=1，2，…，q，识别wiτ，wjτ之间的关系，并根据类别选择ξ，将对应的编码、当前（i，j）和ξ一起构成结构，将此结构先存储在共享工作容器内。如此，完成q对笔画的错离码链在WEL中的生成。

4.4 算法设计

知识码链的生成过程分为2个阶段，第1阶段是跟踪文字书写过程实时生成W、R中的r*及S［k，lmax］；第2阶段是基于S［k，lmax］生成R中的rρ与WEC，WEL。主要步骤如下：

算法2 Q（B）生成

Step1 读入当前书写笔画数据；

Step2 对笔画数据进行前置处理［11］，并有序存入S［k，lmax］；

Step3 识别当前笔画，将对应的笔画编码有序存入W；

Step4 对于非第1条笔画，分析其与前条笔画的关系，存在关系，将关系码有序存入R；不存在则存入部件分割标注；

Step5 是否有文字写完信息，无则转Step1；

Step6 基于S［k，lmax］查询部件分割标志，识别部件关系，将关系码替代分割标志符；

Step7 基于预测错交笔画，将预测的错交笔画的序号对偶有序存入WEC；

Step8 基于S［k，lmax］预测错离笔画，将预测的错离笔画的4元结构有序存入WEL；

Step9 结束。

5 实验测试及结果分析

实验平台主要硬件模块包括7英寸触摸屏及S3C2440A，32 bit ARM 920T内核及其控制器，标准配置64 MB NAND-FLASH，标准配置64 MB SDRAM等。软件开发环境为VS2005，操作系统为W ince 5.0，开发语言为C++。以汉字（L1）、英文（L2）、汉拼（L3）融合为例，即A=3。3文种融合的相关信息结构如表2所示。

表2 3文种计算元共享与独特内容及其对应的编码空间

表2中没有参数的子集栏目表明该子集为空。取笔画粒度m=2，即笔画规模按长、短2种状态设置，f（ss）+f（us）=72，取ε（ss）=10，ε（us）=17，编码空间为001～198；笔画关系空间采用3-3细分编码，即e（sr）= 2，b2=3，b3=3，B2，B3∈｛0，1，2｝f（ssr）=4，f（usr）=5，取ε（ssr）=2，ε（usr）=9，编码空间为20 000～21 922；部件关系空间采用3区位细分编码，即e（pr）=1，b2=3，B2∈｛0，1，2｝，f（spr）=2，f（upr）=1，取ε（spr）=2，ε（upr）= 5，编码空间为3 000x～3 192x。3类计算元编码空间栏给出由算法1生成的相应类计算元编码空间。图3所示为“体”、“E”字的书写教学知识形态或模板结构及其Q（B）的生成内容。

对于模板“体”，写完第1条笔画，笔迹点坐标数据被记录于S［1］，笔画识别模块将该识别结果“008”存于Cstroke（笔画码）容器，并在图3（a）界面的W子窗口显示；第2条写完，笔迹数据放入S［2］，识别结果“006”放入前条笔画编码之后。依据S［1］、S［2］进行第2条笔画、第1条笔画关系识别，该关系为T字交关系，生存的编码为“20311”，存于Crelation（关系码）容器，并显示于图3（a）的R子窗口。第3画“短横”与第2画“长竖”本系统无法确定两者空间关系，在第2画之后插入部件分割标志代码p，将两者定制在两个紧邻部件中，并记录该标志在Crelation中序号。如此直至第7条笔画即该字的最后一条笔画写完，主导笔顺的Cstroke生成结束，Crelation笔画关系编码生成完毕，但部件关系待进一步分析确定。“体”的书写数据S［k，lmax］如表3所示，其中，k=7，lmax=42，xmax=63，xmin=19，ymax= 62，ymin=24。

图3 文字书写教学知识生成实例

表3 “体”字S［k，lmax］

根据记录的标注符在Crelation中的序号，第1轮按序进行由标注符分割的笔画子集（部件）之间的关系识别。该文字只记录了1个标注符，且序号为2，即图3（a）“体”在书写过程中被定制为M 1和M 22个部件，M 1⊇｛S［1］，S［2］｝，M 2⊇｛S［3］，S［4］，S［5］，S［6］，S［7］｝。利用均质比较法识别M 1，M 2关系为居中左右关系，赋予30011码，该码存于Crelation容器，并显示在图3（a）的R子窗口。

从S［3］开始进行错交预测。端点笔段长度取5，延伸步长取2，延伸长度至文字最值边线，预测结果存入Cerrorc（错交码）容器，并显示在图3（a）的WEC子窗口。从S［3］开始进行错离预测，十字交取ξ=0，点与笔画T字交取ξ=2，端点T字取ξ=5，预测结果存入Cerrorl（错离码）容器，并显示在图3（a）的WEL子窗口。

图3（b）为英文大写字母“E”的书写模板及其Q（B），该字存在一对预测错交笔画，无错离结构。

对30个英文字母、30个汉语拼音字母、340个汉字进行编码实验，正确率达到98.3%，录入速率与人工编码比较，效率提高15%，冗码率如图4所示，字数越多，人工冗码率越大，而自动编码较平稳。

图4 手动与自动生成知识点冗码率对比

6 结束语

教学知识点的自动生成是多文种融合的文字书写教学系统核心技术之一。教学知识点的内容结构具有双重性，过于简单生成容易，但影响教学效果和质量，乃至系统的实用性；过于复杂又会导致系统的存储、速度、算法复杂度等开销增大。本文方法在文献［1］系统中得到应用，编码与建模方法按文献［12-13］等予以改进，结构分析方法借鉴文献［14-15］等进行优化，相应的教室系统见文献［16］。

本文从人们书写文字的共性出发，提炼不同文种文字的共享结构与独特结构进行探索，给出多文种融合的计算元数量及其编码空间计算规则；提出多文种通用的基于笔画、笔画关系及部件关系等计算元的文字书写过程计算模型；设计并实现了知识点各字段的生成算法。实验结果表明，该方法笔画及各类关系识别的正确率达到98.3%，录入效率提高15%。

［1］ 戴 永，刘任任，王求真，等.可联网交互的多功能规定格式习字系统及方法：中国，ZL201010149767.2［P］. 2010-09-01.

［2］ Hammadi M，Bezine H，Njah S，et al.Towards an Educational Tool for Arabic Handwriting Learning［C］// Proceedings of IEEE ICEELI'12.Wacington D.C.，USA：IEEE Press，2012：1-6.

［3］ Kherallah M，Bouri F，Alimi A M.On-line Arabic Handwriting Recognition System Based on Visual Encoding and Genetic Algorithm［J］.Engineering Applications of Artificial Intelligence，2009，22（1）：153-170.

［4］ 鄢 琦，骆仁波，皮佑国.无字库智能造字中汉字基元的统计分析与预测［J］.计算机研究与发展，2012，22（4）：33-36.

［5］ 戴 永，王心觉，张维静，等.面向指导的自由式英文字母书写跟踪［J］.湘潭大学自然科学学报，2012，34（2）：85-89.

［6］ Hu Z，Leung H，Xu Y.Automated Chinese Handwriting Error Detection Using Attributed Relational Graph Matching［C］//Proceedings of ICWL'08.Berlin，Germ any：Springer，2008：344-355.

［7］ 王 耀，戴 永.规定格式文字书写练习质量普适评价［J］.计算机工程与应用，2010，46（29）：69-72.

［8］ 孙广武，戴 永，喻世东，等.音素关联的多文种语音融合编码方法［J］.计算机工程与应用，2013，49（19）：217-221.

［9］ Liu C L，Jaeger S，Nakagawa M.Online Recognition of Chinese Characters：The State-of-the-art［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2004，26（2）：198-213.

［10］ Tan C K.An Algorithm for Online Strokes Verification of Chinese Characters Using Discrete Features［C］// Proceedings of the 8th International Workshop on Frontiers in Handwriting Recognition.Wacington D.C.，USA：IEEE Press，2002：339-344.

［11］ 覃冰梅，戴 永，樊 亮.面向联机书写指导的触摸笔迹信息前置处理［J］.计算机应用研究，2012，29（9）：3365-3368.

［12］ Chen Tieling，Dylon E，M a Jun.Binary Search Tree with Vine［J］.Natural Science Journal of Xiangtan University，2013，35（3）：1-8.

［13］ 余 英，罗永超，程明宝.带分批的一类具有恶化加工时间的排序问题的算法研究［J］.湘潭大学自然科学学报，2013，35（2）：14-16.

［14］ 任 昆，戴 永，王求真，等.上下文感知手写数学公式结构分析［J］.湘潭大学自然科学学报，2014，36（2）：85-91.

［15］ 游应德，李成大.一种边界梯度组合的图像识别技术与分割方法［J］.湘潭大学自然科学学报，2014，36（2）：99-103.

［16］ 喻世东，戴 永，王求真，等.适用于文字书写教学教室系统的嵌入式局域网协议［J］.计算机工程，2014，40（9）：284-290.

编辑 索书志

Multilingual Integration Text Writing Teaching Know ledge and Its Automatic Generation Method

LI Wentao，DAIYong，PENG Yujie，XIE Jianbin
（Key Laboratory of Intelligent Computing and Information Processing，Ministry of Education，Xiangtan University，Xiangtan 411105，China）

The teaching resources features of multilingual integration writing teaching system expresses asmultilingual sources leading to data types of know ledgemore，comp lex calculation structures，greater know ledge and so on.According to heterosexual and common rule of writing in different languages，the method is proposed based on the know ledge automatic generation of the calculating of writing on the process.The Computing elements including stroke，stroke relations，component relations are classified by sharing，unique，and the calculation method of all kinds of computing elements coding space is given，the general writing on the process of calculating model which is know ledge structure for the various text types is defined，the automatic generation algorithm of each computing element coding in calculation model is designed and realized.Experimental results show that the generation method can accurately identify various know ledge elements，correct identification rate of strokes and various relations reaches 98.3%，the rate of entry improves 15%efficiency compared with manual coding，redundancy rate decreases by 23%.

multilingual integration；text writing teaching；know ledge point；calculation model of text writing process；computing element；automatic coding

李文涛，戴 永，彭喻杰，等.多文种融合文字书写教学知识及其自动生成方法［J］.计算机工程，2015，41（11）：218-223，231.

英文引用格式：Li Wentao，Dai Yong，Peng Yujie，et al.Multilingual Integration Text Writing Teaching Know ledge and Its Automatic Generation Method［J］.Computer Engineering，2015，41（11）：218-223，231.

1000-3428（2015）11-0218-06

A

TP18

10.3969/j.issn.1000-3428.2015.11.038

湖南省教育厅基金资助项目（13C914）；湖南省“十二五”重点学科建设基金资助项目。

李文涛（1986-），男，硕士研究生，主研方向：知识处理，智能系统；戴 永，教授；彭喻杰，讲师；谢建斌，硕士研究生。

2014-10-10

2014-11-29 E-m ail：liw entaoss@sohu.com