admin 发布的文章

WinCE开发时，WINCE的虚拟设备配置

作者: admin
时间: 2021-08-26
分类: 默认分类
评论

WinCE开发，PlatformBuilder注册的虚拟机平台、设备信息，存放在一XML/XSL的配置文件中，

位置通常在：

C:\ProgramData\Microsoft\corecon\1.0\addons

C:\Users\XXX\AppData\Local\Microsoft\CoreCon\1.0

这两个目录下会存放一些以GUID为文件名的xsl文件，其中存储的就是虚拟机平台、设备信息。

比如，如下文件存放了CHSINT SDK For WinCE 6.0的配置信息

因此，如果希望通过VS调试一个与默认配置有差异的WINCE模拟环境，可以复制一个DEVICE项，并进行修改、调整。

[转载]最近涉及字符串列表存储，为加快检索速度，搜集了一些哈希函数，C语言的代码保存见内

作者: admin
时间: 2021-06-25
分类: 默认分类
评论

static unsigned long _crc32_table[256] ={0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988, 0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91,0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7, 0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9, 0xfa0f3d63, 0x8d080df5,0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172, 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423, 0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924, 0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d,0x76dc4190, 0x01db7106, 0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433, 0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01,0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e, 0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950, 0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0, 0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9,0x5005713c, 0x270241aa, 0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f, 0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad,0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a, 0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb, 0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc, 0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5,0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b, 0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55, 0x316e8eef, 0x4669be79,0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236, 0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28, 0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38, 0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21,0x86d3d2d4, 0xf1d4e242, 0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777, 0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45,0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2, 0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc, 0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693, 0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94, 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d};



unsignedlong crc32(unsigned long crc, unsigned char* input, intlen)

{inti;

    unsignedcharindex;

    unsignedchar*pch;

    pch=input;for( i = 0 ; i < len; i++)

    {

        index= (unsigned char)(crc^*pch);

        crc= (crc>>8)^_crc32_table[index];

        pch++;

    }returncrc;

}//ELF Hash Function
unsigned int ELF_Hash(unsigned char* input, intlen)

{

    unsignedint hash = 0;

    unsignedint x = 0;



    unsignedchar*pch;

    pch= (unsigned char*)input;for(unsigned int i = 0 ; i < len; i++)

    {

        hash= (hash << 4) + (*pch); //hash左移4位，把当前字符ASCII存入hash低四位。
        pch ++;if ((x = hash & 0xF0000000L) != 0)

        {//如果最高的四位不为0，则说明字符多余7个，现在正在存第7个字符，如果不处理，再加下一个字符时，第一个字符会被移出，因此要有如下处理。//该处理，如果最高位为0，就会仅仅影响5-8位，否则会影响5-31位，因为C语言使用的算数移位//因为1-4位刚刚存储了新加入到字符，所以不能>>28
            hash ^= (x >> 24);//上面这行代码并不会对X有影响，本身X和hash的高4位相同，下面这行代码&~即对28-31(高4位)位清零。
            hash &= ~x;

        }

    }//返回一个符号位为0的数，即丢弃最高位，以免函数外产生影响。(我们可以考虑，如果只有字符，符号位不可能为负)
    return (hash & 0x7FFFFFFF);

}///@brief BKDR Hash Function///@detail 本算法由于在Brian Kernighan与Dennis Ritchie的《The C Programming Language》一书被展示而得名，是一种简单快捷的hash算法，也是Java目前采用的字符串的Hash算法（累乘因子为31）。
template<class T>size_t BKDRHash(const T *str)

{

    register size_t hash= 0;while (size_t ch = (size_t)*str++)

    {        

        hash= hash * 131 + ch;   //也可以乘以31、131、1313、13131、131313..//有人说将乘法分解为位运算及加减法可以提高效率，如将上式表达为：hash = hash << 7 + hash << 1 + hash + ch;//但其实在Intel平台上，CPU内部对二者的处理效率都是差不多的，//我分别进行了100亿次的上述两种运算，发现二者时间差距基本为0（如果是Debug版，分解成位运算后的耗时还要高1/3）；//在ARM这类RISC系统上没有测试过，由于ARM内部使用Booth's Algorithm来模拟32位整数乘法运算，它的效率与乘数有关：//当乘数8-31位都为1或0时，需要1个时钟周期//当乘数16-31位都为1或0时，需要2个时钟周期//当乘数24-31位都为1或0时，需要3个时钟周期//否则，需要4个时钟周期//因此，虽然我没有实际测试，但是我依然认为二者效率上差别不大
}returnhash;

}///@brief SDBM Hash Function///@detail 本算法是由于在开源项目SDBM（一种简单的数据库引擎）中被应用而得名，它与BKDRHash思想一致，只是种子不同而已。
template<class T>size_t SDBMHash(const T *str)

{

    register size_t hash= 0;while (size_t ch = (size_t)*str++)

    {

        hash= 65599 * hash +ch;//hash = (size_t)ch + (hash << 6) + (hash << 16) - hash;
}returnhash;

}///@brief RS Hash Function///@detail 因Robert Sedgwicks在其《Algorithms in C》一书中展示而得名。
template<class T>size_t RSHash(const T *str)

{

    register size_t hash= 0;

    size_t magic= 63689;while (size_t ch = (size_t)*str++)

    {

        hash= hash * magic +ch;

        magic*= 378551;

    }returnhash;

}///@brief AP Hash Function///@detail 由Arash Partow发明的一种hash算法。
template<class T>size_t APHash(const T *str)

{

    register size_t hash= 0;

    size_t ch;for (long i = 0; ch = (size_t)*str++; i++)

    {if ((i & 1) == 0)

        {

            hash^= ((hash << 7) ^ ch ^ (hash >> 3));

        }else{

            hash^= (~((hash << 11) ^ ch ^ (hash >> 5)));

        }

    }returnhash;

}///@brief JS Hash Function///由Justin Sobel发明的一种hash算法。
template<class T>size_t JSHash(const T *str)

{if(!*str)         //这是由本人添加，以保证空字符串返回哈希值0
        return 0;

    register size_t hash= 1315423911;while (size_t ch = (size_t)*str++)

    {

        hash^= ((hash << 5) + ch + (hash >> 2));

    }returnhash;

}///@brief DEK Function///@detail 本算法是由于Donald E. Knuth在《Art Of Computer Programming Volume 3》中展示而得名。
template<class T>size_t DEKHash(const T*str)

{if(!*str)         //这是由本人添加，以保证空字符串返回哈希值0
        return 0;

    register size_t hash= 1315423911;while (size_t ch = (size_t)*str++)

    {

        hash= ((hash << 5) ^ (hash >> 27)) ^ch;

    }returnhash;

}///@brief FNV Hash Function///@detail Unix system系统中使用的一种著名hash算法，后来微软也在其hash_map中实现。
template<class T>size_t FNVHash(const T*str)

{if(!*str)    //这是由本人添加，以保证空字符串返回哈希值0
        return 0;

    register size_t hash= 2166136261;while (size_t ch = (size_t)*str++)

    {

        hash*= 16777619;

        hash^=ch;

    }returnhash;

}///@brief DJB Hash Function///@detail 由Daniel J. Bernstein教授发明的一种hash算法。
template<class T>size_t DJBHash(const T *str)

{if(!*str)    //这是由本人添加，以保证空字符串返回哈希值0
        return 0;

    register size_t hash= 5381;while (size_t ch = (size_t)*str++)

    {

        hash+= (hash << 5) +ch;

    }returnhash;

}///@brief DJB Hash Function 2///@detail 由Daniel J. Bernstein 发明的另一种hash算法。
template<class T>size_t DJB2Hash(const T *str)

{if(!*str)    //这是由本人添加，以保证空字符串返回哈希值0
        return 0;

    register size_t hash= 5381;while (size_t ch = (size_t)*str++)

    {

        hash= hash * 33 ^ch;

    }returnhash;

}///@brief PJW Hash Function///@detail 本算法是基于AT&T贝尔实验室的Peter J. Weinberger的论文而发明的一种hash算法。
template<class T>size_t PJWHash(const T *str)

{static const size_t TotalBits        = sizeof(size_t) * 8;static const size_t ThreeQuarters    = (TotalBits  * 3) / 4;static const size_t OneEighth        = TotalBits / 8;static const size_t HighBits        = ((size_t)-1) << (TotalBits -OneEighth);    



    register size_t hash= 0;

    size_t magic= 0;while (size_t ch = (size_t)*str++)

    {

        hash= (hash << OneEighth) +ch;if ((magic = hash & HighBits) != 0)

        {

            hash= ((hash ^ (magic >> ThreeQuarters)) & (~HighBits));

        }

    }returnhash;

}///@brief ELF Hash Function///@detail 由于在Unix的Extended Library Function被附带而得名的一种hash算法，它其实就是PJW Hash的变形。
template<class T>size_t ELFHash(const T *str)

{static const size_t TotalBits        = sizeof(size_t) * 8;static const size_t ThreeQuarters    = (TotalBits  * 3) / 4;static const size_t OneEighth        = TotalBits / 8;static const size_t HighBits        = ((size_t)-1) << (TotalBits -OneEighth);    

    register size_t hash= 0;

    size_t magic= 0;while (size_t ch = (size_t)*str++)

    {

        hash= (hash << OneEighth) +ch;if ((magic = hash & HighBits) != 0)

        {

            hash^= (magic >>ThreeQuarters);

            hash&= ~magic;

        }        

    }returnhash;

}



unsignedint RSHash(char* str, unsigned intlen)  

{  

    unsignedint b    = 378551;  

    unsignedint a    = 63689;  

    unsignedint hash = 0;  

    unsignedint i    = 0;for(i = 0; i < len; str++, i++)  

    {  

        hash= hash * a + (*str);  

        a= a *b;  

    }returnhash;  

}/*End Of RS Hash Function*/unsignedint JSHash(char* str, unsigned intlen)  

{  

    unsignedint hash = 1315423911;  

    unsignedint i    = 0;for(i = 0; i < len; str++, i++)  

    {  

        hash^= ((hash << 5) + (*str) + (hash >> 2));  

    }returnhash;  

}/*End Of JS Hash Function*/unsignedint PJWHash(char* str, unsigned intlen)  

{const unsigned int BitsInUnsignedInt = (unsigned int)(sizeof(unsigned int) * 8);const unsigned int ThreeQuarters     = (unsigned int)((BitsInUnsignedInt  * 3) / 4);const unsigned int OneEighth         = (unsigned int)(BitsInUnsignedInt / 8);const unsigned int HighBits          = (unsigned int)(0xFFFFFFFF) << (BitsInUnsignedInt -OneEighth);  

    unsignedint hash              = 0;  

    unsignedint test              = 0;  

    unsignedint i                 = 0;for(i = 0; i < len; str++, i++)  

    {  

        hash= (hash << OneEighth) + (*str);if((test = hash & HighBits)  != 0)  

        {  

            hash= (( hash ^ (test >> ThreeQuarters)) & (~HighBits));  

        }  

    }returnhash;  

}/*End Of  P. J. Weinberger Hash Function*/unsignedint ELFHash(char* str, unsigned intlen)  

{  

    unsignedint hash = 0;  

    unsignedint x    = 0;  

    unsignedint i    = 0;for(i = 0; i < len; str++, i++)  

    {  

        hash= (hash << 4) + (*str);if((x = hash & 0xF0000000L) != 0)  

        {  

            hash^= (x >> 24);  

        }  

        hash&= ~x;  

    }returnhash;  

}/*End Of ELF Hash Function*/unsignedint BKDRHash(char* str, unsigned intlen)  

{  

    unsignedint seed = 131; /*31 131 1313 13131 131313 etc..*/unsignedint hash = 0;  

    unsignedint i    = 0;for(i = 0; i < len; str++, i++)  

    {  

        hash= (hash * seed) + (*str);  

    }returnhash;  

}/*End Of BKDR Hash Function*/unsignedint SDBMHash(char* str, unsigned intlen)  

{  

    unsignedint hash = 0;  

    unsignedint i    = 0;for(i = 0; i < len; str++, i++)  

    {  

        hash= (*str) + (hash << 6) + (hash << 16) -hash;  

    }returnhash;  

}/*End Of SDBM Hash Function*/unsignedint DJBHash(char* str, unsigned intlen)  

{  

    unsignedint hash = 5381;  

    unsignedint i    = 0;for(i = 0; i < len; str++, i++)  

    {  

        hash= ((hash << 5) + hash) + (*str);  

    }returnhash;  

}/*End Of DJB Hash Function*/unsignedint DEKHash(char* str, unsigned intlen)  

{  

    unsignedint hash =len;  

    unsignedint i    = 0;for(i = 0; i < len; str++, i++)  

    {  

        hash= ((hash << 5) ^ (hash >> 27)) ^ (*str);  

    }returnhash;  

}/*End Of DEK Hash Function*/unsignedint BPHash(char* str, unsigned intlen)  

{  

    unsignedint hash = 0;  

    unsignedint i    = 0;for(i = 0; i < len; str++, i++)  

    {  

        hash= hash << 7 ^ (*str);  

    }returnhash;  

}/*End Of BP Hash Function*/unsignedint FNVHash(char* str, unsigned intlen)  

{const unsigned int fnv_prime = 0x811C9DC5;  

    unsignedint hash      = 0;  

    unsignedint i         = 0;for(i = 0; i < len; str++, i++)  

    {  

        hash*=fnv_prime;  

        hash^= (*str);  

    }returnhash;  

}/*End Of FNV Hash Function*/unsignedint APHash(char* str, unsigned intlen)  

{  

    unsignedint hash = 0xAAAAAAAA;  

    unsignedint i    = 0;for(i = 0; i < len; str++, i++)  

    {  

        hash^= ((i & 1) == 0) ? (  (hash <<  7) ^ (*str) * (hash >> 3)) :  

            (~((hash << 11) + (*str) ^ (hash >> 5)));  

    }returnhash;  

}/*End Of AP Hash Function*/  

//PHP中出现的字符串Hash函数
static unsigned long hashpjw(char *arKey, unsigned intnKeyLength)

{

    unsignedlong h = 0, g;char *arEnd=arKey+nKeyLength;while (arKey <arEnd) {

        h= (h << 4) + *arKey++;if ((g = (h & 0xF0000000))) {

            h= h ^ (g >> 24);

            h= h ^g;

        }

    }returnh;

}//OpenSSL中出现的字符串Hash函数
unsigned int lh_strhash(void *src)

{inti, l;

    unsignedlong ret = 0;

    unsignedshort *s;char *str = (char *)src;if (str ==NULL)return(0);

    l= (strlen(str) + 1) / 2;

    s= (unsigned short *)str;for (i = 0; i < l; i++) 

        ret^= s[i]<<(i&0x0f);return(ret);

}/** The following hash seems to work very well on normal text strings no

 * collisions on /usr/dict/words and it distributes on %2^n quite well, not

 * as good as MD5, but still good.*/unsignedlong OPENSSL_LH_strhash(const char *c)

{

    unsignedlong ret = 0;longn;

    unsignedlongv;intr;if ((c == NULL) || (*c == '\0'))return(ret);/*-

    unsigned char b[16];

    MD5(c,strlen(c),b);

    return(b[0]|(b[1]<<8)|(b[2]<<16)|(b[3]<<24));*/n= 0x100;while (*c) {

        v= n | (*c);

        n+= 0x100;

        r= (int)((v >> 2) ^ v) & 0x0f;

        ret= (ret << r) | (ret >> (32 -r));

        ret&= 0xFFFFFFFFL;

        ret^= v *v;

        c++;

    }return ((ret >> 16) ^ret);

}

[转载]语言/编码检测的复合方法

作者: admin
时间: 2021-06-22
分类: 默认分类
评论

原文地址：https://www-archive.mozilla.org/projects/intl/universalcharsetdetection

英文版本：

A composite approach to language/encoding detection

Shanjian Li (shanjian@netscape.com)
Katsuhiko Momoi (momoi@netscape.com)
Netscape Communications Corp.

[Note: This paper was originally presented at the 19th International Unicode Conference (San Jose). Since then the implementation has gone through a period of real world usage and we made many improvements along the way. A major change is that we now use positive sequences to detect single byte charsets, c.f. Sections 4.7 and 4.7.1. �This paper was written when the universal charset detection code was not part of the Mozilla main source. (See Section 8). Since then, the code was checked into the tree. For more updated implementation, see our open source code at Mozilla Source Tree. - The authors. 2002-11-25.]

1. Summary:

This paper presents three types of auto-detection methods to determine encodings of documents without explicit charset declaration.� We discuss merits and demerits of each method and propose a composite approach in which all 3 types of detection methods are used in such a way as to maximize their strengths and complement other detection methods. We argue that auto-detection can play an important role in helping transition browser users from frequent uses of a character encoding menu into a more desirable state where an encoding menu is rarely, if ever, used.� We envision that the transition to the Unicode would have to be transparent to the users.� Users need not know how characters are displayed as long as they are displayed correctly -- whether it�s a native encoding or one of Unicode encodings.� Good auto-detection service could help significantly in this effort as it takes most encoding issues out of the user�s concerns.

2. Background:

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. This, in spite of the fact that many W3C and IETF recommendations list UTF-8 as the default encoding, e.g. XML, XHTML, RDF, etc. Thus, today's global software applications are required to handle multiple encodings in addition to supporting Unicode.

The current work has been conducted in the context of developing an Internet browser. To deal with a variety of languages using different encodings on the web today, a lot of efforts have been expended. In order to get the correct display result, browsers should be able to utilize the encoding information provided by http servers, web pages or end users via a character encoding menu. Unfortunately, this type of information is missing from many http servers and web pages. Moreover, most average users are unable to provide this information via manual operation of a character encoding menu. Without this charset information, web pages are sometimes displayed as �garbage� characters, and users are unable to access the desired information. This also leads users to conclude that their browser is mal-functioning or buggy.

As more Internet standard protocols designate Unicode as the default encoding, there will undoubtedly be a� significant shift toward the use of Unicode on web pages. Good universal auto-detection can make an important contribution toward such a shift if it works seamlessly without the user ever having to use an encoding menu.� Under such a condition, gradual shift to Unicode could be painless and without noticeable effects on web users since for users, pages simply display correctly without them doing anything or paying attention to an encoding menu.� Such a smooth transition could be aided by making encodings issues less and less noticeable to the users. Auto-detection would play an important role for such a scenario.

3. Problem Scope:

3.1. General Schema

Let us begin with a general schema. For most applications, the following represents a general framework of auto-detection use:

Input Data -> �Auto-detector -> Returns results

An application/program takes the returned result(s) from an auto-detector and then uses this information for a variety of purposes such as setting the encoding for the data, displaying the data as intended by the original creator, pass it on to other programs, and so on.

The auto-detection methods discussed in this paper use an Internet Browser application as an example. These auto-detection methods, however, can be easily adapted for other types of applications.

3.2.� Browser and auto-detection

Browsers may use certain detection algorithms to auto-detect the encoding of web pages. A program can potentially interpret a piece of text in any number of ways assuming different encodings, but except in some extremely rare situations, only one interpretation is desired by the page�s author.� This is normally the only reasonable way for the user to see that page correctly in the intended language.

To list major factors in designing an auto-detection algorithm, we begin with certain assumptions about input text and approaches to them.� Taking web page data as an example,

1. Input text is composed of words/sentences readable to readers of a particular language.� (= The data is not gibberish.)

2. Input text is from typical web pages on the Internet. (= The data is usually not from some dead or ancient language.)

3. The input text may contain extraneous noises which have no relation to its encoding, e.g. HTML tags, non-native words (e.g. English words in Chinese documents), space and other format/control characters.

To cover all the known languages and encodings for auto-detection is nearly an impossible task. In the current approaches, we tried to cover all popular encodings used in East Asian languages, and provided a generic model to handle single-byte encodings at the same time. The Russian language encodings was chosen as an implementation example of the latter type and also our test bed for single-byte encodings.

4. Target multi-byte encodings include UTF8, Shift-JIS, EUC-JP, GB2312, Big5, EUC-TW, EUC-KR, ISO2022-XX, and HZ.

5. Providing a generic model to handle single-byte encodings � Russian language encodings (KOI8-R, ISO8859-5, window1251, Mac-cyrillic, ibm866, ibm855) are covered in a test bed and as an implementation example.

4. Three Methods of Auto-detection:

4.1. Introduction:

In this section, we discuss 3 different methods for detecting the encoding of text data. They are 1) Coding scheme method, 2) Character Distribution, and 3) 2-Char Sequence Distribution. Each one has its strengths and weaknesses used on its own, but if we use all 3 in a complementary manner, the results can be quite satisfying.

4.2. Coding Scheme Method:

This method is probably the most obvious and the one most often tried first for multi-byte encodings. In any of the multi-byte encoding coding schemes, not all possible code points are used. If an illegal byte or byte sequence (i.e. unused code point) is encountered when verifying a certain encoding, we can immediately conclude that this is not the right guess. A small number of code points are also specific to a certain encoding, and that fact can lead to an immediate positive conclusion. Frank Tang (Netscape Communications) developed a very efficient algorithm to detecting character set using coding scheme through a parallel state machine.� His basic idea is:

For each coding scheme, a state machine is implemented to verify a byte sequence for this particular encoding. For each byte the detector receives, it will feed that byte to every active state machine available, one byte at a time. The state machine changes its state based on its previous state and the byte it receives. There are 3 states in a state machine that are of interest to an auto-detector:

�START state: This is the state to start with, or a legal byte sequence (i.e. a valid code point) for character has been identified.
�ME state:� This indicates that the state machine identified a byte sequence that is specific to the charset it is designed for and that there is no other possible encoding which can contain this byte sequence. This will to lead to an immediate positive answer for the detector.
�ERROR state: This indicates the state machine identified an illegal byte sequence for that encoding. This will lead to an immediate negative answer for this encoding. Detector will exclude this encoding from consideration from here on.
�

In a typical example, one state machine will eventually provide a positive answer and all others will provide a negative answer.

The version of PSM (Parallel State Machine) used in the current work is a modification of Frank Tang's original work. Whenever a state machine reaches the START state, meaning it has successfully identified a legal character, we query the state machine to see how many bytes this character has. This information is used in 2 ways.

First, for UTF-8 encoding, if several multi-byte characters are identified, the input data is very unlikely to be anything other than UTF-8. So we count the number of multi-byte characters identified by the UTF-8 state machine. When it reaches a certain number (= the threshold), conclusion is made. �
Second, for other multi-byte encodings, this information is fed to Character Distribution analyzer (see below) so that the analyzer can deal with character data rather than raw data.

4.3. Character Distribution Method:

In any given language, some characters are used more often than other characters. This fact can be used to devise a data model for each language script. This is particularly useful for languages with a large number of characters such as Chinese, Japanese and Korean. We often hear anecdotally about such distributional statistics, but we have not found many published results. Thus for the following discussions, we relied mostly on our own collected data.

4.3.1. Simplified Chinese:

Our research on 6763 Chinese characters data encoded in GB2312 shows the following distributional results:

Number of Most Frequent Characters	Accumulated Percentage
10	0.11723
64	0.31983
128	0.45298
256	0.61872
512	0.79135
1024	0.92260
2048	0.98505
4096	0.99929
6763	1.00000

�� Table 1.� Simplified Chinese Character Distribution Table

4.3.2. Traditional Chinese:

Research by Taiwan�s Mandarin Promotion Council conducted annually shows a similar result for traditional Chinese encoded in Big5.

Number of Most Frequent Characters	Accumulated Percentage
10	0.11713
64	0.29612
128	0.42261
256	0.57851
512	0.74851
1024	0.89384
2048	0.97583
4096	0.99910

�� Table 2. Traditional Chinese Character Distribution Table

4.3.3. Japanese:

We collected our own data for Japanese, then wrote a utility to analyze them.� The following table shows the results:

Number of Most Frequent Characters	Accumulated Percentage
10	0.27098
64	0.66722
128	0.77094
256	0.85710
512	0.92635
1024	0.97130
2048	0.99431
4096	0.99981
	1.00000

�� Table 3.� Japanese Character Distribution Table

4.3.4.� Korean:

Similarly for Korean, we collected our own data from the Internet and run our utility on it. The results are as follows:

Number of Most Frequent Characters	Accumulated Percentage
10	0.25620
64	0.64293
128	0.79290
256	0.92329
512	0.98653
1024	0.99944
2048	0.99999
4096	0.99999

�� Table 4.� Korean Character Distribution Table

4.4. General characteristics of the distributional results:

In all these four languages, we find that a rather small set of coding points covers a significant percentage of characters used in our defined application scope.� Moreover, closer examination of those frequently used code points shows that they are scattered over a rather wide coding range.� This gives us a way to overcome the common problem encountered in the Coding Scheme analyzer, i.e. different national encodings may share overlapping code points.� Because the most frequently occurring sets for these languages have the characteristics described above, the overlap problem between different encodings in the Code Scheme Method will be insignificant in the Distribution Method.

4.5. Algorithm for analysis:

In order to identify characteristics of a language based on the character frequency/distribution statistics, we need an algorithm to calculate a value from a stream of text input. This value should show the likelihood of this stream of text being in a certain character encoding. A natural choice might be to calculate this value based on each character�s frequency weight. But from our experiment with various character encodings, we find that this approach is not necessary and it uses too much memory and CPU power. A simplified version provides a very satisfactory result, and uses much less resources and runs faster. �

In the current approach, all characters in a given encoding are classified into 2 categories, �frequently used� and �not frequently used�.� If a character is among the top 512 characters in the frequency distribution table, it is categorized as a �frequently used� character. The number 512 is chosen because it covers a significant amount of accumulated percentages in any of the 4 language input text while only occupying a small percentage of coding points. We count the number of characters in either category in a batch of input text, and then calculate a float value we call Distribution Ratio. �

The Distribution Ratio is defined as follows:

Distribution Ratio = the Number of occurrences of the 512 most frequently used characters divided by the Number of occurrences of the rest of the characters.

Each of the multi-byte encodings tested actually shows a distinct Distribution Ratio. From this ratio then, we can calculate the confidence level of the raw input text for a given encoding. Following discussions for each encoding should make this clearer.

4.6. Distribution Ratio and Confidence Level:

Let us look at the 4 language data to see the differences in Distribution Ratios.� Note first that we use the term Distribution Ratio in two ways. An �ideal� Distribution Ratio is defined for language scripts/character sets rather than for encodings.� If a language script/character set is represented by more than one encodings, then, for each encoding, we calculate the �actual� Distribution Ratio in the input data by sorting characters into �frequently used� or �not frequently used� categories. This value is then compared against the ideal Distribution Ratio of the language script/character set.� Based on the actual Distribution Ratios obtained, we can calculate the Confidence level for each set of input data as described below.

4.6.1. Simplified Chinese (GB2312):

GB2312 encoding contains two levels of Chinese characters. Level 1 contains 3755 characters, and Level 2, 3008 characters. Level 1 characters are more frequently used than Level 2 ones, and it is no surprise to see that all 512 characters on the most frequently used character list for GB 2312 are within Level 1. Because Level 1 characters are sorted based on pronunciation, those 512 characters are evenly scattered in 3755 code points. These characters occupies 13.64% of all coding points in Level 1, but it covers 79.135% of the character occurrences in a typical Chinese text. In an ideal situation, a piece of Chinese text that contains enough characters should return us something like:

�Distribution Ratio =� 0.79135/(1-0.79135) =3.79

And for a randomly generated text using the same encoding scheme, the ratio should be around 512 / (3755-512)=0.157 if no level 2 character is used.

If we include Level 2 characters into consideration, we can assume that the average probability of each Level 1 character is p1, and that of Level 2 is p2.� The calculation then would be:

512*p1 / (3755*p1 + 3008*p2 � 512*p1) = 512/(3755 + 3008*p2/p1-512)

Obviously, this value is even smaller. In a later analysis, we just use the worst case for comparison.
�

4.6.2. Big 5:

Big5 and EUC-TW (i.e. CNS Character Set) encodings have a very similar story.� Big5 also encodes Chinese characters in 2 levels. The most frequently used 512 characters are evenly scattered in 5401 Level 1 characters. The ideal ratio we can get from a big5-encoded text is:

Distribution Ratio = 0.74851/(1-0.74851) =2.98

And for a randomly generated text should have a ration near

512/(5401-512)=0.105

Since Big5 Level 1 characters are nearly identical to CNS plane 1 characters, the same analysis applies to EUC-TW.

4.6.3. Japanese Shift_JIS & EUC-JP:

For the Japanese Language, Hiragana and Katakana are usually more frequently used than Kanji. Because Shift-JIS and EUC-JP encode Hiragana and Katakana in different coding ranges, we are still able to use this method to distinguish among the two encodings.
Those Kanji characters that are among the most 512 frequently used characters are also scattered evenly among 2965 JIS Level 1 Kanji set.� The same Analysis leads to the following distribution ratio:

Distribution Ratio = 0.92635 / (1-0.92635) = 12.58

For randomly generated Japanese text data, the ratio should be at least

512 / (2965+63+83+86-512) = 0.191.

The calculation includes Hankaku Katakana (63), Hiragana (83), and Katakana (86).

4.6.4. Korean EUC-KR:

In EUC-KR encoding, the number of Hanja (Chinese) characters actually used in a typical Korean text is insignificant. The 2350 Hangul characters coded in this encoding are arranged by their pronunciation.� In the frequency table we got through analyzing a large amount of Korean text data, most frequently used characters are evenly distributed in these 2350 code points. Using the same analysis, in an ideal situation, we get:

Distribution Ratio = 0.98653 / (1-0.98653) = 73.24

For randomly generated Korean text, it should be:

512 / (2350-512) = 0.279.

4.6.5. Calculating Confidence Level:

From the foregoing discussions for each language script, we can define the Confidence level for each data set as follows:

Confidence Detecting(InputText)
{
� for each multi-byte character in InputText
� {
�� TotalCharacterCount++;
�� if the character is among 512 most frequent ones
�� FrequentCharacterCount++;
� }

�� Ratio = FrequentCharacterCount
�� / (TotalCharacterCount-FreqentCharacterCount);
�� Confidence = Ratio / CHARSET_RATIO;
�� Return Confidence;
}

The Confidence level for a given set data is defined as the Distribution Ratio of the input data divided by the ideal Distribution Ratio obtained by the analyses in the preceding sections.

4.7.� Two-Char Sequence Distribution Method:

�
In languages that only use a small number of characters, we need to go further than counting the occurrences of each single character. Combination of characters reveals more language-characteristic information. We define a 2-Char Sequence as 2 characters appearing immediately one after another in input text, and the order is significant in this case. Just as not all characters are used equally frequently in a language, 2-Char Sequence distribution also turns out to be extremely language/encoding dependent. This characteristic can be used in language detection. This leads to better confidence in detecting a character encoding, and is very useful in detecting single byte languages.

Let�s use Russian language as an example. We downloaded around 20MB of Russian plain text, and wrote a program to analyze the text. The program found 21,199,528 2-Char sequence occurrences in total. Among the sequences we found, some of them are irrelevant for our consideration, e.g. space-space combination. These sequences are considered as noises, and their occurrences are not included in the analysis . In the data we used to detect the Russian language encodings, this left 20,134, 122 2-Char sequence occurrences.� That covers about 95% of all the sequence occurrences found in the data.� The sequences used in building our language model can be classified into 4096 different sequences, and 1961 of them appear fewer than 3 times in our 20,134,122 samples. We call these 1961 sequences as Negative Sequence Set of this language.

4.7.1. Algorithm for determining Confidence Level

For single-byte languages, we define the Confidence Level as follows:

Confidence Detecting(InputText) { � for each character in InputText � { �� If character is not a symbol or punctuation character �� TotalCharacters++; �� Find its frequency order in frequency table; �� If (Frequency order < SampleSize) �� { �� FrequentCharCount++; �� If we do not have lastChar �� { �� lastChar = thisChar; �� continue; �� } �� if both lastChar and thisChar are within our sample range �� { �� TotalSequence++; �� If Sequence(lastChar, thisChar) belongs to NegativeSequenceSet �� NetgativeSequenceCount++; �� } �� } �� } �� Confidence = (TotalSequence � NegativeSequenceCount)/TotalSequence �� * FrequentCharCount / TotalCharacters; �� return Confidence;�� } �
�

There are several things in the algorithm that need to be explained.

First, this sequence analysis is not done to all characters. We can build a 256 by 256 matrix to cover all those sequences, but many of those are irrelevant to language/encoding analysis and thus unnecessary.� Since most single-byte languages use fewer then 64 letters, the most frequently used 64 characters seem to cover almost all the language specific characters.� This way, the matrix can be reduced to 64 by 64, which is much smaller.� So we are using 64 as our SampleSize in this work. The 64 characters we choose to build our model are mostly based on the frequency statistics with some adjustment allowed. Some characters, such as 0x0d and 0x0a, play roles very similar to the space character (0x20) in our perspective, and thus have been eliminated from the sampling.

Second, for all the sequences covered by this 64 by 64 model, some sequences are also irrelevant to detecting language/encoding.� Almost all single-byte language encodings include ASCII as a subset, it is very common to see a lot of English words in data from other languages, especially on web sites. It is also obvious that the space-space sequence has no connection with any language encoding. Those are considered as �noise� in our detection and are removed by filtering.
�
Third, in calculating confidence, we need to also count the number of characters that fall into our sample range and those that do not. If most of the characters in a small sample data do not fall into our sampling range, the sequence distribution itself may return us a high value since very few negative sequences might be found in such a case.� After filtering, most of those characters that have been fed to the detector should fall into the sampling range if the text is in the desired encoding. So the confidence obtained from counting negative sequences needs to be adjusted by this number.

To summarize the foregoing:

Only a subset of all the characters are used for character set identification. This keeps our model small. We also improved detection accuracy by reducing noise.
Each language model is generated by a script/tool.
Handling of Latin Alphabet characters:

If the language does not use Latin Alphabet letters, Alphabet -letter to Alphabet -letter sequences are removed as noise for detection. (e.g. English words frequently appear in web pages of other languages.)

If the language does use Latin Alphabet letters, those sequences are kept for analysis.

The number of characters that fall into our sample range and those that do not are counted so that they can be used in calculating the Confidence Level.

5. Comparison of the 3 methods:

5.1. Code scheme:

For many single-byte encodings, all code points are used fairly evenly. And even for those encodings that do contain some unused code points, those unused code points are seldom used in other encodings and are thus unsuitable for encoding detection.

For some multi-byte encodings, this method leads to a very good result and is very efficient. However, because some multi-byte encodings such as EUC-CN and EUC-KR share almost identical coding points, it is very hard to distinguish among such encodings with this method. Considering the fact that a browser normally does not have a large amount of text, we must resort to other methods to decide on an encoding. �

For 7-bit multi-bye encodings like ISO-2022-xx and HZ, which use easily recognizable escape or shift sequences, this method produces satisfactory results. Summarizing, the Code Scheme method,

is very good for 7-bit multi-byte encodings like ISO-2022-xx and HZ.
is good for some multi-byte encoding like Shift_JIS and EUC-JP, but not for others like EUC-CN and EUC-KR.
is not very useful for single-byte encodings.
can apply to any kind of text.
is fast and efficient.

5. 2. Character Distribution:

For multi-byte encodings, and especially those that can not be handled reliably by the Code Scheme method, Character Distribution offers strong help without digging into complicated context analysis. For single-byte encodings, because the input data size is usually small, and there are so many possible encodings, it is unlikely to produce good results except under some special situations. Since the 2-Char Sequence Distribution method leads to a very good detection result in such a case, we have not gone further with this method on single-byte encodings. Summarizing these points, the Character Distribution Method

is very good for multi-byte encodings.
only applies to typical text.
is fast and efficient.

5.3.� 2-Char Sequence Distribution:

In the 2-Char Sequence Distribution method, we can use more information data in detecting language/encodings. That leads to good results even with a very small data sample. But because sequences are used instead of words (separated by a space), the matrix will be very big if it was to apply to multi-byte languages. Thus this method:
�

is very good for single-byte encodings.
is not efficient for multi-byte encodings.
can lead to good results with even small sample size.
only applies to typical text.

6. A composite Approach:

6.1. Combining the 3 methods:

Languages/encodings we want to cover with our charset auto-detector includes a number of multi-byte and single-byte encodings.� Given the deficiencies of each method, none of the 3 methods alone can produce truly satisfactory results.� We propose, therefore, a composite approach which can deal with both types of encodings.

The 2-Char Sequence Distribution method is used for all single-byte encoding detections.
The Code Scheme method is used for UTF-8, ISO-2022-xx and HZ detection. In UTF-8 detection, a small modification has been made to the existing state machine. The UTF-8 detector declares its success after several multi-byte sequences have been identified.� (See Martin Duerst�s (1977) detail). Both the Code Scheme and Character Distribution methods are used for major East Asian character encodings such as GB2312, Big5, EUC-TW, EUC-KR, Shift_JIS, and EUC-JP.

For Japanese encodings like Shift_JIS and EUC-JP, the 2-Char Sequence Distribution method can also be used� because they contain a significant number of Hiragana syallbary characters, which work like letters in single-byte languages.� The 2-Char Sequence Distribution method can achieve an accurate result with less text material.

We tried both approaches -- one with the 2-Char Distribution Method and the other without.� Both led to quite satisfactory results. There are some web sites which contain a lot of Kanji and Katakana characters but only a few Hiragana characters. To achieve the best possible result, we use both the Character Distribution and 2-CharDistribution methods� for Japanese encoding detection.

Here then is one example of how these 3 detection methods are used together.� The upper most control module (for auto-detectors) has an algorithm like the following:

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, otherwise return ASCII; �� } �� else �� return ASCII; �� } �� else if (InputText start with BOM) � { �� return UCS2; � } � else � { �� Call all multi-byte detectors and single-byte detectors; �� Return the one with best confidence; � } }

Summarizing the sequences in the code fragment above,

Most web pages are still encoded in ASCII. This top-level control algorithm begins with an ASCII verifier. If all characters are ASCII, there is no need to launch other detectors except ISO-2022-xx and HZ ones.
ISO-2022-xx and HZ detectors are launched only after encountering ESC or �~{�, and they are abandoned immediately when a 8-bit byte is met.
BOM is being searched to identify UCS2. We found that some web sites send 0x00 inside http stream, and using this byte for identifying UCS2 proved to be unreliable.
If any one of the active detectors received enough data and reaches a high level of confidence, the entire auto-detecting process will be terminated and that charset will be returned as the result. This is called shortcut.

6.2.� Test Results:

As a test for the approach advocated in this paper, we applied our detector(s) to the home pages of 100 popular international web sites without document-based or server-sent HTTP charset.� For all the encodings covered by our detector(s) we were able to achieve 100% accuracy rate.

For example, when visiting a web site that provides no charset information (e.g. the web site at http://www.yahoo.co.jp before its server started sending the charset info), our charset detector(s) generates output like the following:

[UTF8] is inactive [SJIS] is inactive [EUCJP] detector has confidence 0.950000 [GB2312] detector has confidence 0.150852 [EUCKR] is inactive [Big5] detector has confidence 0.129412 [EUCTW] is inactive [Windows-1251 ] detector has confidence 0.010000 [KOI8-R] detector has confidence 0.010000 [ISO-8859-5] detector has confidence 0.010000 [x-mac-cyrillic] detector has confidence 0.010000 [IBM866] detector has confidence 0.010000 [IBM855] detector has confidence 0.010000
This then leads to the determination that EUC-JP is the most likely encoding for this site.

7. Conclusion:

The composite approach that utilizes Code Scheme, Character Distribution and 2-Char Sequence Distribution methods to identify language/encodings has been proven to be very effective and efficient in our environment. We covered Unicode encodings, multi-byte encodings and single-byte encodings. These are representative encodings in our current digital text on the Internet. It is reasonable to believe that this method can be extended to cover the rest of the encodings not covered in this paper.

Though only encodings information is desired in our detection results at this time, language is also identified in most cases. In fact, both Character Distribution and 2-Char Distribution methods rely on characteristic distributional patterns of different language characters. Only in the case of UTF16 and UTF8, encoding is detected but the language remains unknown. But even in such cases, this work can still be easily extended to cover language detection in future.

The 3 methods outlined here have been implemented in Netscape 6.1 PR1 and later versions as the �Detect All� option. We expect our work in auto-detection to free our users further from having to deal with cumbersome manipulations of the Character Coding menu.� The Character Coding menu (or Encoding menu for others) is different from other UI items in the Internet client in that it exposes part of the i18n backend to general users. Its existence itself is a mirror of how messy today�s web pages are when it comes to language/encoding.

We hope that offering good encoding default and universal auto-detection will help alleviate most of the encoding problems our users encounter in surfing the net. Web standards are shifting toward Unicode, particularly, toward UTF-8, as the default encoding. We expect gradual increase of its use on the web. Such shifts need not be overt as more and more users are freed from confronting issues related to encoding while browsing or reading/sending messages, thanks in part to auto-detection.� This is why we advocate good auto-detection and good default encoding settings for Internet clients.

8. Future Work:

Our auto-detection identifies a language. The encoding determination is a byproduct of that determination. For the current work, we only covered Russian as an example of single-byte implementation.� Since it identifies a language and only then which encoding it uses, the more language data models there are, the better the quality of encoding detection.

To add other single-byte languages/encodings, we need a large amount of text sample data for each language and certain degree of language knowledge/analysis.� We currently use a script to generate a language model for all the encodings for that language.

This work is at present not in the Mozilla source but we hope to make it public in the near future. When we do, we hope people with the above qualification will contribute in this area. Because we have not yet tested many single-byte encodings, it is likely that the model we propose here needs to be fine-tuned, modified or possibly even re-designed when applying to other languages/encodings.

�9. References:

Duerst, Martin. 1977. The Properties and Promizes of UTF-8.� 11th Unicode Conference. �� http://www.ifi.unizh.ch/groups/mml/people/mduerst/papers/IUC11-UTF-8.pdf Mandarin Promotion Council, Taiwan. Annual survey results of Traditional Chinese character usage. � http://www.edu.tw/mandr/result/87news/index1.htm Mozilla Internationalization Projects.� http://www.mozilla.org/projects/intl Mozilla.org.� http://www.mozilla.org/ Mozilla source viewing.� http://lxr.mozilla.org/

机器翻译版本：

Shanjian Li (shanjian@netscape.com)
Katsuhiko Momoi (momoi@netscape.com)
Netscape Communications Corp.

[注：本文最初发表于第19 届国际 Unicode 会议（圣何塞）。从那时起，该实现经历了一段真实世界的使用期，我们在此过程中进行了许多改进。一个主要的变化是我们现在使用正序列来检测单字节字符集，参见第 4.7 和 4.7.1 节。本文是在通用字符集检测代码不是 Mozilla 主要来源的一部分时编写的。（见第 8 节）。从那时起，代码被签入到树中。有关更多更新的实现，请参阅我们在Mozilla Source Tree 上的开源代码。- 作者。2002-11-25。]

一、总结：

本文介绍了三种类型的自动检测方法来确定没有显式字符集声明的文档编码。我们讨论了每种方法的优缺点，并提出了一种复合方法，其中所有 3 种类型的检测方法都以这样的方式使用最大限度地发挥其优势并补充其他检测方法。我们认为，自动检测可以在帮助浏览器用户从频繁使用字符编码菜单过渡到更理想的状态方面发挥重要作用，在这种状态下，编码菜单很少使用（如果有的话）。我们设想过渡到 Unicode必须对用户透明。只要字符显示正确，用户就不需要知道字符是如何显示的——无论是本机编码还是 Unicode 编码之一。

2. 背景：

自计算机时代开始以来，已经创建了许多编码方案来表示计算机数据的各种书写脚本/字符。随着全球化的到来和互联网的发展，跨越语言和地区界限的信息交流变得越来越重要。但是多种编码方案的存在构成了一个重大障碍。 Unicode 提供了一种通用编码方案，但由于各种原因，它迄今为止还没有取代现有的区域编码方案。尽管事实上许多 W3C 和 IETF 建议将 UTF-8 列为默认编码，例如 XML、XHTML、RDF 等。因此，除了支持 Unicode 之外，当今的全球软件应用程序还需要处理多种编码。

目前的工作是在开发互联网浏览器的背景下进行的。为了处理当今网络上使用不同编码的各种语言，已经付出了很多努力。为了得到正确的显示结果，浏览器应该能够通过字符编码菜单利用http服务器、网页或最终用户提供的编码信息。不幸的是，许多 http 服务器和网页都缺少这种类型的信息。而且，大多数普通用户无法通过手动操作字符编码菜单来提供这些信息。如果没有这些字符集信息，网页有时会显示为“垃圾”字符，用户无法访问所需的信息。这也导致用户得出结论，他们的浏览器出现故障或有问题。

随着越来越多的 Internet 标准协议将 Unicode 指定为默认编码，毫无疑问，在网页上使用 Unicode 将发生重大转变。良好的通用自动检测可以为这种转变做出重要贡献，如果它在用户不需要使用编码菜单的情况下无缝工作。在这种情况下，逐渐转变到 Unicode 可能会很轻松，并且不会对网络用户产生明显影响，因为对于用户来说，页面只是正确显示，他们无需做任何事情或注意编码菜单。可以通过使用户越来越不注意编码问题来帮助实现这种平滑过渡。自动检测将在这种情况下发挥重要作用。

3. 问题范围：

3.1. 通用架构

让我们从一个通用模式开始。对于大多数应用程序，以下表示自动检测使用的一般框架：

输入数据 -> 自动检测器 -> 返回结果

应用程序/程序从自动检测器获取返回的结果，然后将此信息用于多种用途，例如设置数据的编码、按照原始创建者的意图显示数据、将其传递给其他程序等。

本文中讨论的自动检测方法以 Internet 浏览器应用程序为例。然而，这些自动检测方法可以很容易地适用于其他类型的应用。

3.2.. 浏览器和自动检测

浏览器可能会使用某些检测算法来自动检测网页的编码。一个程序可以假设不同的编码以多种方式解释一段文本，但除了在极少数情况下，页面作者只需要一种解释。这通常是用户唯一合理的方式以预期的语言正确查看该页面。

为了列出设计自动检测算法的主要因素，我们首先对输入文本及其处理方法进行一些假设。以网页数据为例，

1. 输入文本由特定读者可读的单词/句子组成语言. （=数据不是胡言乱语。）

2. 输入文本来自互联网上的典型网页。（= 数据通常不是来自某种死的或古老的语言。）

3. 输入文本可能包含与其编码无关的外来噪声，例如 HTML 标签、非母语单词（例如中文文档中的英文单词）、空格和其他格式/控制字符。

涵盖所有已知语言和自动检测编码几乎是一项不可能完成的任务。在当前的方法中，我们试图涵盖东亚语言中使用的所有流行编码，并提供了一个通用模型来同时处理单字节编码。选择俄语编码作为后一种类型的实现示例，也是我们的单字节编码测试平台。

4.目标多字节编码包括UTF8、Shift-JIS、EUC-JP、GB2312、Big5、EUC-TW、EUC-KR、ISO2022-XX、HZ。

5. 提供处理单字节编码的通用模型俄罗斯语言编码（KOI8-R、ISO8859-5、window1251、Mac-cyrillic、ibm866、ibm855）在测试台和实现示例中进行了介绍。

4. 三种自动检测方法：

4.1. 介绍：

在本节中，我们将讨论 3 种不同的检测文本数据编码的方法。它们是 1) 编码方案方法，2) 字符分布，和 3) 2-字符序列分布。每个都有自己的优点和缺点，但如果我们以互补的方式使用所有 3 个，结果会非常令人满意。

4.2. 编码方案方法：

对于多字节编码，这种方法可能是最明显的，也是最常首先尝试的方法。在任何多字节编码编码方案中，并非使用所有可能的代码点。如果在验证某个编码时遇到非法字节或字节序列（即未使用的代码点），我们可以立即得出结论，这不是正确的猜测。少数代码点也特定于某种编码，这一事实可以立即得出肯定的结论。Frank Tang (Netscape Communications) 开发了一种非常有效的算法，通过并行状态机使用编码方案来检测字符集。他的基本思想是：

对于每种编码方案，都实现了一个状态机来验证该特定编码的字节序列。对于检测器接收到的每个字节，它将将该字节提供给每个可用的活动状态机，一次一个字节。状态机根据它之前的状态和它接收到的字节改变它的状态。自动检测器感兴趣的状态机中有 3 种状态：

START 状态：这是开始的状态，或者已识别字符的合法字节序列（即有效代码点）。
ME 状态：这表明状态机标识了一个字节序列，该字节序列特定于它所设计的字符集，并且没有其他可能的编码可以包含该字节序列。这将导致检测器立即得到肯定的答复。
错误状态：这表示状态机识别出该编码的非法字节序列。这将导致对该编码的立即否定回答。从这里开始，检测器将排除此编码。

在一个典型的例子中，一个状态机最终会提供一个肯定的答案，而所有其他的都会提供一个否定的答案。

目前作品中使用的PSM（Parallel State Machine）版本是对Frank Tang原作的修改。每当状态机到达 START 状态时，这意味着它已成功识别出一个合法字符，我们查询状态机以查看该字符有多少字节。该信息以两种方式使用。

首先，对于 UTF-8 编码，如果识别出多个多字节字符，则输入数据不太可能是 UTF-8 以外的任何其他字符。所以我们统计一下UTF-8状态机识别出的多字节字符的个数。当它达到一定数量（=阈值）时，得出结论。
其次，对于其他多字节编码，此信息被馈送到字符分布分析器（见下文），以便分析器可以处理字符数据而不是原始数据。

4.3. 字符分配方法：

在任何给定的语言中，某些字符的使用频率高于其他字符。这一事实可用于为每种语言脚本设计一个数据模型。这对于包含大量字符的语言特别有用，例如中文、日文和韩文。我们经常听到关于这种分布统计的轶事，但我们没有发现很多已发表的结果。因此，在接下来的讨论中，我们主要依赖于我们自己收集的数据。

4.3.1. 简体中文：

我们对 GB2312 编码的 6763 个汉字数据的研究显示了以下分布结果：

最常见的字符数	累计百分比
10	0.11723
64	0.31983
128	0.45298
256	0.61872
512	0.79135
1024	0.92260
2048	0.98505
4096	0.99929
6763	1.00000

表 1. 简体汉字分布表

4.3.2. 繁体中文：

台湾普通话促进委员会每年进行的研究表明，对 Big5 编码的繁体中文也有类似的结果。

最常见的字符数	累计百分比
10	0.11713
64	0.29612
128	0.42261
256	0.57851
512	0.74851
1024	0.89384
2048	0.97583
4096	0.99910

表 2. 繁体字分布表

4.3.3. 日本人：

我们收集了自己的日语数据，然后编写了一个实用程序来分析它们。下表显示了结果：

最常见的字符数	累计百分比
10	0.27098
64	0.66722
128	0.77094
256	0.85710
512	0.92635
1024	0.97130
2048	0.99431
4096	0.99981
	1.00000

表 3. 日文字符分布表

4.3.4. 韩语：

同样，对于韩语，我们从互联网上收集了我们自己的数据并在其上运行我们的实用程序。结果如下：

最常见的字符数	累计百分比
10	0.25620
64	0.64293
128	0.79290
256	0.92329
512	0.98653
1024	0.99944
2048	0.99999
4096	0.99999

表 4. 韩文字符分布表

4.4. 分布结果的一般特征：

在所有这四种语言中，我们发现一小部分编码点覆盖了我们定义的应用范围中使用的字符的很大一部分。此外，对这些常用编码点的仔细检查表明它们分散在相当广泛的编码中范围。。这为我们提供了一种克服编码方案分析器中遇到的常见问题的方法，即不同的国家编码可能共享重叠的代码点。。因为这些语言最常出现的集合具有上述特征，因此Code Scheme Method 中的不同编码在 Distribution Method 中将无关紧要。

4.5. 分析算法：

为了根据字符频率/分布统计来识别语言的特征，我们需要一种算法来计算文本输入流中的值。此值应显示此文本流采用某种字符编码的可能性。一个自然的选择可能是根据每个字符的频率权重来计算这个值。但是从我们对各种字符编码的实验中，我们发现这种方法是没有必要的，它使用了太多的内存和 CPU 能力。简化版本提供了非常令人满意的结果，并且使用更少的资源并且运行速度更快。

在当前的方法中，给定编码中的所有字符被分为 2 类，“经常使用”和“不经常使用”。如果一个字符在频率分布表中的前 512 个字符中，则将其归类为“经常使用的字符。选择数字 512 是因为它涵盖了 4 种语言输入文本中任何一种的大量累积百分比，而仅占编码点的一小部分。我们计算一批输入文本中任一类别的字符数，然后计算一个我们称为分布比率的浮点值。

分布比率定义如下：

分布比率 = 512 个最常用字符的出现次数除以其余字符的出现次数。

测试的每个多字节编码实际上都显示了不同的分布比率。然后，根据这个比率，我们可以计算给定编码的原始输入文本的置信度。以下对每种编码的讨论应该使这一点更清楚。

4.6. 分配比率和置信度：

让我们看看 4 种语言数据，看看分布比率的差异。首先请注意，我们以两种方式使用术语分布比率。“理想的”分布比率是为语言脚本/字符集而不是编码定义的。如果语言脚本/字符集由多个编码表示，那么对于每种编码，我们计算“实际”分布比率通过将字符分类为“常用”或“不常用”类别来输入数据。然后将该值与语言脚本/字符集的理想分布比率进行比较。根据获得的实际分布比率，我们可以计算每组输入数据的置信度，如下所述。

4.6.1. 简体中文（GB2312）：

GB2312 编码包含两级汉字。级别 1 包含 3755 个字符，级别 2 包含 3008 个字符。1级字比2级字更常用，GB 2312最常用字表中的512个字全都在1级之内也就不足为奇了。因为1级字是按发音排序的，所以这512个字字符均匀地分散在 3755 个代码点中。这些字符占一级所有编码点的 13.64%，但覆盖了典型中文文本中出现的字符的 79.135%。在理想情况下，一段包含足够字符的中文文本应该返回如下信息：

Distribution Ratio = 0.79135/(1-0.79135) =3.79

对于使用相同编码方案的随机生成的文本，如果不使用 2 级字符，则比率应约为 512 / (3755-512)=0.157。

如果我们考虑2级角色，我们可以假设每个1级角色的平均概率是p1，2级角色的平均概率是p2。那么计算将是：

512*p1 / (3755*p1 + 3008* p2 512*p1) = 512/(3755 + 3008*p2/p1-512)

显然，这个值更小。在后面的分析中，我们只使用最坏的情况进行比较。

4.6.2. 大五：

Big5 和 EUC-TW（即 CNS 字符集）编码有一个非常相似的故事。 Big5 也对汉字进行 2 级编码。最常用的512个字符均匀地分散在5401个一级字符中。我们可以从 big5 编码的文本中得到的理想比率是：

Distribution Ratio = 0.74851/(1-0.74851) =2.98

并且对于随机生成的文本应该具有接近

512/(5401-512)=0.105 的比率，

因为 Big5 Level 1字符与 CNS 平面 1 字符几乎相同，同样的分析适用于 EUC-TW。

4.6.3. 日语 Shift_JIS 和 EUC-JP：

对于日语，平假名和片假名通常比汉字更常用。因为 Shift-JIS 和 EUC-JP 在不同的编码范围内对平假名和片假名进行编码，所以我们仍然可以使用这种方法来区分这两种编码。
最常用的 512 个汉字中的那些汉字也均匀地分散在 2965 个 JIS 1 级汉字集中。相同的分析导致以下分布比率：

分布比率 = 0.92635 / (1-0.92635) = 12.58

对于随机生成日文文本数据，比例至少应为

512 / (2965+63+83+86-512) = 0.191。

计算包括半角片假名 (63)、平假名 (83) 和片假名 (86)。

4.6.4. 韩国 EUC-KR：

在 EUC-KR 编码中，典型韩语文本中实际使用的汉字（中文）字符的数量是微不足道的。用这种编码编码的 2350 个韩文字符是按发音排列的。在我们分析大量韩文文本数据得到的频率表中，最常用的字符均匀分布在这 2350 个代码点中。使用相同的分析，在理想情况下，我们得到：

Distribution Ratio = 0.98653 / (1-0.98653) = 73.24

对于随机生成的韩文文本，应该是：

512 / (2350-512) = 0.279。

4.6.5. 计算置信度：

从前面对每个语言脚本的讨论，我们可以定义每个数据集的置信度如下：

Confidence Detecting(InputText)
{
对于InputText中的每个多字节字符
{
TotalCharacterCount++;
如果该字符在 512 个最常见的
字符中 FrequencyCharacterCount++；
}

Ratio =
FrequencyCharacterCount / (TotalCharacterCount-FreqentCharacterCount);
置信度 = 比率 / CHARSET_RATIO；
返回置信度；
}

给定集合数据的置信水平定义为输入数据的分布比率除以通过前面部分中的分析获得的理想分布比率。

4.7.. 双字符序列分布方法：

在仅使用少量字符的语言中，我们需要走得更远而不是计算每个单个字符的出现次数。字符的组合揭示了更多的语言特征信息。我们将 2-Char Sequence 定义为在输入文本中一个接一个出现的 2 个字符，在这种情况下顺序很重要。正如在一种语言中并非所有字符都同样频繁地使用一样，2-Char 序列分布也非常依赖于语言/编码。该特性可用于语言检测。这会提高检测字符编码的信心，并且在检测单字节语言时非常有用。

让我们以俄语为例。我们下载了大约 20MB 的俄文纯文本，并编写了一个程序来分析文本。该程序总共发现了 21,199,528 个 2-Char 序列出现。在我们发现的序列中，其中一些与我们的考虑无关，例如空间-空间组合。这些序列被视为噪声，它们的出现不包括在分析中。在我们用来检测俄语编码的数据中，这留下了 20,134、122 个 2-Char 序列出现。这涵盖了数据中发现的所有序列出现的大约 95%。用于构建我们的语言模型的序列可以是分为 4096 个不同的序列，其中 1961 个在我们的 20,134,122 个样本中出现的次数不到 3 次。我们称这些 1961 序列为该语言的负序列集。

4.7.1. 确定置信水平的算法

对于单字节语言，我们定义置信度如下：

Confidence Detecting(InputText) { 对于 InputText 中的每个字符 { 如果字符不是符号或标点字符 TotalCharacters++; 在频率表中找到它的频率顺序； If (Frequency order < SampleSize) { FrequencyCharCount++; 如果我们没有 lastChar { lastChar = thisChar; 继续； } 如果 lastChar 和 thisChar 都在我们的样本范围内 { TotalSequence++; 如果 Sequence(lastChar, thisChar) 属于 NegativeSequenceSet NetgativeSequenceCount++； } } } 置信度 = (TotalSequence NegativeSequenceCount)/TotalSequence * FrequencyCharCount / TotalCharacters; return Confidence; }
算法中

有几点需要说明。

首先，这种序列分析不是对所有字符进行的。我们可以构建一个 256 x 256 的矩阵来覆盖所有这些序列，但其中许多与语言/编码分析无关，因此是不必要的。由于大多数单字节语言使用少于 64 个字母，最常用的 64 个字符似乎几乎涵盖了所有语言特定字符。这样，矩阵可以减少到 64 x 64，这要小得多。因此我们在这项工作中使用 64 作为我们的 SampleSize。我们选择构建模型的 64 个字符主要基于频率统计，并允许进行一些调整。某些字符，例如 0x0d 和 0x0a，在我们看来与空格字符 (0x20) 非常相似，因此已从采样中排除。

其次，对于这个 64 x 64 模型覆盖的所有序列，一些序列也与检测语言/编码无关。几乎所有单字节语言编码都包含 ASCII 作为子集，看到很多英文单词是很常见的来自其他语言的数据，尤其是网站上的数据。同样明显的是，空间-空间序列与任何语言编码都没有联系。这些在我们的检测中被视为“噪声”，并通过过滤去除。

第三，在计算置信度时，我们还需要计算落入我们样本范围和不落入样本范围的字符数。如果小样本数据中的大部分字符不属于我们的采样范围，序列分布本身可能会给我们返回一个高值，因为在这种情况下可能会发现很少的负序列。过滤后，大多数字符如果文本处于所需的编码中，则已被馈送到检测器应属于采样范围。所以计数负序列得到的置信度需要通过这个数字进行调整。

总结上述内容：

只有所有字符的一个子集用于字符集识别。这使我们的模型很小。我们还通过降低噪声来提高检测精度。
每个语言模型都是由一个脚本/工具生成的。
拉丁字母字符的处理：

如果语言不使用拉丁字母，则将 Alphabet -letter 到 Alphabet -letter 序列作为噪声去除以进行检测。（例如，英语单词经常出现在其他语言的网页中。）

如果语言确实使用拉丁字母，则保留这些序列以供分析。

计算属于我们的样本范围和不属于我们的样本范围的字符数，以便它们可用于计算置信度。

5. 3种方法的比较：

5.1. 代码方案：

对于许多单字节编码，所有代码点都相当均匀地使用。并且即使对于那些确实包含一些未使用的代码点的编码，那些未使用的代码点也很少用于其他编码，因此不适合编码检测。

对于一些多字节编码，这种方法会得到很好的结果，并且非常高效。然而，由于一些多字节编码如EUC-CN和EUC-KR共享几乎相同的编码点，用这种方法很难区分这些编码。考虑到浏览器通常没有大量文本，我们必须求助于其他方法来决定编码。

对于使用易于识别的转义或移位序列的 ISO-2022-xx 和 HZ 等 7 位多字节编码，该方法产生了令人满意的结果。总结一下，Code Scheme 方法，

非常适合 ISO-2022-xx 和 HZ 等 7 位多字节编码。
适用于某些多字节编码，如 Shift_JIS 和 EUC-JP，但不适用于 EUC-CN 和 EUC-KR 等其他编码。
对于单字节编码不是很有用。
可以应用于任何类型的文本。
快速高效。

5. 2. 人物分布：

对于多字节编码，尤其是那些不能被 Code Scheme 方法可靠处理的编码，Character Distribution 提供了强大的帮助，而无需深入研究复杂的上下文分析。对于单字节编码，由于输入的数据量通常比较小，而且可能的编码方式太多，除非在一些特殊情况下，否则不太可能产生好的结果。由于 2-Char Sequence Distribution 方法在这种情况下会产生非常好的检测结果，因此我们没有在单字节编码上进一步使用这种方法。总结这几点，人物分布法

非常适合多字节编码。
仅适用于典型文本。
快速高效。

5.3.. 2-Char 序列分布：

在 2-Char Sequence Distribution 方法中，我们可以使用更多的信息数据来检测语言/编码。即使使用非常小的数据样本，这也会产生良好的结果。但是因为使用序列而不是单词（用空格分隔），如果应用于多字节语言，矩阵将非常大。因此这个方法：

非常适合单字节编码。
对于多字节编码效率不高。
即使样本量很小，也能得到很好的结果。
仅适用于典型文本。

6. 复合方法：

6.1. 结合3种方法：

我们希望用我们的字符集自动检测器覆盖的语言/编码包括许多多字节和单字节编码。鉴于每种方法的缺陷，单独使用这 3 种方法都不能产生真正令人满意的结果。我们建议，因此，可以处理两种类型的编码的复合方法。

2-Char Sequence Distribution 方法用于所有单字节编码检测。
Code Scheme 方法用于 UTF-8、ISO-2022-xx 和 HZ 检测。在 UTF-8 检测中，对现有的状态机做了一个小的修改。UTF-8 检测器在识别出几个多字节序列后宣布其成功。（参见 Martin Duerst's (1977) 详细信息）。Code Scheme 和 Character Distribution 方法都用于主要的东亚字符编码，例如 GB2312、Big5、EUC-TW、EUC-KR、Shift_JIS 和 EUC-JP。

对于 Shift_JIS 和 EUC-JP 等日语编码，也可以使用 2-Char Sequence Distribution 方法。因为它们包含大量平假名 syallbary 字符，其工作方式类似于单字节语言中的字母。 2-Char Sequence Distribution方法可以用较少的文字材料获得准确的结果。

我们尝试了两种方法——一种使用 2-Char Distribution Method，另一种不使用。两种方法都取得了相当令人满意的结果。有一些网站包含很多汉字和片假名字符，但只有少数平假名字符。为了获得最佳结果，我们同时使用 Character Distribution 和 2-CharDistribution 方法来检测日语编码。

下面是这 3 种检测方法如何一起使用的一个示例。最上面的控制模块（用于自动检测器）具有如下算法：

Charset AutoDetection (InputText) { if (InputText 中的所有字符都是 ASCII ) { 如果 InputText 包含 ESC 或 ~{ { 使用 InputText 调用 ISO-2022 和 HZ 检测器；如果其中一个成功，则返回该字符集，否则返回 ASCII； } else 返回 ASCII； } else if (InputText start with BOM) { return UCS2; } else { 调用所有多字节检测器和单字节检测器；返回最有信心的那个； } }

总结上面代码片段中的序列，

大多数网页仍然以 ASCII 编码。这个顶级控制算法从一个 ASCII 验证器开始。如果所有字符都是 ASCII，则无需启动除 ISO-2022-xx 和 HZ 之外的其他检测器。
ISO-2022-xx 和 HZ 检测器只有在遇到 ESC 或 ~{ 后才启动，遇到 8 位字节时立即放弃。
正在搜索 BOM 以识别 UCS2。我们发现一些网站在http流中发送0x00，使用这个字节来识别UCS2被证明是不可靠的。
如果任何一个活动检测器接收到足够的数据并达到高置信度，则整个自动检测过程将终止，该字符集将作为结果返回。这称为捷径。

6.2. 测试结果：

作为对本文提倡的方法的测试，我们将我们的检测器应用于 100 个流行的国际网站的主页，没有基于文档或服务器发送的 HTTP 字符集。对于我们的检测器涵盖的所有编码) 我们能够达到 100% 的准确率。

例如，当访问不提供字符集信息的网站时（例如，在其服务器开始发送字符集信息之前的 http://www.yahoo.co.jp 网站）时，我们的字符集检测器会生成如下输出：以下：

[UTF8] 无效 [SJIS] 无效 [EUCJP] 检测器置信度 0.950000 [GB2312] 检测器置信度 0.150852 [EUCKR] 无效 [Big5] 检测器置信度 0.129412 [EUCTW] 无效 [Windows-1251] 检测器有信心 0.010000 [KOI8-R] 检测器有信心 0.010000 [ISO-8859-5] 检测器有信心 0.010000 [x-mac- cyrillic] 检测器有信心 0.010000 [IBM866] 检测器有信心 0.018000005 [IBM866] IBM05检测器的置信度为 0.010000
这将导致确定 EUC-JP 是该站点最有可能的编码。

7. 结论：

利用代码方案、字符分布和 2 字符序列分布方法来识别语言/编码的复合方法已被证明在我们的环境中非常有效和高效。我们介绍了 Unicode 编码、多字节编码和单字节编码。这些是我们当前互联网上的数字文本中的代表性编码。可以合理地相信，这种方法可以扩展到涵盖本文未涵盖的其余编码。

虽然目前我们的检测结果中只需要编码信息，但在大多数情况下也可以识别语言。实际上，Character Distribution 和 2-Char Distribution 方法都依赖于不同语言字符的特征分布模式。仅在 UTF16 和 UTF8 的情况下，会检测到编码，但语言仍然未知。但即使在这种情况下，这项工作仍然可以很容易地扩展到未来的语言检测。

此处概述的 3 种方法已在 Netscape 6.1 PR1 和更高版本中作为“全部检测”选项实现。我们希望我们在自动检测方面的工作能够让我们的用户免于处理繁琐的字符编码菜单操作。字符编码菜单（或其他人的编码菜单）与 Internet 客户端中的其他 UI 项目的不同之处在于它向一般用户公开了 i18n 后端的一部分。它的存在本身反映了当今网页在语言/编码方面的混乱程度。

我们希望提供良好的编码默认和通用自动检测将有助于缓解我们的用户在网上冲浪时遇到的大多数编码问题。Web 标准正在转向 Unicode，特别是转向 UTF-8，作为默认编码。我们预计它在网络上的使用会逐渐增加。这种转变不需要公开，因为越来越多的用户在浏览或阅读/发送消息时不再面临与编码相关的问题，部分归功于自动检测。这就是为什么我们提倡良好的自动检测和良好的默认编码设置对于互联网客户。

8. 未来工作：

我们的自动检测识别一种语言。编码确定是该确定的副产品。对于当前的工作，我们仅将俄语作为单字节实现的示例进行了介绍。由于它识别一种语言，并且只识别它使用的编码，因此语言数据模型越多，编码检测的质量就越好。

要添加其他单字节语言/编码，我们需要每种语言的大量文本样本数据和一定程度的语言知识/分析。我们目前使用脚本为该语言的所有编码生成语言模型。

这项工作目前不在 Mozilla 源中，但我们希望在不久的将来公开。当我们这样做时，我们希望具有上述资格的人在这方面做出贡献。因为我们还没有测试过很多单字节编码，所以我们在这里提出的模型很可能需要在应用于其他语言/编码时进行微调、修改甚至可能重新设计。

9. 参考：

杜斯特，马丁。1977. UTF-8 的特性和承诺。第 11 届 Unicode 会议。 http://www.ifi.unizh.ch/groups/mml/people/mduerst/papers/IUC11-UTF-8.pdf 台湾普通话推广委员会。繁体字使用情况年度调查结果。 http://www.edu.tw/mandr/result/87news/index1.htm Mozilla 国际化项目。http://www.mozilla.org/projects/intl Mozilla.org .。http://www.mozilla .org/ Mozilla 源代码查看.. http://lxr.mozilla.org/

[转载]一种字符编码猜测工具的实现方法

作者: admin
时间: 2021-06-22
分类: 默认分类
评论

摘要
自从进入计算机时代后，人们创造了许多编码，来表示各国的语言文字。这些编码从一开始设计时，就没有考虑到要和其它编码兼容，它们只是为某个国家或某种语言来服务的。

随着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

目录
摘要

Abstract

第一章引言

1.1 背景

1.2 论文的主要工作

1.3 论文的组织

第二章各种编码介绍

2.1 ASCII码

2.2 ISO-8859系列

2.3 ISO-2022系列

2.3.1 ISO-2022-CN

2.3.2 ISO-2022-JP

2.3.3 ISO-2022-KR

2.4 Unicode

2.4.1 简介

2.4.2 UTF-16

2.4.3 UTF-8

2.4.4 UTF-32

2.5 本章小结

第三章 Mozilla字符编码猜测实现方法

3.1 编码模式方法

3.2 字符分布方法（Character Distribute）

3.3 双字符序列分布方法（2-Char Sequence Distribute）

3.4 复合方法

3.5 本章小结

第四章字符编码猜测实现

4.1 理论背景

4.2 噪声数据

4.3 主要算法

4.4 实现方法概要

4.5 样本的获得

4.6 可行性分析

4.7 与Mozilla的比较

4.7.1 功能

4.7.2准确率

4.7.3 效率与复杂性

4.7.4 扩展性

4.8 本章小结

第五章总结与展望

参考文献

致谢

附录：部分域名国家（地区）对照表

第一章引言
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）

整个北欧地区．．．（重新组织了拉丁４）

注意：

1. 一个字符集可能用于多个地区，如ISO-8859-1，可以用于西欧，也可用于澳洲，北美等地区。

2. 一种语言不一定只能被一种编码表示，如拉丁１到拉丁６都能表示德语。

每个字符集有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 $ ) <F>，其中<F>表示终结字符，由ISO指定。SS2标号的形式是ESC $ * <F>，SS3标号的形式是ESC $ + <F>。新出现的同种标号会覆盖前面的标号，如SO标号ESC $ ) A可以覆盖之前出现的SO标号ESC $ ) G，接下来的出现在SO变换后的字符将由新的SO标号指定的字符集来解码。

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

GB 2312, CNS 11643-plane-1

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变换函数字符集对应关系及标号意义表

KSC 5601

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

表4-2 直线L2

表4-3 直线L3

应用方法一：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”，可能会找到行：<meta http-equiv="Content-Type" content="text/html; charset=utf-8">，说明该页面是以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

187

UTF-8-de

321

794

UTF-8-fr

204

1178

UTF-8-ir

125

1286

UTF-8-it

113

761

1016

UTF-8-cn

322

UTF-8-ru

109

1601

UTF-8-gr

113

1160

UTF-8-no

1321

UTF-8-es

459

UTF-8-pt

150

499

UTF-8-lt

123

731

UTF-8-pl

505

UTF-8-th

124

1777

UTF-8-si

767

UTF-8-jp

125

932

UTF-8-il

128

2541

UTF-8-cz

856

UTF-8-vn

110

782

UTF-8-tr

121

379

1017

UTF-8-ro

126

628

1210

UTF-8-am

104

1430

UTF-8-se

682

UTF-8-kr

112

507

Big5

164

Shift-JIS

1090

EUC-KR

166

EUC-JP

184

662

ISO-8859-1-de

105

201

2225

ISO-8859-1-fr

121

238

2849

ISO-8859-1-es

451

910

ISO-8859-1-pt

110

123

768

ISO-8859-1-se

102

274

2410

ISO-8859-1-is

365

1219

ISO-8859-1-ge

393

ISO-8859-2

101

133

1164

ISO-8859-2-pl

138

117

1362

ISO-8859-2-si

139

2833

ISO- 8859-2-c z

132

298

ISO-8859-2-ro

119

1543

3299

ISO-8859-7

426

ISO-8859-9

144

704

1451

ISO-8859-10

137

1391

2331

Windows-874

209

Windows-1250-cz

102

316

Windows-1250-si

122

136

2512

2613

Windows-1251

Windows-1255

341

Windows-1256

117

562

Windows-1257

104

637

962

ARMSCII-8

112

594

KOI8-R

374

表中加粗（红色）的数据表示猜测错误的情况（编码正确，但猜测语言错误），其余的都是表示猜测正确的情况。所有的编码都猜测正确了，除了猜测语言会有部分错误。这可能是由于这两种语言非常相近，也有可能是得到的样本非典型。即使是可能性最高的那个猜测错误，第二可能性的都是正确的结果。

组间差的最小值一般在100以内，组间方差在500内。最小值越小，说明可信度越高。次小值指名了第二可能性的编码。次小值和最小值之间的比例组间差一般超过1.5，组间方差超过3。比例越大，说明可信度越高。

从表中，可以看出准确编码的差值和最接近准确编码的那个值差距很大，这个说明了猜测结果是其它错误编码的可能性很小。

这些样本所含的数据都比较多，所以得到很高的准确率也不足为奇。若只含有少量的数据，准确率如何呢？下面这些表说明了这个问题。

表4-5到表4-16是两种方法在不同数据量的情况下各种编码的准确率情况：

表4-5 猜测GB2312的准确率

样本大小

组间差

组间方差

最小值准确率

次小值准确率

最小值准确率

次小值准确率

10字符

50%

70%

100%

30字符

100%

表4-6 猜测UTF-8-jp的准确率

样本大小

组间差

组间方差

最小值准确率

次小值准确率

最小值准确率

次小值准确率

10字符

90%

100%

30字符

100%

表4-7 猜测UTF-8-ru的准确率

样本大小

组间差

组间方差

最小值准确率

次小值准确率

最小值准确率

次小值准确率

10字符

100%

30字符

100%

表4-8 猜测Windows1251的准确率（和Windows1250-si较相似）

样本大小

组间差

组间方差

最小值准确率

次小值准确率

最小值准确率

次小值准确率

10字符

80%

100%

70%

100%

30字符

100%

80%

100%

表4-9 猜测Big5的准确率（和EUC-JP较相似）

样本大小

组间差

组间方差

最小值准确率

次小值准确率

最小值准确率

次小值准确率

10字符

90%

100%

80%

100%

30字符

100%

90%

100%

表4-10 猜测UTF-8-kr的准确率（和EUC-JP较相似）

样本大小

组间差

组间方差

最小值准确率

次小值准确率

最小值准确率

次小值准确率

10字符

100%

30字符

100%

表4-11 猜测UTF-8-cn的准确率

样本大小

组间差

组间方差

最小值准确率

次小值准确率

最小值准确率

次小值准确率

10字符

100%

30字符

100%

表4-12 猜测UTF-8-ir的准确率

样本大小

组间差

组间方差

最小值准确率

次小值准确率

最小值准确率

次小值准确率

10字符

100%

30字符

100%

表4-13 猜测Shift-JIS的准确率

样本大小

组间差

组间方差

最小值准确率

次小值准确率

最小值准确率

次小值准确率

10字符

50%

100%

40%

30字符

90%

100%

90%

100%

表4-14 猜测UTF-8-fr的准确率

样本大小

组间差

组间方差

最小值准确率

次小值准确率

最小值准确率

次小值准确率

10单词

100%

30单词

100%

表4-15 猜测UTF-8-de的准确率

样本大小

组间差

组间方差

最小值准确率

次小值准确率

最小值准确率

次小值准确率

30单词

90%

100%

90%

100%

60单词

100%

表4-16 猜测ISO-8859-1-fr的准确率

样本大小

组间差

组间方差

最小值准确率

次小值准确率

最小值准确率

次小值准确率

10单词

100%

30单词

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的同事们，在将近半年的实习中，我真的学到了很多很多。感谢你们对我的悉心指导，让我对自己有了新的认识。这段经历，是我人生的一大笔财富。

感谢我的舍友以及同学。在学习中，你们给了我很多支持与帮助，在生活中，你们给了我很多快乐。

感谢南京大学软件学院的所有老师，有了你们辛勤的劳动，才会有我们美好的未来。能在软件学院学习，真的是我的荣幸，在这里遇见那么多的好老师，学到那么多的知识。

附录：部分域名国家（地区）对照表
域名

国家（地区）

域名

国家（地区）

中国

越南

中国台湾

斯洛文尼亚

中国香港

克罗蒂亚

法国

以色列

德国

利比里亚

瑞典

波兰

冰岛

日本

俄罗斯

韩国

格鲁吉亚

意大利

亚美尼亚

泰国

罗马尼亚

葡萄牙

土耳其

捷克

伊朗

希腊

叙利亚

挪威

西班牙

立陶宛

————————————————
版权声明：本文为CSDN博主「windy444」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/windy444/article/details/2007921

[转载]一种语言/编码检测的复合方法

作者: admin
时间: 2021-06-22
分类: 默认分类
评论

翻译自Mozilla的网站。
这篇论文讨论了组合三种不同的检测方法来实现自动字符集检测。
A composite approach to language/encoding detection)
Shanjian Li (shanjian@netscape.com )
Katsuhiko Momoi (momoi@netscape.com )
Netscape Communications Corp.

[ 注：这篇论文最初发表在19届国际Unicode会议 (19th International Unicode Conference)(San Jose)。那以后，我们的实现经受住了时间和实际应用的检验，并且，我们还作了许多改进。一个主要的变化是我们现在使用正序列来检测单字节字符集，参见 4.7和4.7.1节。这篇论文写于通用字符集检测代码集成到Moailla主代码前(参见第8节)。自此以后，字符集检测代码被合并到了代码树中。如想查看最新的实现，请在Mozilla的代码树中查看相应代码。作者 - 2002年11月25日。]

1.概要：

这篇论文提供三种自动检测的方法来判定无明显字符集声明的文档的编码。我们将分别讨论每种方法的优点和缺点，并且提供了一种复合后的，更有效的方法来检测编码，这样，三种检测方法就可以互为补充。我们认为自动检测在使浏览器用户避免经常使用编码菜单手动选择编码上很有用，同时在编码菜单很少出现的情况下，提供了更合理的处理方式。我们假设，文档转化到Unicode对用户是透明的。无论字符编码采用的是某种Unicode编码还是本地编码，用户仅需知道字符最终显示是正确的就行。好的自动编码检测能有效的帮助用户处理大部分的编码事项，而无需用户手动参与。

2.背景：

自从进入计算机时代以来，人们创造了许多使用计算机数据表示的编码方案来表达不同的文字/字符集。随着全球化和Internet的发展，跨语言和区域的信息交换越来越重要。但是现存的多种编码方案对此是一个屏障。Unicode提供了通用的编码解决方案，但是，迄今为止，各种各样的因素使它并没有代替现存的区域编码方案。除了W3C和IETF建议使用UTF-8作为缺省编码，比如XML，XHTML， RDF。因此，现今的国际化软件不仅要处理Unicode编码，还要处理其它多种不同的编码方式。

我们当前的工作是在开发Internet 浏览器的环境中开展的。为了处理如今Web上使用不同编码的各种语言，我们做了许多努力。为了获取正确的显示结果，浏览器需要利用HTTP服务器返回的编码信息，网页或者是最终用户通过选择编码菜单而得到的编码方式。此外，大部分用户没有能力手动的通过编码菜单来进行操作。如果没有编码信息的话，网页有时就会显示为“垃圾”字符，用户就无法得到他们想要的信息。这最终会导致用户认为他们的浏览器有故障或有Bug。

由于越来越多的 Internet标准协议指定Unicode作为缺省的编码方式，网页将会不容置疑的转向使用Unicode来编码。好的通用自动检测方法可以对这种转向提供重要的贡献，因为它们工作很自然，无需用户使用编码菜单。在这种情况下，渐进的转向将会以用户不易察觉的方式进行，这是由于，对用户来说，网页总会显示正确，他们无需考虑使用编码菜单。这种平滑的转变将使编码对用户来说越来越不需要关注。自动检测在这种场景中将很关键。

3.问题范围(Problem Scope)：
3.1. 通用模式

让我们从通用的模式开始。对大多数的应用，下面的示例将代表一个自动检测使用的通用框架：

输入数据 -> 自动检测器 -> 返回结果

应用/程序接受自动检测器返回的结果，并且将信息使用在不同用途上，比如，设置数据的编码，显示原始创建者的数据，将它传给其他的程序，等等。

这篇论文中所讨论的自动检测方法使用Internet浏览器作为应用环境，其他的应用也可以很容易的将其移植。

3.2. 浏览器和自动检测

浏览器可以使用某种检测算法来自动检测网页的编码方式。一个程序可以潜在的在假定不同编码的前提下，对一段文本做出随意的解释，但是，除了一些极端罕见的情况外，只有一种解释才是网页作者想要得。这就是为什么通常对用户来说，只有指定的语言才能正确合理的显示网页。

为了列出设计自动检测算法中的主要因素，我门对输入文本和步骤作如下假定，以网页数据作例，

对某种语言来说，输入文本由对读者来说具有可读性的单词/句子组成。(=数据具有非垃圾性)
输入文本是从Internet上的典型网页中取得的。(=数据不是从一些消失的或者是古代的语言中取得的)
输入文本中有可能包含和编码无关的，额外的噪音数据。比如HTML的标记，无关的单词(如，出现在中文文档中的英文单词)，空格和其它的格式/控制字符。
对自动检测来说，要包含所有已知语言和编码方式几乎是一项无法完成的任务。在现今的方法中，我们试图包含所有东亚语言中常用的编码，同时，对单字符检测也提供了一种通用模式。俄语编码被选择作为后一种检测方法实现的例子，同时也作为单字符检测测试的基础。
目标中的多字节编码方式包括 UTF8，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介绍

在这一节中，我们讨论三种不同的检测文本数据编码的方法，它们是1)编码模式方法(Coding scheme method，2)字符分布(Character Distribute)，和3)双字符序列分布(2-Char Sequence Distribute)。每种方法单独使用的时候，都有它的长处和不足，如果我们以互补的方式使用所有3种方法的话，结果将是非常理想的。

4.2编码模式方法

这种方法在检测多字节编码的时候也许是最显而易见的方法，也是通常最容易使用的方法。在任何多字节编码模式中，并不是所有可能的代码点都被使用的。如果在验证特定编码的时候，碰到一个非法字节或非法字节序列(如，无用的代码点)，我们可以立即判断出这种编码猜测不是正确的。一小部分的代码点同样也能代表特定的编码方式，这样，我们也能利用这种事实立即做出正确的判断。Frank Tang(Netscape Communications)开发了一个非常有效的，基于编码模式的，通过使用并行状态机(parallel state machine)来检测字符集的算法。他的基本思想是：

对每一个编码模式，都有一个相应的状态机被用来验证这种特定编码的字节序列。对检测器收到的每一个字节，它将会被输入到每一个可用的，活动的状态机中，每次一个字节。状态机基于前一个状态和它所收到的字节来改变它的状态。自动检测器对状态机的三种状态感兴趣：

START 状态：这种状态代表两种情形，初始化，或是代表字符集的一个合法字节序列已被验证。
ME 状态：这种状态代表状态机验证到了字符集特有的一个字节序列，并且其它可能的字符集不包含这个字节序列。这会导致检测器立即返回一个确定的回答。
ERROR 状态：这种状态代表状态机验证了字符集的一个非法字节序列。这会立即导致对这种字符集的否定回答。检测器从此将会排除这种编码方式，不作考虑。

在一个典型的例子中，只有一个状态机会作出确定的回答，而其它的状态机会做出的否定的回答。

我们当前工作中使用的PSM(Parallel State Machine)版本是Frank Tang原先工作改造后的版本。只要一个状态机达到START状态，就意味着它成功检测了一个合法的字符序列，我们向状态机查询这种字符序列中总共有多少个字节。这个信息会用在2个方面：

首先，对UTF-8编码方式来说，如果有许多多字节的序列都通过验证的话，输入的数据很少有可能不是采用UTF-8编码的。因此，我们统计UTF-8状态机验证过的多字节数。当达到一个特定的数量时(=阀值)，结论就可以做出了。
其次，对其它的多字节编码来说，这个信息可以输入到字符分布分析器(可以查看下面的介绍)，这样，分析器就可以在字符数据而不是原始数据的基础上进行工作了。

4.3字符分布方法：

无论哪种语言，总有一些字符比其它字符更常用。利用这个事实，我们可以对每种语言建立起相应的数据模式。对那些字符数较多的语言，比如汉语，日语和韩语，尤其有用。我们经常听到与此有关的分布统计，但是我们没有找到太多的公布结果。因此，为了继续讨论，我们依赖自己搜集的数据。

4.3.1.简体中文：

我们对采用GB2312编码的6763个字符研究的结果，显示出如下的分布结果：

Number of Most Frequent Characters	Accumulated Percentage
10	0.11723
64	0.31983
128	0.45298
256	0.61872
512	0.79135
1024	0.92260
2048	0.98505
4096	0.99929
6763	1.00000

Table 1. Simplified Chinese Character Distribution Table
4.3.2.繁体中文：

对于采用Big5编码的繁体中文，台湾普通话推广委员会(Taiwan's Mandarin Promotion Council)年度研究显示了类似的结果。

Number of Most Frequent Characters	Accumulated Percentage
10	0.11713
64	0.29612
128	0.42261
256	0.57851
512	0.74851
1024	0.89384
2048	0.97583
4096	0.99910

Table 2. Traditional Chinese Character Distribution Table

4.3.3.日语

对日语，我们采用自己搜集的数据，并写了一个实用程序来分析它们。下面的表格显示了结果：

Number of Most Frequent Characters	Accumulated Percentage
10	0.27098
64	0.66722
128	0.77094
256	0.85710
512	0.92635
1024	0.97130
2048	0.99431
4096	0.99981
	1.00000

Table 3. Japanese Character Distribution Table

4.3.4.韩语

同样，对于韩语，我们采用自己从Internet上搜集的数据，并用我们自己的实用程序分析它们，结果如下：

Number of Most Frequent Characters	Accumulated Percentage
10	0.25620
64	0.64293
128	0.79290
256	0.92329
512	0.98653
1024	0.99944
2048	0.99999
4096	0.99999

Table 4. Korean Character Distribution Table

4.4.分布结果的通用特性：

对所有4种语言，我们发现在我们定义的应用范围内，很少一部分的编码点占据了较大的百分比。此外，对这些代码点的更进一步的考察显示它们散布在一个很广的编码范围中。这给了我们克服在编码模式分析中遇到的通用问题的一种途径，如，不同国家的编码有可能共享一些相互重叠的代码点。由于这些语言中最常出现的字符集具有我们上面描述的特性，因此，在编码模式方法中不同编码有相互重叠的问题，将在分布方法中变得无关紧要了。

4.5.分析算法

为了验证某个语言基于字符出现频率/分布的统计特性，我们需要一个从文本输入流中计算出一个数值的算法。这个数值将表明文本是某种字符集编码的可能性。一个很直观的做法是用每个字符的出现频率权重来计算这个值。不过，从我们对不同字符编码的经验上，我们发现这种做法并不是必须的，而且它占用了太多 CPU处理能力和过多的内存。一个简单的版本同样提供了很令人满意的结果，并且使用非常少的资源，同时运行得很快。

在我们当前的方法中，一个给定编码中的所有字符会被分到两个类别中，“经常使用的”和“非经常使用的”。如果一个字符是出现在出现频率分布表中的前 512个字符中，它会被分类到“经常使用”。之所以选择512，是由于它在所有4种语言的输入文本中都覆盖了很大一部分的百分比，同时仅占据一小部分的代码点。在输入文本中，我们以批处理的方式统计每个类别中字符的数量，然后计算一个我们称之为分布率(Distribuion Ratio)的浮点值。

分布率的定义如下

分布率 = 出现在512个最常用的的字符中的字符数量 / 出现在剩下的字符中的字符数量

每一种检测过的多字节编码方法都显示了独特的分布率。从分布率起，我们就可以对原始输入的文本对一个给定的编码方法来计算可信度。下面对每一种编码方法的讨论将会对这个问题说得更清楚一些。

4.6分布率和可信度(Confidence Level)：

让我们分别通过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*p2 – 512*p1) = 512/(3755 + 3008*p2/p1-512)

很明显，这个值将更小。在后面的分析中，我们仅使用最坏的情况作为比较。

4.6.2.Big 5：

Big5和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.279

4.6.5.计算可信度

从前面对每一种语言的讨论，我们可以以如下的形式定义出每一种数据集的可信度

Confidence Detecting(InputText)
{
for each multi-byte character in InputText
{
      TotalCharacterCount++;
      if the character is among 512 most frequent ones
          FrequentCharacterCount++;
}

   Ratio = FrequentCharacterCount
                / (TotalCharacterCount-FreqentCharacterCount);
   Confidence = Ratio / CHARSET_RATIO;
   Return Confidence;
}

对每一种数据集的可信度定义为输入数据的分布率除以从上面分析得出的理想分布率。

4.7.双字符序列分布方法

对仅使用很少一部分字符的语言来说，我们需要比统计单字符出现率更进一步。字符组合揭示了更多的语言-字符特性。我们定义双字符序列为在输入文本中接连出现的2个字符，在这种情况中，顺序是非常重要的。由于在一种语言中，并不是所有字符都具有相同的出现率，双字符序列分布非常倾向于与语言/编码相关。这种特性可以用在语言检测上。在检测字符编码的时候，这会导致更好的可信度，在检测单字节编码上很有用处。

用俄语举例来说。我们下载了20MB的俄语纯文本，并且编写了一个程序来分析文本。这个程序发现了总共为21199528个双字符序列。在我们发现的序列中，有一些是和我们的考察无关的，比如空格-空格组合。这些序列被认为是噪音序列，并且，它们的出现没有被包含在分析中。在我们用来检测俄语的数据中，去处这些噪音数据，剩下20134122个双字符序列。总共占据我们从数据中所发现序列的95%。用来建立我们语言模式的序列可以被分为4096个不同的序列，并且，其中的1961个序列在我们的20134122个样本中出现次数少于3次。我们称这些序列为这种语言的负序列集。

4.7.1.可信度检测算法

对单字节语言，我定义如下的可信度：

Confidence Detecting(InputText)
{
for each character in InputText
{
      If character is not a symbol or punctuation character
          TotalCharacters++;
    Find its frequency order in frequency table;
      If (Frequency order < SampleSize)
      {
        FrequentCharCount++;
        If we do not have lastChar
        {
           lastChar = thisChar;
           continue;
        }
        if both lastChar and thisChar are within our sample range
        {
         TotalSequence++;
         If Sequence(lastChar, thisChar) belongs to NegativeSequenceSet
           NetgativeSequenceCount++;
        }
      }
   }
   Confidence = (TotalSequence – NegativeSequenceCount)/TotalSequence
                * FrequentCharCount / TotalCharacters;
   return Confidence;
}

在这个算法中，需要对如下事情解释一下。

首先，序列分析没有对所有的字符都进行。我们当然可以通过建立一个256 x 256的矩阵来包含所有的那些字符序列，但是，其中的许多对语言/编码分析来说是无关的。由于绝大多数的单字节语言仅使用数量不多于64个的字母，而最常使用的64个字符几乎包含了所有语言中都有的字符。因此，矩阵可以缩减成为更小的64 x 64。所以我们使用64作为我们工作中的采样大小。我们选择用来建立我们模式
的64个字符，是基于频率统计并作了相应调整后的。一些字符，比如0x0d和0x0a，在我们的观点中，和空格(0x20)很相似，所以，从我们的样本中移除了。

其次，对所有被64 x 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 Duerst's(1977))。编码模式方法和字符分布方法一起作用在了对主要东亚字符编码进行检测上，例如GB2312，Big5，EUC-TW， EUC-KR，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, otherwise return ASCII;
       }
       else
          return ASCII;
   }
   else if (InputText start with BOM)
{
      return UCS2;
}
else
{
      Call 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%的准确率。

例如，当我们访问一个没有提供字符集信息的网站(例如，在http://www.yahoo.co.jp 上的网站的服务器没有发送字符信息前)，我们的的字符检测器生成如下的输出：

[UTF8] is inactive
[SJIS] is inactive
[EUCJP] detector has confidence 0.950000
[GB2312] detector has confidence 0.150852
[EUCKR] is inactive
[Big5] detector has confidence 0.129412
[EUCTW] is inactive
[Windows-1251 ] detector has confidence 0.010000
[KOI8-R] detector has confidence 0.010000
[ISO-8859-5] detector has confidence 0.010000
[x-mac-cyrillic] detector has confidence 0.010000
[IBM866] detector has confidence 0.010000
[IBM855] detector has confidence 0.010000

因此，EUC-JP编码对这个站点来说是最可能的编码方式。

7.结论：

在我们的环境中，利用编码模式，字符分布和双字符序列分布的复合方法来检测语言/编码被证明是非常有效的。我们覆盖了Unicode编码，多字节和单字节编码方式。在我们当前的Internet数字文本中，这些编码方式是很有代表性的。我们有理由相信，通过扩展，这种方法可以覆盖没有包括在这篇论文中的，余下的编码方式。

尽管在当前，在我们的检测中，只有编码信息才是我们所需要的，在大多数的情况下，语言信息同样也能被识别出。事实上，字符分布和双字符分布方法都依赖于不同语言字符集的分布模式。只有在UTF16和UTF8的情况下，编码方式能被识别出，而语言信息仍是未知的。即使是在这种情况下，我们的工作也可通过将来的被扩展以覆盖语言信息的检测。

这里列出的三种检测方法在Netscape 6.1 PR1中已被实现了，并且作为后继版本中的"Detect All"选项。我们希望我们在自动检测上的工作可以使用户从麻烦的对字符编码菜单操作中解脱出来。字符编码菜单(或者其他形式的编码菜单)与其它的 Internet客户端的界面元素不同，它们对一般的用户暴露了部分国际化的信息。它的存在折射出了当前的网页加入语言/编码方式后是多么的凌乱。

我们希望通过提供缺省的好的编码和通用自动检测能帮助用户在处理网络事务中可以避免大部分的问题。Web标准正在向使用Unicode作为缺省编码转移，特别的，是在向UTF-8转移。我们期望其在Web中逐渐地被使用。由于使用了自动检测，这种转移可以悄然进行，越来越多的用户在浏览，或是在阅读 /发送消息的时候将从面对编码事宜中解放出来。这也是为什么我们提倡互联网客户端要使用好的自动检测方法和好的缺省的编码设置。

8.将来的工作：

我们的自动检是设计用来识别语言的。编码判断是这个识别的副产品。在当前工作中，在单字节实现中，我们用俄语举例。由于它识别语言和这个语言下的编码方式，因此语言数据越多，编码检测的质量越高。

要想加入其它的单字节语言/编码，我们需要每一种语言的，大量的文本采样数据，同时需要对语言的认知/分析有一定的深度。我们当前使用脚本来对一种语言的所有编码生成一种语言模式。

当前，我们的工作还没有在Mozilla源代码中体现出来，但我们希望在不远的将来我们的工作会变得公开。我们希望有人在这个领域内做出贡献。因为我们还没有对许多单字节编码做过测试，我们希望在处理其它语言/编码的时候，我们在这里提出的模式可以得到更好的调整，修改甚至是重新设计。

9.引用
Duerst, Martin. 1977. The Properties and Promizes of UTF-8. 11th Unicode Conference.
http://www.ifi.unizh.ch/groups/mml/people/mduerst/papers/IUC11-UTF-8.pdf
Mandarin Promotion Council, Taiwan. Annual survey results of Traditional Chinese character usage.
http://www.edu.tw/mandr/result/87news/index1.htm
Mozilla Internationalization Projects.  http://www.mozilla.org/projects/intl
Mozilla.org.  http://www.mozilla.org/
Mozilla source viewing.  http://lxr.mozilla.org/