维吾尔文搜索引擎中的压缩技术

摘要：在对常用压缩技术进行介绍的基础上，结合维吾尔语代码特点来选择合适的压缩技术对文本进行压缩，以实现压缩率的提高，从而减少搜索引擎对数据空间要求。通过初步实验验证所选方法具有一定的正确性，取得了一定的效果。

关键词：数据压缩；维吾尔语；搜索引擎

中图分类号：TP274文献标识码：A文章编号：1009-3044(2011)27-6623-02

Uyghur Search Engine Compression

XUE Zhong-qi, Winira・Musajan, ZHAO Li-hong

(College of Information Science and Technology of Xinjiang University, Urumqi 830046, China)

Abstract: In the introduction to commonly used compression technology based on the combined characteristics of Uyghur code to select the appropriate compression technique for text compression to achieve compression rates have increased, thereby reducing the space required for data search engine. Selected by preliminary experimental verification method has some validity, achieved some results.

Key words: data compression; Uyghur; search engine

海量网络数据的涌现，进而对数据传输时间和数据存储技术、检索响应时间提出更多挑战，这些问题正是影响搜索引擎的关键。迄今为止，已经有相当多的数据压缩算法及技术方法被开发出来并广为应用[1]，同时还有不少专门针对大量数据的压缩而开发的算法和工具，如RAR、ZIP等。互联网上也有对数据压缩进行分析的文章，但这些研究仅针对各自领域压缩对象或压缩格式进行分析。虽然，这些研究所提出的方法在未考虑语言特点的情况下也能够对维吾尔文等基于阿拉伯文字的语种提供一定量的压缩率，但其效果远远不如基于英文的压缩操作。目前，在新疆地区提供各种网络服务的维、哈、柯文（维吾尔文为主）网站正以指数规律迅速增多，对已有维、哈、柯文搜索引擎研究的基础上引入数据压缩技术，并结合维吾尔文特点进行了分析。显然，数据压缩技术的使用可以有效减轻服务器的压力并提高搜索引擎的检索速度、减少数据存储空间。

1 压缩技术简单介绍

一般说来，数据压缩的工作是将符号流或数据流转换成相应的代码。显然，只有输出的代码流长度小于源符号流时，所做的数据压缩才是有效的。数据压缩中按照压缩是否失真将压缩分为无损压缩和有损压缩。搜索引擎中文本压缩要求无失真仅是研究无损压缩。无损压缩的编码方式分为两种类型：基于统计编码和基于字典编码[2]。

1.1 统计编码

利用哈夫曼编码Huffman算法压缩文件就是对文本中的字符进行重新编码，对于使用频率越高的字符，其编码也越短。但要求编码属于前缀码，即字符A的编码的前段，不可能为字符B的编码。产生哈夫曼编码需要对原始数据扫描两遍，第一遍扫描要精确地统计出原始数据中的每个字符出现的频率，第二遍是建立哈夫曼树并进行哈夫曼编码。编码后的文本文件，主要包含Huffman码表部分和压缩内容部分。解压缩时，先把Huffman码表取出来，然后对压缩内容部分各个字符进行逐一解码，还原源文件。

1.2 字典编码

字典编码方法是压缩中常用的一种无损压缩方法。基本原理是以较长的字符串或经常出现的字母搭配构成字典中的各个表项，然后用相对较短的数字或符号来表示。LZ77算法常称为基于滑动窗口的自适应字典压缩方法，该算法将一个虚拟的、可以跟随压缩进程滑动的窗口作为术语字典。待压缩的字符串如果在该窗口中出现，则输出其出现位置和长度。LZ78算法不同于LZ77算法就是它放弃了窗口的概念，采用树形结构构造字典和保存短语，从而确保文件中的内容均能反映到字典中。1984年由TA Welch对LZ78算法修改而成的一种实用的算法[3]。LZW压缩算法的基本思想是建立一个串表，将输入字符串映射成定长的码字输出。串表具有“前缀性”：假设任何一个字符串P和某一个字符S组成一个字符串PS，若PS在串表中，则S为P的扩展，P为S的前缀。字符串表是动态生成的，编码前先将其初始化，使其包含所有的单字符串。在压缩过程中，串表中不断产生压缩信息的新字符串，存储新字符串时也保存新字符串PS的前缀P相对应的码字。在解压缩过程中，解码器可根据编码字恢复出同样的字符串表，解出编码数据流。

2 基于维吾尔文文字特点的文本数据压缩

到目前为止，民文网页的总数目大约在5万个左右。虽然这些网页内容所占用的存储空间对一般服务器来说不一个很大的数字，但考虑网络的发展趋势和网页的增长数量时，该问题应予以重视。

2.1 维吾尔文字符在Unicode编码表中的分布特点

维吾尔文以及主要在新疆地区所使用的哈萨克、柯尔克孜等文种是基于阿拉伯字母的。维吾尔文由32个字母组成，且这些字母还有120多个变形体。其特点如下：

第一，基于阿拉伯字母的所有文字（包括维、哈、柯文）字符集中在Unicode表中的“Arabic”和“Arabic Presentation Forms”子区域，但维、哈、柯字符对应的代码是不连续分布的。所有的维吾尔文字母的代码在Unicode代码表中占有两个字节（都是06XX）。

第二，维吾尔文的字是由一个或者多个字母组成，每个字母有基本形式和四种不同的书写形式（尾部与下一个字母相连的首写形式、尾部与相邻字母连接的中间形式、首部与上一个字母相连的尾写形式和首尾与相邻字母都不相连的独立形式）[5]。

2.2 两种压缩方式分析

鉴于以上的特点，结合以下两种数据压缩方式分析：

哈夫曼编码(Huffman)处理方法。Huffman编码非常便于硬件实现，在改变任何符号二进制编码引起少量密集表现方面是最佳的。但哈夫曼树(哈夫曼表)作为编码环境必须输入,接受端通过信道传输接受哈夫曼表，以重建哈夫曼树，供解码器使用。该算法不对重复字符或重复子串统计编码，而且符号的出现频率不能预知，需要统计和编码两次处理，维哈柯语言文字有自身的地域特点，网页的数量较少。在实际运行时，现有的硬件条件可以满足其统计需求，构建哈夫曼树。并可将其应用到实时性较强的搜索引擎中。在解码时仍是采用已建立好的哈夫曼树，进行快速解码。

LZW编码处理方法。其压缩的原理在于用字典中词条的编码代替被压缩数据中的字符串。因此字典中的词条越长越多，压缩率就越高。加大字典的容量可以提高压缩率。但字典的容量要受到计算机内存的限制，而且其字典也会被填满。这样当字典不能再加入新词条后，过老的字典就不能保证高的压缩率。为了解决这个问题在压缩时必须监视压缩率，当压缩率下降时,清除匹配概率较小的词条而保留匹配概率较大的词条。这就需要及时的对字典进行更新保证其压缩率。LZW算法相对复杂，但编码速度快通用性好，适合复杂语种条件下的使用，更好的为维、哈、柯文与英文的混合语言文本编码做好基础。

维吾尔文以UTF-8或UTF-16代码标准存储数据时各自占用两个字节空间，可以通过字母的映射使其转化为利用单字节存储的文字。首先通过算法，将基于阿拉伯文的维吾尔文转化为基于拉丁文的维吾尔文，而后采用压缩算法进行压缩。实验结果如表1所示。

表1几种文本的压缩率

注：1.压缩率是指原始文件大小除以压缩后文件大小，数值越大越好。2."―"指转化过程中出现异常。

实验数据表明通过先转化后压缩明显的提高文本压缩效率，验证该方法的正确。但该方法在对混合语种进行实验时，出现异常。

3 结束语

目前压缩技术已经成为国内外的研究热点，文本压缩技术的应用很广泛，在今后的工作中将对几种压缩算法在搜索引擎中使用得出的具体数据进行分析。实验中，纯文本的维吾尔文文本转化后的压缩率比未转化的有所提高。但对于维吾尔文与英文混合文本，转化后不能将其正确解码，需要进一步的对算法进行优化，使其适合实际需要。从而选出更快速、更适合维吾尔语的压缩方法，进一步改善压缩质量，减少存储空间提高搜索引擎的准确率与召回率。

参考文献：

[1] 卢亮,张博文.搜索引擎原理实践与应用[M].北京:电子工业出版社,2007.

[2] 曾玲,饶志宏.几种数据压缩算法的比较[J].通信技术,2002,9(129):12-15.

[3] Alberto Apostolico，Fabio Cunial,Sequence similarity by gapped LZW[EB/OL]./search/searchresult.jsp?newsearch=true&queryText=LZW.

[4] 维尼拉・木沙江,艾尔肯・伊米尔.维文Unicode在线处理技术与实现[J].新疆大学学报,2004.

[5] 赵永进,郭大庆,卢有飞,李英凡.维文软件中排版关键技术的研究与实现[J].计算机工程与应用,2007.

[6] 买日旦・吾守尔,维尼拉・木沙江.电子词典软件系统中对维、哈、柯文进行自动判别技术的研究[J].新疆大学学报,2011,2.

[7] DB/2190-2005,信息交换用维吾尔文、哈萨克文、柯尔克孜文编码字符集、基本集与扩展集[S].