（计算机软件与理论专业论文）基于文本的语言识别方法研究.pdf

南京邮电大学硕士研究生学位论文中文摘要 中文摘要 本文的研究工作是针对因特网上的文本数据进行语言识别，包括网页和电子邮件内容 等，以构建实时、高效的语言识别模块为目标，设计了一种复合方法来实现多语种文本的 语言识别。 本文首先介绍了区域编码方案和u n i c o d e 并存的现状，指出语言识别在计算机自然语 言处理领域中的广泛应用，分析了语言识别方法的研究现状。然后，具体研究了目前主要 的基于文本的语言识别方法，包括基于编码非重叠区的、采用字频分布统计的、利用马尔 可夫模型建立语言模型的以及采用部分匹配预测压缩算法的语言识别方法，这些技术将被 用到文中提出的语言识别模块设计方案中。之后，本文设计了一种语言识别的方法，即融 合了基于编码非重叠区的识别方法和语言统计模型识别方法的复合识别方法。在对真实数 据进行实验和分析的基础上，设计了语言字符分布律统计模型和可信度计算模型，保证了 准确和高效地实现语言识别。 本文设计和实现的语言识别模块能够对目前因特网上广泛使用的主要语言字符集进 行识别，包括u n i c o d e 字符集，多字节和单字节编码方式的字符集，满足电子邮件转发和 过滤引擎、网页编码识别等实时系统的应用需要，并且该模块已经在国家某部委的应用工 程中得到了应用，获得了很好的评价。 关键词：语言识别，语言模型，字符集，基于文本 a b s t r a c t t h et h e s i sf o c u s e so nt e x t b a s e dl a n g u a g ei d e n t i f i c a t i o nf r o mi n t e r n e td a t a ，i n c l u d i n gw e b p a g e sa n de - m a i lc o n t e n t ，e t c t oc r e a t eh i g h l ye f f i c i e n ta n dr e a l t i m el a n g u a g ei d e n t i f i c a t i o n m o d u l e ，ac o m p o s i t em e t h o di su s e d ，w h i c hc 柚r e c o g n i z em u l t i l i n g u a lt e x t f i r s t l y , t h ec o e x i s t e n c es t a t u so fu n i e o d ea n dr e g i o n a lc o d i n gs c h e m e si si n t r o d u c e d t h e n i tp o i n t so u th o w w i d e l yl a n g u a g ei d e n t i f i c a t i o ni su s e di nn a t u r a ll a n g u a g ep r o c e s s i n ga n d r e v i e w st h em a i n l yr e s e a r c h e sh a sb e e nd o n ei nt h ef i e l d i ti n t r o d u c e sr e p r e s e n t a t i v em e t h o d s o ft e x t - b a s e dl a n g u a g ei d e n t i f i c a t i o n ，s u c ha st h r o u g hn o n o v e r l a p p i n gc o d i n g ，c o m m o nw o r d s a p p r o a c h ，m a r k o vl a n g u a g em o d e la p p r o a c h ，n g r a ma p p r o a c h ，c o m p r e s s i o nb a s e da p p r o a c h w i t hp p m ( p r e d i c t i o nb yp a r t i a lm a t c h i n g ) t h et e c h n o l o g i e su s e di nt h o s em e t h o d sa r ep a r t l y c h o s e nt ob u i l dal a n g u a g ei d e n t i f i c a t i o nm o d u l e t h ea l g o r i t h mf o c u s e so nh o wt ou s e n o n 。o v e r l a p p i n gc o d i n go fc h a r a c t e r sa n ds t a t i s t i c a ll a n g u a g em o d e lt oe n s u r ea c c u r a c ya n d e f f i c i e n c yi nl a n g u a g ei d e n t i f i c a t i o n i tp r o p o s e dm e t h o d st oc r e a t el a n g u a g ed i s t r i b u t i o nm o d e l a n dc o n f i d e n c em o d e l a l a n g u a g ei d e n t i f i c a t i o nm o d u l ei sb u i l tt oi d e n t i f ym o s tc h a r a c t e rs e t su s i n go ni n t e r a c t ， i n c l u d i n gu n i c o d e ，s i n g l e - b 礼ea n dm u l t i b y t ec h a r a c t e rs e t s t h em o d u l ei sq u a l i f i e dt ob eu s e d i nr e a l - t i m es y s t e ma p p l i c a t i o n s ，s u c ha se m a i l f o r w a r d i n ga n df i l t e r i n ge n g i n e w e bp a g e s e n c o d i n gi d e n t i f i c a t i o n ，e t c k e y w o r d s ：l a n g u a g ei d e n t i f i c a t i o n ，l a n g u a g em o d e l ，c h a r a c t e rs e t ，t e x t b a s e d 南京邮电大学硕士研究生学位论文图表清单 图表清单 图i - i 因特网用户世界范围分布情况1 图i - 2 网民使用的l o 种主要语言的分布情况图z 图i - 3 网页显示文档已被翻译成3 3 5 种语言3 图i - 4 采用统计学方法进行语言识别的一般架构图5 图3 - i 有限状态机的工作原理1 3 图3 2d u n n i n g 基于马尔可夫模型的识别算法测试结果1 7 图3 3 单词”f o r m a t ”的字符序列1 8 图3 - 4c a v n a r 的n - g r 锄特征值距离算法1 9 图4 - i 语言识别模块的框架2 5 图4 2 语言识别模块在邮件内容过滤中的应用2 6 图4 - 3 单字节编码识别的可信度算法3 4 图4 - 4 单字节编码识别中主要的类关系图3 6 图4 5 实现g b l 8 0 3 0 编码识别算法用到的类及类之间的关系3 7 图4 - 6 语言识别模块最上层的控制算法4 2 图4 7 模块实现中用到主要类及类关系图j 4 3 表i - iu n i c o d e 在亚洲和非洲的使用情况统计4 表2 - 1 部分文字编码的c h a r s e t 值8 表3 1g r e f e n s t e t t e 对字频统计语言识别方法的测试结果1 4 表3 2c a v n a r 采用n - g r a m 方法进行语言识别的结果数据2 0 表3 3 利用p p m c 算法为字符串”a b r a c a d a b r a 建立上下文模型( 最大历史长度为2 ) 2 2 表3 - 4 利用表3 - 3 模型计算c 、d 、t 的编码位数2 3 表3 - 5t e a h a n 采用p p m 算法对六种语言测试的识别结果2 4 表4 - i 中、日、韩字符分布统计表3 9 表4 2 语言识别模块测试结果1 4 4 表4 - 3 语言识别模块测试结果2 4 5 5 0 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名： 熟鱼耋日期：皇! ：i ：丝旦 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理。 研究生签名：f 系z 白多导师签 坚塑! ! 盔兰壁主堕些兰兰些望兰一 塑! 童堕丝 第l 章绪论 1 1 研究背景 随着信息基础设施建设日益完善，因特网( i n t e m e t ) 在人们日常生活申变得越来越 重要，它已深入到人们生产、生活的各个领域，向人们提供着巨大的并日还在不断增长的 信息资源和服务，越来越多的公司、企业通过网页宣传自己，越来越多的科研机关和学校 通过网页交流科研成果越米越多的组织和个人拥有了自己的主页，越来越多的报刊、杂 志加八了i n t e m e t 的大家庭。c n n i c ( 中国互联网络信息中心) 发布的第2 1 欢中国互 联网络发展状况统计报告显示吼截至2 0 0 7 年1 2 月3 1 日，中国网民数达到2 l 亿， 中国网页为8 47 亿个网站总字节数己经达到1 9 8 3 4 8 g b 。伴随着i n t e m e t 的快速发展， 网负、电子邮件等带来了海带的文本数据。每天，这些海量的文本通过丌联网牛成、传 播、变换、储存和访问，进 位于吐界各地的人们日常牛活中。 在i m e m e t 带来的海量文本数据中，语言多样性带来的问题特别值得关注。来自 i n t e m e tw o r l ds t a t s 的统计数据显示”，2 0 0 7 年末，全世界人1 2 约为6 60 7 亿，网民约占 2 0 ，人数达到1 3 2 亿，各地网民分布情况如图i l 所示，网民使用的l o 种主要语言的 分布情况如图1 2 所示。 w o f i di n t e r n e tu s e r s d e c e m b e r2 0 0 7 i 鬯1 。 黝 图1 - i 因特网用户世界范围分布情况 - l 塑重墅皇盔堂塑婴墨笔堂鲨!里! 垩堕堡 t o p1 0i n t e r n e tl a n g u a g e s - n o v e m b e r2 0 0 7 c _ o p a r i s h = j j a p m 纠一8 8 fr e n c hl - _ 6 4 g o r m a n 曼_ 6 2 p m m e 一_ 5 1 ar a b i c 日_ k o r e a n 羔| 一3 4 i t a l i a nui3 3 r e s t l a n g u a g e s 鞠函黼嘲嘲簟嘲2 d 0 5 01 0 01 5 02 0 02 5 03 0 03 5 04 0 04 5 0 m o f u s e r 0 s 0 ur c l n ”m e - i d s t a t sc o m c o p y t i g h t 2 0 0 8m i n ar t sm ar k e l i n ggr o 叩 图l 网民使用的1 0 种主要语占的分布情况图 数据显示使用十种主要语言的网民约占世界网民总数的8 37 ，其中使用英语的网民占 的比莺最大，占到三成以上。实际上，据统计，世界上使用人数较多的语言主要有8 2 种， 这些语言中任何一种都有超过1 0 0 0 万人在使用其他使用人数相对较少的语者更是多达 数千种。在联合围c i 目站上，你可以发现联合国大会一九四八年通过并颁布的世界人权宣 言已被翻译成3 3 5 种语言( 图1 - 3 ) ，其中有部分语言的翻译是以图片方式提交的。在 计算机中，语言信息的编码方式复杂多样，最初的字符集是a s c i i ( a m e r i c a ns t a n d a r dc o d e f o ri n f o r m a t i o ni n t e r c h a n g e ，美国倩息互换标准代码j ，但是，由于a s c l l 支持的字符很有 限，在多国文字表达方面等有很人的不足，为了将率国语言输八计算机，各个国家和地区 产生了不同的字符编码方案，以亚太地区为例，有中文编码方案g b 2 3 1 2 、g b l 8 0 3 0 、b 1 g 5 ， 同语编码方案s h i f l - j i s 、e u c j p 、j i s ，韩语编码方案e u c k r 等等。这些区域编码方 案大部分都是对a s c i i 进行扩展，扩展的内容各不相同。 塑星型里查芏堡! 型塞圭芏些堡苎里! 里堑丝 图1 3 网页显示文档已被翻译成3 3 5 种语言 由于区域编码方案太多且彼此之间不兼容，互相之间存在冲突的情况，在多种语言文 字同时使用及存储的情况下，如果没有一种语言识别的机制，就会给信息的变换和理解带 来障碍。只有当信息的编码和解码能够统的时候，信息才是可以被交换和理解的；当信 息编码和解码不能够统一的时候，信息就不能被交换和理解了。以网页为例，h t m l 语 言并没有规定页面中必须给定c o n t e n t - t y p e 值引，在很多h t m l 页面中就没有包含 c o n t e n t t y p e 值，这样当某个地区的互磺网站点将其网页的编码方案设为当地语言，且末 给出贞面的语言信息，那么，其他地区的用户访问该站点时，计算机是无法进行正确解码 的，浏览器展现给用户的将是一些毫无意义的乱码。 u n i c o d e 提供了通用的编码解决方案，它给每个字符提供了一个唯一的数字p “。1 9 9 0 年开始研发，】9 9 4 年正式公布u n i c o d e 在面世以来的十多年发展迅速，其标准已经被工 业界的领导们所采用，例如a p p l e ，h p , i b m ，m i c r o s o f t ，o r a c l e ，s a p , s u n ，s y b a s e 等，晟新 的标准如x m l ，j a v a ，e c m a s e r i p t ( j a v a s c r i p t ) ，l d a 只c o r b a30 ，w m l 等都需要 u n i c o d e ，u n i c o d e 是实现i s o 九e c1 0 6 4 6 的正规方式。但是，i t u t ( t e l e c o m m u n i c a t i o n s t a n d a r d i z a t i o ns e c t o r ，国际电信磺盟远程通信标准化组) 对i n t e r n e t 上u n i c o d e 的使用情 况调查( 表1 - i ) 表明川日前u n i e o d e 并没有取代现存的区域编码方案。在各种区域编 码方案和u n i c o d e 还将长期并存的情况下，语言识别提供了种良好的解决力案，使得区 域编码方案向u n i c o d e 的转变过程，能够渐进平精地进行。 南京邮电人学硕十研究生学位论文第l 章绪沦 表1 1u n i c o d e 在亚洲和非洲的使用情况统计 u n i c o d e 在亚洲和非洲的使用情况统计 亚洲语言( 未统计中、日、韩三国)非洲 涧垒u 寸f 日72 0 0 5 年9 月2 0 0 5 年1 2 月 访问的w e b 服务器数目3 3 ，6 9 4 1 8 2 ，6 7 l 至少含有一个u n i c o d e 页面 5 ，0 0 89 ，1 8 4 的w e b 服务器 ( 1 5 ) ( 5 ) 抓取的网页数4 3 0 0 万7 7 0 0 万 5 6 0 万6 6 0 万 使用u n i c o d e 的网页数 ( 1 3 ) ( 1 1 ) 面对因特网上不断产生的海量文本数据，文本数据挖掘( t e x tm i n i n g ) 这- - 新兴学科已 成为一个引人瞩目，发展迅速的领域。人们开发了各种各样的文本数据挖掘系统，例如基 于内容和特定语言的网络爬虫和搜索引擎系统、文档分类系统、机器翻译系统等等。这些 系统在进行自然语言处理时，不仅需要知道数据的编码方案( 以便还原数据) ，而且需要 知道是哪种自然语言的数据。各种语言在作进一步的形态加工，如在进行词干提取或分析 之前，必须要获得文本的语种信息。此外，如果要对一个词汇进行拼写检查，也需要先知 道语种信息，以便采用具体的规则。因此，语言识别在自然语言处理领域具有重要的作用。 1 2 研究现状 根据数据来源的不同，语言识别可分为基于语音的语言识别和基于文本的语言识别。 这里的文本是指只有文字处理没有图像等其他的程序处理。本文主要探讨基于文本的语言 识别，在以下内容中，如未特别说明，所指的语言识别均为基于文本的语言识别。 什么是基于文本的语言识别? 其定义是：能够从文本或文本片段中，自动、高效、正 确地识别出语言、字符集和编码信息。g o l d 在1 9 6 7 年发表的论文“l a n g u a g ei d e n t i f i c a t i o n i nt h el i m i t ”可视为语言识别领域的开创性工作【2 0 】，他将语言识别视为一个封闭类问题： 给定一个可能的语言列表清单，提供语言样本，要求在有限的时间内对样本按语言进行分 类。当时的实验假设所有语言都有一个公共的字形表示方式，并且样本是从特定语言的文 本中随机选取的字符串。 、 在这之后，人们做了大量的研究和测试，各种自动化的语言识别方法被广泛用在科研 和工业领域。这其中主要有两大类方法，首先，基于语言编码规则的识别方法。例如，基 于编码非重叠区的识别方法是一种比较简单实用的语言识别方法。该方法基于这么一个现 象：虽然各种字符编码空间有重叠的部分，但也不是完全一致的，利用并编码空间的非重 叠区即可达到编码识别的目的。若待识别文本中出现了某个只存在于某种编码空间的字 4 南京邮电人学硕【j 研究生学位论文第l 章绪论 符，则可以排除其它编码形式的可能性。基于标点符号的识别方法是一种特殊的基于编码 非重叠区的方法。标点符号在各种编码形式下内码均不相同，因此通过统计标点符号在各 种编码形式下的出现概率即可识别文本的编码形式。语言识别的第二类方法是采用统计学 方法来进行的。这类统计学方法包括：基于字频分布的语言识别方法，基于n g r a m 模型 的语言识别方法【】，基于马尔可夫模型的编码识别方法【坨】，基于压缩的部分匹配预测 ( p p m ，p r e d i c t i o nb yp a r t i a lm a t c h i n g ) 识别方法【1 4 】【1 7 】等。 目前语言识别方法的研究主要集中在使用统计学方法进行语言识别上。这类方法通过 大规模的语料库训练，提取一系列语言模型，然后通过比较文本与训练好的语言模型的特 征值，进行匹配，如c a v n a r 等人依据字符同时出现所具有的特征建立了n g r a m 统计模 型，d u n n i n g 用马尔可夫模型实现了语言识别。采用统计学方法进行语言识别的一般架构 如图l - 4 所示： ；五言- i 口旦i i 语言l 1 语言( in ，n = l ，2 ，) j - 坎刊 - j 1语言l l 。黛黛套孽跫。一 坳日t b 一 。、i d “1 0 馥 缓锄貔i l 蹴锄缓 i 需要进行语言识别识别结果：最接 争的文本 ； 语言识别算法 0，。近的语言信息； 。| 。? j 懑 k ，茹弗，；私。砌勰；。彩；瓣，彩铷。觑。么魏h 。力 图1 _ 4 采用统计学方法进行语言识别的一般架构图 语言识别在自然语言处理各领域均有广泛的应用，如文本信息抽取、文本分类、文本 聚类、电子邮件转发和过滤引擎、网页编码和语言的识别、信息检索系统、机器翻译、基 于内容和特定语言的网络爬虫和搜索引擎等。目前，国内基于文本的语言识别方法的研究 主要集中在中文汉字的识别上【2 3 】阱】，随着国际交流、商务来往以及个人沟通的迅速增长， 多语种文本的语言识别将会越来越重要。 1 3 本文的主要工作 本文的主要工作如下： 1 ) 分析了目前语言识别方法的研究现状，对目前主要的语言识别方法进行了介绍， 并结合测试结果概括了各种算法的优点和缺点。 南京邮电人学硕十研究生学何论文 第l 章绪论 2 ) 设计了一种语言识别的复合方法。将基于编码非重叠区的识别方法和采用语言统 计模型的识别方法进行复合，在对真实数据进行实验和分析的基础上，设计了语 言字符分布律统计模型和可信度计算模型，保证了准确和高效地实现语言识别。 3 ) 用我们设计的复合语言识别方法实现了一个语言识别模块，该模块能够对目前 i n t e m e t 上广泛使用的主要语言编码方式进行识别，包括u n i c o d e 字符集、多字节 和单字节编码方式的字符集，满足电子邮件转发和过滤引擎、网页编码识别等实 时系统的应用需要。 4 ) 对我们实现的语言识别模块进行了测试和分析。 论文的内容组织结构如下： 第一章介绍了基于文本的语言识别的研究背景和现状。 第二章介绍了语言识别方法中的一些概念及相关技术。 第三章分析了目前语言识别的主要方法及各种方法的优缺点。 第四章提出了我们设计的一种复合的语言识别方法，并介绍了我们采用这种复合方法 实现的一个语言识别模块，文中详细地说明了复合方法的设计和模块的实现过程，并对模 块进行了测试和分析。 第五章对本文的主要工作进行了总结。 6 南京邮电人学硕十研究生学停论义第2 爷相关概念和技术 第2 章相关概念和技术 2 1 语言 语言文字是一个民族的重要特征。每一个民族都要通过语言进行内部交流和与其他民 族进行交流，所以每个民族至少有一种语言，有的还会讲几种语言。语言根据他们共有的 特点可以划分成不同的“语系”。 。 2 2 字符和字节 字符是各种文字和符号的总称，包括各国文字、标点符号、图形符号、数字等。在计 算机中，字符是表达信息的主要方式，字符的主体部分是a s c i i ( a m e r i c a ns t a n d a r dc o d e f o ri n f o r m a t i o ni n t e r c h a n g e ，美国信息互换标准代码) 。 字节是计算机中存储数据的单元，一个8 位的二进制数，是一个很具体的存储空间。 2 3 字符集和编码 字符集是一组抽象字符的集合，即多个字符的集合。编码规定每个字符是用一个字节 还是多个字节存储，以及用哪些字节来存储。 各个国家和地区在制定编码标准的时候，“字符的集合”和“编码”一般都是同时制 定的。因此，平常我们所说的“字符集”，比如：g b 2 3 1 2 ，g b l 8 0 3 0 ，g b k 等，除了有“字 符的集合”这层含义外，同时也包含了“编码”的含义。但是，对于u n i c o d e 来说，“u n i c o d e 字符集”包含了各种语言中使用到的所有“字符”，是唯一的。而用来给u n i c o d e 字符集 编码的标准却有很多种，如u t f 8 ，u t f 1 6 ，u n i c o d el i t t l e ，u n i c o d eb i g 等。 2 4 文本和文档 纯文本文件也称非文书文件，如计算机源程序文件、原始数据文件等均属于纯文本文 件，它注重的是字母符号的内在含义，一般不需要编辑排版。在文本文什内除回车符外， 没有其他不可打印或显示的控制符，因此，在各种文字处理系统问可以1 1 j 互通用。 7 南京邮电人学硕十研究生学何论义第! 窜相关概念和技术 带格式文本文件通称文档文件，也称文书文件，例如文章、报告、书信、通知等都属 于文档文件。它注重文字表现形式，成文时需要对字符、段落和页面格式进行编辑排版。 在文档文件中，由于不同的文字处理系统设计的格式控制符有所不同，因此，文档文件在 不同的文字处理系统间需要格式转换，不能直接相互通用。此外，文档文件内除文本外， 还可插入图形、表格，甚至声像等非文本资料。 2 5 网页页面中的语言特征 在w 3 ch t m l 4 0 的标准中， 常用于h t m l 页面中以标识一些系统信息。 其中系统变量c o n t e n t t y p e 中常包含了此页面所用的字符集信息。例如下面存在于一个 h t m l 页面中的 信息： 表示系统变量c o n t e n t - t y p e 的值为t e x t h t m l ；c h a r s e t = - g b 2 3 1 2 ， 即指出了此h t m l 页面 所用的字符集为g b 2 31 2 。 表2 1 部分文字编码的c h a r s e t 值 部分文字编码的c h a r s e t 值 文7 编码c h a r s e t 值 g b 2 3 1 2 g b g b 一2 31 2 8 0 b i 9 5 b l g 5 i s o 2 0 2 2 j p j i s i s o 一2 0 2 2 j p 2 e u c j p e u c x e u c j p s h i f t j i s s h i f t - j i s x s j i s 所以，根据h t m l 页面中的系统变量c o n t e n t t y p e 的值，就可以简便而有效的识 别出页面所使用的字符集。但是，h t m l 语言并没有规定页面中必须给定c o n t e n t - t y p e 值，在很多h t m l 页而中就没有包含c o n t e n t t y p e 值。当不能从系统变量c o n t e n t t y p e 获得页面语言信息时，就需要从分析页面中的字符编码入手，识别出页而的语言。 2 6 电子邮件中的语言特征 对邮件进行编码最初的原因是因为i n t e m e t 上的很多网关不能正确f 0 输8 b i t 内码的 字符，比如汉字等。编码的原理就是把8 b i t 的内容转换成7 b i t 的形式以能正确传输，在 南京邮电人学硕十研究生学何论迎 第2 章相关概念和技术 接收方收到之后，再将其还原成8 b i t 的内容。 在m i m e 协议之前，邮件的编码曾经有过u u e n c o d e 等编码方式，但是由于m i m e 协议算法简单，并且易于扩展，现在已经成为邮件编码方式的主流，不仅是用来传输8 b i t 的字符，也可以用来传送二进制的文件，如邮件附件中的图像、音频等信息，而且扩展了 很多基于m i m e 的应用。从编码方式来说，m i m e 定义了两种编码方法b a s e 6 4 与 q p ( q u o t e p r i n t a b l e ) 。在对二进制文件或者多字节文本进行转化时，b a s e 6 4 得到的“字节 串”比q u o t e d p r i n t a b l e 更短。在对英文文本进行转化时，q u o t e d - p r i n t a b l e 得到的“字 节串”比b a s e 6 4 更短。 当一段t e x t 或者h t m l 通过电子邮件传送时，发送的内容首先通过一种指定的字 符编码转化成“字节串”，然后再把“字节串”通过一种指定的传输编码 ( c o n t e n t t r a n s f e r - e n c o d i n g ) 进行转化得到另一串字节串”。比如，打开一封电子邮件 源代码，可以看到类似的内容： c o n t e n t - t y p e ：t e x t p l a i n ； c h a r s e t = ”g b 2 312 ” c o n t e n t t r a n s f e r - e n c o d i n g ：b a s e 6 4 s b g + q c r q u q 0 l7 c f 4 y e e 7 4 b g j z 9 w 7 + b 3 w u d z a 7 d b q o m q n c 9 0 k v p k z x q 0 6 u q o17 c n n s a p w o n d e d q o n c g 一 邮件的标题，用了一种更简短的格式来标注“字符编码”和“传输编码”。比如，标 题内容为”中”，则在邮件源代码中表示为： 正确的标题格式 s u b j e c t ：= ? g b 2 31 2 7 b ? i t a = 9 = 其中， 第一个“= ? ”与“? ”中间的部分指定了字符编码，在这个例子中指定的是g b 2 3 1 2 。 “? ”与“? ”中间的“b ”代表b a s e 6 4 。如果是“q ”则代表q u o t e d p r i n t a b l e 。 “? ”与“? = ”之间的部分，就是经过g b 2 3 1 2 转化成字节串，再经过b a s e 6 4 转化 后的标题内容。 如果阅读邮件时出现乱码，一般是因为“字符编码”或“传输编码”指定有误，或者 是没有指定。对没有“c o n t e n t - t y p e ”头字段的r f c 8 2 2 消息，默认是采刖u s a s c i i 字 符集、纯文本类型的内容。它可以被精确的描述为： c o n t e n t - t y p e ：t e x t p l a i n ；c h a r s e t 2 u s a s c i i 这个缺省值是在没有指定“c o n t e n t t y p e ”头字段时而使用的。而且，在遇到句法错 o 南京邮电人学硕十研究生学化论义第2 争相关概念和技术 误的“c o n t e n t t y p e ”头字段时，也会使用这个缺省值。当消息中存在“m i m e v e r s i o n ” 头字段，而缺少“c o n t e n t t y p e ”头字段时，接收方的用户代理也可以假定发送者所发送 的是u s a s c i i 字符集的纯文本内容。在没有“m i m e v e r s i o n ”头字段或有错误语法的 “c o n t e n t - t y p e ”头字段时，仍然可以假定其内容是u s - a s c i i 字符集的纯文本，但是这 就不是发送者的本意了。 2 7 分词 英文是以词为单位的，词和词之间是靠空格隔开，然而很多语言中词与词之间是没有 这种天然的分隔符的，例如，英文句子i 锄as t u d e n t ，用中文则为：“我是一个学生”。计 算机可以很简单通过空格知道s t u d e n t 是一个单词，但是不能很容易明白“学”、“生”两个 字合起来才表示一个词。把中文的汉字序列切分成有意义的词，就是中文分词，对于其他 语言也是这样。“我是一个学生”，分词的结果是：我是一个学生。 还是以中文为例，在基于内容分析的邮件过滤方法中，中文邮件和英文等字母文字的 电子邮件一个重要差别在于，英文使用单词代表一个语义，在许多过滤方法中都是以单词 或者单词联结某些符号以表达特定含义的组合，如“h e l l o ! ”等，作为基本的计算单元。 中文中语义的基本单位足词，而构成计算机编码单元的是单个的字。如果直接应用基于字 母文字的方法，显然不能使用字作为计算单元，因此分词就成了必须要考虑的问题。 分词技术属于自然语言处理技术范畴，对于一句话，人可以通过自己的知识来明白哪 些是词，哪些不是词，但如何让计算机也能理解? 其处理过程就是分词算法。现有的分词 算法主要分为三大类：基于字符串匹配的分词方法、基于理解的分词方法和基于统计的分 词方法。 2 8 语言模型 语言模型是一个单纯的、统一的、抽象的形式系统，语言客观事实经过语言模型的描 述，比较适合于电子计算机进行自动处理，因而语言模型对于自然语言的信息处理具有重 大的意义。 语言模型与语言客观事实之间的关系，如同数学上的抽象直线与具体直线之间的关 系。 语言模型主要分为规则模型和统计模型两种。统计语言模型是用概率统计的方法来揭 示语言单位内在的统计规律。 l o 南京邮电人学硕f ：研究生学何论文第：帝相关概念和技术 语言模型的性能通常用交叉熵( c r o s se n t r o p y ) 和复杂度( p e r p l e x 时) 来衡量。交叉 熵的意义是该模型对文本识别的难度，或者从压缩的角度来看，压缩每个闻平均要用几个 位来编码。复杂度的意义是用该模型表示这一文本平均的分支数，其倒数可视为每个词的 平均概率。 南京邮电人学硕十研究生学何论文第3 章语言i j ! ) ；i j 的主要方法和评价 第3 章语言识别的主要方法和评价 3 1 基于编码非重叠区的识别方法 基于编码非重叠区的识别方法是一种比较简单实用的语言识别方法。陔方法基于这么 一个现象：虽然各种字符编码空间有重叠的部分，但也不是完全一致的，利用各编码空间 的非重叠区即可达到编码识别的目的。若待识别文本中出现了某个只存在于某种编码空间 的字符，则可以排除其它编码形式的可能性。 在检测多字节编码的时候，基于编码非重叠区的识别方法也许是最显而易见的方法， 也是通常最容易使用的方法。在多字节编码模式中，并不是所有可能的代码点都被使用的。 如果在验证特定编码的时候，碰到一个非法字节或非法字节序列( 如，无厂h 的代码点) ，我 们可以立即判断出这种编码猜测是错误的。一部分的代码点同样也能代表特定的编码方 式，这样，我们也能利用这种事实立即做出正确的判断。 有限状态机( f s m ，f i n i t es t a t em a c h i n e ) 是软件上常用的一种处理方法。在描述有限 状态机时，状态、事件、转换和动作是经常会碰到的几个基本概念。 状态( s t a t e ) 指的是对象在其生命周期中的一种状况，处于某个特定状态中的对 象必然会满足某些条件、执行某些动作或者是等待某些事件。 事件( e v e n t ) 指的是在时间和空间上占有一定位置，并且对状态机来讲是有意义 的那些事情。事件通常会引起状态的变迁，促使状态机从一种状态切换到另一种 状态。 转换( t r a n s i t i o n ) 指的是两个状态之问的一种关系，表明对象将在第一个状态中 执行一定的动作，并将在某个事件发生同时某个特定条件满足时进入第二个状 态。 动作( a c t i o n ) 指的是状态机中可以执行的那些原子操作，所谓原子操作指的是 它们在运行的过程中不能被其他消息所中断，必须一直执行下去。 有限状态机的工作原理如图3 1 所示： 1 2 南京邮电人学硕十研究生学何论文第3 章语苦u ：j _ ；i j 的主要方法和评价 i 当前状态 发生事件e v e n t ic u i 一s ta te i 一 执行动作a c t io n 设置下一状态号n x t s t a te 有限状态机工作原理 图3 1 有限状态机的工作原理 发生事件( e v e n t ) 后，根据当前状态( c u rs t a t e ) ，决定执行的动作( a c t i o n ) ，并设置下一个状 态号( n x ts t a t e ) 。 以下是一种通过过使用并行状态机( p a r a l l e ls t a t em a c h i n e ) 来检测字符集的算法，其基 本思想是：对每一个编码模式，都有一个相应的状态机被用来验证这种特定编码的字节序 列。对检测器收到的每一个字节，它将会被输入到每一个可用的，活动的状态机中，每次 一个字节。状态机基于前一个状态和它所收到的字节来改变它的状态。自动检测器对状态 机的三种状态感兴趣： s t a r t 状态：这种状态代表两种情形，初始化，或是代表字符集的一个合法字 节序列已被验证。 m e 状态：这种状态代表状态机验证到了字符集特有的一个字节序列，并且其它 可能的字符集不包含这个字节序列。这会导致检测器立即返回一个确定的回答。 e r r o r 状态：这种状态代表状态机验证了字符集的一个非法字节序列。这会立 即导致对这种字符集的否定回答。检测器从此将会排除这种编码方式，不作考虑。 在一个典型的例子中，只有一个状态机会做出确定的回答，而其它的状态机会做出的否定 的回答。 基于编码非重叠区的识别方法，其不足之处在于：对许多单字节编码来说，使用到的 代码点基本足均匀分布的，而且即使对包含一些无用代码点的编码方式，那些无用的代码 点在其他编码方式中也很少被使用，因此，仅靠基于编码非重叠区的识别方法是无法达到 较好的识别结果的。 3 2 基于字频分布的识别方法 无论哪种语言，总有一些字符比其它字符更常用。利用这个事实，我们可以对每种 语言建立起相应的数据模型。这种方法对字符数较多的语言，比如汉语，口语和韩语，尤 其有用。基于字频分布的语言别算法如下： 1 分别从每种语言的训练样本中提取最常用的字( 高频字) ，利用这些高频字建立 1 3 直塞邮电大学硕士研究生学位论文第3 章语言识别的主要方法和评价 语言特征模型。 2 根据己建立的语言特征模型，分别统计待识别的文本中各种语言高频字的出现次 数 3 出现某种语言高频字最多的即为目标语言。 o r e f e n s t e t t e 从欧洲语料库样本e c ic d - r o m ( c o r p u sf r o me u r o p e a nc o r p u si n i t i a t i v e ) 中选取了2 7 种欧洲语言的报纸文章，对基于字频分布的识别方法进行了测试，测试结果 如表3 1 所示【1 5 】： 表3 1g r e f e n s t e t t e 对字频统计语言识别方法的测试结果 i d e n t i f i e da s l a n g u a g e d a n i s hd u t c h e n g l i s h f r e n c hg e l m a l li t a l i a n n o r w e g i a np o r t u g u e s es p a n i s h 7 7 9 d a n i s h6 0 3 23l2 55l2 8 62l2 7 5 d u t c h26 9 1 4 8 5 9 2 l 1 76 l e n g l i s h 2 7 8 0 8263 986 f r e n c h425 0 2 332 4271 41 3 g e r m a n5 6759 25 5 9 01 453 3l1 2 5 i t a l i a n3 53l8l l5 7 4 21 51 899 7 n o r w e g i a n 8ll2221 3 1 0 2l2 p o r t u g u e s e 2891 21 42 638 5 0 56 91 4 0 s p a n i s h 3l1 62 35 1 5 01 9 8 表3 - 1 中最后一列，表示待识别文本中的各语言高频词出现次数相等，这种情况下就无 法判定目标文本的语言种类了，这也是基于字频分布的语言识别方法的一个局限性。 基于字频分布的语言识别方法有如下优点：实现简单，相对计算量小。其缺点是，识 别率不高，而且对于短文本，例如文本中字符数目小于1 0 个，由于高频词在其中出现的 概率就很小，也会导致识别结果的可信度严重降低。 3 3 基于马尔可夫模型的识别方法 本节我们将讨论基于马尔可夫模型( m a r k o vm o d e l ，m m ) 的语言识别方法，该方法 通过马尔可夫模型建立统计语言模型，预测文档源于已知语言模型的概率。 3 3 1 马尔可夫过程 当一个随机过程在给定现在状态及所有过去状态情况下，未来状态的条件概率分布仅 依赖于当前状态，即现在状态与过去状态是条件独立的。那么此随机过程即具有马尔可夫 性质，