「ハフマン符号」の版間の差分
削除された内容 追加された内容
編集の要約なし |
|||
47行目:
が得られ、個数の多い文字ほど短い符号が割り当てられていることがわかる。
==実装==
[[Groovy]]で実装を説明する。まず、符号情報とハフマン木のクラスを作る。
<source lang="groovy">
class CodeInfo { int code, codeSize }
class TreeNode implements Comparable<TreeNode> {
byte value; int occurrence; List<TreeNode> children;
int compareTo(TreeNode that) { this.occurrence - that.occurrence }
}
</source>
すると、バイト値→符号情報のテーブルは以下のようにして作れる。
<source lang="groovy">
CodeInfo[] createValue2Code(byte[] data) {
// 各バイト値の発生回数を数える
TreeNode[] nodes = new TreeNode[256]
for (int i in 0..<256) { nodes[i] = new TreeNode(value: i) }
for (byte v in data) { nodes[v].occurrence++ }
// ハフマン木を作成
PriorityQueue<TreeNode> queue = new PriorityQueue<TreeNode>(nodes as List)
while (queue.size() > 1) {
TreeNode n1 = queue.poll(), n2 = queue.poll()
queue << new TreeNode(occurrence: n1.occurrence + n2.occurrence, children: [n1, n2])
}
TreeNode root = queue.poll()
// 深さ優先探索でバイト値→符号情報を作成
CodeInfo[] value2code = new CodeInfo[256]
dfs(value2code, root, 0, 0)
return value2code
}
void dfs(CodeInfo[] value2code, TreeNode node, int code, int codeSize) {
if (node.children == null) {
value2code[node.value] = new CodeInfo(code: code, codeSize: codeSize)
} else {
dfs(value2code, node.children[0], code << 1, codeSize + 1)
dfs(value2code, node.children[1], (code << 1) + 1, codeSize + 1)
}
}
</source>
圧縮のために以下のようなビットストリームのクラスを作る。
<source lang="groovy">
class BitStream {
BitSet bs = new BitSet(); int len = 0, pos = 0;
void write(int v, int bits) {
for (int i in 0..<bits) { bs[len++] = ((v >>> i) & 1) != 0 }
}
int read(int bits) {
int v = 0; for (int i in 0..<bits) { if (bs[pos++]) { v |= 1 << i } }
return v
}
String toString() { "length = $len, {" + (0..<len).findAll({ bs[it] }).join(", ") + "}" }
}
</source>
すると、バイト値→符号情報のテーブルを使い以下のようにして圧縮できる。
<source lang="groovy">
void compress(BitStream bs, byte[] data, CodeInfo[] value2code) {
for (byte v in data) {
CodeInfo codeInfo = value2code[v]
bs.write(codeInfo.code, codeInfo.codeSize)
}
}
</source>
== 関連項目 ==
| |||