中文信息处理技术原理与应用(3).ppt

《中文信息处理技术原理与应用(3).ppt》由会员分享，可在线阅读，更多相关《中文信息处理技术原理与应用(3).ppt（62页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 中文信息处理技术原理与应用（三）北京信息工程学院计算机系李宝安1中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 第三章 汉字字形存储与压缩技术 汉字字形存储与字形码汉字字形存储与字形码 点阵存储与压缩存储点阵存储与压缩存储 汉字压缩存储常见方法分类汉字压缩存储常见方法分类 压缩与还原技术及其重要指标压缩与还原技术及其重要指标 汉字笔画矢量存储方法汉字笔画矢量存储方法 部件组字压缩部件组字压缩 汉字子信息块哈夫曼树存储方法汉字子信息块哈夫曼树存储方法 汉字字形轮廓存储方法汉字字形轮廓存

2、储方法 黑白段与线性增量存储方法黑白段与线性增量存储方法 笔画轮廓压缩存储方法笔画轮廓压缩存储方法 2中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 汉字字形存储与字形码 产生汉字字形的方法有产生汉字字形的方法有模拟式模拟式和和数字式数字式两种：两种：模拟式：模拟式：如字模板、字模摄像、飞点扫描字模、全如字模板、字模摄像、飞点扫描字模、全息照相等，特点是文字质量高，价格较便宜，缺息照相等，特点是文字质量高，价格较便宜，缺点是文字读出机构复杂，读取速度低、维护要求点是文字读出机构复杂，读取速度低、维护要求高，文字变动困难。高，文字变动困难。数字式：数字式：输出文字

3、一致性好，稳定不变，速度快，输出文字一致性好，稳定不变，速度快，文字尺寸变更比较灵活，但存储量大、成本较高。文字尺寸变更比较灵活，但存储量大、成本较高。随着中文信息处理技术的发展，模拟式产生文字随着中文信息处理技术的发展，模拟式产生文字字形的方法已逐渐淘汰，这里只介绍数字式汉字字形的方法已逐渐淘汰，这里只介绍数字式汉字字形产生和存储的方法。字形产生和存储的方法。3中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 汉字字形的数字化 由于计算机内部只认由于计算机内部只认0 0和和1 1这些二进制代码，汉这些二进制代码，汉字字形信息要想保存下来，也必须象汉字的键字字形信

4、息要想保存下来，也必须象汉字的键盘码和交换码一样，实现计算机内部的盘码和交换码一样，实现计算机内部的“数字数字化化”。将汉字写在划分有将汉字写在划分有m m行行n n列小方格的网格方块列小方格的网格方块中，该方块称为中，该方块称为mnmn点阵，每个小方格是一个点阵，每个小方格是一个点，有笔画部分是黑点，文字的背景部分是白点，有笔画部分是黑点，文字的背景部分是白点，点阵中的黑点就描绘出汉字字形，称为汉点，点阵中的黑点就描绘出汉字字形，称为汉字点阵字形。字点阵字形。4中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 不同使用领域对汉字质量的要求 使 用 领 域分辨率（

5、线/毫米）密度品质点阵规格要求（以3.7mm2的五号字为例）监视器显示462.02.5低1616 2424通用型字形简易印刷（一般打印、文稿输出）6162.22.5中2424 32324848 6464制版印刷20250.1高100100精密型字形5中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 整字存储与压缩存储 汉字字形存储按存储方法分为整字存储和压缩汉字字形存储按存储方法分为整字存储和压缩存储两大类。存储两大类。整字存储整字存储:把汉字字形点阵信息按字节全部存放把汉字字形点阵信息按字节全部存放在存储器中，需要使用时直接读出，这种存储在存储器中，需要使用时直

6、接读出，这种存储方式就是整字存储，它原理简单、使用方便，方式就是整字存储，它原理简单、使用方便，响应时间快，可以保证字形质量。响应时间快，可以保证字形质量。压缩存储压缩存储:不是直接将字形信息存储起来，而是不是直接将字形信息存储起来，而是先用压缩技术对点阵文字信息进行压缩，压缩先用压缩技术对点阵文字信息进行压缩，压缩后的信息存入存储器，使用时，再把压缩信息后的信息存入存储器，使用时，再把压缩信息还原成点阵字形。这样做的目的主要是为了减还原成点阵字形。这样做的目的主要是为了减少存储量。少存储量。6中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 问题：随着近年来存储

7、器价格大幅度下降，并且由于压缩字库在使用时有一个字形还原的过程，出字速度有影响，字形可能存在失真现象等缺点，请问压缩字形存储器在当前是不是毫无竞争力而被淘汰呢？7中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 回答：NO！8中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 原因压缩存储在价格上存在优势，这不仅因为存储容量本身小、价格低，而压缩存储在价格上存在优势，这不仅因为存储容量本身小、价格低，而且还要考虑到维持电路（如电源、存储器辅助电路等）的开销比整字存且还要考虑到维持电路（如电源、存储器辅助电路等）的开销比整字存储低；储低；

8、汉字字数或字号增加，整字存储的存储量会线性增加，而压缩存储能够汉字字数或字号增加，整字存储的存储量会线性增加，而压缩存储能够方便地应付，存储量增加不多；方便地应付，存储量增加不多；制版印刷用的精密型汉字字形，目前都采用压缩方法存储；制版印刷用的精密型汉字字形，目前都采用压缩方法存储；压缩字形便于制成小型卡式压缩存储的专用字库，体积很小，便于在单压缩字形便于制成小型卡式压缩存储的专用字库，体积很小，便于在单板机和通用微机中使用，所占用的空间较少，在板卡的制造工艺上具有板机和通用微机中使用，所占用的空间较少，在板卡的制造工艺上具有优势；优势；设计压缩字形存储指导思想的改变，不是一味追求压缩率，而是

9、针对克设计压缩字形存储指导思想的改变，不是一味追求压缩率，而是针对克服压缩存储的主要缺点，把提高复原后的汉字质量和出字速度作为主要服压缩存储的主要缺点，把提高复原后的汉字质量和出字速度作为主要解决的问题，把压缩率降到次要地位。这种从实用出发，适当控制压缩解决的问题，把压缩率降到次要地位。这种从实用出发，适当控制压缩率的做法是推广压缩存储的有效措施；率的做法是推广压缩存储的有效措施；某些压缩方法和技术对中文处理系统的设计有启发；某些压缩方法和技术对中文处理系统的设计有启发；计算机计算机CPUCPU的运算速度越来越快，压缩字库的字形还原也越来越快；的运算速度越来越快，压缩字库的字形还原也越来越快；

10、对于计算机辅助设计（如在建筑对于计算机辅助设计（如在建筑CADCAD软件中）等应用领域，经常要求的字软件中）等应用领域，经常要求的字形的变倍处理，采用压缩存储方法更容易实现。形的变倍处理，采用压缩存储方法更容易实现。9中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 汉字压缩存储常见方法分类 字形压缩方法很多，约有数十种，各有优缺点字形压缩方法很多，约有数十种，各有优缺点和应用对象，将它们归纳一下，可分为两大类：和应用对象，将它们归纳一下，可分为两大类：图形压缩和汉字结构压缩。图形压缩和汉字结构压缩。图形压缩图形压缩采用了一般二维图形的信息压缩方法；采用了一般二维

11、图形的信息压缩方法；结构压缩结构压缩是针对汉字结构特点而提出的压缩方是针对汉字结构特点而提出的压缩方法。法。笔画矢量、哈夫曼树、部件组合适合于低、中笔画矢量、哈夫曼树、部件组合适合于低、中质量的通用型汉字宇形压缩；质量的通用型汉字宇形压缩；字形轮廓适用于高质量通用型汉字字型压缩字形轮廓适用于高质量通用型汉字字型压缩 ；黑白段、线性增量、笔画轮廓适用于精密型汉黑白段、线性增量、笔画轮廓适用于精密型汉字字型压缩。字字型压缩。10中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 压缩与还原技术及其重要指标 1 1压缩率压缩率，用来衡量压缩后字形存储容量减少的程度。用来衡

12、量压缩后字形存储容量减少的程度。其中其中L L为压缩前字形所占存储字节数，为压缩前字形所占存储字节数，C C为压缩后字形所占存储字节数。为压缩后字形所占存储字节数。2 2 失真率失真率，用来衡量压缩后字形相对于原来字形失真的程度用来衡量压缩后字形相对于原来字形失真的程度 。其中其中Q Q为压缩前字形的信息量，为压缩前字形的信息量，E E为经压缩还原后失真的信息总量。为经压缩还原后失真的信息总量。3 3字形复原速率字形复原速率R R，用来衡量压缩后复原到原点阵字形的速度。用来衡量压缩后复原到原点阵字形的速度。R=1R=1秒内产生的汉字字形数目秒内产生的汉字字形数目4 4压缩字形的自动生成能力，利

13、用压缩存储方法生成压缩字库的能力。压缩字形的自动生成能力，利用压缩存储方法生成压缩字库的能力。5 5压缩后字形变换能力，包括还原成原点阵字形，生成各种大小字形的变倍性能。压缩后字形变换能力，包括还原成原点阵字形，生成各种大小字形的变倍性能。L=（L C）100%Q=E 100%11中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 汉字笔画矢量存储方法基本原理汉字是直线性文字，一个汉字是许多直线段所组成的二维几何图形。如果能够对汉字是直线性文字，一个汉字是许多直线段所组成的二维几何图形。如果能够对这些直线段实现压缩，则整个汉字的字形信息也可得到压缩。这些直线段实现压

14、缩，则整个汉字的字形信息也可得到压缩。笔画矢量笔画矢量压缩压缩中的中的“笔画笔画”指的就是指的就是这这些直些直线线段，段，给给二二维汉维汉字字图图形加上笛卡儿坐形加上笛卡儿坐标标X-YX-Y，汉汉字笔画（注意，即上述的直字笔画（注意，即上述的直线线段）段）。输输出出汉汉字字时时，用表示字形的各笔画信息，得出笔画形状，一般，用表示字形的各笔画信息，得出笔画形状，一般为为1 1bitbit宽宽的直的直线线段，段，形成形成该该字点字点阵阵字形数据。存字形数据。存储汉储汉字的字的实质实质就是把字形就是把字形转转化化为为坐坐标标，输输出出汉汉字就是字就是根据坐根据坐标转换为标转换为字形。字形。具体具体有

15、三种表达方法：有三种表达方法：笔画的两个端点坐笔画的两个端点坐标标（xi1xi1、yi1yi1）和（和（xi2xi2、yi2yi2），），其中其中i i是是汉汉字字图图形中某一笔画，形中某一笔画，1 1是起点坐是起点坐标标，2 2是是终终点坐点坐标标。这这种表示法叫笔画坐种表示法叫笔画坐标标法法；用矢量表示笔画，即用矢量的起点（用矢量表示笔画，即用矢量的起点（x i1x i1，y i1y i1）和矢量的和矢量的长长度、方向。常用度、方向。常用矢量在矢量在x x、y y轴轴上的投影上的投影长长度度LxiLxi和和LyiLyi表示向量的表示向量的长长度、方向度、方向；用一系列尾首相用一系列尾首相接

16、的矢量来表示笔画。矢量有虚接的矢量来表示笔画。矢量有虚实实之分，之分，实实矢量表示矢量表示实实有笔画，虚矢量表示没有有笔画，虚矢量表示没有的空笔画，一个矢量的起点（的空笔画，一个矢量的起点（xi1xi1，yi1 yi1）是上一矢量的是上一矢量的终终点（点（x x（i-1i-1）2 2，y y（i-i-1 1）2 2）。）。这这种表示法叫做矢量存种表示法叫做矢量存储储法法。12中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 笔画坐标法 笔画坐标法用存储汉字笔画两个端点坐标来压缩字形信息。若取点阵左上角为坐标原点，对于图3-3（a）的“汉”字，8个笔画端点ABCDB

17、FGHIJKL的坐标（xi，yi），其中 i=l，2，12就确定了“汉”字的字形。若用1616点阵，则x和y值可用4位二进制数来表示，用8位存储器存放“汉”字各端点坐标值，前4位存x值，后4位存y值。13中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 xy7 4 3 0笔画坐标法端点坐标数据结构：“汉”字端点的存储数据：14中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 从上面从上面“汉汉”字字的笔画坐标法存储数据看，的笔画坐标法存储数据看，存存储储“汉汉”字的笔画端点字的笔画端点一共用了一共用了1212个字个字节节，而直接存，而

18、直接存储储16161616点点阵阵字形需要字形需要28=3228=32个字个字节节。采用笔画坐。采用笔画坐标标法存法存储储“汉汉”字，信息是直接存字，信息是直接存储储的的1 12.72.7，即，即压缩压缩率率为为62.5%62.5%。据据统计统计，常用六千多汉字的平均笔画根数约为常用六千多汉字的平均笔画根数约为1414，由此可算出对，由此可算出对应不同点阵字形笔画坐标压缩法所需要的存储量，见表应不同点阵字形笔画坐标压缩法所需要的存储量，见表3 34 4。比。比较表较表3 34 4与对应点阵在整字存储方式下的字节数可知，笔画坐标与对应点阵在整字存储方式下的字节数可知，笔画坐标法可以压缩字形信息，

19、而且，随着字形点阵规格的增加，压缩率法可以压缩字形信息，而且，随着字形点阵规格的增加，压缩率也随之提高，当然，字形的美观也受到更多的损失。也随之提高，当然，字形的美观也受到更多的损失。如采用如采用16161616点阵时，压缩率为点阵时，压缩率为12.512.5，即所需的存储量下降到，即所需的存储量下降到原来的原来的87.587.5。而采用。而采用32323232点阵，压缩率为点阵，压缩率为72.772.7，存储量下，存储量下降到原来的降到原来的1/31/3以下。实际采用笔画坐标法压缩时，还可使用一些以下。实际采用笔画坐标法压缩时，还可使用一些别的措施进一步提高压缩率。别的措施进一步提高压缩率。

20、15中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 表表3 34 4 笔画坐标法压缩汉字字形的存储量笔画坐标法压缩汉字字形的存储量 16中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 笔画坐标法实例 字形采用字形采用15161516点阵，取坐标原点在字的左上点阵，取坐标原点在字的左上角，角，x x是列数，是列数，y y是行数。因此，每个汉字是是行数。因此，每个汉字是x x方向方向1515个单位、个单位、y y方向方向1616个单位的平面图形。个单位的平面图形。笔画端点坐标范围笔画端点坐标范围x x方向是方向是00E E，y y方向

21、是方向是00F F。根据存储的汉字每个笔画的端点坐标，生成汉根据存储的汉字每个笔画的端点坐标，生成汉字时，按照一定规律从起点到终点画出每条直字时，按照一定规律从起点到终点画出每条直线，也就形成了汉字线，也就形成了汉字15161516点阵字形。点阵字形。17中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用（l）存储用的压缩信息 1)1)直接笔画信息直接笔画信息笔画两个端点的坐标值，分为以下两种。笔画两个端点的坐标值，分为以下两种。基本笔画信息基本笔画信息 有九种。每个基本笔画都用两个字节表示起、终点坐标。有九种。每个基本笔画都用两个字节表示起、终点坐标。复合笔画信息

22、。复合笔画信息。包括汉字中常出现的一些基本笔画的组合，如图包括汉字中常出现的一些基本笔画的组合，如图3535（1 1）所示。若）所示。若将该图复合笔画的端点和折点给出如图将该图复合笔画的端点和折点给出如图3535（2 2）所示的编号，则）所示的编号，则这些复合笔画的坐标信息列出如表这些复合笔画的坐标信息列出如表3535。因为。因为x x方向坐标范围是方向坐标范围是0 0到到E E，所以，第一字节的第一位所以，第一字节的第一位F F可以作为复合笔画的标志。由表可以作为复合笔画的标志。由表335 5可知，对于复合笔画，没有必要将所有端、折点的坐标值都存可知，对于复合笔画，没有必要将所有端、折点的坐

23、标值都存入，因为未存入的其他点阵坐标可以根据已知信息产生。入，因为未存入的其他点阵坐标可以根据已知信息产生。横竖撇捺点挑折捺勾双笔竖一丨丿、乛丨18中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 图3-5 复合笔画及端、折点编号 12312312431234143212341234 A B C D E F G19中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 A AB BC CD DE EF FGG第一字节第一字节 FXFX2 2FXFX2 2FFFFFFFFFFFFFFFFFFFF第二字节第二字节 x x1 1y y1 1x x

24、3 3y y3 3 x x1 1y y1 1 x x2 2y y4 4 x x1 1y y2 2 x x1 1y y1 1 x x1 1y y1 1 第三字节第三字节 x x3 3y y3 3 x x1 1y y1 1 x x3 3y y3 3 x x1 1y y1 1 x x3 3y y4 4 x x3 3y y4 4 x x3 3y y3 3 第四字节第四字节 x x3 3y y3 3 表3-5 复合笔画坐标信息 20中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 2)部件信息 在笔画坐标法中引入部件信息，其含意和部件在笔画坐标法中引入部件信息，其含意和部件

25、组字压缩法不同。这里是把存储器内多个汉字组字压缩法不同。这里是把存储器内多个汉字公用的笔画信息提出来做为部件，并用直接笔公用的笔画信息提出来做为部件，并用直接笔画信息来表示，而且也不组成部件库。画信息来表示，而且也不组成部件库。在其它汉字用到某个部件时，以两个字节作为在其它汉字用到某个部件时，以两个字节作为指针指向这个部件，即可根据部件的直接笔画指针指向这个部件，即可根据部件的直接笔画信息画出相应的点阵。在笔画坐标法中引出部信息画出相应的点阵。在笔画坐标法中引出部件概念，显然能进一步压缩存储信息量。件概念，显然能进一步压缩存储信息量。21中文信息处理技术中文信息处理技术中文信息处理技术原理与应

26、用原理与应用原理与应用 3)全点阵信息 某些笔画多又便于拆成部件的字，存放全部点某些笔画多又便于拆成部件的字，存放全部点阵信息反而能使信息量小些。例如阵信息反而能使信息量小些。例如“囊囊”字有字有2626段笔画，用笔画坐标存储需段笔画，用笔画坐标存储需5252字节，而点阵字节，而点阵直接存储只要直接存储只要3232字节。字节。综上所述，用笔画坐标构成的压缩存储器是汉综上所述，用笔画坐标构成的压缩存储器是汉字自行端点坐标信息和部件指针信息的集合。字自行端点坐标信息和部件指针信息的集合。汉字中相同部件的笔画信息集中存放，它和其汉字中相同部件的笔画信息集中存放，它和其他汉字是通过部件指针互相联系的。

27、他汉字是通过部件指针互相联系的。22中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用（2）汉字的生成 用笔画坐标法构成压缩存储器后，接着就是根据这些用笔画坐标法构成压缩存储器后，接着就是根据这些信息形成被查找的汉字点阵，使输出的汉字笔画布局信息形成被查找的汉字点阵，使输出的汉字笔画布局匀称，清晰美观。这主要是解决如何区分笔画类型和匀称，清晰美观。这主要是解决如何区分笔画类型和写出合适的笔画这两个问题。写出合适的笔画这两个问题。1)1)笔画的区分笔画的区分 23中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 2 2）笔画的形成笔画的形

28、成 形成横、竖、双笔竖等笔画点阵比较直观，如对坐标形成横、竖、双笔竖等笔画点阵比较直观，如对坐标（x x1 1y y1 1）起到（起到（x xi2i2y y2 2）止的各字节止的各字节y y1 1位置上全部位置上全部x x值置值置“1 1”就形成笔画横的点阵。就形成笔画横的点阵。对于撇、捺、挑、捺钩等笔画，由于同一笔画各段粗对于撇、捺、挑、捺钩等笔画，由于同一笔画各段粗细不同，在不同字中形状也不一样，所以要根据它们细不同，在不同字中形状也不一样，所以要根据它们在不同字形的不同位置和各段不同粗细来形成合适的在不同字形的不同位置和各段不同粗细来形成合适的点阵。这些笔画各段的粗细变化是有规律的、连续

29、的，点阵。这些笔画各段的粗细变化是有规律的、连续的，利用这一点可以形成对应于各段粗细不同的笔画点阵。利用这一点可以形成对应于各段粗细不同的笔画点阵。而同一种笔画在不同字中或在同一字的不同部位有不而同一种笔画在不同字中或在同一字的不同部位有不同的斜率，是随着笔画坐标差同的斜率，是随着笔画坐标差x x和和y y的比值而变化，的比值而变化，是坐标差之比的函数。所以，根据是坐标差之比的函数。所以，根据x/x/y y可分类形成可分类形成不同形状的同一种笔画。不同形状的同一种笔画。24中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 矢量存储法 取坐标原点为文字的左上角，用一

30、系列矢量表示汉字字形的笔画，在存储器内存储矢量的端点到一矢量端点的坐标增量。x(或y)增量为正，表示自左向右（或自上向下）；为负则反之。规定每个汉字的第一矢量起点是坐标原点，实矢量为实有笔画，用“1”表示；虚矢量是没有的空笔画，用“0”表示 25中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 表表3-9 3-9 对应于图对应于图3-73-7（c c）“汉汉”字矢量存储法的数据字矢量存储法的数据 矢 量xy实矢量/虚矢量OA110AB221BC-310CD221DE-190EF3-71FG1-60GH801HI-481IJ-551JK2-110KL361LM551

31、26中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 字形信息的描述 对于对于16161616点阵，用两个字节表示一个矢量。点阵，用两个字节表示一个矢量。其中其中F F称为笔形特征，有称为笔形特征，有6 6位二进制数，用位二进制数，用“000000000000”表示空笔画，用表示空笔画，用“000001000001”表示实表示实笔画，当笔画，当F F“111111111111”时表示实笔画的末笔。时表示实笔画的末笔。x x，y y各用各用5 5位二进制数，包括了一位符号位二进制数，包括了一位符号位，位，x x、y y可以表示可以表示1515到到1515之间的任何整

32、之间的任何整数。数。F x y 15 10 9 5 4 0 27中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 笔形特征的利用 上述矢量表示中，笔形特征上述矢量表示中，笔形特征F F未能充分利用，可未能充分利用，可用它来扩展矢量表示法的功能。例如在汉字中，用它来扩展矢量表示法的功能。例如在汉字中，组合笔画组合笔画“口口”用得很多，可以定义一种专用用得很多，可以定义一种专用表示表示“口口”的笔形码，如的笔形码，如:由于某一种笔形特征后还有由于某一种笔形特征后还有x x，y y作为参数，作为参数，所以，其表现能力是很强的。例如所以，其表现能力是很强的。例如“口口”笔

33、形笔形信息，可表示各种大、小、长、扁的信息，可表示各种大、小、长、扁的“口口”，而且只要把起点设置好就可以放到任何位置上。而且只要把起点设置好就可以放到任何位置上。利用笔形特征利用笔形特征F F剩余的编码，可定义几十种常剩余的编码，可定义几十种常用的组合笔画，以进一步压缩字形信息。用的组合笔画，以进一步压缩字形信息。0 0 0 0 1 0 x y 15 10 9 5 4 0 28中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 F000010表示“口”字形，x，y是“口”的宽度和高度。它实际上取代了由四个矢量组合而成的“口”字。0000010y000001x000

34、00010-y000001-x0再如，我们用F 000011表 示组合笔画“冂”它也由四个矢量组成。0000010y000001x00000010-y000001 -x029中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 部件信息的利用 汉字中，有些部件使用率很高，如氵、木、忄、汉字中，有些部件使用率很高，如氵、木、忄、扌、讠、礻、艹、纟、亻、彳、冫等等，很多扌、讠、礻、艹、纟、亻、彳、冫等等，很多汉字都共有这些部件。把它们做成标准部件，汉字都共有这些部件。把它们做成标准部件，这些部件在汉字中有固定位置，这样，在许多这些部件在汉字中有固定位置，这样，在许多字中可

35、以直接调用这些部件信息，可以进一步字中可以直接调用这些部件信息，可以进一步压缩存储量。压缩存储量。如规定如规定F F100000100000为调用标准部件命令，为调用标准部件命令，D D是指是指向标准部件的指针，有十位二进制，可以表示向标准部件的指针，有十位二进制，可以表示10241024种部件。种部件。30中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 1 0 0 0 0 0 D15 10 9 0 31中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 字形信息的还原 字形信息还原指的是从矢量信息反转成点阵信息。字形信息还原指的是从

36、矢量信息反转成点阵信息。1 1）用程序把部件调用信息和组合笔画信息转换成矢量信息。用程序把部件调用信息和组合笔画信息转换成矢量信息。2 2）把有序实虚矢量还原成点阵把有序实虚矢量还原成点阵凡是虚笔画不描点，只是改变起点位置。凡是虚笔画不描点，只是改变起点位置。凡凡是是实实笔笔画画要要描描点点，根根据据x x，y y值值决决定定描描点点数数和和方方向向。由由下列直线方程决定下列直线方程决定 y yy/y/x x x x 其中，其中，x x1 1，2 2，33（x x，y0y0）若若x x是是正正，向向右右走走；x x是是负负，向向左左走走。y y为为正正则则下下走走，y y为为负负则则上上走走。

37、这这样样，对对应应一一个个x x，计计算算出出y y，取取整整后后决决定定描点的位置。描点的误差小于等于描点的位置。描点的误差小于等于0.50.5格。格。矢量存储法的压缩率是笔画矢量法中最高的，缺点是生成点矢量存储法的压缩率是笔画矢量法中最高的，缺点是生成点阵信息较慢。笔画矢量压缩共同的缺点是生成的字形不大美阵信息较慢。笔画矢量压缩共同的缺点是生成的字形不大美观，对观，对16161616点阵压缩率较低。点阵压缩率较低。32中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 子信息块哈夫曼树压缩 汉字点阵的冗余度 具有最小带权路径长度的哈夫曼（Huffman）树 哈夫

38、曼树的构成和压缩码的获得 主要算法和结果33中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 汉字点阵的冗余度 汉字是一种二维图形，可以从图形角度进行信息压缩。将汉字点阵图形分割成汉字是一种二维图形，可以从图形角度进行信息压缩。将汉字点阵图形分割成mnmn子子矩阵，称为子信息块，发现有许多子信息块是相同的，说明汉字图形有较大冗余度。矩阵，称为子信息块，发现有许多子信息块是相同的，说明汉字图形有较大冗余度。因此，利用子信息块编码存储，便可达到压缩汉字点阵信息量的目的。因此，利用子信息块编码存储，便可达到压缩汉字点阵信息量的目的。在在16161616、24242424

39、汉字点阵图形中，子信息块可取汉字点阵图形中，子信息块可取2222，1313，2121，1212等。对于等。对于mnmn子信息块子信息块,所表达的状态数所表达的状态数N N为为:N=2 N=2 mnmn 如对于如对于2222子信息块，有子信息块，有N N1616种状态。这种状态。这N N种子信息块状态在汉字中并不足等概率出种子信息块状态在汉字中并不足等概率出现的，实际出现的概率颁布和等概率有较大偏差，偏差愈大，对压缩编码愈有利。现的，实际出现的概率颁布和等概率有较大偏差，偏差愈大，对压缩编码愈有利。由于汉字使用的笔画中横、竖为多，而且横多于竖，所以相邻子信息块关系密切，左由于汉字使用的笔画中横、

40、竖为多，而且横多于竖，所以相邻子信息块关系密切，左右相信的子信息块关系最密切。例如，某汉字的一个子块如图右相信的子信息块关系最密切。例如，某汉字的一个子块如图310310（a a）所示，则其）所示，则其相邻的右边的子块的状态如图相邻的右边的子块的状态如图310310（a a）的概率要远大于如图）的概率要远大于如图310310（b b）的概率。）的概率。(a)(b)图3-10 两种子块的状态图3-1034中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 子信息块哈夫曼树压缩的设计思想 汉字点阵中各相邻的子块之间具有一定的统计规汉字点阵中各相邻的子块之间具有一定的统计

41、规律。如果汉字采用全点阵信息表示，其冗余度很律。如果汉字采用全点阵信息表示，其冗余度很大。对子信息块状态进行统计分析，可以得到一大。对子信息块状态进行统计分析，可以得到一个各状态出现概率的高低序列，设法使概率高的个各状态出现概率的高低序列，设法使概率高的代码短，概率低的代码长，从而使平均码最短，代码短，概率低的代码长，从而使平均码最短，这就是哈夫曼树算法，所以利用汉字点阵的冗余这就是哈夫曼树算法，所以利用汉字点阵的冗余度和哈夫曼树具有最小带权路径长度这个性质，度和哈夫曼树具有最小带权路径长度这个性质，能将汉字点阵信息进行压缩。能将汉字点阵信息进行压缩。35中文信息处理技术中文信息处理技术中文信

42、息处理技术原理与应用原理与应用原理与应用 具有最小带权路径长度的哈夫曼（Huffman）树 怎样利用汉字点阵的冗余度进行压缩编码呢？用怎样利用汉字点阵的冗余度进行压缩编码呢？用哈夫曼树是一个好办法。哈夫曼树是一个好办法。给定数列给定数列w1,w2,w1,w2,wnwn，以此，以此n n个数构成森林个数构成森林F F。其中，每棵树其中，每棵树TiTi的根结点为的根结点为WiWi ，而其左、右子树，而其左、右子树均为空。将均为空。将F FT1,T2,T1,T2,TnTn从小到大排序，先从小到大排序，先取出取出T1,T2T1,T2组成一棵树，使其根结点组成一棵树，使其根结点T TT1+T2T1+T2

43、，然后再根据其大小插入到然后再根据其大小插入到F F中去。反复此过程，直中去。反复此过程，直到到F FT T只有一棵树为止。这样构成的树称为哈夫只有一棵树为止。这样构成的树称为哈夫曼树曼树 。36中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 哈夫曼（Huffman）树建造实例 例如例如WG=WG=7 7、5 5、2 2、4 4，其构造过程如图其构造过程如图311311所示，在所示，在这个数列中的每个数对应哈夫这个数列中的每个数对应哈夫曼树的一片叶子，这些叶子即曼树的一片叶子，这些叶子即哈夫曼树所带的权。此例的构哈夫曼树所带的权。此例的构造过程共造过程共4 4步

44、，其带权路径长步，其带权路径长度为度为 WPLWPL7 75252232343433535 从构造过程可明显看出，这样从构造过程可明显看出，这样的哈夫曼树必然具有最小的带的哈夫曼树必然具有最小的带权路径长度。用哈夫曼树叶子，权路径长度。用哈夫曼树叶子，权值大的离根近，权值小的离权值大的离根近，权值小的离根远的性质可以形成最短编码。根远的性质可以形成最短编码。图3-11 哈夫曼树构造过程 37中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 哈夫曼树的构成和压缩码的获得 将给定某子信息块相邻将给定某子信息块相邻N N个子信息块状态的概个子信息块状态的概率，这率，这N

45、 N个数列作为叶子，用哈夫曼算法构成个数列作为叶子，用哈夫曼算法构成哈夫曼树，并取每一级的左路径代码为哈夫曼树，并取每一级的左路径代码为0 0，右，右路径代码为路径代码为1 1，从树根开始到相应的叶子，即，从树根开始到相应的叶子，即可得到不等长的编码。可得到不等长的编码。设取设取2222子块，共有子块，共有1616种不同状态，如图种不同状态，如图312312所示。设给定子块状态为所示。设给定子块状态为P0P0，在这个条件下，在这个条件下，其相邻子点阵的其相邻子点阵的1616种不同状态产生的概率为种不同状态产生的概率为w0w0、w1w1、w2w2、w15w15，如表，如表312312所示。表中所

46、示。表中概率值是统计具有代表性的概率值是统计具有代表性的384384个个14141414点阵点阵汉字所得。汉字所得。38中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 图3-12 22子块的16种状态表3-12 相邻于P0的16种不同状态子块产生的概率 39中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 以以w0w0、w1w1、w2w2、w15w15为叶子构成哈为叶子构成哈夫曼树，并取毎一级夫曼树，并取毎一级的左路径代码为的左路径代码为0 0，右，右路径代码为路径代码为1 1，如图，如图331313所示。所示。由于子块的状态有由于

47、子块的状态有1616种，因而构成的哈夫种，因而构成的哈夫曼树有曼树有1616棵。棵。从哈夫曼树根起到树从哈夫曼树根起到树叶止，可得到对应该叶止，可得到对应该树叶的状态的代码，树叶的状态的代码，如表如表313313所示所示 图3-13 以表3-12中的数列构成的哈夫曼树40中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 状态状态条件概率值条件概率值代码代码P P0 00.4380.4381 1P P1 10.0500.0500000000000P P2 20.0110.01101110000111000P P3 30.0410.0410001000010P P4

48、40.0320.0320110001100P P5 50.1320.132010010P P6 60.0320.0320001100011P P7 70.0140.014011011011011表3-13 图3-13的哈夫曼树叶的状态代码41中文信息处理技术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 由表由表313313可见，发生概率小的状态分得的代码可见，发生概率小的状态分得的代码长，发生概率大的状态分得的代码短。这样，长，发生概率大的状态分得的代码短。这样，平均代码长度就缩短了。平均代码长度就缩短了。平均代码长度带权路径长度平均代码长度带权路径长度0.43810.438

49、10.05050.05050.01170.01170.04150.04150.03250.03250.13230.13230.03250.03250.01460.01460.01160.01160.02460.02460.14830.14830.02360.02360.02550.02550.00280.00280.01560.01560.00180.00182.82.8 而变换前子块平均代码长为而变换前子块平均代码长为4 4，由于变换后所，由于变换后所得代码的平均长度缩短，所以用子信息块哈夫得代码的平均长度缩短，所以用子信息块哈夫曼树法可以压缩存储量。曼树法可以压缩存储量。42中文信息处理技

50、术中文信息处理技术中文信息处理技术原理与应用原理与应用原理与应用 主要算法和结果 用子信息块哈夫曼树压缩汉字字形，其主要算法有五个：（用子信息块哈夫曼树压缩汉字字形，其主要算法有五个：（1 1）哈）哈夫曼树叶子的获得夫曼树叶子的获得 频次（正比于条件概率值）统计算法。（频次（正比于条件概率值）统计算法。（2 2）哈夫曼树的构造算法。（哈夫曼树的构造算法。（3 3）优化哈夫曼树的构造算法。（）优化哈夫曼树的构造算法。（4 4）压）压缩算法。（缩算法。（5 5）还原算法。）还原算法。下面给出一个用子信息块哈夫曼树压缩汉字字形的结果。下面给出一个用子信息块哈夫曼树压缩汉字字形的结果。字数字数3943