实验要求

将附件中的英文文献用最佳不等长编码进行压缩。即利用霍夫曼编码（Huffman Code）、算术编码（Arithmetic Code）和LZ编码（Lempel-Ziv Code）任一编码算法对文献实现无损压缩。

实验内容

使用Go语言实现霍夫曼编码（Huffman Code）的编码和译码过程，生成可执行的二进制文件，对文献实现无损压缩和解压过程。

概要设计

功能模块设计

系统总共由文件读写模块、霍夫曼编码译码模块组成、数据形成模块、数据类型转换模块组成。

文件读写模块：以二进制方式读取和写入文件内容的功能。
霍夫曼编码译码模块：包含统计字符出现次数功能，生成树节点功能，生成唯一霍夫曼树功能。
数据形成模块：包含读/写标志位功能，读/写编码类型功能，读/写译码表功能，读/写填充长度功能，读/写编码功能。
数据类型转换模块：包含bit串与Byte的互相转换功能，整型数与Byte的互相转换等功能。

编程语言

Golang

结果展示形式：

编码和译码操作均使用同一个二进制文件，即“dmsc_windows_amd64.exe”文件。

压缩（编码）

将需要压缩的文件改名，即以“.0”（不包含双引号）结尾（如test.txt.0），拖拽该文件到二进制文件上，将立刻开始进行压缩；压缩结束后，在需要压缩文件的同目录下生成一个以“.bin”（不包含双引号）结尾的文件，该文件即是经过霍夫曼编码压缩后的文件。

解压（译码）

将需要解压的文件改名，即以“.bin”（不包含双引号）结尾（如test.txt.0.bin），拖拽该文件到二进制文件上，将立刻开始进行解压；解压完成后，在需要解压文件的同目录下生成一个以“.0”（不包含双引号）结尾的文件，该文件即是经过霍夫曼编码解压后的文件。

算法实现思路

编码译码工作流程

图1 霍夫曼编码译码流程图

压缩文件头设计

图2 文件头设计

关键代码说明

树节点定义

1
2
3
4
5
6
7
8
9


type TreeNode struct {
    Character  byte      `json:"character"`  // 字母
    Weight     uint32    `json:"weight"`     // 权重
    FNode      *TreeNode `json:"fnode"`      // 父节点
    LNode      *TreeNode `json:"lnode"`      // 左节点
    RNode      *TreeNode `json:"rnode"`      // 右节点
    Code       string    `json:"code"`       // 编码
    IsLeafNode bool      `json:"isleafnode"` // 为叶节点
}

编码流程

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


func EncodeHandler(filePath string, textByteSlice []byte) {

    if len(textByteSlice) == 0 {
        fmt.Println("There is no character in text!")
        os.Exit(1)
    }

    // 统计字符出现次数
    characterFrequencyMap := util.CountCharacterFromText(textByteSlice)

    // 生成霍夫曼树节点
    treeNodeMap := GenerateHuffmanTreeNode(characterFrequencyMap)

    // 生成霍夫曼树
    GenerateHuffmanTree(treeNodeMap)

    // 仅做测试用
    // PrintTreeMap(treeNodeMap)

    byteChannelToFile := make(chan byte, 64)

    // 准备二进制文件所需的数据
    go writeBinaryFile(treeNodeMap, characterFrequencyMap, textByteSlice, byteChannelToFile)

    // 构造输出文件名
    binaryFileName := fmt.Sprintf("%s.bin", filePath)
    fmt.Println("binaryFileName", binaryFileName)
    util.WriteByteToFile(binaryFileName, byteChannelToFile)
}

初始化组成霍夫曼树的节点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


func GenerateHuffmanTreeNode(characterFrequencyMap map[byte]uint32) (treeNodeMap map[byte]*TreeNode) {
    treeNodeMap = make(map[byte]*TreeNode)
    for k, v := range characterFrequencyMap {
        if _, ok := treeNodeMap[k]; !ok {
            treeNodeMap[k] = &TreeNode{
                Character:  k,
                Weight:     v,
                FNode:      nil,
                LNode:      nil,
                RNode:      nil,
                Code:       "",
                IsLeafNode: true,
            }
        }
    }
    return
}

生成霍夫曼树

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


func GenerateHuffmanTree(treeNodeMap map[byte]*TreeNode) (rootNode *TreeNode) {

    // 验证：map是无序的
    // for k, v := range treeNodeMap {
    //  fmt.Println(k, v)
    // }

    // 转换成Slice便于排序
    tns := treeNodeMapToTreeNodeSlice(treeNodeMap)
    // 排序，当排序完成后，出现次数小的在前面
    // 出现次数相同时，ASCII码小的排在前面
    sort.Sort(TreeNodeSlice(tns))

    if len(tns) == 1 {
        panic("There is none in TreeNodeSlice!")
    }

    for len(tns) != 1 {
        tempNode := TreeNode{
            Character:  0, // 非叶节点均为0
            Weight:     tns[0].Weight + tns[1].Weight, // 合并权重最小的两个节点
            LNode:      tns[0], // 默认左节点权重比右边小，若权重相等，则默认左节点的ASCII值比右节点小
            RNode:      tns[1],
            FNode:      nil,
            Code:       "",
            IsLeafNode: false,
        }
        tns[0].FNode = &tempNode // 注意取地址
        tns[1].FNode = tns[0].FNode
        tns = append(tns[2:], &tempNode) // 新节点添加进切片，并删除已经被合并的两个权重最小的两个节点
        // 再次排序
        sort.Sort(TreeNodeSlice(tns))
    }

    rootNode = tns[0]
    distributeCode(rootNode)

    return
}

根据霍夫曼树递归分配节点的编码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


func distributeCode(node *TreeNode) {
    if node.LNode != nil {
        node.LNode.Code = fmt.Sprintf("%s%d", node.Code, 0)
        distributeCode(node.LNode)
    }
    if node.RNode != nil {
        node.RNode.Code = fmt.Sprintf("%s%d", node.Code, 1)
        distributeCode(node.RNode)
    }
    return
}

解码流程

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41


func DecodeHandler(filePath string, fileContent []byte) {

    byteChannelFromBinaryFile := make(chan byte, 1024)

    // 读取文件
    go func(byteChannelFromBinaryFile chan<- byte) {
        for _, eachByte := range fileContent {
            byteChannelFromBinaryFile <- eachByte
        }
        close(byteChannelFromBinaryFile)
    }(byteChannelFromBinaryFile)

    codeNumber := util.ReadCodeNumber(byteChannelFromBinaryFile)
    characterFrequencyMap := readCodeFrequencyAndGenerateCharacterFrequencyMap(codeNumber, byteChannelFromBinaryFile)

    // 生成霍夫曼树节点
    treeNodeMap := GenerateHuffmanTreeNode(characterFrequencyMap)
    // 生成霍夫曼树
    rootNode := GenerateHuffmanTree(treeNodeMap)

    // 仅做测试用
    // PrintTreeMap(treeNodeMap)

    // 获得填充长度
    paddingLength := util.ReadPaddingLength(byteChannelFromBinaryFile)
    fmt.Println("paddingLength", paddingLength)

    bitChannel := make(chan bool, int(math.Pow(2, 16)))

    // 读取编码文件的编码部分
    go util.ConvertCodeByteToCodeBit(paddingLength, byteChannelFromBinaryFile, bitChannel)
    
    byteChannelToTextFile := make(chan byte, 1024)
    
    // 译码
    go decodeTextFromTreeNodeMap(rootNode, bitChannel, byteChannelToTextFile)

    fmt.Println("filePath", filePath)
    // 译码内容写入文件
    util.WriteByteToFile(filePath, byteChannelToTextFile)
}

根据霍夫曼树将比特流译码成字符

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


func decodeTextFromTreeNodeMap(rootNode *TreeNode, bitChannel <-chan bool, byteChannel chan<- byte) {
    currentNode := rootNode
    for each := range bitChannel {
        if each == false {
            // 0则进入左子树
            currentNode = currentNode.LNode
        } else {
            // 1则进入右子树
            currentNode = currentNode.RNode
        }
        // 若是叶节点则输出字符
        if currentNode.IsLeafNode {
            byteChannel <- currentNode.Character
            currentNode = rootNode
        }
    }
    close(byteChannel)
}

将bit串类型的编码转变成可写入文件的Byte

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


func ConvertCodeStringToCodeByte(bc <-chan bool, byteChannelToFile chan<- byte) (paddingLength uint8) {
    byteLength := uint8(0)
    tempByte := uint8(0) // 结合tempBytePointer

    var tempBytePointer *uint8 = &tempByte // 重复使用
    for {
        receivedBit, ok := <-bc
        if ok {
            switch receivedBit {
            case false:
                // 左移一位，末尾默认补0
                *tempBytePointer <<= 1
            case true:
                // 左移一位，末尾补零后再加1
                *tempBytePointer = (*tempBytePointer << 1) + 1
            }
            byteLength++
            // 满8位bit则输出一个Byte
            if byteLength == 8 {
                byteChannelToFile <- *tempBytePointer
                *tempBytePointer = 0
                byteLength = 0
            }
        } else {
            // 没有更多的bit时，检查需要填充0以补满8位的个数
            if byteLength != 0 {
                paddingLength = 8 - byteLength
                for i := byteLength; i != 8; i++ {
                    *tempBytePointer <<= 1
                }
                byteChannelToFile <- *tempBytePointer
            }
            close(byteChannelToFile)
            break
        }
    }
    return
}

将Byte类型的编码转变成bit以供解码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


func ConvertCodeByteToCodeBit(paddingLength uint8, inByteChannel <-chan byte, outBitChannel chan<- bool) {
    var tempByte byte
    receivedByte1, ok1 := <-inByteChannel
    receivedByte2, ok2 := <-inByteChannel
    for {
        // 对于receivedByte1来说，若还能取到下一个，则receivedByte1不需要根据填充数对bit进行截断
        if ok1 && ok2 {
            for i := uint8(8); i > uint8(0); i-- {
                tempByte = receivedByte1 & (uint8(1) << (i - 1))
                if tempByte != uint8(0) {
                    outBitChannel <- true
                } else {
                    outBitChannel <- false
                }
            }
            receivedByte1, ok1 = receivedByte2, true
            receivedByte2, ok2 = <-inByteChannel
        } else {
            // 否则需要进行截断，即根据paddingLength舍弃填充的0
            for i := uint8(8); i > paddingLength; i-- {
                tempByte = receivedByte1 & (uint8(1) << (i - 1))
                if tempByte != uint8(0) {
                    outBitChannel <- true
                } else {
                    outBitChannel <- false
                }
            }
            close(outBitChannel)
            break
        }
    }
}

入口main函数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


func main() {

    var filePath string
    // os.Args[0]是二进制文件自身的路径
    // os.Args[1]是拖拽到二进制文件上 文件的路径
    filePath = os.Args[1]

    // 以下两行做测试用
    // filePath = "files/test2.txt.0"
    // filePath = "files/test2.txt.0.bin"

    fileContent := util.ReadFromFile(filePath)

    // 检测是否0x19 0x15开头
    flagExist := util.ReadFlag(fileContent[0:2])
    // fmt.Println(flagExist)

    if flagExist {
        CodeType := util.ReadCodeType(fileContent[2])
        filePath = filePath[0 : len(filePath)-4]
        switch CodeType {
        case 0:
            // 霍夫曼编码
            huffman.DecodeHandler(filePath, fileContent[3:])
        }
    } else {
        filePathStringSlice := strings.Split(filePath, ".")
        encodeType := filePathStringSlice[len(filePathStringSlice)-1]
        switch encodeType {
        case "0":
            // 霍夫曼解码
            huffman.EncodeHandler(filePath, fileContent)
        }
    }
}

系统测试

	源文件	压缩文件
文件名	test.txt.0	test.txt.0.bin
文件大小	7KB	4KB
压缩比（压缩文件/源文件）	60.99%

图3为源文件（左）和压缩文件（右）的最后一部分字节序列比较，

图3 源文件（左）和压缩文件（右）的最后一部分字节序列比较

体会

在代码实现过程中遇到了一些困难，也尝试着自己解决。

压缩文件的文件头是自己设计且需要有的，如果没有文件头，则无法在只有压缩文件的前提下进行解压。
编码和译码的霍夫曼树是一致的，如果不一致则会译码错误。
使用Go编程是在尝试学习新型语言。项目完全自己开发，并未引入任何第三方库。
已开源到Github项目，遵循MIT开源协议。

信息论及其应用小作业 数据压缩