我的本科毕业设计（非水文，设计了一个新算法）：一种字符编码猜测工具的实现方法
摘要
自从进入计算机时代后，人们创造了许多编码，来表示各国的语言文字。这些编码从一开始设计时，就没有考虑到要和其它编码兼容，它们只是为某个国家或某种语言来服务的。
随着Internet的发展，各国间的联系更加紧密，出现在人们视野中的不再是单纯某个国家的文字，越来越多其他国家的文字出现在了本地的计算机上。再加上由于历史原因，即使是一个国家的文字，都可能会以多种编码形式出现。虽然，一种统一的编码Unicode流行起来了，并成为了发展趋势，但在目前的环境中，仍然存在着其他各种编码。这样，本地的计算机上就需要处理许多种的编码。
以错误的编码打开一个文本会导致乱码，人们需要知道文本具体的编码信息。人们需要手动选择各种编码，直到能够正确显示文本为止，这是个痛苦的过程。字符编码猜测工具能使人们从这种繁琐的过程中解脱出来。
现在已经有了一些字符编码猜测工具了，如IE和Mozilla都有这种功能。本文提出了另一种实现该工具的方法，实践证明，该方法具有很高的可靠性，效率也很高，并且简单易懂，可扩展。
识别语言种类是该工具的另一个副产品，目前上述两种浏览器提供了部分功能。本文提出的方法，能够猜测出更详细的语言信息，例如ISO-8859-1，UTF-8的语言信息。
关键字：
全球化，本地化，字符编码，编码猜测
Abstract
Since the beginning of the computer age, many encoding schemes have been created to represent various writing scripts/characters for computerized data. With the advent of globalization and the development of the Internet, information exchanges crossing both language and regional boundaries are becoming ever more important. But the existence of multiple coding schemes presents a significant barrier. The Unicode has provided a universal coding scheme, but it has not so far replaced existing regional coding schemes for a variety of reasons. Thus, today's global software applications are required to handle multiple encodings in addition to supporting Unicode.
The text can not be shown correctly if we open it with wrong encoding. It takes pains to choose all the encoding till the text is shown correctly. The encoding detection tool can help us.
Such tools exist in some browser like Mozilla and IE. This article is about a new and simple way to implement the tool. It is proved to be stable, efficient and extendable.
One additional function provided by this tool is to guess the language of the text. It can show the language information in more detail than Mozilla and IE. For example: language information for encoding UTF-8 and ISO-8859-1.
Keywords：
Globalization, Localization, Charset, Encoding detection
目录
3.2 字符分布方法（Character Distribute）… 11
3.3 双字符序列分布方法（2-Char Sequence Distribute）… 12
第一章 引言
1.1 背景
自从进入计算机时代以来，人们创造了许多使用计算机数据表示的编码方案来表达不同的文字/字符集。随着全球化和Internet的发展，跨语言和区域的信息交换越来越重要。但是现存的多种编码方案对此是一个屏障。Unicode提供了通用的编码解决方案，但是，迄今为止，各种各样的因素使它并没有代替现存的区域编码方案。除了W 3C 和IETF建议使用UTF-8作为缺省编码，比如XML，XHTML，RDF。因此，现今的国际化软件不仅要处理Unicode编码，还要处理其它多种不同的编码方式[1]。
以错误的编码打开一个文本会导致乱码的出现，人们需要知道文本具体的编码信息。网络上传播的HTML文件有时会通过标签指定编码，但这不是必需的，在实际情况中，能找到大量不带编码信息的HTML文件。即使是带有编码信息的HTML文件，也有可能因书写的错误，导致了错误的编码信息。
一种低效但是可行的方法是，可以逐个以每种编码来打开文本，直到能正常显示文本，不出现乱码为止。但人们会厌倦这种方法，因为那需要花费大量的时间。
一个自动猜测字符编码的工具能够把人们从这种琐碎的工作中解救出来，它能够自动猜测文本的编码形式，从而正确地显示文本。
看起来有些不可思议，但目前确实有了一些已经实现的工具，如IE，Mozilla等浏览器。它们提供一个自动选择编码的菜单，当遇到一个未指定编码的HTML文件时，便会自动调用这个工具，得出最可能的编码，然后正确显示网页。
之所以能实现这样的工具，是因为文本中会包含很多的编码信息，一些数据会在某些编码中经常出现，而有些则永远不会出现。还有一些编码会有一些标记的符号（字符序列），如UTF的BOM（字节顺序标记），ISO-2022的ESC序列，通过这些标记，能够准确地定位到该编码。
本文提供了实现这种工具的另一个方法，实践证明，该方法具有很高的可靠性，效率也很高，并且简单易懂，可扩展。
1.2 论文的主要工作
本论文从讨论各种编码的内部原理开始，从中找出猜测一部分编码可用的方法。如ISO-2022编码特殊的ESC序列，UTF的BOM，这些可以作为判断该种编码的一个依据。在分析各种编码中，可以看出大部分编码ASCII 0-127部分的代码点相同，这样可以去除一部分噪声数据。
接下来介绍了Mozilla字符编码猜测工具的实现。这样就能了解到其他工具是如何实现的，通过比较，可以看出本文实现的优越性以及不足，从而为他人选择本文实现作为一个依据。
最重要的部分，详细介绍了本实现。介绍了算法组间方差以及组间差，以及实现方法的概要。重点是放在可行性分析上，要让人们知道这个方法确实行的通，需要有大量的数据来说明。该 部分会有许多试验数据组成的表，来说明该方法是可靠的。最后，通过与Mozilla实现的比较，说明了该方法的优越性。
1.3 论文的组织
第一章：简要字符编码猜测工具出现的背景，以及实现该工具的可行性并介绍了作者的工作和论文的结构。
第二章：简单介绍了各种编码，包括ASCII码，ISO-2022编码，Unicode编码。
第三章：介绍了Mozilla实现字符编码猜测工具的方法。
第四章：详细介绍了作者提出的实现方法，包括主要算法，实现的方法要点。还给出了该方法的可信性分析，以实验数据说明该方法具有很高的可靠性。最后比较了本文实现和Mozilla的实现，从中可以看出本文实现的优越性。
第二章 各种编码介绍
2.1 ASCII码
ASCII（American Standard Code for Information Interchange），它的全称是“美国信息交换标准代码”。每个ASCII码以1个字节（Byte）储存，从0到数字127代表不同的常用符号，例如大 写A的ASCII码是65，小写a则是97。由于ASCII字节的七个位，最高位并不使用，所以后来又将最高的一个位也编入这套内码中，成为八个位的延伸 ASCII（Extended ASCII）码，这套内码加上了许多外文和表格等特殊符号，成为目前常用的内码[2]。
2.2 ISO-8859系列
ISO-8859字符集系列上世纪80年代中期由欧洲制造商协会（ECMA）设计并被ISO所接受，是一整套关于字母语言的8位图形字符集，现已有至少15种字符集存在该系列中。下面列举了其中10种，并指出了其对应的地区或语言[3]：
表2-1 字符集语言对应表
字符集名称
语系
语言或国家
ISO-8859-1
拉丁1（西欧）
法语，西班牙语，葡萄牙语，意大利语，德语，荷兰语，丹麦语，瑞典语，挪威语，英语，爱尔兰语，斯瓦西里语，班图语．．．
ISO-8859-2
拉丁2（东欧）
捷克语，匈牙利语，波兰语，罗马尼亚语，克罗地亚语，斯洛伐克语．．．
ISO-8859-3
拉丁3（南欧）
世界语，马耳他语，土耳其语．．．
ISO-8859-4
拉丁4（北欧）
格陵兰语，拉普兰语，爱沙尼亚语，拉脱维亚语，立陶宛语．．．
ISO-8859-5
斯拉夫语
保加利亚语，俄语，马其顿语，塞尔维亚语，乌克兰语．．．
ISO-8859-6
阿拉伯语
阿拉伯语．．．
ISO-8859-7
希腊语
希腊语．．．
ISO-8859-8
希伯来语
希伯来语，依地语．．．
ISO-8859-9
拉丁5（土耳其）
土耳其语．．（用一些土耳其字符代替拉丁１中很少使用的冰岛字符）．
ISO-8859-10
拉丁6（北欧Nordic）
整个北欧地区．．．（重新组织了拉丁４）
注意：
一个字符集可能用于多个地区，如ISO-8859-1，可以用于西欧，也可用于澳洲，北美等地区。
一种语言不一定只能被一种编码表示，如拉丁１到拉丁６都能表示德语。
每个字符集有256个字符，其中0-127部分与扩展ASCII码对应部分相同，128-159是一些很少被使用的控制字符，在ISO 6429中被称为C1集。区别在于160-255部分。下图为ISO-8859编码的结构图。
0 128 160 255
ASCII
C1集
区别部分
图2-1 ISO-8859编码结构图
图2-2和图2-3列举了2种字符集160-225部分的字符。
图2-2 ISO-8859-1（拉丁1）
图2-3 ISO-8859-7（希腊）
2.3 ISO-2022系列
对于像中文，日文，韩文这样的文字，无法只用8位来表示所有的字符。ISO 2022提供了这样一种技术，它能在一种字符编码中支持多种字符集，可以用8位或16位来表示一个文字（字符），是一种变长的编码，这样，就能表示所有的上述东亚字符了。该编码还有个显著的特点，就是所有的字节都是以0开始（ASCII的0-127部分），有效位数是7，所以在网络传输中，可以只传7位。但同时出现了一个问题，如何区分哪些是ACSII部分的字符，哪些是东亚字符？ISO 2022用到的是标号（designations ）和变换函数（shift functions）。
标号又称ESC序列（escape sequence），是一串以ASCII的ESC（ox1B）开头的字符串，特定的字符串指明所用的字符集。
变换函数指明以何种方式解释接下来的字符，包括以何种字符集解释，解释多长的字节（接下来的两个字节或所有新的变换出现前的字节）。
下面介绍一下ISO-2022-CN（中文），ISO-2022-JP（日文），以及ISO-2022-KR（韩文）的实现方式。
2.3.1 ISO-2022-CN
ISO-2022-CN有3种标号：SO标号，SS2标号和SS3 标号（SS3只出现于ISO-2022-CN-EXT中）。SO标号的形式是ESC $ )
ISO-2022-CN有4种变换：SI，SO，SS2，SS3（SS3变换只出现于ISO-2022-CN-EXT中）。
SI变换由一个字节ox 0F 指定，表明后面的字节都应该解释为ASCII，直到遇到另一个变换。文本以SI为默认的变换，没有出现其它SI变换时，所有字节都将被解释为ASCII，即文本以ACSII字符开头。对于文本的每一行，若有汉字字符存在，一定要指定一个SO标号，即上一行指定的标号在本行不起作用。在行结束之前，一定要变换到ASCII（SI），当然若本行不含汉字字符，就不需要这样的变换了，整个一行都是ASCII字符（关于ISO-2022-CN的形式语法，详见RFC 1922 7.1节）[5]。
SO变换由一个字节ox0E指定，表明接下来的字节由SO标号指定的字符集来解释。
SS2变换由两个字节ox1B4E指定，表明接下来两个字节由SS2标号指定的字符集来解释，之后的字节又将由之前定义的变换来解释（SI或SO）。
SS3变换由两个字节ox1B 4F 指定，表明接下来两个字节由SS3标号指定的字符集来解释，之后的字节又将由之前定义的变换来解释（SI或SO）。
该编码支持的字符集有ASCII，GB2312，CNS 11643-plane-1和CNS 11643-plane-2。
ISO-2022-CN所用的标号，变换函数，以及支持的字符集如表2-2所示，标号含义如表2-3所示。
表2-2 ISO-2022-CN 字符集变换函数对应表
字符集
变换函数
ASCII
SI
GB 2312, CNS 11643-plane-1
SO
CNS 11643-plane-2
SS2
表2-3标号含义
ESC $ ) A
表明在SO变换后的字节是由GB2312编码的汉字字符，直至出现另一个SO标号。
ESC $ ) G
表明在SO变换后的字节是由CNS 11643-plane-1编码的汉字字符，直至出现另一个SO标号。
ESC $ * H
表明紧接在SS2变换后的两个字节是由CNS 11643-plane-2编码的汉字字符，直至出现另一个SS2标号。
ISO-2022-CN-EXT是对ISO-2022-CN的一个扩展，支持汉字字符集：GB，Big5和CNS 11643，详见RFC 1922[5]。
2.3.2 ISO-2022-JP
ISO-2022-JP比ISO-2022-CN出现更早，与ISO-2022-CN类似，但更简单些，因为它没有用到变换函数，只用到了标号。标号（ESC序列）与字符集之间的对应关系如表2-4所示。
表2-4 ISO-2022-JP标号字符集对应表
ESC 序列
字符集
ESC ( B
ASCII
ESC ( J
JIS X 0201-1976 ("Roman" set)
ESC $ @
JIS X 0208-1978
ESC $ B
JIS X 0208-1983
JIS X 0201与ASCII基本相同，除了两个字符：反斜线符号（backslash）和tilde (~)。backslash被日元符号代替，tilde被overline代替。
JIS X 0208 字符集包括日本汉字，平假名，片假名和其它一些符号和字符。
若一行中含有JIS X 0208字符集，则在该行结束前，需要转换到ASCII或JIS X 0201字符集，这个转换指明了下一行开始所用的字符集。文本必须以ASCII结束，关于ISO-2022-JP的形式语法，详见RFC 1468[6]。
2.3.3 ISO-2022-KR
ISO-2022-KR也有标号和变换函数，如表2-5所示：
表2-5 ISO-2022-KR变换函数字符集对应关系及标号意义表
SO
KSC 5601
SI
ASCII
ESC $ ) C
在第一个SO变换出现前的某一行的开始出现一次
KSC 5601字符集包括Hangul，Hanja，图形和一些其它外来字符，每个字符由两个字节组成。
ESC $ ) C标号的出现表明将要出现KSC 5601字符集中的字符，至多出现一次。若未出现，表明所有的字符都是ASCII。关于ISO-2022-KR的形式语法，详见RFC 1557[7]。
2.4 Unicode
2.4.1 简介
从ISO-2022字符集的实现方式中，可以看到一种处理CJK（中文，日文，韩文）的方式，就是使用ESC序列和控制字符，这样就可以处理包含很多字符的语言了。Unicode标准使用了另一种方式，并且能处理更广泛的字符，包含了世界上所有被广泛使用的字符集。下面，来看一下这种编码方式。
Unicode是被Unicode协会开发和维护的一套工业标准字符集，在1988年被提出。Unicode字符集能够支持超过100万的字符，其开发的最终目的是能够支持所有语言的字符以及许多现在和过去世界上经常使用的符号。
最初，Unicode的设计目标是把每个字符设计成16位，不管该16位的字符出现于数据的何处，都能表示同一个字节。这样，最多能表示65,536个字符。
之后，Unicode就处于不断发展之中。这时候就不得不提与之关系密切的另一个标准：ISO/IEC 10646。这个标准的工作组成立于1984年，其目标与Unicode极其相似，就是设计一个国际字符标准，以使能够支持世界上所有的书写系统。这就是人们现在熟悉的通用字符集（UCS brief for Universal Character Set）。
1991年前后，两个项目的参与者都认识到，世界不需要两个不同的单一字符集。它们合并双方的工作成果，并为创立一个单一编码表而协同工作。两个项目仍都存在并独立地公布各自的标准，但Unicode协会和ISO/IEC JTC1/SC2都同意保持Unicode和ISO 10646标准的码表兼容，并紧密地共同调整任何未来的扩展[10]。
Unicode的设计者很快发现65,536个字符对于中文这样的象形文字来说是不够的，所以他们对16位编码作了改进，提出了UTF-16，允许超过100万的字符。ISO/IEC标准使用31位的代码空间（codespace），允许超过20亿的字符，但100万多的字符足够了，所以永久保留了一部分代码空间。
Unicode又提出了两种编码形式UTF-8和UTF-32，下面会作一些简介。
2.4.2 UTF-16
Unicode的代码空间是从U+0000到U+10FFFF，共分为17个面板，第0个面板是从U+0000到U+FFFF，称为基本多语言面板（BMP brief for Basic Multilingual Plane），包含了大多数常用的字符。其它16个面板称为辅助面板（Supplementary Planes），其中许多还未被分配到。
代码空间中有些代码点（codepoints）是永久不分配的，有些是保留作非字符用的。如每个面板的最后两个代码点U+nFFFE 和 U+nFFFF不能被编码成字符，软件设计者可以在内部处理中使用它们。还有许多保留的私有用途代码点，详见参考文献[11]。
有2048个特殊的保留代码点：U+D800到U+DFFF，这些点在UTF-16中被用作特殊用途——代理代码单元（surrogate code units或surrogates）。这2048个保留代码点被均分为两组，每组1024个代码点。0xD800–0xDBFF被称为高位代理（high surrogates），0xDC00–0xDFFF被称为低位代理（low surrogates）。一个高位代理加上跟在后面的一个低位代理组成一个代理对，一共有1,024×1,024 = 1,048,576种可能，正好包括了所有在辅助面板中的代码点，这样就能表示超过100万个字符了。
因为是用两个字节来表示一个字符或代理，所以涉及到字节序的问题。大端是以最重要的字节开始，次重要的字节结束，小端则相反。编码形式和字节序对应一个字符编码模式（character encoding scheme）。
UTF-16有3种字符编码模式，UTF-16BE（大端），UTF-16LE（小端），UTF-16（未指定端）。指定端的就非常容易处理了，对于未指定端的，一种方法是同时试两种字节序，若解析出的字符从一种语言跳向了另一种语言，就说明很大可能不是以该字节序编码的。
为了解决这个问题，代码点U+FEFF被指定为字节序标记（BOM brief for byte order mark）。字节序标记被放在文件或数据流的开始，两个相邻的字节oxFE和oxFF只有在一种字节序中能表示字符，因为U+FFFE是被保留的。oxFE+oxFF表明是大端，oxFF+oxFE表明是小端。字符U+FEFF还有另一个意思--ZERO WIDTH NO-BREAK SPACE，在未指定字节序的UTF-16编码文件开始的U+FEFF只会被解释为字节序标记。
字节序标记还有另一个用处：暗示字符编码。在绝大多数现存编码中，文件以0xFE 0xFF或 0xFF 0xFE开头是不太可能的，这个文件以UTF-16形式编码的可能性非常大。
2.4.3 UTF-8
UTF-8的设计是为了兼容现存的软件，这些软件被设计为处理8位的文本数据。所以有必要使Unicode字符集中ASCII 0x00至0x 7F 的部分仍像原来一样，用8位表示。
UTF-8用一个到四个的字节序列来表示整个Unicode代码空间（理论上最多可有六个字节长）。
表2-6展示了UTF-8编码的方式以及对应Unicode代码点的区间。
表2-6 UTF-8编码方式表
U-00000000 - U -0000007F :
0xxxxxxx
U-00000080 - U-000007FF:
110xxxxx 10xxxxxx
U-00000800 - U-0000FFFF:
1110xxxx 10xxxxxx 10xxxxxx
U-00010000 - U-001FFFFF:
11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
U-00200000 - U-03FFFFFF:
111110xx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx
U-04000000 - U-7FFFFFFF:
1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx
xxx的位置由字符编码数的二进制表示的位填入，越靠右的x具有越少的特殊意义，只用最短的那个足够表达一个字符编码数的多字节串。注意在多字节串中，第一个字节的开头“ 1 ” 的数目就是整个串中字节的数目[10]。
UTF-8没有字节序的问题，因为它是一个一个字节的处理数据的。但它也有BOM：EF BB BF，只是用来指示它是用UTF-8来编码的。
2.4.4 UTF-32
UTF-32用32位来表示一个字符，和Unicode代码空间中的字符是一一对应的。
UTF-32也有字节序的问题，用字节序列0x00 0x00 0xFE 0xFF和 0xFF 0xFE 0x00 0x00来表明大小端。
2.5 本章小结
本章介绍了ASCII码，ISO-8859编码，ISO-2022编码，以及Unicode。了解这些编码的内部实现原理，是本文实现的需要。后面章节会介绍识别ISO-2022编码的状态机，用到的就是这边的编码知识。用BOM来识别UTF编码也需用到Unicode编码的知识。本章是本文实现的理论基础。
第三章 Mozilla字符编码猜测实现方法
Mozilla使用的是三种不同的检测文本数据编码方法的综合：编码模式方法，字符分布方法，双字符序列分布方法。
3.1 编码模式方法
对每一个编码模式，都有一个相应的状态机被用来验证这种特定编码的字节序列。对检测器收到的每一个字节，它将会被输入到每一个可用的，活动的状态机中，每次一个字节。状态机基于前一个状态和它所收到的字节来改变它的状态。自动检测器对状态机的三种状态感兴趣[1]：
l START状态：这种状态代表两种情形，初始化，或是代表字符集的一个合法字节序列已被验证。
l ME状态：这种状态代表状态机验证到了字符集特有的一个字节序列，并且其它可能的字符集不包含这个字节序列。这会导致检测器立即返回一个确定的回答。
l ERROR状态：这种状态代表状态机验证了字符集的一个非法字节序列。这会立即导致对这种字符集的否定回答。检测器从此将会排除这种编码方式，不作考虑。
3.2 字符分布方法（Character Distribute）
无论哪种语言，总有一些字符比其它字符更常用。利用这个事实，我们可以对每种语言建立起相应的数据模式。对那些字符数较多的语言，比如汉语，日语和韩语，尤其有用。
判断是否属于某个编码的度量是分布率和可信度。一个给定编码中的所有字符会被分到两个类别中，“经常使用的”和“非经常使用的”。如果一个字符是出现在出现频率分布表中的前512个字符中，它会被分类到“经常使用”。之所以选择512，是由于它在上述字符较多语言的输入文本中都覆盖了很大一部分的百分比，同时仅占据一小部分的代码点。
分布率的定义如下：
分布率=出现在512个最常用的字符中的字符数量/出现在剩下字符中的字符数量
可信度的定义如下：
可信度 = 实际分布率 / 理想分布率
实际分布率是对于待测文本应用分布率公式计算得来的值，理想分布率是事先得到的，一般是对于该编码的大量样本应用分布率公式得到的，而且这个值是和语言相关的。
可信度越大，说明越有可能是该编码。若对于很大的文本来说，在该编码上的可信度应该接近于1。如何判断是不是该编码，要用到两个阈值，一个是可信的阈值，一个是不可信的阈值。高于可信的阈值，说明是该编码，低于的话，说明不是该编码[1]。
3.3 双字符序列分布方法（2-Char Sequence Distribute）
对仅使用很少一部分字符的语言来说，我们需要比统计单字元出现率更进一步。字符组合揭示了更多的语言-字符特性。我们定义双字符序列为在输入文本中 接连出现的2个字符，在这种情况中，顺序是非常重要的。由于在一种语言中，并不是所有字符都具有相同的出现率，双字符序列分布非常倾向于与语言/编码相关。这种特性可以用在语言检测上。在检测字符编码的时候，这会导致更好的可信度，在检测单字节编码上很有用处。
序列分析没有对所有的字符都进行。我们当然可以通过建立一个256×256的矩阵来包含所有的那些字符序列，但是，其中的许多对语言/编码分析来说是无关的。由于绝大多数的单字节语言仅使用数量不多于64个的字母，而最常 使用的64个字符几乎包含了所有语言中都有的字符。因此，矩阵可以缩减成为更小的64×64。所以我们使用64作为我们工作中的采样大小[1]。
计算分布率和可信度的方法类似字符分布方法。
3.4 复合方法
双字符序列分布方法可用来检测所有的单字节编码。编码模式方法可以用在UTF-8，ISO-2022-xx和HZ检测上。在UTF-8检测 中，对现有的状态机作了一点修改。UTF-8检测器的成功检测是在对多个多字节序列验证之后作出的。编码模式方法和字符分布方法一起作用在了对主要东亚字符编码进行检测上，例如GB2312，Big5，EUC-TW， EUC-KR，Shift_JIS和EUC-JP。
对日语编码，如Shift_JIS和EUC-JP，双字符序列分布方法同样也能用于检测，这是由于它们包含许多具有明显特征的平假名字符，这些平假名字符和单字节语言中的字母很相似。双字符序列分布方法在很少文本的情况下也能得到精确的结果。
上层的控制算法从ASCII验证开始。如果所有字符都是ASCII的，除了ISO-2022-xx和HZ编码外，其它检测器就无需使用了。
ISO-2022-xx和HZ检测器在遇到ESC或"~{"时会被载入，并且，在遇到8bit字节的时候，它们会被立即抛弃。
在验证UCS2编码的时候，会搜索BOM是否出现。我们发现有些网站在http流中发送0x00，但是，使用这个字节来验证UCS2编码被证明是不可信的。
如果任一处于启动状态的检测器接收到足够的数据并且达到了很高的可信度，整个自动检测过程将被终止，同时字符编码会作为结果返回。我们称之为快捷模式[1]。
3.5 本章小结
本章主要介绍Mozilla字符编码猜测工具的实现方式：编码模式方法，字符分布方法，双字符序列分布方法，以及三种方式的综合。本章的目的在于给出本文实现的一个比较对象，在比较中，说明本文实现的优越性。
第四章 字符编码猜测实现
4.1 理论背景
对于一段不是随机出现，而是有实际意义的文本来说，其内部总会有一些关联。一种很明显的关联是各种常用字符的出现频率总会很高，如对于中文，“的”、“了”之类的出现频率非常高。如同Mozilla的实现方式一样，实现中可以统计一些（512个）常用字符的分布率，然后同理想分布率比较，得出可靠度，来确定可能的编码。这种方法的一个缺陷是，它只对那些用两个字节编码的语言有效，如GB2312，Big5等，对于单字节的编码，如ISO-8859-2，就只能用其变通方式，双字符序列分布方法。而像UTF-8那样用不确定字节编码的，就没有办法用该种频率分析方法了，只能用编码模式的方法来确定。
这样，必然带来了分析程序的复杂性，同时导致了效率的低下。一开始，程序不能够确定用哪种方式来猜测编码，必须逐一试用。如先用状态机探测，接下来用单字符序列分析，接着再双字符序列分析。当然，可能在状态机探测时，就能得出了可信的结果，但从平均效率来讲，这种方法还是很低效的。
本文的出发点，是去找一种更简单，效率更好，但同样可靠的方法来猜测字符编码—单字节频率分析。
4.2 噪声数据
对各种字符编码进行深入研究后，能够发现，有一部分代码点大多数编码采用同一种形式来表示，那就是ASCII码0-127部分的代码点。除了像UTF-16，UTF-32之类的，对那部分代码作了特殊处理，对于这两种编码，本实现目前只能判断含有BOM的，还有待于扩展。
既然，本文实现所能处理的大部分编码该部分都相同，那么一种有效的方式，就是忽略这部分代码点。本文把这部分代码点称为噪声数据。当然，这样还是会忽略一些有效信息的，对于单字节编码的语言来说，如同Mozilla那样，可以用双字节分布方法，来得到更多的语言信息。在多字节编码情况下，组成一个字符的多个字节中，属于ASCII 0-127部分的也会被忽略掉。但在绝大多数情况下，损失的这部分信息是可以忍受的，在可行性分析中，本文将给出数据加以说明。
这样，本文实现所要做的，就是读入每一个字节，对于0-127部分的（字节高位是0），直接忽略，记录的是128-255的部分（字节高位是1）。
需要注意的是，一些编码所有的字符都是ASCII 0-127部分的，如ISO-2022-CN，ISO-2022-JP，ISO-2022-KR，HZ等，本文实现中需要对这些编码进行特殊处理，用到的方法是状态机识别。
4.3 主要算法
既然现在只有128个字节要考虑，本文实现可以方便地记录每个字节的情况了。这个不同于Mozilla，需要给出512个常用字符，这些字符在转换成int值后，不一定是连续的。这样，对于判断是不是属于这512个常用字符会有些困难，简单的方法和高效的办法难以两得。但本文实现的128个字符属于一个连续的区间，这样就很容易处理了，效率也很高。
主要的思想就是用到了数学统计的方法，本文提供两种方法，来计算待测文本和各种编码的关联度。
方法一：组间差
组间差定义为：组间差= ，其中 指待测数据集第 个分量的值， 指对于理想数据集，第 个分量的值。
方法二：组间方差
这边的方差，不同于统计学中一般的方差，由本人自己定义，暂称为组间方差，定义为：
组间方差= ，其中 指待测数据集第 个分量的值， 指对于理想数据集，第 个分量的值。
表4-1 直线L1
X1
X2
X3
X4
X5
X6
5
10
13
6
2
0
表4-2 直线L2
X1
X2
X3
X4
X5
X6
2
8
12
14
4
2
表4-3 直线L3
X1
X2
X3
X4
X5
X6
3
9
14
7
3
1
应用方法一：L3和L1的组间差=7，L3和L2的组间差=13
应用方法二：L3和L1的组间方差=9，L3和L2的组间方差=56
这两种方法都说明了L3和L1更相似一些。
这两种算法相同的地方是，都能得到一个非负值，这个值越小，就说明可信度越高。
从实验数据来看，两者的准确率比较相近。但组间差的效率优于组间方差，组间方差要多用到一次乘法。所以，实现中，用到的是组间差。
4.4 实现方法概要
首先需要一些编码的样本，这个是本实现花时间最多的地方，很多编码还找不到。对于一个文本，逐个字节进行分析。因为绝大部分编码ASCII码部分采用相同形式的编码（UTF-16等除外），所以在分析过程中忽略byte值在0~127之间的部分，对于128-255部分的，记录每个出现的频率，记录进数组（绝对值即为下标），称为出现频率数组AFA（Appear Frequency Array）。
因为要猜测的文本的大小是不固定的，所以实现中需要有一个统一的度量来生成AFA。
实现中用到的是单位是：出现次数/一百有效字节。有效字节是指去处噪声数据后得到的字节数。
对于所有编码的样本，计算出每个的出现频率数组，写入文件diff.table，组成出现频率表AFT（Appear Frequency Table）。这张表可以是一开始就给定的，在发布的版本中不需要给出编码样本。diff.table在必要时可以重构，如需要增加或删除一些编码时，本程序提供方法来重新构造diff.table。
一些编码会对应许多不同的语言，如UTF-8，ISO-8859-1等，同一编码的不同语言间AFA会有些差别，为更准确的猜测，本文实现对这些编码按语言进行分类，如UTF-8-cn，表示是中文UTF-8的编码。（域名和国家的对照表见附录）
有了AFT，再计算出待猜测文本的AFA，然后与AFT表中的每个AFA进行组间差或组间方差计算，取最小差对应的那个编码为猜测结果。
对于编码：ACSII，ISO-2022-CN，ISO-2022-KR，ISO-2022-JP，所有的byte值都在0~127之间，无法得到AFA。在第一遍对整个样本的遍历中，可以得到信息，是否该文件byte值在0~127间，然后进行第二遍遍历。此时用到的方法是设计一个有穷状态自动机DFA，依据的是各自的ESC序列：:
ISO-2022-CN : ESC $ ) A
ESC $ ) G
ESC $ * H.
ISO-2022-KR : ESC $ ) C
ISO-2022-JP : ESC $ B
ESC $ @
由ESC序列得到的DFA如图4-1所示：
图4-1 ISO-2022编码ESC序列的DFA
4.5 样本的获得
本文实现需要大量的样本，包括许多的测试样本。这里所有的样本都是在Internet上获得。根据各国的域名来访问各种网站，如：要访问法国的网站，则可以搜索www.*.fr。当然，在有一些该编码的文本后，就可以从中取一些作为关键字搜索，如：用“مروز”来搜索阿拉伯文字。
到达某个网页后，如何查看编码？有两个方法，一个是在页面源代码中查找关键字“charset”，可能会找到行：，说明该页面是以utf-8为编码的。但并不是所有的源代码中都会提供该关键字的。另一个方法，就是使用浏览器的功能，在IE中为菜单：查看->编码，Firefox中是：查看->字符编码。Firefox提供的信息会更详细一些。
如何保存网页？用复制-粘贴的方法是不可取的，这样，大部分情况下，这不会以想要的编码来保存，除非原来的编码是UTF-8等。需要保存的是整个HTML文件（Ctr-S保存），只有这样，原始的信息才不会丢失或转换成其它格式。但复制-粘贴方式提供了保存UTF-8编码的一种方式。如，一个网页若是以EUC-JP编码的，按此方式保存到文本文件时，选择以UTF-8为编码，这样就能得到以UTF-8为编码的日文样本了。
4.6 可行性分析
下面，将用一些数据来说明该方法的可行性。所有测试样本都来自Internet，所有的测试文本都是随机取得的。本文实现提供了方法，可以批量测试某个文件夹下的所有文件，这样就能有效提高工作效率。由于时间精力所限，无法进行详尽的分析，收集的样本并不是很多。但从这些数据中，可以看出该方法的准确性是很高的。
表4-4是所有编码应用两种方法的结果，这里每个都只测一个文本：
表4-4 所有编码运用两种方法得到的统计结果
编码
组间差
组间方差
最小值
次小值
最小值
次小值
GB2312
26
77
34
187
UTF-8-de
45
72
321
794
UTF-8-fr
38
74
204
1178
UTF-8-ir
18
125
24
1286
UTF-8-it
85
113
761
1016
UTF-8-cn
25
94
25
322
UTF-8-ru
26
109
46
1601
UTF-8-gr
10
113
10
1160
UTF-8-no
19
95
79
1321
UTF-8-es
24
61
52
459
UTF-8-pt
36
71
150
499
UTF-8-lt
37
76
123
731
UTF-8-pl
13
85
19
505
UTF-8-th
1
124
1
1777
UTF-8-si
18
79
44
767
UTF-8-jp
41
98
125
932
UTF-8-il
8
128
8
2541
UTF-8-cz
13
86
21
856
UTF-8-vn
24
110
32
782
UTF-8-tr
55
121
379
1017
UTF-8-ro
82
126
628
1210
UTF-8-am
10
104
10
1430
UTF-8-se
11
54
21
682
UTF-8-kr
13
112
13
507
Big5
33
69
63
164
Shift-JIS
22
90
26
1090
EUC-KR
28
72
30
166
EUC-JP
28
80
184
662
ISO-8859-1-de
33
105
201
2225
ISO-8859-1-fr
38
121
238
2849
ISO-8859-1-es
57
97
451
910
ISO-8859-1-pt
37
110
123
768
ISO-8859-1-se
30
102
274
2410
ISO-8859-1-is
45
94
365
1219
ISO-8859-1-ge
17
81
25
393
ISO-8859-2
29
101
133
1164
ISO-8859-2-pl
31
138
117
1362
ISO-8859-2-si
9
139
19
2833
ISO- 8859-2-c z
32
50
132
298
ISO-8859-2-ro
85
119
1543
3299
ISO-8859-7
13
80
17
426
ISO-8859-9
72
144
704
1451
ISO-8859-10
65
137
1391
2331
Windows-874
8
81
8
209
Windows-1250-cz
28
56
102
316
Windows-1250-si
122
136
2512
2613
Windows-1251
13
18
17
26
Windows-1255
23
85
41
341
Windows-1256
19
117
51
562
Windows-1257
77
104
637
962
ARMSCII-8
16
112
24
594
KOI8-R
5
73
5
374
表中加粗（红色）的数据表示猜测错误的情况（编码正确，但猜测语言错误），其余的都是表示猜测正确的情况。所有的编码都猜测正确了，除了猜测语言会有部分错误。这可能是由于这两种语言非常相近，也有可能是得到的样本非典型。即使是可能性最高的那个猜测错误，第二可能性的都是正确的结果。
组间差的最小值一般在100以内，组间方差在500内。最小值越小，说明可信度越高。次小值指名了第二可能性的编码。次小值和最小值之间的比例组间差一般超过1.5，组间方差超过3。比例越大，说明可信度越高。
从表中，可以看出准确编码的差值和最接近准确编码的那个值差距很大，这个说明了猜测结果是其它错误编码的可能性很小。
这些样本所含的数据都比较多，所以得到很高的准确率也不足为奇。若只含有少量的数据，准确率如何呢？下面这些表说明了这个问题。
表4-5到表4-16是两种方法在不同数据量的情况下各种编码的准确率情况：
表4-5 猜测GB2312的准确率
样本大小
组间差
组间方差
最小值准确率
次小值准确率
最小值准确率
次小值准确率
10字符
50%
70%
70%
100%
30字符
100%
100%
100%
100%
表4-6 猜测UTF-8-jp的准确率
样本大小
组间差
组间方差
最小值准确率
次小值准确率
最小值准确率
次小值准确率
10字符
90%
100%
100%
100%
30字符
100%
100%
100%
100%
表4-7 猜测UTF-8-ru的准确率
样本大小
组间差
组间方差
最小值准确率
次小值准确率
最小值准确率
次小值准确率
10字符
100%
100%
100%
100%
30字符
100%
100%
100%
100%
表4-8 猜测Windows1251的准确率（和Windows1250-si较相似）
样本大小
组间差
组间方差
最小值准确率
次小值准确率
最小值准确率
次小值准确率
10字符
80%
100%
70%
100%
30字符
100%
100%
80%
100%
表4-9 猜测Big5的准确率（和EUC-JP较相似）
样本大小
组间差
组间方差
最小值准确率
次小值准确率
最小值准确率
次小值准确率
10字符
90%
100%
80%
100%
30字符
100%
100%
90%
100%
表4-10 猜测UTF-8-kr的准确率（和EUC-JP较相似）
样本大小
组间差
组间方差
最小值准确率
次小值准确率
最小值准确率
次小值准确率
10字符
100%
100%
100%
100%
30字符
100%
100%
100%
100%
表4-11 猜测UTF-8-cn的准确率
样本大小
组间差
组间方差
最小值准确率
次小值准确率
最小值准确率
次小值准确率
10字符
100%
100%
100%
100%
30字符
100%
100%
100%
100%
表4-12 猜测UTF-8-ir的准确率
样本大小
组间差
组间方差
最小值准确率
次小值准确率
最小值准确率
次小值准确率
10字符
100%
100%
100%
100%
30字符
100%
100%
100%
100%
表4-13 猜测Shift-JIS的准确率
样本大小
组间差
组间方差
最小值准确率
次小值准确率
最小值准确率
次小值准确率
10字符
50%
100%
40%
40%
30字符
90%
100%
90%
100%
表4-14 猜测UTF-8-fr的准确率
样本大小
组间差
组间方差
最小值准确率
次小值准确率
最小值准确率
次小值准确率
10单词
100%
100%
100%
100%
30单词
100%
100%
100%
100%
表4-15 猜测UTF-8-de的准确率
样本大小
组间差
组间方差
最小值准确率
次小值准确率
最小值准确率
次小值准确率
30单词
90%
100%
90%
100%
60单词
100%
100%
100%
100%
表4-16 猜测ISO-8859-1-fr的准确率
样本大小
组间差
组间方差
最小值准确率
次小值准确率
最小值准确率
次小值准确率
10单词
100%
100%
100%
100%
30单词
100%
100%
100%
100%
表中最小值准确率是指一次性猜码正确的比率，次小值准确率是最小值和次小值中有一个猜码准确的比率。
这里测试的样本都很小，实际情况的文本数据量都要比这个大多了。样本大小分为两个精度级，字符数和单词数。对于CJK等象形文字，精度为字符数，即以每一个文字为单位。因为这些编码ASCII 0-127部分出现的频率比较少，即噪声数据较少，所以测试中能用相对较少的数据作为样本。但对于法语，德语这些语言，噪声数据的比例非常大，所以需要相对多一点的数据量，精度为单词数。
从这张表能看出，对于极少量的数据（30个字符或单词），本实现都能有接近100%的准确率，次小值准确率达到了100%。实际情况下的数据量会比这个大的多，这样，得到的AFA会更接近于理想的AFA，得到的结果就会更准确。对于这些数据，同样在IE6.0和Mozilla Firefox 1.5中测试过，得到的准确率结果是：
IE6.0<本文实现< Mozilla Firefox 1.5
这些数据表明，这个实现方法是可行的，在实际应用中有很高的准确率。
4.7 与Mozilla的比较
4.7.1 功能
从能够识别的编码来说，两种实现能识别数量相当的编码。
本文实现能够识别的编码：GB-2312，Big5，ISO-2022-CN，EUC-KR，ISO-2022-KR，Shift-JIS，EUC-JP，ISO-2022-JP，ASCII，UTF-8，ISO-8859-1，ISO-8859-2，ISO-8859-7，ISO-8859-9（土耳其），ISO-8859-10（挪威），Windows874（泰国），Windows1250，Windows1251（西里尔语），Windows1255（希伯来语），Windows1256（阿拉伯语），Windows1257（波罗的海），ARMSCII-8（亚美尼亚），KOI8-R（西里尔语）。
Mozilla能够识别，而本文实现不能识别的编码：EUC-TW，MacCyrillic，IBM855， IBM866，ISO-8859-5，Windows-1252，Windows-1253，TIS-620 (Thai)。
本文实现能识别，Mozilla不能识别的编码：ISO-8859-1，ISO-8859-9，ISO-8859-10，Windows874，Windows1256，Windows1257，ARMSCII-8。
不能够识别的那部分编码，绝大多数情况是由于在Internet上未能找到该编码的网页，缺少样本，如：EUC-TW，MacCyrillic，IBM855，IBM866，TIS-620 (Thai)，未找到这些编码的样本。
本文实现较Mozilla的一大优点在于能够更精确的定位语言。虽然Mozilla能够定位一些语言信息，特别是那种一个编码只对应一种语言的情况，如Shift-JIS一定为日文，但对于一种编码对应多种语言的情况，便不能给出语言信息了，如UTF-8，ISO-8859-1（Mozilla中用的是Window1252）。但本实现能够细化到语言层面，即便是一种编码对应多种语言，也能知道其具体语言的种类。
本文实现能够识别的语言：汉语（简体，繁体），日语，韩语，英语（ASCII），德语，法语，意大利语，土耳其语，挪威语，泰国语，西里尔语（俄语），阿拉伯语，波罗的海语，亚美尼亚语，希腊语，西班牙语，葡萄牙语，波兰语，斯洛文尼亚语，捷克语，越南语，罗马尼亚语，瑞典语。
4.7.2 准确率
在可行性分析中，对于较小的数据量，给出了准确性的比较，本实现的准确率小于Mozilla Firefox 1.5。因为Mozilla运用了多种方法，来确定编码，而本方法较简单，忽略了一部分有效信息。但即便是很少的数据，本实现也能达到接近100%的准确率。对于大量的数据，两者的准确率基本没有区别，都达到了100%。
4.7.3 效率与复杂性
Mozilla的实现需要用多种方法来判断字符编码：编码模式方法，字符分布方法，双字符序列分布方法。其中编码模式方法会用到许多的状态机，而且每个状态机都会被运行到。
相比之下，本实现只用到两种方法，单字节分布法和状态机识别方法，其中状态机识别方法中只存在一个状态机，用来识别ISO-2022编码和ASCII码。不同于Mozilla的实现，这里只需用到其中一种方法，在第一遍扫描样本后，就能得到信息，确定用哪种方法。计算最小组间差或方差的时间复杂度也是O（n），其中n为能猜测编码的总数。AFT是预先生成的，节约了大量的时间。空间复杂度也很小，这里没有读入整张的AFT，而是每次只读入其中的一个AFA，而Mozilla的实现需要读入大量的表。
本文实现的复杂性也低于Mozilla。直观来说，本文实现的代码量远低于Mozilla，只有500行左右。Mozilla用到很多状态机，而本文实现只用到一个。本文实现用的是单字节分布方法，所有的文本都统一处理，而Mozilla对多字节语言和单字节语言分开处理，并且对于每一种编码，需要单独的表。双字节编码用512个常用字符，单字节编码用到64×64的常用双字节序列表。
4.7.4 扩展性
Mozilla的实现方式具有很大的可扩展性，但这种扩展性是建立在对新加编码有一定深度了解的基础上。有了这个基础，才能写出判别这个编码的状态机，才能找出这个编码常用的字符集。至少从代码量上来说，会增加许多。
本文实现的扩展比起Mozilla更方便，对于一个新的编码，只需要有足够的样本，即使对它的编码原理一点都不了解，都能够很方便地加入到本实现所支持的编码中去。所做的只是在编码列表中加入该编码，然后重新生成AFT，存入diff.table即可。这个过程只是增加一行代码而已。
4.8 本章小结
本章是本文的重点，介绍了本文的实现方式。其中介绍了两种算法，组间差和组间方差，用来判断两种编码的相似性。在可行性分析中，给出了详细的数据，来说明本文实现猜测编码具有很高的准确率。最后是和Mozilla实现的比较，从功能，准确率，效率，复杂性，扩展性等方面来说明本文实现的优越性。
第五章 总结与展望
字符编码猜测工具在实际中有很广泛的应用，因为本地的计算机需要处理多种多样的编码。该工具能够使用户从繁琐的手动选择编码的过程中解脱出来，从而大大提高了生产效率。
虽然目前已经有了一些该种工具的实现，如Mozilla等，但这些工具一般实现都比较复杂。本文的一大创新是提出了一种简单的实现该工具的方法，单字节分布方法和状态机识别方法的结合。该方法具有很高的准确率，并且比起Mozilla有更高的效率，更好的扩展性，程序也更简单易懂。该实现能够判别的编码种类同Mozilla不相上下，并且在语言识别方面，功能更强大。
本文实现还有一些不完善的地方，如：可以添加可视化的界面，可以增加一些编码。将来的工作，就是完善这些地方，并推广这种方法，使之与一些流行的软件结合，运用到实际中去。
参考文献
[1] Shanjian Li、Katsuhiko Momoi，中文翻译来自http://blog.i5un.com/item/21，A composite approach to language/encoding detection，19th International Unicode Conference，November 2002
[2] ASCII码简介，http://www.pep.com.cn/200406/ca478658.htm
[3] The ISO 8859 Alphabet Soup，
http://www.unicodecharacter.com/charsets/iso8859.html
[4] ISO Latin 9 as compared with ISO Latin 1，
http://www.cs.tut.fi/~jkorpela/latin9.html#euro
[5] HF. Zhu、DY. Hu、ZG. Wang、TC. Kao、WCH. Chang、M. Crispin，RFC 1922 ： Chinese Character Encoding for Internet Messages，Network Working Group，March 1996
[6] J. Murai、M. Crispin、E. van der Poel，RFC 1468 Japanese Character Encoding for Internet Messages，Network Working Group，June 1993
[7] U. Choii、K. Chon、H. Park，RFC 1557 Korean Character Encoding for Internet Messages，Network Working Group，December 1993
[8] ISO 2022 (Encyclopedia)，
http://www.absoluteastronomy.com/enc3/iso_20222
[9] www.unicode.org
[10] Peter Constable，Understanding Unicode™ A general introduction to the Unicode Standard (Sections 1-5)，Computers & Writing Systems ，June 2001
[11] Markus Kuhn，中国LINUX论坛翻译小组xLoneStar译，UTF-8 and Unicode FAQ
[12] Mozilla字符编码猜测源码，
http://lxr.mozilla.org/seamonkey/source/extensions/universalchardet/src/base/
[13] Universal Encoding Detector，http://chardet.feedparser.org/docs/
[14] A tutorial on character code issues，http://www.cs.tut.fi/~jkorpela/chars.html
致谢
首先要感谢我的父亲和母亲，是你们默默地在背后支持我的学业，是你们在我最失意的时候给我以鼓励，你们是我动力的源泉，我的一切成就都属于你们。
也要感谢我的导 师张瑾玉 老师。对于我的论文，她给予了很多的修改意见，使我能够顺利完成论文。您严谨求实、孜孜不倦的治学态度，令人佩服。
还要感谢IBM上海CDL的同事们，在将近半年的实习中，我真的学到了很多很多。感谢你们对我的悉心指导，让我对自己有了新的认识。这段经历，是我人生的一大笔财富。
感谢我的舍友以及同学。在学习中，你们给了我很多支持与帮助，在生活中，你们给了我很多快乐。
感谢南京大学软件学院的所有老师，有了你们辛勤的劳动，才会有我们美好的未来。能在软件学院学习，真的是我的荣幸，在这里遇见那么多的好老师，学到那么多的知识。
附录：部分域名国家（地区）对照表
域名
国家（地区）
域名
国家（地区）
cn
中国
vn
越南
tw
中国台湾
si
斯洛文尼亚
hk
中国香港
hr
克罗蒂亚
fr
法国
il
以色列
de
德国
lr
利比里亚
se
瑞典
pl
波兰
is
冰岛
jp
日本
ru
俄罗斯
kr
韩国
ge
格鲁吉亚
it
意大利
am
亚美尼亚
th
泰国
ro
罗马尼亚
pt
葡萄牙
tr
土耳其
cz
捷克
ir
伊朗
gr
希腊
sy
叙利亚
no
挪威
es
西班牙
lt
立陶宛
手机扫一扫
移动阅读更方便
你可能感兴趣的文章