# HuffmanCoding

**Repository Path**: z2huo/HuffmanCoding

## Basic Information

- **Project Name**: HuffmanCoding
- **Description**: 赫夫曼树及赫夫曼编码的Java实现，其中给出了示例文件用来进行文档压缩
- **Primary Language**: Java
- **License**: GPL-3.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2020-01-01
- **Last Updated**: 2020-12-19

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

### 1. 相关知识介绍
#### 1.1 赫夫曼树
赫夫曼数（Huffman）树，又称最优树，是一类带权路径长度最短的树。有着广泛的应用，比如在数据文件的压缩方面。

**路径长度**：从树中的一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称作路径长度。树的路径长度是从树根到每一结点的路径长度之和。

**带权路径长度**：结点的带权路径长度为从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度为树中所有叶子结点的带权路径长度之和。

带权路径长度最小的树称为**最优二叉树或赫夫曼树**

#### 1.2 赫夫曼算法
赫夫曼最早给出了一个带有一般规律的算法，俗称赫夫曼算法，可以构造赫夫曼树。

1. 初始化： 根据给定的n个权值{w1,w2,…wn}构成n棵二叉树的集合F={T1,T2,..,Tn}，其中每棵二叉树Ti中只有一个带权wi的根结点，左右子树均空。
1. 找最小树：在F中选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且至新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
1.  删除与加入：在F中删除这两棵树，并将新的二叉树加入F中。
1. 判断：重复前两步（2和3），直到F中只含有一棵树为止。该树即为哈夫曼树

#### 1.3 前缀编码
**前缀编码** 是指对字符集进行编码时，要求字符集中任一字符的编码都不是其它字符的编码的前缀，例如：设有abcd需要编码表示（其中，a=0、b=10、c=110、d=11,则表示110的前缀可以是c或者da，不唯一）

**自我理解**：前缀编码的特殊性与树的结构有关，赫夫曼树中只有叶子节点才是存有编码值的节点，而且到达每一个叶子节点的路径都是唯一的，所以不可能出现一个字符的编码是另一个字符编码的前缀的情况。

### 2. 具体实现
为实现赫夫曼编码及其过程，编写程序的功能大致如下：
- 读取待编码文档，并且对其中的字符进行频率统计
- 根据频率统计结果构造赫夫曼树，并生成赫夫曼编码规则
- 根据编码规则将待编码文档进行编码，生成压缩后的文档，同时将编码规则也输出到文件中
- 可以根据存储有编码规则的文件和编码后的文件进行解码

下面是程序中各个类及其功能：
- Encode：编码流程调度类
- Decode：解码流程调度类
- Node：节点实体类
- HuffmanTree：赫夫曼树构造类
- CharacterCounter：字符出现频率统计类
- RuleWriter：编码规则输出类
- RuleReader：编码规则读取类
- TextReader：待编码文件读取类