点阵字库的压缩与还原

实验目的

1．了解汉字字形库压缩的需求与常用压缩方法。

2．理解点阵字库黑白段压缩方法、线性增量压缩方法。

3．掌握点阵字库黑白段压缩与还原的实现。

实验内容

1．根据点阵字形描述技术写出汉字的字形点阵码。

2．编写程序，使用黑白段压缩方法对指定汉字的点阵码进行压缩。

3．编写程序，对黑白段压缩后的汉字点阵码进行解压缩。

预备知识

一、字形库的压缩

由于书刊、报纸的实际印刷中对汉字点阵的要求通常很高，因此往往需要使用512× 512点阵或者1024×1024点阵的汉字字形库。以512×512为例，此时一个汉字就需要512×512／8＝32KB的存储空间，那么如果采用512×512点阵把Unicode的BMP中每个汉字以宋体、楷体、仿宋体、黑体四种最常用的字体描述出来，就需要20902×4×32KB＝2612．75MB的存储空间，如果采用1024×1024点阵需要10451MB。而实际上我国印刷用汉字至少需要20多种字体、20多种字号，这种存储需求在20世纪80年代和90年代初期是难以接受的。显然需要对点阵字库进行压缩存储，从而降低对存储的要求。

对汉字字形库采用的常用压缩方法有：黑白段压缩法、部件压缩法和轮廓字形压缩法。其中，轮廓字形压缩法是如今最流行的方法，这种方法压缩比大，且能保证汉字的质量；黑白段压缩法是专门针对点阵字库的压缩方法，该方法具有简单、易实现的优点。

二、黑白段压缩法

黑白段压缩法是20世纪60年代德国Hell公司首先在第三代阴极射线管照排机Digiset上采用的方法，黑白段描述法只记录字形水平方向上每条线的各个黑段和白段的长度，而不存储整个点阵。字形点阵可以毫不失真地复原。

黑白段压缩的思想：有数据的部分被称为黑段，无数据的部分被称为白段，然后通过扫描点阵信息交替记录下每行的黑段与白段，并设计了“重复行数”来处理汉字中大量存在的连续多行点阵信息相同的情况。

黑白段的具体记录原始数据格式如下：

【行标识】【重复行数】【白段】【黑段】……【白段】【黑段】

例如，“王”字的48×48点阵的宋体字形如图8．1所示，设行标识为“*”，则它的黑白段压缩码的存储参见表8．1。

图8．1 “王”字的48×48点阵字形

表8．1 “王”字的黑白段压缩描述

续表

三、黑白段的压缩效果

图8．1中的“王”字的点阵字形直接存储到计算机的时候，占用了48×48／8＝288个字节。采用了黑白段压缩法压缩后，设行标识、重复行数、白段、黑段都占用一个字节，那么“王”字需要占用81个字节，压缩效果显然是非常明显的。由于每一行黑段和白段的和应该是48，在实际实现的时候，每行最后一个黑白段信息可以通过48减去该行前面各项的和计算出来，因此每行最后一个黑白段信息可以省略。如果这样的话，48×48点阵的“王”字只需要用66个字节存储。显而易见，对于点阵数越大的字形库，黑白段的压缩率越高。

四、线性增量压缩法

对图8．1中“王”字进行观察，很容易发现：其中第6到第8行，左边的白段在逐渐递减一个，中间的黑段在逐渐递增两个，右边的白段在逐渐递减一个。下面两横的笔锋同样也呈现如此的规律。此时可以使用线性增量方法对黑白段进行改进与优化。线性增量主要用于处理汉字点阵中大量存在的斜线，它的思想是：在一行黑、白段记录信息的后面再注明线段的增量，这样下一行的黑、白段长度在上一行的基础上按增量的大小作相应的变化。

线性增量的具体记录原始数据格式如下：

【行标识】【重复行数】【白段】【白段增量】【黑段】【黑段增量】

……【白段】【白段增量】【黑段】【黑段增量】

因为线性增量式黑白段的辅助手段，二者处理后的数据会同时出现。因此在表示数据的时候，为了与黑白段所表示的行加以区别，线性增量表示的行标记应该有所不同。表8．2显示了对“王”字综合使用黑白段与线性增量之后的压缩数据，其中以“*”开头的行表示以黑白段压缩，以“$”开头的行表示以线性增量压缩，所以在每个黑白段的数据后面多了一个增量信息。

表8．2 “王”字形黑白段和线性增量综合压缩的描述

五、哈夫曼字形压缩法

哈夫曼字形压缩法的思想是将汉字的点阵图看作由多个子点阵构成的，子点阵的尺寸可以是2×2、1×2或者2×1等，然后统计所有汉字点阵中这些子点阵的概率，接着根据子点阵的概率分布进行哈夫曼编码，从而得出所有汉字的哈夫曼编码，最后用这些子点阵的编码存储到汉字库中。图8．2显示了一个2×2点阵的16种状态，经过统计发现：汉字中横竖笔画多于撇捺等笔画，因此图8．2中状态12的概率大于状态1。

图8．2 2×2点阵的16种状态

如果对所有汉字的点阵进行统计，可以得出图8．2中的所有状态的概率，然后使用哈夫曼编码法对16种状态进行不等长编码，保证概率最高的编码最短，这样同样可以实现较好的压缩效果。具体的统计与编码结果参见表8．3。

表8．3 16种2×2点阵的哈夫曼编码

实验原理

一、哈夫曼编码

哈夫曼压缩是一种在图形图像压缩中广泛使用的压缩方法，TIFF和JPEG等图像格式就使用了哈夫曼压缩。哈夫曼压缩基于哈夫曼树的概念，需要做哈夫曼编码和哈夫曼译码。哈夫曼树又称最优二叉树，它是一种带权路径长度最短的二叉树。哈夫曼压缩原理是先统计需要编码状态的出现概率，然后将短的码赋予出现频率高的状态，而将长的码赋予出现频率低的状态。因为哈夫曼编码简单有效，所以得到了广泛的应用。但是产生哈夫曼编码要对原始数据扫描两遍：第一遍扫描要精确地统计出原始数据中每个值出现的频率；第二遍扫描是建立哈夫曼树并进行编码。由于需要建立二叉树并遍历二叉树生成编码，因此数据压缩和还原速度都较慢。

哈夫曼树生成步骤：

（1）对给定的权值集合W＝｛W1，W2，W3，…，Wi，…，Wn｝，其中已经按照从小到大排序，它们构成n棵二叉树的初始集合F＝｛T1，T2，T3，…，Ti，…，Tn｝，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。

（2）在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。

（3）从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。

（4）重复步骤（2）和步骤（3），直到集合F中只有一棵二叉树为止。

得到了哈夫曼树，可以认为每个节点到左子树的边为0，到右子树的边为1，然后为每个叶子找到从根节点过来的最短路径，这样就得到了该叶子的哈夫曼编码。

综上可见，利用哈夫曼压缩前提要构建哈夫曼编码，构建哈夫曼编码的实质是生成哈夫曼树，而生成哈夫曼树又需要每个节点的权值，这个需要统计而来。

二、点阵数据、黑白段数据和线性增量数据的转换

根据实验七可以发现，把字形的点阵数据显示在屏幕上是一个比较简洁明了的机械处理过程，主要是充分利用了位运算进行位测试。因此基于软件分层和函数独立的思想，可以让负责显示字形的函数只读取点阵数据并显示。

数据压缩的过程就是把点阵数据变成黑白段和线性增量数据，解压的过程就是把黑白段和线性增量数据变成点阵数据。

实验环境

一、操作系统

Windows 2000以上版本，例如，Windows 2000／XP／Vista／7／8／8．1／10等。

二、开发环境

C、C＃或Java等语言集成开发环境。

实验步骤

1．针对HZK48S编写函数，实现把一个汉字的点阵码转换为黑白段压缩码。函数原型如下：

int dotEncode（unsigned char hzdot［288］，unsigned char*des）

／*

本函数用于将一个汉字的48×48横向点阵码转换为黑白段压缩码

参数： unsigned char hz［288］为一个汉字的48×48横向点阵码；

unsigned char*des为黑白段压缩后的编码

返回值：压缩后编码的字节长度

*／

请在实验报告中给出该函数的代码实现。

2．针对前面黑白段压缩的数据，编写函数将其还原为16×16的点阵码，函数原型如下：

int dotDecode（unsigned char hzdot［288］，unsigned char*des）

／*

本函数用于将一个汉字的黑白段压缩码还原为16×16横向点阵码

参数： unsigned char*des为黑白段压缩后的编码，以′＼0′结束

unsigned char hz［288］为还原的16×16横向点阵码；

返回值：无

*／

请在实验报告中给出该函数的代码实现。

3．利用实验步骤1中的dotEncode函数编写完整程序对HZK48S中所有汉字进行黑白段压缩，并计算出在整个字库上的压缩率，在此基础上考虑如何进一步改进。

4．将表8．3中的概率作为权值，编写程序构建一棵哈夫曼树，并利用该树得到哈夫曼编码。

思考题

1．请给出对正文中16种2×2点阵的哈夫曼编码过程。

2．哈夫曼压缩和黑白段压缩各有什么优缺点？

3．如何在哈夫曼或黑白段压缩后的数据中快速检索到一个汉字的字形？

参考文献

［1］唐英敏，张艳霞，吕肖庆．基于汉字构形的True Type字库压缩方法［J］．微电子学与计算机， 2007，24（6）：52－55．

［2］蒋贤春，翟喜奎．计算机中文信息处理规范和应用指南［M］．北京：北京图书馆出版社，2012．1．

［3］朱巧明，李培峰，吴娴等．中文信息处理技术教程［M］．北京：清华大学出版社，2005．9．

［4］陈志成，何华灿，毛明毅．GB18030字库的解读与压缩封装程序设计［J］．计算机工程与应用，2002，38（18）：119－121．

［5］李宝安．中文信息处理技术［M］．北京：清华大学出版社，2005．7．