基于组合学的数据编码方法研究

摘要

在信息技术迅猛发展的今天，数据编码技术广泛应用在计算机、多媒体和通信等多门学科领域，成为基本工具和基础研究问题之一，在各类研究和应用的发展中扮演重要角色。本文提出一种基于组合学的数据编码新方法，简称组合编码，它根据自身性质和优势，可以在数据压缩、数据保密等多个领域发挥作用，对于信息的处理和存储传输具有重要意义。
　　 组合编码方法是根据组合学原理，利用字符序列空间与其序数空间的关系进行编码。该方法需要编码与解码双方预先约定一个基准序列，编码时可以根据该基准序列计算出序列对应的序数，解码时则可以根据该基准序列由序数回推出原序列。序数计算是组合编码的技术关键。本文对序数性质进行了研究：序数取值取决于基准序列；序数大小取决于字符频率分布。
　　 由于组合编码方法涉及的运算量很大，因此本文研究了相应的旨在提高运算效率的优化算法。分析了不同数进制对序数计算速度的影响，发现数进制长度与运算速度基本成正比。本文还采用比例运算以替换计算量庞大的排列组合运算，推导出相应迭代公式，优化了序数计算过程，减少了运算量，从而提高了序数计算速度。此外，还对某些特殊情况进行了研究。总之，优化算法提高了组合编码方法的运算效率。
　　 为了进一步提高组合编码运算效率，提出了并行技术。有两种并行编码方法：段内并行编码和段间并行编码。段内并行主要采用多线程技术实现，其关键技术是对序列进行拆分；段间并行算法主要是针对多处理机进行了初步探讨。
　　 组合编码技术可用于多个领域的研究与应用。本文利用组合编码中有关序数空间小于序列空间这一性质对数据进行压缩，即当原序列长度与序数长度之间所节省字节足以抵消字符频率表及其它辅助信息空间时，便可以进行组合压缩。组合压缩技术充分体现有重复即有冗余这一事实。为了便于实验，需要选取一个合适的分段长度。为此对内容无规律的随机文件中分段字符频率分布规律进行了研究，该研究对于频率表的压缩优化乃至整个组合压缩技术的实现起到关键作用。
　　 本文还研究了组合压缩与算术压缩、字典压缩之间的关系。组合压缩是一种结合算术压缩技术的字典压缩方法，是一种不依赖概率统计特性的通用压缩技术。它适用于压缩无记忆信源，特别适合压缩字符频率相近的无记忆信源。理论分析表明当序列长度足够大时，组合压缩比字典压缩更加逼近压缩极限。该压缩技术配合其它压缩方法可以使最终压缩效果更逼近信息熵，在一定空间下能够尽可能多的存储数据，节省资源。
　　 有关组合编码方法的研究，今后的工作还有很多，特别是优化技术和并行算法设计，在加密解密等其它应用方面也有很大扩展空间。

目录

文摘

英文文摘

第1章 绪论

1.1 引言

1.2 编码技术概述

1.2.1 编码技术

1.2.2 数据压缩编码

1.3 海量历史数据压缩的需求

1.4 本文的研究内容和组织结构

第2章 信息熵理论和主要压缩编码方法

2.1 信息熵理论

2.2 统计编码

2.2.1 哈夫曼编码

2.2.2 Golomb编码

2.2.3 游程编码

2.2.4 算术编码

2.2.5 基于字典的编码

2.3 预测编码

2.3.1 DPCM基本原理

2.3.2 语音信号的预测编码

2.3.3 图像的预测编码

2.4 变换编码

2.5 分析综合编码

2.6 本章小结

第3章 基于组合学的数据编码方法

3.1 基于组合学的数据编码方法基本思想

3.1.1 组合编码方法基本概念

3.1.2 组合编码方法基本思路

3.2 序数计算公式的推导

3.3 最大序数计算公式的推导

3.4 实例分析

3.4.1 按样品频率降序计算序数

3.4.2 样品频率降序情况下的序列回推

3.4.3 样品排列顺序对序数的影响

3.5 组合编码全局最大序数研究

3.6 本章小结

第4章 组合编码方法的优化技术

4.1 不同数进制对运算速度的影响

4.2 合并简化计算

4.2.1 求解当前字符前面各字符排列组合值之和

4.2.2 第一个假设字符的排列组合值

4.2.3 特殊情况的处理

4.2.4 实例的合并简化

4.2.5 优化算法比较分析

4.2.6 比例计算的实现

4.3 本章小结

第5章 组合编码并行技术研究

5.1 并行计算与并行压缩编码

5.2 组合编码方法的段内并行编码技术

5.2.1 分组串行

5.2.2 分组并行

5.2.3 并行计算的相关与冲突及其进一步优化

5.3 组合编码方法的段间并行编码技术

5.4 本章小结

第6章 组合编码应用技术研究

6.1 问题提出

6.2 组合压缩方法研究

6.3 组合压缩与字典压缩比较分析

6.4 组合编码在保密编码中的潜在应用

6.4.1 分组密码设计准则

6.4.2 组合加密

6.5 组合编码在信道编码中的潜在应用

6.6 本章小结

结论

参考文献

攻读博士学位期间发表的论文和取得的科研成果

致谢

个人简历