编码高效Unicode_GB编码转换算法的设计和实现

高效Unicode/GB编码转换算法的设计和实现

倪晓军

(南京邮电大学计算机学院,江苏南京210003)

摘要:为了在存储空间和运算能力严格受限的嵌入式系统中实现Unicode和GB2312编码的相互转换,设计了一种高效

率的编码转换算法。该算法通过提取数据表中公共部分实现压缩存储,采用索引和二分法查找相结合的方式进行快速查

找,和传统的转换算法相比约节省25%的存储空间,查找效率最高约提高3倍。该算法可在无操作系统支持的嵌入式系

统中实现汉字编码之间的高效率的转换。

关键词:汉字编码;GB2312;Unicode;索引;二分法查找

中图分类号:TP311 文献标识码:A 文章编号:1673- 629 X(2009)09- 0021 -04

A High- Performance Unicode/GB Transcoding Algorithm

N I Xiao2jun

(College of Computer,Nanjing University of Posts and Telecommunications ,Nanjing 210003 ,China)

Abstract :To address the characteristics of strict limitation on storage space and computing ability in embedded systems , a novel transfor2mation method for the exchange between GB2312 code and Unicode is presented in this paper The proposed method require less storagespace by extracting the common part o f converting table , and realize quick searching speed by combining index and binary searchingmethod Compared with the traditional trans form ation algorithm, it can save about 25%storage space while about three times faster , itcan be run efficiently without the support of operating system

Key words :Chinese coding;GB2312;Unicode;index;binary searching

0 引 言 位码,区码0109主要存放各种字母、符号及制表符

字符必须编码后才能被计算机处理。我国在 等内容,区码1687则存放按汉语拼音字母顺序排列1980年提出了GB2312汉字编码方案,共收录了7445 的汉字。为了在使用中区分汉字编码和A SCII编码,个字符,包括6763个汉字和682个其它符号。相对于 需要将汉字区位码的高低字节各加上0xA0,才是该汉庞大的汉字字符,GB2312所收录的汉字太少,因此 字的GB2132编码。通过计算(区号- 1) 3 94+(位1995年国家推出了汉字扩展规范GB K1.0,共收录了 号- 1)可计算出某汉字在整个汉字库中的位置序号。21886个汉字和图形符号。 2000年又制定了GB18030 Unicode是由国际组织设计的一种字符编码方案,每个编码方案,是取代GB K1 .0的正式国家标准。该标准 编码由两个字节组成,共可表示65536个字符,由于共收录了27484个汉字,同时还收录了藏文、蒙文、维 编码空间较大,Un ic o d e可以容纳全球所有的语言文吾尔文等主要的少数民族文字[ 1 ] 。 字[2] 。正因为如此,在国际化趋势的推动下,越来越多

从GB2312、GBK到GB 18030,这些编码方案都是 的计算机系统采用Unic ode作为字符编码。 目前国向下兼容的,即同一个字符在这些方案中总是有相同 家标准只要求所有的计算机平台必须支持的编码,后续的标准支持更多的字符。在这些编码中, GB18030 ,所以很多嵌入式应用目前在处理汉字时使英文和中文可以统一地处理。 GB 2312编码标准把汉 用的还是传统的GB2312编码。但现在要求使用Uni2字分成94个区,每个区内包含94个汉字,用区号和位 code编码的场合越来越多。例如,目前的GSM短消息号组成的2字节编码来表示一个汉字,称为汉字的区 收发中文数据时,中文都是以Un ic o de进行编码,放入

用户数据(UD)字段中进行传输的[3 ,4] 。因此,当类似

嵌入式系统教学与研究工作。 码之间的转换工作[5] 。

· 22 · 计算机技术与发展 第19卷

Unic ode编码和GB2312码之间并无固定的转换 列数据加上0 x8080是字符的GB2132编码,减去规则,它们之间的转换必须通过查表的方式完成。一 0 x2020则是区位码。第二列是对应的Un ic o de编码,般的操作系统都提供了这种编码转换的功能,应用程 第三列是Un ic o d e的名称。表格中的各列可以是逗号序设计者只要调用相应的A PI就可以完成编码的转 分隔的,也可以是Tab或空格分隔的。

换[6] 。但在计算能力和存储资源都严格受限的嵌入式 根据这个转换表格可以看出,不管是字母区还是系统中,很多应用甚至都没有使用操作系统,更没有对 汉字区,GB2312编码的数据是连续的,但是对应的U2Unicode和GB2132编码转换的支持。文中以Unicode nicode编码则存在不连续的现象。

和GB2312编码互相转换为目的,针对这种情况设计 为了设计基于二级索引方式的存储结构,需要对了一种存储空间需求少、查找效率高的Un ic o de/ 上述的编码对照表进行以下几个步骤的处理:GB2312编码转换算法,并在不同的嵌入式应用平台上 第一步,将上述编码对照表转化成按照Unic o de进行了测试和比较。 编码排序的表格;

这个工作借助高级语言在计算机上很容易实现,1 Unicode/GB2312编码转换算法的设计 代码简单描述如下:

] ;

行GB2312编码到Un ic o d e编码的转换时,根据汉字的 {

GB2312编码计算出其在汉字库中的索引值,以此为下 ArrayUnico de[i ][0]=0;

标访问该数组即可得到对应的Unicode。 ArrayUnicode[i ][ 1 ]=0;

1.2 Unicode转换为GB2312码 }

汉字Unicode编码的排列和GB2132编码的排列 while( ! feof(fp) ) //处理整个文件中的每一行

完全不同,由于GB2312编码收录的只是常用汉字,故 {

对应的Unicode编码间有不连续的现象,因此Unicode fgets( s ,100,fp) ; //读取一行

转换为GB2132只能通过查表的方式进行。为此作者 ss“canf(s %X\ t%X” ,&GBCode,&Unicode) ;//格式化数据设计了一种基于二级索引和二分法查找的Unic ode编码到GB2132编码的转换算法,以达到节省存储空间 ArrayUnicode[Unicode] [ 1 ]=GBCode; //第一列存放Unicode编和提高查询速度的目的。 码,第二列存放GB2312编码

11211 二级索引存储结构的设计 }

GB2132编码到Un ic o d e编码的转换表可以从U2 上述程序段执行完毕后,A rrayUn ico de数组中所n icode组织的F T P上下载,网络上也有很多其它的下 有ArrayUn icod e[x] [0]项不为0的就表示该Un icode载源。转换表通过文本的方式描述了每个GB2132编 编码(x)有对应的GB2312编码,否则就表示此Uni2码所对应的Unic ode编码,例如对于字母符号区: c ode编码(x)没有GB2312编码与之对应。

0x2121 0x3000 # IDEOGRAPHIC SPACE 第二步,去掉所有Unicode编码项为0的数组单0x2122 0x3001 # IDEOGRAPHIC COMMA 元;

0x2123 0x3002 # IDEOGRAPHIC FULL ST OP 扫描ArrayUnicode,将所有ArrayUnicode[x] [0]为0x21240x30FB# KATAKANAMIDDLEDOT 0的项全部去掉,生成的就是只有与GB2312编码对应

对于汉字区:0 x30210 x554 A# <CJ K> n icode[Un ico de] [ 1 ]中存储的则是对应的GB2312编0x30220x963 F# <CJK>

前两列是用文本方式的十六进制数表示的。第一 ArrayUnic ode数组的第一列中且按升序排列,这样U2

第9期 倪晓军:高效Unicode/GB编码转换算法的设计和实现 · 23 ·

nicode编码高字节相同的所有编码项都排列在一个连 unsigned int BSearch(unsigned char 3 Table,unsigned int Addr1 ,续的存储空间中)

[0]中的Un ic o de编码按高字节进行分组,即所有高字 {

为: if(Code<c)high=mid- 1 ; //调整上限值,查找左子集

有了索引表的帮助,可以根据Unicode编码的高 return 0xffff; //查找不成功

字节控制查找范围,节省查找时间。索引表和存储表 }

的组织及相互关系如图1所示。 B S e arch函数通过传递参数的方式给定要查找的

图1 索引表及压缩存储表结构图 {

;

;

算法的基本思想是首先将这n元素分成个数大致相同

的两半,取a[n/2]与欲查找的x作比较,如果x等于 //在索引表中查找该高字节Unicode的位置(索引表共98项)a[n/2]则找到x,算法终止。如果x<a[n/2],则只 Start Pos =BSearch(PositionIndex,0,98 ,HiByte) ;要在数组a的左半部继续搜索x;如果x>a[n/2],则 if(StartPos == 0xffff) return 0;//如果没查到则返回0(无只要在数组a的右半部继续搜索x,按此规则不断循 效的GB2312编码)

· 24 · 计算机技术与发展 第19卷

找结束地址 单片机,在24M H z晶振频率的情况下,二分法查找方

Index2=PositionIndex[Start Pos+4] 3256 +PositionIndex 式下每个字符的平均查找时间大约为1毫秒,比二级[StartPos+5] ; 索引顺序搜索快3倍左右。而对于32位ARM7的

ARM 7的CPU内部具有乘法器,减少乘除运算带来的

//取出低字节Unicode存储地址后面两个地址的内容(字 效果就不太明显了。

节)组成GB2312编码

GBCode=Unicode To GB Table [ Start Pos+1 ] 3 256+Uni2 3 结束语code To GBTable[StartPo s+2] ; 采用文中所设计的Unico de编码和GB2312编码return GBCode; 的双向转换算法可以有效地减少转换表的存储容量,} 提高查找效率,特别对于编码容量固定但无统一转换2 算法的效率分析

2.1 存储效率 存储空间和CPU处理时间供程序使用。该算法使用

该算法设计的Un ic o de编码和GB2312编码的双 参考文献:

向转换表的总大小为37519字节,即使是程序存储空 [ 1 ]邱发林Unicode及中文到Unicode转换[J ] 科技信息,间只有64k字节的M CS- 51单片机系统,也可以使用 2006(3) :20- 21

该算法。 [2] 张晓培,李 祥从Unicode到GB K的内码转换[J]微计

2.2 查找效率 算机应用,2006(6) :757-759

在进行GB2312编码转换为Unicode编码的查找 [3 ] ETSI GTS GSM 03 40 Version 5 3 0 Di gital Cellular时

每个子项几乎都不超过128项,使用二分法最差情况 [6]徐妙君,张晓霞短消息控件的设计与实现[J ] 计算机技也只需要7次搜索,而两次搜索的总搜索次数在绝大 术与发展,2007,17 (8) :64-66

多数情况下都不需要14次。 同时,把Un ic o de编码分 [7]陈慧南数据结构———使用C++语言描述[M] 南京:东成高低两个字节分别处理,对8位CPU来说更容易获 南大学出版社,2001

得较高的处理效率。经实际程序测试,对于MCS- 51