win32 api提供的字符编码转换函数MultiByteToWideChar和WideCharToMultiByte的效率如何不大清楚,一般用途的情况下,字符串不会太长,线性还是O(n^2)还是指数复杂度,时间差是不会感觉出来的。不过这篇博文提出的算法,是确确实实的线性时间复杂度,也即O(n)。n是字符串的长度。余没有读过FireFox的字符转换代码,但应该也是线性时间复杂度。话说回来,这玩意如果能设计成O(n)以上,那还真是活见鬼了。这个算法的意义是,如果你不满意系统提供的转换函数时,可以自己整一套出来。
这个算法已经用在UniCue的Big5ToUnicode程序中。源码下载:http://unicue.googlecode.com/svn/trunk/,装个svn客户端会下得畅快点。
字符编码转换的关键是建立一个字符映射表。比如:
#Big5 Unicode
0x8140 0x4E17
0x8141 0x4E22
0x8142 0x4E2C
0x8143 0x4E55
0x8144 0x4E62
0x8145 0x4E8A
字符映射表可以是一个双向表,通过一方编码查询对方编码。但双向表的效率很低,双向转换还不如分成两个独立的单向转换。
上面的表其实是以Big5为主键的单向表,可以实现Big5到Unicode的查询(反过来查询不现实)。可以将它保存为txt文本,每次转换打开txt查询,不过只有傻子才这样做。
这里是一个相对完全的Big5到Unicode的映射:uao250-b2u.txt,由Mozilla TW提供。Windows系统自带的映射表CP950字符不全,Big5码中的日文假名到Unicode的映射缺失,导致使用MultiByteToWideChar转换或者通过IE转换会丢失字符。
既然不能使用txt文本来查询映射,那如何查询速度才快呢?
如果按Big5码的顺序将对应的Unicode字符全部放置在内存中,起始地址(假设是A)的Unicode字符对应的就是Big5的0x8140,如果来了一个Big5字符假设是0x9C5A,那么它所对应的Unicode字符的内存地址就是A+(0x9C5A-0x8140)*2(注意一个Unicode字符占据两个字节),访问这个地址读取两个Byte就得到Unicode字符。指针加偏移量,访问时间是常数,整个字符串转换不就是线性时间复杂度了嘛。
我们打开uao250-b2u.txt,共19782个Big5字符,最后一个字符0xFEFE,第一个字符0x8140,0xFEFE-0x8140再加1,是32191。等等!这可与文本中的字符数目不吻合啊?原来Big5编码并没有连续的占据0x8140~0xFEFE的全部空间,我们在使用uao250-b2u.txt建立映射表时必须将未定义的空间也全部填写上,映射到Unicode的什么字符其实没关系,不过看到有文章推荐是映射为0xFFFD。
单向映射表可以写代码时就码进去,当然还真有人这么干,也可以保存为硬盘上的一个文件,在进行转换时才读取文件,拷贝文件中的二进制流重建映射表。
下面是生成映射表文件的代码,可以以LittleEndian或BigEndian方式存放Unicode字符,但推荐LittleEndian方式。LittleEndian方式的映射表文件在拷贝到内存时,高低位顺序是正确的,可以直接赋给WCHAR字符。代码需配合Google svn上的uao250-b2u.txt(删除了Mozilla TW版的第一行和最后的空行)使用。输出得到的映射表文件b2u-little-endian.map大小是64382字节。
#include "stdafx.h"
#include <string>
#include <fstream>
#include <iostream>
using namespace std;
unsigned char CharToHex(char ch)
{
//0-9
if (ch >= '0' && ch <= '9')
return (ch - '0');
//9-15
if (ch >= 'A' && ch <= 'F')
return (ch - 'A' + 0xA);
//9-15
if (ch >= 'a' && ch <= 'f')
return (ch - 'a' + 0xA);
return(0);
}
int _tmain(int argc, _TCHAR* argv[])
{
string inFilename="uao250-b2u.txt";
ifstream infile(inFilename.c_str());
if (!infile)
{
cerr<<"Unable to open b2u.txt!\n";
return -1;
}
ofstream outfile_littleendian("b2u-little-endian.map",ios::binary);
if (!outfile_littleendian)
{
cerr<<"Can not open b2u-little-endian.map!\n";
return -1;
}
char LITTLEENDIANBOM[2]={'\xFF','\xFE'};
//outfile_littleendian.write(LITTLEENDIANBOM,2);
/*
ofstream outfile_bigendian("b2u-big-endian.map",ios_base::binary);
if (!outfile_bigendian)
{
cerr<<"Can not open b2u-big-endian.map!\n";
return -1;
}
char BIGENDIANBOM[2]={'\xFE','\xFF'};
outfile_bigendian.write(BIGENDIANBOM,2);
*/
string str;
int i=0;
int offset=0x8140;
char zero[2]={'\xFD','\xFF'};
while(getline(infile,str))
{
i++;
//读取Big5码位
int Big5offset;
Big5offset=CharToHex(str[5])+CharToHex(str[4])*16+CharToHex(str[3])*16*16+CharToHex(str[2])*16*16*16;
while(offset!=Big5offset)
{
offset++;
outfile_littleendian.write(zero,2);
}
offset++;
//注意Unicode字符在内存中是先低位后高位
//写入映射表可以以big_endian或little_endian方式
//推荐采用little_endian方式
unsigned char HighByte,LowByte;
HighByte=CharToHex(str[9])*16 +CharToHex(str[10]);
LowByte=CharToHex(str[11])*16+CharToHex(str[12]);
if ((HighByte>255)||(LowByte>255))
cerr<<"Error occur in Line "<<i<<"!\n";
outfile_littleendian.write((char*)&LowByte,1);
outfile_littleendian.write((char*)&HighByte,1);
/*
unsigned char bigEndian[2];
bigEndian[0]=CharToHex(str[9])*16 +CharToHex(str[10]);
bigEndian[1]=CharToHex(str[11])*16+CharToHex(str[12]);
outfile_bigendian.write(bigEndian,2);
*/
}
cout<<i<<" lines done!\n";
infile.close();
outfile_littleendian.close();
//outfile_bigendian.close();
return 0;
}
自定义的字符映射表这样就创建完毕啦。使用就很简单了。
使用了MFC中的CString和CFile的转换函数,当然也可以不用MFC这一套
Big5toUnicode中的b2u-CString.h:
//big5 to Unicode转换函数
#pragma once
#include "stdafx.h"
#define BIG5OFFSET 0x8140
//big5Str最后一个字符为终止符
CString Big5ToUnicode(const char* big5Str,UINT length)
{
CString unicodeStr;
unicodeStr=_T("");
if (!big5Str)
return unicodeStr;
if (length==0)
return unicodeStr;
TCHAR path[MAX_PATH]; //最长260
GetModuleFileName(NULL, path, MAX_PATH);
CString mapPath=CString(path);
int position=mapPath.ReverseFind('\\');
mapPath=mapPath.Left(position);
mapPath+=_T("\\b2u-little-endian.map");
//加载映射表
CFile loadMap;
if (!loadMap.Open(mapPath,CFile::modeRead))
{
loadMap.Close();
::AfxMessageBox(_T("Big5toUnicode map loading error!"));
return unicodeStr;
}
UINT mapLength=loadMap.GetLength();
char *mapBuffer=new char[mapLength];
loadMap.Read((void *)mapBuffer,mapLength);
loadMap.Close();
//转换
unsigned char low=0,high=0;
TCHAR chr=0;
for (UINT i=0;i<length;)
{
//big5码的字符是先高位后低位
//高位至少从0x81起
//big5Chr[1]:高位
//big5Chr[0]:低位
memcpy(&high,big5Str+i,1); //读取第一个byte
i++;
if (high>0x80) //第一个byte是高位
{
memcpy(&low,big5Str+i,1); //读取低位
i++;
}
else
{
low=high;
high=0;
}
chr=low+high*256;
if (chr<BIG5OFFSET)
{
unicodeStr.AppendChar(chr);
}
else
{
int offset;
offset=chr-BIG5OFFSET;
memcpy((void*)&chr,mapBuffer+offset*2,2);
unicodeStr.AppendChar(chr);
}
}
delete []mapBuffer;
mapBuffer=NULL;
return unicodeStr;
}
可执行的测试程序在此:http://code.google.com/p/unicue/downloads/list
评论