golang哈夫曼編碼壓縮文件代碼實現(xiàn)全流程(超詳細(xì)版)

一、最近研究了一些通用的壓縮算法庙曙，發(fā)現(xiàn)目前各大博客中和相關(guān)教程中關(guān)于使用golang實現(xiàn)哈夫曼壓縮算法的好文章屈指可數(shù)，大多是實驗性的代碼，并沒有完全實現(xiàn)壓縮文件的所有必要步驟

1.僅僅介紹了哈夫曼樹的機制椭豫，并沒有算法實現(xiàn)，只知道原理可不一定能寫出代碼
2.代碼實現(xiàn)了哈夫曼樹的構(gòu)造旨指，并且完成編碼赏酥，存儲在string變量中，打印出被哈夫曼編碼過的字符串谆构，不知道這樣做的意義何在裸扶，這其實變相增大了文件的體積，是一種耍流氓行為搬素，壓根沒有達(dá)到目的
3.通過全局變量將編碼的table保存在內(nèi)存中呵晨，而非保存在被壓縮的文件中，這也是一種耍流氓行為熬尺，難道我們需要拿到原文件和壓縮文件才能解壓摸屠？
本文較長，想了解某個模塊實現(xiàn)的同學(xué)可以跳轉(zhuǎn)到標(biāo)題四后如下序列
1.詞頻統(tǒng)計猪杭，2. 哈夫曼樹的實現(xiàn)餐塘，3.從哈夫曼樹得到編碼表，4.將經(jīng)過哈夫曼編碼的字符寫入文件中
5.將編碼表寫入文件頭的細(xì)節(jié)皂吮，6-7.解壓縮文件的細(xì)節(jié)

二戒傻、為了解決以上所述的痛點税手，真正用golang寫出能夠壓縮解壓縮文件的代碼，我將著重解決以下幾個問題

結(jié)合golang的特性需纳，展示構(gòu)建哈夫曼樹過程中heap接口的應(yīng)用芦倒，用足夠簡單的代碼構(gòu)建哈夫曼樹
用位運算將被編碼的字符寫入bit中，真正實現(xiàn)對字符集的壓縮
用io操作不翩，展現(xiàn)讀寫文件頭table的細(xì)節(jié)兵扬，真正保證壓縮文件具有全量的信息

三、Talk is cheap show me the code

先貼出全量代碼 , 文件輸入輸出路徑均定義在代碼開頭的const變量中口蝠，有想驗證代碼可用性的同學(xué)可以自行拷貝實驗

package main

import (
    "bufio"
    "bytes"
    "container/heap"
    "crypto/md5"
    "encoding/hex"
    "fmt"
    "io/ioutil"
    "log"
    "os"
    "sort"
    "strconv"
    "strings"
)

const filePath = `D:\dataCourpus\file.010`
const outPutPath = `D:\dataCourpus\outPut`
const depressPath = `D:\dataCourpus\depress.txt`
const contentBuffer = 5000000


type TreeNode struct {
    Val int
    Times int
    Left *TreeNode
    Right *TreeNode
}

type  treeHeap []*TreeNode

func (p treeHeap) Less( i , j int) bool {
    return p[i].Times <= p[j].Times
}

func (p treeHeap) Len() int {
    return len(p)
}

func (p treeHeap) Swap(i , j int) {
    p[i] , p[j] = p[j] , p[i]
}

func (p *treeHeap) Push(node interface{}) {
    *p = append(*p, node.(*TreeNode))
}

func (p *treeHeap) Pop()  interface{} {
    n := len(*p)
    t := (*p)[n-1]
    *p = (*p)[:n-1]
    return t
}

// 測試壓縮解壓縮的正確性
func main() {
    HuffmanEncoding(filePath,outPutPath)
    depress(outPutPath,depressPath)
    originMD5 , _:= MD5File(filePath)
    recoverMD5 , _ := MD5File(depressPath)
    fmt.Println(originMD5 == recoverMD5)
}

func HuffmanEncoding (filePath , outPath string) {
    // 思路： 1. 讀取文本內(nèi)容器钟，存放到內(nèi)存中，或者以流的形式讀取文本內(nèi)容妙蔗，構(gòu)建二叉樹即可傲霸。
    // 統(tǒng)計每個字出現(xiàn)的頻次
    file ,err := os.Open(filePath)
    if err != nil  {
        log.Fatalln(err)
        return
    }
    defer file.Close()
    // 我們不需要關(guān)心總量是多少，因為分母是固定的眉反，只需要知道頻率按次數(shù)排序即可昙啄。
    imap := getFrequencyMap(file)
    plist := make(treeHeap,0)
    // 遍歷map ,將鍵值對存入pair，然后按頻率排序
    for k , v := range imap {
        plist = append(plist, &TreeNode{Val: k,Times: v})
    }
    sort.Sort(plist)
    //如果文件是空的寸五，還構(gòu)造個屁
    if len(plist) == 0 {return}
    hTree := initHuffmanTree(plist)
    /*遍歷哈弗曼樹梳凛，生成哈夫曼編碼表(正表，用于編碼),key(ASSCII),value(路徑痕跡)*/
    encodeMap := make(map[int]string)
    createEncodingTable(hTree , encodeMap)

    // 將輸入文件的字符通過碼表編碼梳杏，輸出到另一個文件 , 壓縮模塊完成
    encoding(filePath , outPath , encodeMap)

}

func writeTable(path string, codeMap map[int]string , left int) {
    file ,err := os.Create(path)
    if err != nil {
        return
    }
    // 第一行韧拒，寫入文件頭的長度
    var buff bytes.Buffer
    buff.WriteString(strconv.Itoa(len(codeMap)+1) + "\n")
    for k , v := range codeMap {
        buff.WriteString(strconv.Itoa(k) + ":" + v + "\n")
    }
    buff.WriteString(strconv.Itoa(left) + "\n")
    file.WriteString(buff.String())
    file.Close()
}


/* 一次性讀入，存到string或者buffer.string中 */
func encoding(inPath string, outPath string , encodeMap map[int]string) {
    /*1.先嘗試一次性讀入*/
    inFile ,err  := os.Open(inPath)
    defer inFile.Close()
    if err != nil {
        return
    }
    reader := bufio.NewReader(inFile)
    fileContent := make([]byte,contentBuffer)
    count , _ := reader.Read(fileContent)
    var buff bytes.Buffer
    //string編碼
    for i := 0 ; i < count ; i ++  {
        v := fileContent[i]
        if code , ok := encodeMap[int(v)] ; len(code)!= 0  && ok  {
            buff.WriteString(code)
        }
    }
    res := make([]byte,0)
    var buf byte = 0
    //bit編碼
    //TODO 記錄bit剩余位秘狞，很簡單只要對buff.bytes取長度對8取余即可
    for idx , bit := range buff.Bytes() {
        //每八個位使用一個byte讀取叭莫，結(jié)果存入res數(shù)組即可
        pos := idx % 8
        if pos == 0 && idx > 0 {
            res = append(res, buf)
            buf = 0
        }
        if bit == '1' {
            buf  |=   1 <<  pos
        }
    }
    //TODO 這個left是剩余待處理的位數(shù)
    left := buff.Len() % 8
    res = append(res, buf)
    // 將編碼數(shù)組寫入文件 , TODO 先將碼表和left數(shù)寫入文件蹈集，解碼時在開頭讀取
    writeTable(outPath,encodeMap,left)
    outFile , err := os.OpenFile(outPath,os.O_APPEND|os.O_CREATE|os.O_WRONLY, 0644)
    if err != nil{
        return
    }
    wcount , err := outFile.Write(res)
    if err != nil {
        fmt.Println(wcount)
        return
    }
}

//碼表烁试，考慮到性能必須要生成 map, key(int對應(yīng)ASSCII??，string對應(yīng)bit編碼拢肆，后續(xù)轉(zhuǎn)成bit)
func createEncodingTable(node *TreeNode , encodeMap map[int]string )  {
    /*思路：回溯遍歷二叉樹减响，用byte記錄0 1??，遇到葉子節(jié)點就轉(zhuǎn)換成string存入碼表
        遍歷順序：根左右
    */
    tmp := make([]byte,0)
    var depth func (treeNode *TreeNode)
    depth = func (root *TreeNode) {
        //如果已經(jīng)遍歷到空郭怪，返回
        if root == nil {
            return
        }
        //如果遍歷到的是葉子節(jié)點 , byte轉(zhuǎn)換成string支示，入表
        if root.Left == nil && root.Right == nil {
            encodeMap[root.Val] = string(tmp)
        }
        //如果是普通節(jié)點，左右遞歸回溯即可 #規(guī)則： 左0右1
        tmp = append(tmp ,'0' )
        depth(root.Left)
        tmp[len(tmp)-1] = '1'
        depth(root.Right)
        tmp = tmp[:len(tmp)-1]
    }
    depth(node)
}

func initHuffmanTree(plist treeHeap) *TreeNode {
    //使用優(yōu)先隊列構(gòu)造最小路徑權(quán)值哈夫曼樹
    heap.Init(&plist)
    for plist.Len() > 1 {
        t1 := heap.Pop(&plist).(*TreeNode)
        t2 := heap.Pop(&plist).(*TreeNode)
        root := &TreeNode{Times: t1.Times + t2.Times}
        if t1.Times > t2.Times {
            root.Right  , root.Left = t1 , t2
        }else {
            root.Right , root.Left = t2 , t1
        }
        heap.Push(&plist,root)
    }
    return plist[0]
}

func getFrequencyMap( file *os.File ) map[int]int {
    imap := make(map[int]int)
    // 讀入文件數(shù)據(jù)鄙才，readline 記入map中颂鸿，統(tǒng)計頻次
    // 注意：Create不區(qū)分文件名大小寫
    reader := bufio.NewReader(file)
    buffer := make([]byte,contentBuffer)
    readCount , _ := reader.Read(buffer)
    for i := 0 ; i < readCount ; i ++ {
        imap[int(buffer[i])] ++
    }
    return imap
}


func depress( inPath , depressPath string) {
    // originPath 原文件(或者可以傳入碼表)， inPath 讀入被壓縮的文件 , depressPath 還原后的輸出路徑
    encodeMap := make(map[int]string)
    decodeMap := make(map[string]int)
    //2.讀入壓縮文件
    compressFile , _ := os.Open(inPath)
    // br 讀取文件頭 ,返回偏移量
    br := bufio.NewReader(compressFile)
    left , offset  := readTable(*br , encodeMap)
    for idx , v  := range encodeMap {
        decodeMap[v] = idx
    }
    // 解碼string暫存區(qū)
    var buff bytes.Buffer
    // 編碼bytes暫存區(qū)
    codeBuff := make([]byte,contentBuffer)
    codeLen , _  := compressFile.ReadAt(codeBuff,int64(offset))
    //遍歷解碼 , 讀取比特
    for i := 0 ; i < codeLen  ; i ++ {
        //對每個byte單獨進(jìn)行位運算轉(zhuǎn)string
        perByte := codeBuff[i]
        for j := 0 ; j < 8 ; j ++ {
            //與運算
            buff.WriteString(strconv.Itoa( int( (perByte >> j) & 1 ) ) )
        }
    }
    // 對照碼表攒庵，解碼string , 對8取余目的是解決正好讀滿8個bit的情況發(fā)生
    contentStr  := buff.String()[:buff.Len() - (8 - left) % 8]
    bytes := make([]byte, 0 )
    //用切片讀contenStr即可
    for star , end := 0 , 1 ; end <= len(contentStr) ; {
        charValue , ok := decodeMap[contentStr[star:end]]
        if ok {
            bytes = append(bytes, byte(charValue))
            star = end
        }
        end ++
    }

    depressFile , _ := os.Create(depressPath)
    depressFile.Write(bytes)
    depressFile.Close()
}

func readTable( br bufio.Reader , encodeMap map[int]string) (int ,int )  {
    lineStr ,  _  , _ := br.ReadLine()
    lines , _ := strconv.Atoi(string(lineStr))
    for i := 0 ; i < lines - 1  ; i ++ {
        lineContent , _ , _:= br.ReadLine()
        kvArr := strings.Split(string(lineContent),":")
        k , v := kvArr[0] , kvArr[1]
        kNum , _:= strconv.Atoi(k)
        encodeMap[kNum] = v
    }
    leftStr , _ ,_:= br.ReadLine()
    left , _ := strconv.Atoi(string(leftStr))
    return left , br.Size() - br.Buffered()
}

func MD5Bytes(s []byte) string {
    ret := md5.Sum(s)
    return hex.EncodeToString(ret[:])
}

func MD5File(file string) (string, error) {
    data, err := ioutil.ReadFile(file)
    if err != nil {
        return "", err
    }
    return MD5Bytes(data), nil
}

四嘴纺、接下來按代碼的實現(xiàn)順序败晴，分模塊講解代碼的各個部分

統(tǒng)計詞頻，壓縮的基石
getFrequencyMap方法栽渴，使用map記錄文件中字符對應(yīng)ASCII碼出現(xiàn)的次數(shù)尖坤，因為golang中沒有char類型，這里用int替代

func getFrequencyMap( file *os.File ) map[int]int {
    imap := make(map[int]int)
    // 讀入文件數(shù)據(jù)闲擦，readline 記入map中慢味，統(tǒng)計頻次
    reader := bufio.NewReader(file)
    buffer := make([]byte,contentBuffer)
    readCount , _ := reader.Read(buffer)
    for i := 0 ; i < readCount ; i ++ {
        imap[int(buffer[i])] ++
    }
    return imap
}

構(gòu)造哈夫曼樹的節(jié)點，順便按照詞頻給這些節(jié)點進(jìn)行排序

    plist := make(treeHeap,0)
    // 遍歷map ,按頻率排序
    for k , v := range imap {
        plist = append(plist, &TreeNode{Val: k,Times: v})
    }
    sort.Sort(plist)

其中heap堆的實現(xiàn)如下墅冷，實現(xiàn)了heap接口的結(jié)構(gòu)體既是可排序數(shù)組纯路，也可以當(dāng)作優(yōu)先隊列來使用

type TreeNode struct {
    Val int
    Times int
    Left *TreeNode
    Right *TreeNode
}

type  treeHeap []*TreeNode

func (p treeHeap) Less( i , j int) bool {
    return p[i].Times <= p[j].Times
}

func (p treeHeap) Len() int {
    return len(p)
}

func (p treeHeap) Swap(i , j int) {
    p[i] , p[j] = p[j] , p[i]
}

func (p *treeHeap) Push(node interface{}) {
    *p = append(*p, node.(*TreeNode))
}

func (p *treeHeap) Pop()  interface{} {
    n := len(*p)
    t := (*p)[n-1]
    *p = (*p)[:n-1]
    return t
}

使用優(yōu)先隊列構(gòu)造哈夫曼樹
使用遞歸也可以生成哈夫曼樹，但是不能保證樹的結(jié)構(gòu)是最優(yōu)的寞忿，我們需要保證構(gòu)建的哈夫曼樹具有最小權(quán)值路徑和感昼，這樣才能使得壓縮的效率最大化，從代碼可以清晰的看到罐脊，實現(xiàn)了堆接口后的哈夫曼樹構(gòu)造非常簡單定嗓。因為heap是優(yōu)先隊列的緣故，每次插入都會按Times（頻次）升序排序保證下次合成的兩兩節(jié)點權(quán)值之和是所有節(jié)點中最小的萍桌，plist[0]即為構(gòu)造完成哈夫曼樹的根節(jié)點.

func initHuffmanTree(plist treeHeap) *TreeNode {
    // 使用優(yōu)先隊列構(gòu)造最小路徑權(quán)值哈夫曼樹
    heap.Init(&plist)
    for plist.Len() > 1 {
        t1 := heap.Pop(&plist).(*TreeNode)
        t2 := heap.Pop(&plist).(*TreeNode)
        root := &TreeNode{Times: t1.Times + t2.Times}
        if t1.Times > t2.Times {
            root.Right  , root.Left = t1 , t2
        }else {
            root.Right , root.Left = t2 , t1
        }
        heap.Push(&plist,root)
    }
    return plist[0]
}

使用回溯法得到經(jīng)過哈夫曼樹編碼以后的table
encodeMap中key為字符的ASCII碼值宵溅，用int表示，value為哈夫曼樹從根節(jié)點到葉子節(jié)點的左右路徑編碼值上炎，用string表示恃逻，其中tmp記錄遞歸過程中所走過的路徑，往左走用'0'表示藕施，往右走用'1'表示寇损，最后再轉(zhuǎn)換成string就得到了對應(yīng)ASCII碼的編碼值。

func createEncodingTable(node *TreeNode , encodeMap map[int]string )  {
    /*  思路：回溯遍歷二叉樹裳食，用byte記錄0 1??矛市，遇到葉子節(jié)點就轉(zhuǎn)換成string存入碼表
        遍歷順序：根左右
    */
    tmp := make([]byte,0)
    var depth func (treeNode *TreeNode)
    depth = func (root *TreeNode) {
        //如果已經(jīng)遍歷到空，返回
        if root == nil {
            return
        }
        //如果遍歷到的是葉子節(jié)點 , byte轉(zhuǎn)換成string诲祸，入表
        if root.Left == nil && root.Right == nil {
            encodeMap[root.Val] = string(tmp)
        }
        // 如果是普通節(jié)點浊吏，左右遞歸回溯即可 #規(guī)則： 左0右1
        tmp = append(tmp ,'0' )
        depth(root.Left)
        tmp[len(tmp)-1] = '1'
        depth(root.Right)
        tmp = tmp[:len(tmp)-1]
    }
    depth(node)
}

我們來到了最關(guān)鍵的一步，這里將使用編碼表將字符對應(yīng)的哈夫曼編碼轉(zhuǎn)換成bit位存入文件中救氯，轉(zhuǎn)換過程使用了位運算,代碼模塊較長找田，先將代碼貼出，再分塊講解

func encoding(inPath string, outPath string , encodeMap map[int]string) {
    /*1. 一次性讀入文件內(nèi)容*/
    inFile ,err  := os.Open(inPath)
    defer inFile.Close()
    if err != nil {
        return
    }
    reader := bufio.NewReader(inFile)
    fileContent := make([]byte,contentBuffer)
    count , _ := reader.Read(fileContent)
    var buff bytes.Buffer
    // string編碼
    for i := 0 ; i < count ; i ++  {
        v := fileContent[i]
        if code , ok := encodeMap[int(v)] ; len(code)!= 0  && ok  {
            buff.WriteString(code)
        }
    }
    res := make([]byte,0)
    var buf byte = 0
    // bit編碼
    // 記錄bit剩余位着憨，很簡單只要對buff.bytes取長度對8取余即可
    for idx , bit := range buff.Bytes() {
        //每八個位使用一個byte讀取墩衙，結(jié)果存入res數(shù)組即可
        pos := idx % 8
        if pos == 0 && idx > 0 {
            res = append(res, buf)
            buf = 0
        }
        if bit == '1' {
            buf  |=   1 <<  pos
        }
    }
    // 這個left是剩余待處理的位數(shù)
    left := buff.Len() % 8
    res = append(res, buf)
    // 先將碼表和left數(shù)寫入文件，解碼時在開頭讀取
    writeTable(outPath,encodeMap,left)
    outFile , err := os.OpenFile(outPath,os.O_APPEND|os.O_CREATE|os.O_WRONLY, 0644)
    if err != nil{
        return
    }
    wcount , err := outFile.Write(res)
    if err != nil {
        fmt.Println(wcount)
        return
    }
}

首先是讀入文件，將每一個字符都轉(zhuǎn)換成被哈夫曼編碼過的string漆改，比如a轉(zhuǎn)換成"01"

    /*1. 一次性讀入文件內(nèi)容*/
    inFile ,err  := os.Open(inPath)
    defer inFile.Close()
    if err != nil {
        return
    }
    reader := bufio.NewReader(inFile)
    fileContent := make([]byte,contentBuffer)
    count , _ := reader.Read(fileContent)
    var buff bytes.Buffer
    //string編碼
    for i := 0 ; i < count ; i ++  {
        v := fileContent[i]
        if code , ok := encodeMap[int(v)] ; len(code)!= 0  && ok  {
            buff.WriteString(code)
        }
    }

其次植袍，將文件中的每一個字符根據(jù)哈夫曼編碼Map對應(yīng)的string轉(zhuǎn)換成一個個bit存入byte數(shù)組中

    res := make([]byte,0)
    var buf byte = 0
    // bit編碼
    // 記錄bit剩余位，很簡單只要對buff.bytes取長度對8取余即可
    for idx , bit := range buff.Bytes() {
        //每八個位使用一個byte讀取籽懦，結(jié)果存入res數(shù)組即可
        pos := idx % 8
        if pos == 0 && idx > 0 {
            res = append(res, buf)
            buf = 0
        }
        if bit == '1' {
            buf  |=   1 <<  pos
        }
    }
    // 這個left是剩余待處理的位數(shù)
    left := buff.Len() % 8
    res = append(res, buf)

這里詳細(xì)講解存入過程 :
每個byte的初始狀態(tài)都是00000000（八位）于个，假設(shè)要存入的字符串為"0111011110101"（13位）,那么我們需要兩個byte來記錄字符串的信息，從前往后遍歷字符串暮顺，用pos記錄當(dāng)前遍歷到的字符串下標(biāo)厅篓，讀到'1'時，對byte的對應(yīng)比特位進(jìn)行或操作,這樣進(jìn)行八次讀取捶码，第一個byte就變成了011101111的倒序排列byte1 : 11101110羽氮，因為后續(xù)我們讀入的時候也是倒序讀入，所以這樣做是可行的惫恼，還剩最后五位"10101"用一個新的byte來記錄档押，同理byte2 : 00010101
byte2的前三位是空余位，讀入的時候我們并不考慮祈纯，所以用left來記錄最后一個byte要讀入的bit位數(shù)即可令宿。left = 13 % 8 = 5 腕窥。我們將所有經(jīng)過位運算的byte存入byte數(shù)組粒没，先保留在內(nèi)存中，等待完成文件頭的處理簇爆，再把編碼集寫入文件癞松，就完成了最重要的一步，哈夫曼編碼壓縮入蛆。

將table寫入文件頭响蓉，將編碼結(jié)果寫入文件
writeTable函數(shù)，我們記錄map的長度加上left位的長度哨毁，這些都是重要的信息枫甲，每個鍵值對用換行隔開，key和value用":"做分割挑庶，以備在讀入的時候解析言秸。

func writeTable(path string, codeMap map[int]string , left int) {
    file ,err := os.Create(path)
    if err != nil {
        return
    }
    // 第一行软能，寫入文件頭的長度
    var buff bytes.Buffer
    buff.WriteString(strconv.Itoa(len(codeMap)+1) + "\n")
    for k , v := range codeMap {
        buff.WriteString(strconv.Itoa(k) + ":" + v + "\n")
    }
    buff.WriteString(strconv.Itoa(left) + "\n")
    file.WriteString(buff.String())
    file.Close()
}

接下來迎捺，我們用追加寫入模式打開文件，寫入編碼結(jié)果即可

 outFile , err := os.OpenFile(outPath,os.O_APPEND|os.O_CREATE|os.O_WRONLY, 0644)
    if err != nil{
        return
    }
    wcount , err := outFile.Write(res)
    if err != nil {
        fmt.Println(wcount)
        return
    }

讀取文件查排，進(jìn)行解壓縮
這一步就很簡單了凳枝。有了文件頭中的編碼表table，以及我們之前做過的位運算基礎(chǔ)，倒序操作一遍即可

func depress( inPath , depressPath string) {
    // originPath 原文件(或者可以傳入碼表)岖瑰， inPath 讀入被壓縮的文件 , depressPath 還原后的輸出路徑
    encodeMap := make(map[int]string)
    decodeMap := make(map[string]int)
    //2.讀入壓縮文件
    compressFile , _ := os.Open(inPath)
    // br 讀取文件頭 ,返回偏移量
    br := bufio.NewReader(compressFile)
    left , offset  := readTable(*br , encodeMap)
    for idx , v  := range encodeMap {
        decodeMap[v] = idx
    }
    // 解碼string暫存區(qū)
    var buff bytes.Buffer
    // 編碼bytes暫存區(qū)
    codeBuff := make([]byte,contentBuffer)
    codeLen , _  := compressFile.ReadAt(codeBuff,int64(offset))
    //遍歷解碼 , 讀取比特
    for i := 0 ; i < codeLen  ; i ++ {
        //對每個byte單獨進(jìn)行位運算轉(zhuǎn)string
        perByte := codeBuff[i]
        for j := 0 ; j < 8 ; j ++ {
            //與運算
            buff.WriteString(strconv.Itoa( int( (perByte >> j) & 1 ) ) )
        }
    }
    // 對照碼表叛买，解碼string , 對8取余目的是解決正好讀滿8個bit的情況發(fā)生
    contentStr  := buff.String()[:buff.Len() - (8 - left) % 8]
    bytes := make([]byte, 0 )
    //用切片讀contenStr即可
    for star , end := 0 , 1 ; end <= len(contentStr) ; {
        charValue , ok := decodeMap[contentStr[star:end]]
        if ok {
            bytes = append(bytes, byte(charValue))
            star = end
        }
        end ++
    }

    depressFile , _ := os.Create(depressPath)
    depressFile.Write(bytes)
    depressFile.Close()
}

其中的重點就是位運算操作，將bit信息還原成string蹋订，再到編碼table中找到對應(yīng)的ASCII碼值

//遍歷解碼 , 讀取比特
    for i := 0 ; i < codeLen  ; i ++ {
        //對每個byte單獨進(jìn)行位運算轉(zhuǎn)string
        perByte := codeBuff[i]
        for j := 0 ; j < 8 ; j ++ {
            //與運算
            buff.WriteString(strconv.Itoa( int( (perByte >> j) & 1 ) ) )
        }
    }
// 對照碼表率挣，解碼string , 對8取余目的是解決正好讀滿8個bit的情況發(fā)生
    contentStr  := buff.String()[:buff.Len() - (8 - left) % 8]

//用切片讀contenStr即可
    for star , end := 0 , 1 ; end <= len(contentStr) ; {
        charValue , ok := decodeMap[contentStr[star:end]]
        if ok {
            bytes = append(bytes, byte(charValue))
            star = end
        }
        end ++
    }

詳情參見注釋，在此不做贅述

最后一個細(xì)節(jié)露戒，在讀取文件時椒功，如何分別讀入文件頭和壓縮內(nèi)容
我這里采用的是使用io.reader，按行號讀取文件頭后再計算已經(jīng)讀入的偏移量智什，最后使用file.readAt方法來接著讀入文件內(nèi)容
readTable 調(diào)用點：返回offset偏移量在最后ReadAt方法中使用

left , offset  := readTable(*br , encodeMap)
    for idx , v  := range encodeMap {
        decodeMap[v] = idx
    }
    // 解碼string暫存區(qū)
    var buff bytes.Buffer
    // 編碼bytes暫存區(qū)
    codeBuff := make([]byte,contentBuffer)
    codeLen , _  := compressFile.ReadAt(codeBuff,int64(offset))

readTable方法:

func readTable( br bufio.Reader , encodeMap map[int]string) (int ,int )  {
    lineStr ,  _  , _ := br.ReadLine()
    lines , _ := strconv.Atoi(string(lineStr))
    for i := 0 ; i < lines - 1  ; i ++ {
        lineContent , _ , _:= br.ReadLine()
        kvArr := strings.Split(string(lineContent),":")
        k , v := kvArr[0] , kvArr[1]
        kNum , _:= strconv.Atoi(k)
        encodeMap[kNum] = v
    }
    leftStr , _ ,_:= br.ReadLine()
    left , _ := strconv.Atoi(string(leftStr))
    return left , br.Size() - br.Buffered()
}

到此為止动漾，實現(xiàn)哈夫曼編碼壓縮文件的所有方法和細(xì)節(jié)已經(jīng)展示完畢，解決了我開頭所述的三個痛點荠锭，即哈夫曼編碼的代碼實現(xiàn)旱眯，將編碼轉(zhuǎn)換成bit壓縮至文件的實現(xiàn)，文件頭讀取的過程证九，如有不足之處煩請各位指教删豺。

以上內(nèi)容皆為本人原創(chuàng)，轉(zhuǎn)載請注明出處