语言编码检测的复合方法.docx

一种语言/编码检测的复合方法1. 概要本文提供了三种自动检测方法来判定无明显字符集声明的文档的编码。我们将分别讨论每种方法的优点和缺点，并提供一种复合的、更有效的方法来检测编码，这样，三种检测方法就可以互为补充。我们认为自动检测在使浏览器用户避免经常使用编码菜单手动选择编码上很有用，同时在编码菜单很少出现的情况下，提供了更合理的处理方式。我们假设，文档转化到Unicode 对用户是透明的。无论字符编码采用的是某种Unicode 编码还是本地编码，用户仅需知道字符最终显示是正确的就行了。好的自动编码检测能有效地帮助用户处理大部分编码事项而无需用户手动参与。2. 背景自从进入计算机时代以来，人们创造了许多使用计算机数据表示的编码方案来表达不同的文字/字符集。随着全球化和Internet 的发展，跨语言和区域的信息交换越来越重要。但是，现存的多种编码方案对此是一个屏障。Unicode 提供了通用的编码解决方案，但是，迄今为止，各种各样的因素使它并没有代替现存的区域编码方案，尽管W3C 和IETF 建议使用UTF-8 作为缺省编码，比如在XML、XHTML 或RDF 中。因此，现今的国际化软件不仅要处理Unicode 编码，还要处理其它多种不同的编码方式。我们当前的工作是在开发Internet 浏览器的环境中开展的。为了处理当前Web 上使用不同编码的各种语言，我们做了许多努力。为了获取正确的显示结果，浏览器需要利用HTTP 服务器返回的编码信息、网页或者最终由用户通过选择编码菜单而得到的编码方式。不幸的是，此类信息在许多HTTP 服务器和网页中是缺失的。此外，大部分用户没有能力手动地通过编码菜单来进行操作。如果没有编码信息的话，网页有时就会显示为“垃圾”字符，用户就无法得到他们想要的信息。这最终会导致用户认为他们的浏览器有故障或者有Bug。由于越来越多的Internet 标准协议指定Unicode 作为缺省的编码方式，网页将会不容置疑地转向使用Unicode 来编码。好的通用自动检测方法可以对这种转向提供重要的贡献，因为它们得工作很自然，无需用户使用编码菜单。在这种情况下，渐进的转向将会以用户不易察觉的方式进行，这是因为对用户来说，网页总会正确显示，他们无需考虑使用编码菜单。这种平滑的转变将使编码对用户来说越来越不需要关注。自动检测在这种场景中将非常关键。3. 问题范围3.1 通用模式首先让我们从通用的模式开始。对大多数应用，下面的示例将代表一个自动检测使用的通用框架：输入数据- 自动检测器- 返回结果应用程序接受自动检测器返回的结果，并且将信息用于不同的用途，如设置数据编码、显示原始创建者的数据、将它传给其他的程序等等。本文讨论的自动检测方法将使用Internet 浏览器作为应用环境，其他的应用也可以很容易地移植。3.2 浏览器和自动检测浏览器可以使用某种检测算法来自动检测网页的编码方式。一个程序可以潜在的在假定不同编码的前提下，对一段文本做出随意的解释，但是，除了一些极端罕见的情况外，只有一种解释才是网页作者想要的。这就是为什么通常对用户来说，只有指定的语言才能正确合理地显示网页。为了列出设计自动检测算法时的主要因素，我门对输入文本及步骤作如下假定，以网页数据为例。对某种语言来说，输入文本由对读者来说具有可读性的单词/句子组成(即数据具有非垃圾性)。输入文本是从Internet 上的典型网页中取得的(即数据不是从一些消失的或者古代的语言中取得的)。输入文本中有可能包含和编码无关的、额外的噪音数据。如HTML 标签、无关的单词(如出现在中文文档中的英文单词)、空格和其它的格式/控制字符等。对自动检测来说，要包含所有已知语言和编码方式几乎是一项无法完成的任务。在现有的方法中，我们试图包含所有东亚语言中常用的编码，同时，对单字符检测也提供了一种通用模式。俄语编码被选择作为后一种检测方法实现的例子，同时也作为单字符检测测试的基础。目标中的多字节编码方式包括UTF-8、Shift-JIS、EUC-JP、GB2312、Big5、EUC-TW、EUC-KR、ISO2022-XX 和HZ。提供一种通用模式来处理单字节编码。俄语编码(KOI8-R、ISO8859-5、window1251、Mac-cyrillic、ibm866 和ibm855)将作为实现的例子，同时也是测试的基础。4. 自动检测的三种方法4.1 介绍在这一节中，我们将讨论3 种不同的检测文本数据的编码的方法，它们是：编码模式方法；字符分布；双字符序列分布。每种方法在单独使用的时候都有它的长处和不足，但如果我们以互补的方式使用所有3 种方法的话，结果将是非常理想的。4.2 编码模式方法这种方法在检测多字节编码的时候也许是最显而易见的方法，通常也是最容易使用的方法。在任何多字节编码模式中，并不是所有可能的编码点都被使用的。如果在验证特定编码的时候碰到一个非法字节或非法字节序列(如无用的编码点)，我们就可以立即判断出这种编码猜测是不正确的。一小部分编码点同样也能代表特定的编码方式，这样，我们也可以利用这一事实立即做出正确的判断。Frank Tang(Netscape Communications)开发了一种非常有效的、基于编码模式的、通过使用并行状态机(parallel state machine)来检测字符集的算法。他的基本思想是：对每一个编码模式，都有一个相应的状态机被用来验证这种特定编码的字节序列。检测器收到的每一个字节都将被输入到每个可用的、活动的状态机中，每次一个字节。状态机基于前一个状态和它所收到的字节来改变它的状态。自动检测器对状态机的三种状态感兴趣： START 状态：这种状态代表两种情形，即初始化或是代表字符集的一个合法字节序列已被验证。 ME 状态：这种状态代表状态机验证到了字符集特有的一个字节序列，并且其它可能的字符集不包含这个字节序列。这会导致检测器立即返回一个确定的回答。 ERROR 状态：这种状态代表状态机验证了字符集的一个非法字节序列。这会立即导致对这种字符集的否定回答。检测器从此将会排除这种编码方式，不作考虑。在一个典型的例子中，只有一个状态机会做出确定的回答，而其它的状态机会做出的否定的回答。我们当前的工作中使用的PSM(Parallel State Machine)版本是FrankTang 原先的工作改进后的版本。只要一个状态机达到START 状态，就意味着它成功检测了一个合法的字符序列，我们向状态机查询这种字符序列中总共有多少个字节。这个信息会用在2 个方面：首先，对UTF-8 编码方式来说，如果有许多多字节的序列都通过验证的话，输入的数据很少有可能不是采用UTF-8 编码的。因此，我们统计UTF-8 状态机验证过的多字节数。当达到一个特定的数量(即阀值)时，结论就可以做出了。其次，对于其它的多字节编码来说，这个信息可以输入到字符分布分析器(可以参阅下面的介绍)，这样，分析器就可以在字符数据而不是原始数据的基础上进行工作了。4.3 字符分布方法无论哪种语言，总有一些字符比其它字符更常用。利用这个事实，我们可以对每种语言建立起相应的数据模式。这对于那些字符数较多的语言，比如汉语、日语和韩语尤其有用。我们经常听到与此有关的分布统计，但我们没有找到太多的公布结果。因此，为了继续讨论，我们依赖自己搜集的数据。4.3.1 简体中文我们对采用GB2312 编码的6763 个字符研究显示出如下的分布结果：Our research on 6763 Chinese characters data encoded in GB2312 shows the following distributional results:Number of Most Frequent CharactersAccumulated Percentage100.11723640.319831280.452982560.618725120.7913510240.9226020480.9850540960.9992967631.00000表1 简体中文字符分布表4.3.2 繁体中文对于采用Big5 编码的繁体中文， 台湾普通话推广委员会(TaiwansMandarin Promotion Council)年度研究显示了类似的结果：Number of Most Frequent CharactersAccumulated Percentage100.11713640.296121280.422612560.578515120.7485110240.8938420480.9758340960.99910表2 繁体中文字符分布表4.3.3 日语对日语，我们采用自己搜集的数据，并写了一个实用程序来分析它们。下面的表格显示了结果：Number of Most Frequent CharactersAccumulated Percentage100.27098640.667221280.770942560.857105120.9263510240.9713020480.9943140960.999811.00000表3 日语字符分布表4.3.4 韩语同样，对于韩语，我们采用自己从Internet 上搜集的数据，并用我们自己的实用程序分析它们，结果如下：Number of Most Frequent CharactersAccumulated Percentage100.25620640.642931280.792902560.923295120.9865310240.9994420480.9999940960.99999表4 韩语字符分布表4.4 分布结果的通用特性对于所有4 种语言，我们发现在我们定义的应用范围内，很少一部分的编码点占据了较大的百分比。此外，对这些编码点的更进一步的考察显示它们散布在一个很广的编码范围中，这给了我们一种克服在编码模式分析中遇到的通用问题的途径，即不同国家的编码有可能共享一些相互重叠的代码点。由于这些语言中最常出现的字符集具有我们上面描述的特性，因此，在编码模式方法中不同编码有相互重叠的问题，将在分布方法中变得无关紧要了。4.5 分析算法为了验证某种语言基于字符出现频率/分布的统计特性，我们需要一个从文本输入流中计算出一个数值的算法。这个数值将表明文本是某种字符集编码的可能性。一个很直观的做法是用每个字符的出现频率权重来计算这个值。不过，从我们对不同字符编码的经验看，我们发现这种做法并不是必须的，而且它占用了太多CPU 处理能力和过多的内存。一个简单的版本同样提供了很令人满意的结果，并且只使用非常少的资源，同时运行得很快。在我们当前的方法中，一个给定编码中的所有字符会被分列到两个类别中：“经常使用的”和“非经常使用的”。如果一个字符出现在出现频率分布表中的前512 个字符中，它将被分类到“经常使用”。之所以选择512，是由于它在所有4 种语言的输入文本中都覆盖了很大一部分的百分比，同时仅占据很小一部分的编码点。在输入文本中，我们以批处理的方式统计每个类别中字符的数量，然后计算一个我们称之为分布率(Distribution Ratio)的浮点值。分布率的定义如下：分布率= 出现在512 个最常用的字符中的字符数量/ 出现在剩下的字符中的字符数量每一种检测过的多字节编码方法都显示了独特的分布率。从分布率出发，我们可以对原始输入的文本对一个给定的编码方法来计算可信度。下面对每种编码方法的讨论将会对这个问题说得更清楚一些。4.6 分布率和可信度让我们分别通过4 种语言的数据来查看分布率的不同。注意，术语“分布率”代表两个意思。“理想”的分布率是对语言/字符集的定义而不是对编码的定义。如果某种语言/字符集表现为多种编码方式，那么对每一种编码，我们通过将输入数据分类为“经常使用的”或“非经常使用的”来计算“实际上的”分布率，然后将这个值和理想的语言/字符集分布率进行比较。基于实际上获得的分布率，我们可以计算输入数据对每一种字符集的可信度。具体描述如下。4.6.1 简体中文(GB2312)GB2312 包含两级中文字符，1 级包含3755 个字符，2 级包含3008 个字符。1级字符比2 级字符常用，同时，不难知道512 个最常用的字符都包含在GB2312的1 级字符中。由于1 级字符按照发音来排序，因此，512 个最常用的字符几乎完全分散在3755 个编码点中。尽管这些字符只占据1 级字符的所有编码点中的13.64%，但在典型的中文文本中，它们却有79.135%的出现机会。在理想的状况下，一段包含足够多的字符的中文文本会给我们返回如下结果：分布率= 0.79135/(1-0.79135) = 3.79并且，对使用同样的编码方案随机生成的文本来说，不考虑2 级字符的话，分布率大致为：512/(3755-512) = 0.157如果我们将2 级字符考虑进去的话，我们假定1 级字符中每个字符出现的概率为p1，2 级的为p2，计算的公式将是：512*p1/(3755*p1+3008*p2512*p1) = 512/(3755+3008*p2/p1-512)很明显，这个值将更小。在后面的分析中，我们仅使用最坏的情况作为比较。4.6.2 Big 5Big5 和EUC-TW(如CNS 字符集)编码具有类似的情况。Big5 同样将中文字符编码成2 级。最常用的512 个字符均匀的分布在5401 个1 级字符中。从Big5编码文本中得到的理想分布率是：分布率= 0.74851/(1-0.74851) = 2.98并且，对随机生成的文本，分布率为：512/(5401-512) = 0.105由于Big5 的1 级字符基本上等同于CNS 字符集的1 级字符，所以对EUC-TW来说，可以适用同样的分析。4.6.3 日语Shift_JIS和EUC-JP对日语来说，平假名和片假名比日文汉字更常用。由于Shift-JIS 和EUC-JP将平假名和片假名编码在不同的编码区域，因此我们仍然可以使用上述方法将这两种编码区分开。那些在512 个最常用的字符中出现的日文汉字字符仍然分布在2965 个1 级JIS 日文汉字集中。同样的分析得出如下的分布率：分布率= 0.92635/(1-0.92635) = 12.58对随即生成的日文文本数据，分布率最少为：512/(2965+63+83+86-512) = 0.191上列计算中包含了Hankaku 片假名(63 个)、平假名(83 个)和片假名(86 个)。4.6.4 韩语EUC-KR在EUC-KR 编码中，实际使用在典型的韩语文本中的中文字符可以忽略不计。使用这种编码的2350 个韩语字符按照发音排列。在我们分析了大量的韩语文本数据后得到的频率表中，最常用的字符均匀地分布在2350 个代码点中。用同样的分析方法，在理想的情况下，我们得到：分布率= 0.98653/(1-0.98653) = 73.24对随机生成的韩语文本，分布率为：512/(2350-512) = 0.2794.6.5 计算可信度从前面对每一种语言的讨论，我们可以以如下的形式定义出每一种数据集的可信度：Confidence Detecting(InputText)for each multi-byte character in InputTextTotalCharacterCount+;if the character is among 512 most frequent onesFrequentCharacterCount+;Ratio = FrequentCharacterCount/(TotalCharacterCount-FreqentCharacterCount);Confidence = Ratio/CHARSET_RATIO;Return Confidence;对每一种数据集的可信度定义为输入数据的分布率除以从上面分析得出的理想分布率。4.7 双字符序列分布方法对于仅使用很少一部分字符的语言来说，我们需要比统计单字符出现率更进一步。字符组合揭示了更多的语言/字符特性。我们定义双字符序列为在输入文本中接连出现的2 个字符，在这种情况下，顺序是非常重要的。由于在一种语言中并不是所有字符都具有相同的出现率，双字符序列分布非常倾向于与语言/编码相关。这种特性可以用在语言检测上。在检测字符编码的时候，这会导致更好的可信度，在检测单字节编码上很有用处。用俄语举例来说。我们下载了20MB 的俄语纯文本，并且编写了一个程序来分析文本。这个程序发现了总共为21199528 个双字符序列。在我们发现的序列中，有一些是和我们的考察无关的，比如空格-空格组合，这些序列被认为是噪音序列，并且它们的出现没有被包含在分析中。在我们用来检测俄语的数据中，除去这些噪音数据，还剩下20134122 个双字符序列。总共占据我们从数据中所发现得序列的95%。用来建立我们地语言模式的序列可以被分为4096 个不同的序列，并且，其中的1961 个序列在我们的20134122 个样本中出现次数少于3次。我们称这些序列为这种语言的负序列集。对单字节语言，我们定义如下的可信度：Confidence Detecting(InputText)for each character in InputTextif character is not a symbol or punctuation characterTotalCharacters+;find its frequency order in frequency table;if (Frequency order SampleSize)FrequentCharCount+;if we do not have lastCharlastChar = thisChar;continue;if both lastChar and thisChar are within our sample rangeTotalSequence+;if Sequence(lastChar, thisChar) belongs toNegativeSequenceSetNetgativeSequenceCount+;Confidence = (TotalSequence NegativeSequenceCount)/TotalSequence* FrequentCharCount / TotalCharacters;return Confidence;在这个算法中，需要对下面的问题进行一些解释。首先，序列分析没有对所有的字符都进行。我们当然可以通过建立一个256*256 的矩阵来包含所有的那些字符序列，但是，其中的一大部分对语言/编码分析来说是无关的。由于绝大多数的单字节语言仅使用数量不多于64 个的字母，而最常使用的64 个字符几乎包含了所有语言中都有的字符，因此，矩阵可以缩减小为64*64。所以我们使用64 作为采样的大小。我们选择用来建立模式的64个字符是基于频率统计并作了相应调整后的，有些字符，比如0x0d 和0x0a，在我们看来与空格(0x20)很相似，所以被我们从样本中移除了。其次，对于所有被64*64 矩阵模式包含的序列，其中的许多同样对检测语言/编码来说是无关的。几乎所有的单字节语言编码都包含ASCII 子集；在其它的语言数据中，英语单词也会比较常见，尤其在网页中；空格-空格序列对任何的语言编码来说明显是无关的。所有这些在我们的检测中都被认为是噪音数据，并且通过过滤被移除了。最后，在计算可信度上，我们需要同时统计出现在和不出现在我们采样范围内的字符数。如果一个小的采样数据中的大部分字符都出现在我们的采样范围内的话，由于在这种情况下负序列很少出现，因此序列分布本身将会返回一个较高的值。通过过滤，如果文本使用的是希望的编码的话，大部分提供给检测器的字符将会落在采样范围内。因此，通过统计负序列获得的可信度需要用这个数值调整一下。对前面叙述的总结如下： . 字符集验证的时候，只用到了所有字符中的一少部分子集。这保证了我们的模式不会过大。我们同样也通过减少噪音序列来保证我们的检测准确率更高。 . 每种语言模式都是使用脚本/工具生成的。 . 在处理Latin 字母表字符时： . 如果语言中没有使用Latin 字母的话，字母-字母序列被认为是噪音序列而从检测中被移除了(比如网页中出现在其他语言中的英语单词)； . 如果语言中使用Latin 字母的话，这些序列被保留下来用以分析。 . 落入采样范围的字符和没有落入采样范围的字符都被计数，这样，它们就可以用来计算可信度了。5. 三种方法的比较5.1 编码模式对许多单字节编码来说，所有使用到的编码点都是均匀分布的。甚至对那些包含一些无用代码点的编码方式来说，这些无用的代码点在其它的编码方式中很少被使用，因此，本方法不适合用于单字节编码检测。对多字节编码方式，本方法能得到一个很好的结果，并且很有效。但是，由于一些编码方法，如EUC-CN 和EUC-KR 几乎有完全类似的代码点，使用本方法很难区分将它们区分出来。考虑到浏览器通常不会包含大量文本的事实，我们必须使用其它的方法来检测编码。对于7bit 的编码方式，如ISO-2022-xx 和HZ，由于它们使用了容易识别的转义序列或变换序列，本方法可以得到一个满意的结果。对编码模式方法可以概括如下： . 很适合处理7bit 的编码方式，如ISO-2022-xx 和HZ。 . 适合处理某些多字节编码，如Shift_JIS 和EUC-JP，但不适合处理其它的编码，如EUC-CN 和EUC-KR。 . 对单字节编码不是很有用。 . 能应用于任何类型的文本。 . 快速而有效。5.2 字符分布对多字节编码，尤其是那些编码模式方法不能有效处理的多字节编码来说，字符分布方法提供了很大的帮助，同时避免了对复杂上下文进行深入分析的麻烦。对单字节编码，由于输入的数据量通常很少，而且有太多可能的编码方式，除非在特定情况下，本方法不大可能取得理想的结果。由于双字符序列分布方法对这种情况能获得很好的检测结果，因此，我们没有在单字节编码检测中过多考虑使用本方法。对字符分布方法总结如下： . 很适合处理多字节编码方式。 . 只适用于特定文本。 . 快速而有效。5.3 双字符序列分布在双字符序列分布中，我们可以使用更多的数据信息来检测语言/编码。甚至在只有很少数据样本的情况下，也能得到好的结果。但是由于使用序列代替了单词(通过空格分隔)，在处理多字节语言的时候，矩阵将会变得很大。因此，本方法： . 很适合处理单字节编码。 . 对多字节编码方式来说，不是太适合。 . 在样本大小很小的情况下，也能获得好的结果。 . 只适用于特定文本。6. 复合方法6.1 组合三种方法在我们的字符集自动检测器所处理的语言/编码中，既有单字节编码，又有多字节编码。基于上面三种方法的定义，单独使用其中的任何一种都无法产生满意的结果。因此我们建议使用复合的方法来处理所有这些编码。双字符序列分布方法可用来检测所有的单字节编码。编码模式方法可以用在UTF-8、ISO-2022-xx 和HZ 检测上。在UTF-8 检测中，对现有的状态机作了一点修改。UTF-8 检测器的成功检测是在对多个多字节序列验证之后做出的(详见Martin Duersts(1977)。编码模式方法和字符分布方法一起作用在对主要东亚字符编码进行检测上，如GB2312、Big5、EUC-TW、EUC-KR、Shift_JIS 和EUC-JP。对日语编码，如Shift_JIS 和EUC-JP，双字符序列分布方法同样也能用于检测，这是由于它们包含许多具有明显特征的平假名字符，这些平假名字符和单字节语言中的字母很相似。双字符序列分布方法在文本很少的情况下也能得到精确的结果。我们试验了两种方法，一种使用双字符分布方法，另一种不使用，它们都取得了满意的结果。有一些网站包含许多汉字和片假名字符，但是仅有少量平假名字符。为了尽可能获得最好的结果，我们在日语编码检测上既使用了字符分布方法，又使用了双字符分布方法。这里有一个这三种检测方法结合在一起使用的例子。最上层的控制模块(对自动检测来说)算法如下：Charset AutoDetection (InputText)if (all characters in InputText are ASCII)if InputText contains ESC or call ISO-2022 and HZ detector with InputText;if one of them succeed, return that charset, otherwisereturn ASCII;elsereturn ASCII;else if (InputText start with BOM)return UCS2;elseCall all multi-byte detectors and single-byte detectors;Return the one with best confidence;对以上代码片断序列的概括如下： . 很大一部分网站仍然使用ASCII 编码。上层的控制算法从ASCII 验证开始，如果所有字符都是ASCII 的，则除了ISO-2022-xx 和HZ 编码外，其它检测器就无需使用了。 . ISO-2022-xx 和HZ 检测器在遇到ESC 或时会被载入，并且在遇到8bit 字节的时候，它们会被立即抛弃。 . 在验证UCS2编码的时候，会搜索BOM是否出现。我们发现有些网站在HTTP流中发送0x00，但是使用这个字节来验证UCS2 编码被证明是不可信的。 . 如果任一处于激活状态的检测器接收到足够的数据并且达到了很高的可信度，则整个自动检测过程将被终止，同时字符编码会作为结果返回。我们称之为快捷模式。6.2 测试结果作为本文中极力推荐方法的测试，我们将我们的检测器应用在了100 个流行的，但是没有基于文档或服务器发送HTTP 字符集信息的国际网站。对包含在我们检测器中的全部编码方式来说，我们可以获得100%的准确率。例如，当我们访问一个没有提供字符集信息的网站(www.yahoo.co.jp)，我们的字符检测器生成如下的输出：UTF8 is inactiveSJIS is inactiveEUCJP detector has confidence 0.950000GB2312 detector has confidence 0.150852EUCKR is inactiveBig5 detector has confidence 0.129412EUCTW is inactiveWindows-1251 detector has confidence 0.010000KOI8-R detector has confide