小熏的编程日记

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

相关文章:

Ansi to Unicode 1.0发布 UniCue项目始动 GBK、Shift-JIS、BIG5编码检测算法 ANSI2Unicode 1.0.3正式版发布 UniCue 1.3beta6 – 一个编码转换工具 Chinese Converter – 简繁繁简转换程序 tak的内嵌cue提取 flac的内嵌cue提取