一个线性时间复杂度的字符编码转换算法

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

2010年5月26日 | 归档于 程序
  1. Aifu
    2010年6月5日 21:53 | #1

    CueCurer是一个使用.NET Framework编写的cue文件编码批量自动转换器和扩展名修复器,用于解决因编码或扩展名错误等原因造成乱码或无法播放的问题。

    http://code.google.com/p/cuecurer/

    CueCode是是一个专门用来解决cue文件中乱码的软件,可以将Big5码的繁体中文转换成简体中文,或将特殊西欧字符(ISO 8859-1字符集中ASCII码大于等于128的字符)转换成GB拼音字符或形状近似的英文字符,或将日文(Shift-JIS)转换成中文GBK编码。

    http://www.comicer.com/stronghorse/software/html/CueCode.htm

    一不小心捡到了俩个……

发表评论

XHTML: 您可以使用这些标签: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
:wink: :-| :-x :twisted: :) 8-O :( :roll: :-P :oops: :-o :mrgreen: :lol: :idea: :-D :evil: :cry: 8) :arrow: :-? :?: :!: