盒子
盒子
文章目录
  1. Nim 编程早茶
    1. huffman 编码
    2. Nim 语言实现 huffman 编码

Nim 编程实现霍夫曼编码

Nim 编程早茶

这一节 介绍如何使用 Nim 语言实现 huffman 编码,下一节,我们介绍如何使用霍夫曼编码压缩文件。

huffman 编码

huffman 编码是一种高效的前缀码,常用于文件压缩。我们表示一个英文字符,使用定长码,需要 8 位的存储空间。而 huffman 编码是一种变长码,对于不同的字符,表示的二进制位数量不同。出现频率高的字符,使用位数少的二进制表示,反之,使用位数多的二进制表示。比如说,字符 a 在文件中出现频率最多,我们设为 0,而 c 出现的频率最低,我们设置为 1011。注意前缀码的意思是,每一个字符的二进制表示都不能是其他字符二进制表示的前缀。比如 01, 011 这种编码就不是前缀码。

Nim 语言实现 huffman 编码

首先,我们需要统计字符出现的频数,我们可以借助标准库中的CountTable 来统计频数。

我们还需要借助,之前实现的Nim 编程优先队列

首先实现一个简单的二叉树,作为 huffman 树的底层数据结构。

1
2
3
4
5
6
7
type
TreeObj* = object
left*: ref TreeObj
right*: ref TreeObj
value*: char
priority*: float
Tree* = ref TreeObj

我们需要建立字符与二进制编码的对应表。只需递归地 buildTable。如果左节点存在,该字符对应字符串加 “0”,如果右节点存在,该字符对应字符串加 “1”。如果没有左右结点,那么就保存该字符对应字符串到哈希表中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
proc newTree*(left: Tree=nil, right: Tree=nil, value: char='\0', priority: float=0.0): Tree =
Tree(left: left, right: right, value: value, priority: priority)

proc isLeaf*(t: Tree): bool =
return t.left.isNil and t.right.isNil

proc buildTable*(t: Tree, st:var Table[char, string], s:string) =
if t.isLeaf:
st[t.value] = s
return
buildTable(t.left, st, s & "0")
buildTable(t.right, st, s & "1")

proc buildTable*(t: Tree): Table[char, string] =
var
st: Table[char, string]
s: string
buildTable(t, st, s)
return st

我们统计出每个字符出现的频数,然后将字符插入到优先队列中。完成初始化之后,每次取出优先队列中,最小的两个字符,分别作为 huffman 树的左右结点;并把两个字符出现频数相加,作为该结点的频数值。当优先队列中只有一个结点时,说明我们 huffman 树已经完成构建。

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
import priorityqueue, sequtils, tables, streams


proc huffman*(text: string, path="output.txt") =
if text.len == 0:
return
var
s = newPriorityQueue[Tree](maxQueue=false)
counter = toCountTable(text)
# 初始化优先队列
for k, v in counter:
s.push(Tree(value: k, priority: float(v)), float(v))
# 构建 huffman 树
while s.len > 1:
let
t1 = s.pop
t2 = s.pop
s.push(newTree(t1, t2, '\0', t1.priority + t2.priority), t1.priority + t2.priority)

let tree = s.pop
# 递归地构建查询表
let dict = buildTable(tree)
var output: string
for c in text:
output.add(dict[c])
echo dict
echo output
# var strm = newFileStream(path, fmWrite)
# defer: strm.close()
# writeCode(strm, text, tree, dict)

最后我们来测试程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
when isMainModule:
import random, os
randomize(1024)

var
n = 1000
res: string = newString(n)
# letters = toSeq('a' .. 'z')
#for i in 0 ..< n:
# res[i] = sample(letters)
res = "ABRACADABRA!"
# var input = newFileStream("input.txt", fmRead)
# let text = input.readAll
huffman(res)

输出:

1
2
{'R': "101", 'A': "0", 'B': "110", 'C': "1110", '!': "100", 'D': "1111"}
0110101011100111101101010100