ハフマン符号は 1952 年にハフマン (D. Huffman) が考案した、平均符号長を最小にすることができる符号化法です。ハフマン符号については拙作のページ Algorithms with Python シャノン・ファノ符号とハフマン符号 をお読みください。
ハフマン木はハフマン符号を構成するときに作成する「符号木」のことです。符号木については整数の符号化 をお読みください。今回はハフマン木を操作するプログラムを作ります。作成する関数を示します。
拙作のページ 整数の符号化 で作成したライブラリ bitio.rs を使っています。あらかじめコンパイルしておいてください。
//
// huffman.rs : ハフマン木の操作
//
// Copyright (C) 2018-2022 Makoto Hiroi
//
use std::cmp::Ordering;
use std::collections::{BinaryHeap, HashMap};
extern crate bitio;
use bitio::*;
// ハフマン木
#[derive(Debug)]
pub enum Tree {
Leaf(u64, u64),
Node(u64, Box<Tree>, Box<Tree>)
}
impl Tree {
fn get_cnt(&self) -> u64 {
match self {
&Leaf(n, _) => n,
&Node(n, _, _) => n
}
}
}
use Tree::*;
// BinaryHeap を最小ヒープにするため Ord を定義する
impl Ord for Tree {
fn cmp(&self, other: &Tree) -> Ordering {
self.get_cnt().cmp(&other.get_cnt()).reverse()
}
}
impl PartialOrd for Tree {
fn partial_cmp(&self, other: &Tree) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl PartialEq for Tree {
fn eq(&self, other: &Tree) -> bool {
self.get_cnt() == other.get_cnt()
}
}
impl Eq for Tree { }
// ハフマン木の生成
pub fn make_tree(freq_table: &Vec<u64>) -> Tree {
let mut que = BinaryHeap::new();
for x in 0 .. freq_table.len() {
let cnt = freq_table[x];
if cnt > 0 { que.push(Leaf(cnt, x as u64)); }
}
if que.len() == 1 {
if let Some(&Leaf(_, x)) = que.peek() {
let c = if x == 0 { 1 } else { 0 };
que.push(Leaf(0, c));
}
}
loop {
let n = que.pop().unwrap();
if que.is_empty() { return n; }
let m = que.pop().unwrap();
let node = Node(n.get_cnt() + m.get_cnt(), Box::new(n), Box::new(m));
que.push(node);
}
}
// 符号語の生成
fn make_code_sub(node: &Tree, n: u64, code: u64, table: &mut HashMap<u64, (u64, u64)>) {
match node {
&Leaf(_, c) => {
table.insert(c, (n, code));
}
&Node(_, ref left, ref right) => {
make_code_sub(left, n + 1, code << 1, table);
make_code_sub(right, n + 1, (code << 1) | 1, table);
}
}
}
pub fn make_code(node: &Tree) -> HashMap<u64, (u64, u64)> {
let mut table = HashMap::new();
make_code_sub(node, 0, 0, &mut table);
table
}
// ハフマン木の出力
pub fn write_tree(node: &Tree, bits: u64, writer: &mut BitWriter) -> std::io::Result<()> {
match node {
&Leaf(_, c) => {
writer.putbit(1)?;
writer.putbits(bits, c)?;
},
&Node(_, ref left, ref right) => {
writer.putbit(0)?;
write_tree(left, bits, writer)?;
write_tree(right, bits, writer)?;
}
}
Ok(())
}
// ハフマン木の入力
pub fn read_tree(bits: u64, reader: &mut BitReader) -> std::io::Result<Tree> {
if reader.getbit()? == 1 {
// 葉
let code = reader.getbits(bits)?;
Ok(Leaf(0, code))
} else {
let left = read_tree(bits, reader)?;
let right = read_tree(bits, reader)?;
Ok(Node(0, Box::new(left), Box::new(right)))
}
}
// 復号
pub fn huffman_decode(tree: &Tree, reader: &mut BitReader) -> std::io::Result<u64> {
let mut node = tree;
loop {
match node {
&Leaf(_, c) => return Ok(c),
&Node(_, ref left, ref right) => {
node = if reader.getbit()? == 0 { left } else { right };
}
}
}
}
// 符号化
pub fn huffman_encode(code_table: &HashMap<u64, (u64, u64)>, code: u64, writer: &mut BitWriter) -> std::io::Result<()> {
let &(n, c) = code_table.get(&code).unwrap();
writer.putbits(n, c)?;
Ok(())
}
リスト : 簡単なテスト (huff_test.rs)
use std::io::prelude::*;
use std::io::{self, BufReader};
extern crate huffman;
use huffman::*;
use Tree::*;
extern crate bitio;
use bitio::*;
// ハフマン木の表示
fn print_space(mut n: usize) {
while n > 0 {
print!(" ");
n -= 1;
}
}
pub fn print_tree(node: &Tree, code: &mut Vec<i32>) {
match node {
&Leaf(_, c) => {
print_space(code.len());
println!("* {}, {:?}", c, code);
},
&Node(_, ref left, ref right) => {
code.push(0);
print_tree(left, code);
code.pop();
print_space(code.len());
println!("*");
code.push(1);
print_tree(right, code);
code.pop();
}
}
}
fn main() {
let reader = BufReader::new(io::stdin());
// 出現頻度票の生成
let mut freq_table = vec![0u64; 256];
for c in reader.bytes() {
freq_table[c.unwrap() as usize] += 1;
}
// ハフマン木の生成
let tree = make_tree(&freq_table);
print_tree(&tree, &mut vec![]);
println!("{:?}", make_code(&tree));
// ハフマン木の出力
{
let mut writer = BitWriter::create("huff_test.en").unwrap();
write_tree(&tree, 8, &mut writer).unwrap();
}
// ハフマン木の入力
let mut reader = BitReader::open("huff_test.en").unwrap();
let tree1 = read_tree(8, &mut reader).unwrap();
print_tree(&tree1, &mut vec![]);
println!("{:?}", make_code(&tree1));
}
コンパイルは、最初に rustc -O -L . --crate-type=lib huffman.rs でライブラリを作成し、そのあとで rustc -L . huff_test.rs とします。
test.txt: abccddeeeeffffgggggggghhhhhhhh
$ ./huff_test < test.txt
* 100, [0, 0, 0]
*
* 102, [0, 0, 1]
*
* 103, [0, 1]
*
* 104, [1, 0]
*
* 99, [1, 1, 0, 0]
*
* 97, [1, 1, 0, 1, 0]
*
* 98, [1, 1, 0, 1, 1]
*
* 101, [1, 1, 1]
{98: (5, 27), 103: (2, 1), 99: (4, 12), 97: (5, 26), 101: (3, 7), 102: (3, 1), 104: (2, 2), 100: (3, 0)}
* 100, [0, 0, 0]
*
* 102, [0, 0, 1]
*
* 103, [0, 1]
*
* 104, [1, 0]
*
* 99, [1, 1, 0, 0]
*
* 97, [1, 1, 0, 1, 0]
*
* 98, [1, 1, 0, 1, 1]
*
* 101, [1, 1, 1]
{100: (3, 0), 103: (2, 1), 104: (2, 2), 97: (5, 26), 99: (4, 12), 98: (5, 27), 102: (3, 1), 101: (3, 7)}
ハフマン木の形は シャノン・ファノ符号とハフマン符号 の例題とは異なりますが、これでも同じ平均符号長 (80 / 30) になります。
//
// huff_encode.rs : ハフマン符号化
//
// Copyright (C) 2018-2022 Makoto Hiroi
//
extern crate bitio;
extern crate huffman;
use std::fs::File;
use std::io::prelude::*;
use std::io::BufReader;
use bitio::BitWriter;
use huffman::*;
fn encode_file(src: &String, dst: &String) -> std::io::Result<()> {
let mut wr = BitWriter::create(dst)?;
// 出現頻度表の作成
let mut freq_table = vec![0u64; 256];
let mut size = 0;
{
let rd = BufReader::new(File::open(src)?);
for r in rd.bytes() {
freq_table[r? as usize] += 1;
size += 1;
}
}
// ファイルサイズ
wr.putbits(64, size)?;
if size == 0 { return Ok(()); }
// ハフマン木
let tree = make_tree(&freq_table);
write_tree(&tree, 8, &mut wr)?;
// 符号語の生成
let code = make_code(&tree);
// 符号化
let rd = BufReader::new(File::open(src)?);
for r in rd.bytes() {
huffman_encode(&code, r? as u64, &mut wr)?;
}
Ok(())
}
fn main() {
let args: Vec<_> = std::env::args().collect();
if args.len() < 3 {
println!("usage: huff_encode input_file output_file");
} else {
match encode_file(&args[1], &args[2]) {
Ok(_) => (),
Err(err) => println!("{}", err.to_string())
}
}
}
//
// huff_decode.rs :: ハフマン符号 (復号)
//
// Copyright (C) 2018-2022 Makoto Hiroi
//
extern crate bitio;
extern crate huffman;
use std::fs::File;
use std::io::prelude::*;
use std::io::BufWriter;
use bitio::BitReader;
use huffman::*;
fn decode_file(src: &String, dst: &String) -> std::io::Result<()> {
let mut rd = BitReader::open(src)?;
let mut wr = BufWriter::new(File::create(dst)?);
let mut size = rd.getbits(64)?; // ファイルサイズの取得
if size == 0 { return Ok(()); }
let tree = read_tree(8, &mut rd)?; // ハフマン木の取得
while size > 0 {
let c = huffman_decode(&tree, &mut rd)?;
wr.write(&[c as u8])?;
size -= 1;
}
Ok(())
}
fn main() {
let args: Vec<_> = std::env::args().collect();
if args.len() < 3 {
println!("usage: huff_decode input_file output_file");
} else {
match decode_file(&args[1], &args[2]) {
Ok(_) => (),
Err(err) => println!("{}", err.to_string())
}
}
}
それでは簡単な実行例として、Canterbury Corpus で配布されているテストデータ The Large Corpus を圧縮してみましょう。
| ファイル名 | サイズ | エントロピー | 下限値 | Huffman |
|---|---|---|---|---|
| bible.txt | 4,047,392 | 4.342751 | 2,197,103 | 2,218,536 |
| e.coli | 4,638,690 | 1.999821 | 1,159,569 | 1,159,686 |
| world192.txt | 2,473,400 | 4.998313 | 1,545,354 | 1,558,721 |
| 合計 | 11,159,482 | 4,902,026 | 4,936,943 |
どのファイルも下限値に近い圧縮率になりました。ただし、同じ記号が極端に多いファイルの場合、ハフマン符号では下限値の近くまで圧縮できないことがあります。
たとえば、The Canterbury Corpus の ptt5 は記号 0 がとても多く出現するファイルです。ptt5 のエントロピーを計算すると 1.210176 になるので、下限値は 77,636 byte になりますが、ハフマン符号では 106,758 byte までしか圧縮することができません。記号 0 に 1 ビットの符号語を割り当てても、限界に近い圧縮率を達成することはできないのです。「算術符号」または「レンジコーダ (Range Coder)」を用いると、記号に 1 ビット未満の符号語を割り当てることができるので、このような場合でも限界に近い圧縮率を達成することができます。
ハフマン符号は、出現頻度の高い記号には短い符号語を、低い記号には長い符号語を割り当てることでデータ圧縮を実現しました。これに対して、LZ 符号は「辞書に基づく符号化方式 (辞書法, dictionary-based coding) 」といって、ハフマン符号とはまったく異なるアプローチでデータ圧縮を実現しています。辞書法は入力された記号列を辞書に登録し、その辞書を使って符号化を行います。辞書法は多くの圧縮ツールで用いられているオーソドックスな方法です。
今回は辞書法の一つで「スライド辞書法」と呼ばれている LZ77 符号 (LZSS 符号) のプログラムを Rust で作ってみましょう。アルゴリズムの詳しい説明は拙作のページ Algorithms with Python LZ77 符号 (LZSS 符号) をお読みくださいませ。
//
// lzss_encode.rs : LZSS 符号 (符号化)
//
// Copyright (C) 2018-2022 Makoto Hiroi
//
extern crate bitio;
use std::fs::{self, File};
use std::io::prelude::*;
use std::io::BufReader;
use std::collections::HashMap;
use bitio::BitWriter;
// 定数
const MIN_LEN: usize = 3;
const MAX_LEN: usize = 18;
const LEN_BITS: u64 = 4;
const POS_BITS: u64 = 13;
const SW_SIZE: usize = 1 << POS_BITS;
const SW_LIMIT: usize = SW_SIZE * 2;
const NIL: usize = SW_LIMIT + MAX_LEN;
struct SWindow {
reader: BufReader<File>,
buffer: [u8; SW_LIMIT + MAX_LEN],
htable: HashMap<u32, usize>,
next: [usize; SW_SIZE],
data_size: usize,
match_len: usize,
match_pos: usize
}
impl SWindow {
fn new(filename: &str) -> std::io::Result<SWindow> {
let fs = File::open(filename)?;
let mut sw = SWindow {
reader: BufReader::new(fs),
buffer: [0u8; SW_LIMIT + MAX_LEN],
htable: HashMap::new(),
next: [NIL; SW_SIZE],
data_size: 0,
match_len: 0,
match_pos: 0,
};
// ファイルの読み込み
sw.data_size = sw.reader.read(&mut sw.buffer)?;
Ok(sw)
}
// ハッシュ値を求める
fn hash_value(&self, rp: usize) -> u32 {
let mut value = 0u32;
for i in 0 .. MIN_LEN {
value = (value << 8) + self.buffer[rp + i] as u32;
}
value
}
// データの挿入
fn insert(&mut self, rp: usize) {
let value = self.hash_value(rp);
match self.htable.get(&value) {
Some(x) if *x != NIL => self.next[rp & (SW_SIZE - 1)] = *x,
_ => self.next[rp & (SW_SIZE - 1)] = NIL
}
self.htable.insert(value, rp);
}
// 最長一致列の探索
fn search(&mut self, rp: usize) {
let value = self.hash_value(rp);
let limit = if rp < SW_SIZE { 0 } else { rp - SW_SIZE };
self.match_len = 0;
self.match_pos = 0;
if let Some(m) = self.htable.get(&value) {
let mut n = *m;
while n != NIL && n >= limit {
if self.buffer[rp + self.match_len] == self.buffer[n + self.match_len] {
let mut x = 0;
while x < MAX_LEN {
if self.buffer[rp + x] != self.buffer[n + x] {
break;
}
x += 1;
}
if self.match_len < x {
self.match_len = x;
self.match_pos = n;
if x == MAX_LEN { break; }
}
}
n = self.next[n & (SW_SIZE - 1)];
}
// データの終端をチェック
if self.match_len != 0 && self.match_len >= self.data_size - rp {
self.match_len = self.data_size - rp;
}
}
}
// 更新
fn update(&mut self, rp: usize) -> std::io::Result<usize> {
if self.data_size < SW_LIMIT + MAX_LEN {
return Ok(rp);
}
// データの移動
for i in 0 .. SW_SIZE + MAX_LEN {
self.buffer[i] = self.buffer[i + SW_SIZE];
}
self.data_size = SW_SIZE + MAX_LEN + self.reader.read(&mut self.buffer[SW_SIZE + MAX_LEN ..])?;
// ハッシュ表の更新
let mut work = vec![];
for (k, v) in self.htable.iter_mut() {
if *v < SW_SIZE {
work.push(*k);
} else if *v != NIL {
*v -= SW_SIZE;
}
}
for k in work {
self.htable.remove(&k);
}
for i in 0 .. SW_SIZE {
if self.next[i] != NIL && self.next[i] > SW_SIZE {
self.next[i] -= SW_SIZE;
} else {
self.next[i] = NIL;
}
}
Ok(rp - SW_SIZE)
}
}
fn encode_file(src: &String, dst: &String) -> std::io::Result<()> {
let mut wr = BitWriter::create(dst)?;
// ファイルサイズ
let metadata = fs::metadata(src)?;
let size = metadata.len();
if size == 0 { return Ok(()); }
wr.putbits(64, size)?;
let mut sw = SWindow::new(src)?;
let mut rp = 0;
while rp < sw.data_size {
let num;
sw.search(rp);
if sw.match_len < MIN_LEN {
num = 1;
wr.putbit(0)?;
wr.putbits(8, sw.buffer[rp] as u64)?;
} else {
num = sw.match_len;
wr.putbit(1)?;
wr.putbits(LEN_BITS, (num - MIN_LEN) as u64)?;
wr.putbits(POS_BITS, (rp - sw.match_pos - 1) as u64)?;
}
for _ in 0 .. num {
sw.insert(rp);
rp += 1;
if rp >= SW_LIMIT {
rp = sw.update(rp).unwrap();
}
}
}
Ok(())
}
fn main() {
let args: Vec<_> = std::env::args().collect();
if args.len() < 3 {
println!("usage: lzss_encode input_file output_file");
} else {
match encode_file(&args[1], &args[2]) {
Ok(_) => (),
Err(err) => println!("{}", err.to_string())
}
}
}
ライブラリ bitio.rs を使っているので、あらかじめコンパイルしておいてください。あとは、rustc -O -L . lzss_encode.rs でコンパイルすることができます。
//
// lzss_decode.rs :: LZSS 符号 (復号)
//
// Copyright (C) 2018-2022 Makoto Hiroi
//
extern crate bitio;
use std::fs::File;
use std::io::prelude::*;
use std::io::BufWriter;
use bitio::BitReader;
// 以下の定数は lzss_enocde.rs と同じにすること
const MIN_LEN: usize = 3;
const LEN_BITS: u64 = 4;
const POS_BITS: u64 = 13;
const SW_SIZE: usize = 1 << POS_BITS;
fn decode_file(src: &String, dst: &String) -> std::io::Result<()> {
let mut rd = BitReader::open(src)?;
let mut wr = BufWriter::new(File::create(dst)?);
let mut size = rd.getbits(64)?; // ファイルサイズの取得
if size == 0 { return Ok(()); }
let mut buffer = [0u8; SW_SIZE];
let mut rp: usize = 0;
while size > 0 {
let num;
if rd.getbit()? == 1 {
num = rd.getbits(LEN_BITS)? + MIN_LEN as u64;
let mut pos = (rd.getbits(POS_BITS)? + 1) as usize;
pos = if rp >= pos { rp - pos } else { (rp + SW_SIZE) - pos };
for _ in 0 .. num {
let c = buffer[pos];
wr.write(&[c])?;
buffer[rp] = c;
pos += 1;
rp += 1;
if pos >= SW_SIZE { pos = 0; }
if rp >= SW_SIZE { rp = 0; }
}
} else {
num = 1;
let c = rd.getbits(8)? as u8;
wr.write(&[c])?;
buffer[rp] = c;
rp += 1;
if rp >= SW_SIZE { rp = 0}
}
size -= num;
}
Ok(())
}
fn main() {
let args: Vec<_> = std::env::args().collect();
if args.len() < 3 {
println!("usage: lzss_decode input_file output_file");
} else {
match decode_file(&args[1], &args[2]) {
Ok(_) => (),
Err(err) => println!("{}", err.to_string())
}
}
}
ライブラリ bitio.rs を使っているので、あらかじめコンパイルしておいてください。あとは、rustc -O -L . lzss_decode.rs でコンパイルすることができます。
それでは簡単な実行例として、Canterbury Corpus で配布されているテストデータ The Large Corpus を圧縮してみましょう。
| ファイル名 | サイズ | LZSS | Huffman |
|---|---|---|---|
| bible.txt | 4,047,392 | 1,523,519 | 2,218,536 |
| e.coli | 4,638,690 | 1,576,480 | 1,159,686 |
| world192.txt | 2,473,400 | 1,172,800 | 1,558,721 |
| 合計 | 11,159,482 | 4,272,799 | 4,936,943 |
LZSS 符号はテキストファイルとの相性が良くて、ハフマン符号よりも高い圧縮率になります。なお、スライド窓を大きくすると、圧縮率はもう少し高くなります。ただし、符号化に時間がかかるようになるので注意してください。
一般的なテキストファイルを LZSS 符号で符号化する場合、最長一致系列の長さは短い場合が多く、長い場合は少ないと考えられます。したがって、長さを固定長で符号化すると圧縮率はどうしても悪くなってしまいます。このような場合、小さな正整数ほど短い符号語で表せる可変長符号、具体的には Elias のガンマ符号を使うと圧縮率を改善することができます。1987 年に T. C. Bell が開発した LZB 符号は、長さと位置の符号化に可変長符号を用いることで圧縮率を改善しています。詳しい説明は拙作のページ Algorithms with Python LZB 符号と LZH 符号 をお読みくださいませ。
今回作成するプログラムは、長さだけをガンマ符号で符号化する簡略版ですが、符号語を区別するフラグ (0: 記号, 1: 長さと位置) を長さの符号語に含める、具体的には長さ 0 のあとに記号 (8 bit) を、正整数のあとに位置を出力すると、ちょっとだけですが圧縮率を改善することができました。詳細はプログラムリストをお読みくださいませ。
//
// lzb_encode.rs : LZB 符号 (符号化)
//
// Copyright (C) 2018-2022 Makoto Hiroi
//
extern crate bitio;
use std::fs::{self, File};
use std::io::prelude::*;
use std::io::BufReader;
use std::collections::HashMap;
use bitio::BitWriter;
// 定数
const MIN_LEN: usize = 3;
const MAX_LEN: usize = 256;
const POS_BITS: u64 = 16;
const SW_SIZE: usize = 1 << POS_BITS;
const SW_LIMIT: usize = SW_SIZE * 2;
const NIL: usize = SW_LIMIT + MAX_LEN;
// スライド窓
struct SWindow {
reader: BufReader<File>,
buffer: Box<[u8; SW_LIMIT + MAX_LEN]>, // 大きな配列は Box でヒープ上に確保する
htable: HashMap<u32, usize>,
next: Box<[usize; SW_SIZE]>,
data_size: usize,
match_len: usize,
match_pos: usize
}
impl SWindow {
fn new(filename: &str) -> std::io::Result<SWindow> {
let fs = File::open(filename)?;
let mut sw = SWindow {
reader: BufReader::new(fs),
buffer: Box::new([0u8; SW_LIMIT + MAX_LEN]),
htable: HashMap::new(),
next: Box::new([NIL; SW_SIZE]),
data_size: 0,
match_len: 0,
match_pos: 0,
};
// ファイルの読み込み
sw.data_size = sw.reader.read(&mut *sw.buffer)?;
Ok(sw)
}
// ハッシュ値を求める
fn hash_value(&self, rp: usize) -> u32 {
let mut value = 0u32;
for i in 0 .. MIN_LEN {
value = (value << 8) + self.buffer[rp + i] as u32;
}
value
}
// データの挿入
fn insert(&mut self, rp: usize) {
let value = self.hash_value(rp);
match self.htable.get(&value) {
Some(x) if *x != NIL => self.next[rp & (SW_SIZE - 1)] = *x,
_ => self.next[rp & (SW_SIZE - 1)] = NIL
}
self.htable.insert(value, rp);
}
// 最長一致列の探索
fn search(&mut self, rp: usize) {
let value = self.hash_value(rp);
let limit = if rp < SW_SIZE { 0 } else { rp - SW_SIZE };
self.match_len = 0;
self.match_pos = 0;
if let Some(m) = self.htable.get(&value) {
let mut n = *m;
while n != NIL && n >= limit {
if self.buffer[rp + self.match_len] == self.buffer[n + self.match_len] {
let mut x = 0;
while x < MAX_LEN {
if self.buffer[rp + x] != self.buffer[n + x] {
break;
}
x += 1;
}
if self.match_len < x {
self.match_len = x;
self.match_pos = n;
if x == MAX_LEN { break; }
}
}
n = self.next[n & (SW_SIZE - 1)];
}
// データの終端をチェック
if self.match_len != 0 && self.match_len >= self.data_size - rp {
self.match_len = self.data_size - rp;
}
}
}
// 更新
fn update(&mut self, rp: usize) -> std::io::Result<usize> {
if self.data_size < SW_LIMIT + MAX_LEN {
return Ok(rp);
}
// データの移動
for i in 0 .. SW_SIZE + MAX_LEN {
self.buffer[i] = self.buffer[i + SW_SIZE];
}
self.data_size = SW_SIZE + MAX_LEN + self.reader.read(&mut self.buffer[SW_SIZE + MAX_LEN ..])?;
// ハッシュ表の更新
let mut work = vec![];
for (k, v) in self.htable.iter_mut() {
if *v < SW_SIZE {
work.push(*k);
} else if *v != NIL {
*v -= SW_SIZE;
}
}
for k in work {
self.htable.remove(&k);
}
for i in 0 .. SW_SIZE {
if self.next[i] != NIL && self.next[i] > SW_SIZE {
self.next[i] -= SW_SIZE;
} else {
self.next[i] = NIL;
}
}
Ok(rp - SW_SIZE)
}
}
fn encode_file(src: &String, dst: &String) -> std::io::Result<()> {
let mut wr = BitWriter::create(dst)?;
// ファイルサイズ
let metadata = fs::metadata(src)?;
let size = metadata.len();
if size == 0 { return Ok(()); }
wr.putbits(64, size)?;
let mut sw = SWindow::new(src)?;
let mut rp = 0;
while rp < sw.data_size {
let num;
sw.search(rp);
if sw.match_len < MIN_LEN {
num = 1;
wr.gamma_encode(0)?;
wr.putbits(8, sw.buffer[rp] as u64)?;
} else {
num = sw.match_len;
wr.gamma_encode((num - MIN_LEN + 1) as u64)?;
wr.putbits(POS_BITS, (rp - sw.match_pos - 1) as u64)?;
}
for _ in 0 .. num {
sw.insert(rp);
rp += 1;
if rp >= SW_LIMIT {
rp = sw.update(rp).unwrap();
}
}
}
Ok(())
}
fn main() {
let args: Vec<_> = std::env::args().collect();
if args.len() < 3 {
println!("usage: lzb_encode input_file output_file");
} else {
match encode_file(&args[1], &args[2]) {
Ok(_) => (),
Err(err) => println!("{}", err.to_string())
}
}
}
//
// lzb_decode.rs : LZB 符号 (復号)
//
// Copyright (C) 2018-2022 Makoto Hiroi
//
extern crate bitio;
use std::fs::File;
use std::io::prelude::*;
use std::io::BufWriter;
use bitio::BitReader;
// 以下の定数は lzb_enocde.rs と同じにすること
const MIN_LEN: usize = 3;
const POS_BITS: u64 = 16;
const SW_SIZE: usize = 1 << POS_BITS;
fn decode_file(src: &String, dst: &String) -> std::io::Result<()> {
let mut rd = BitReader::open(src)?;
let mut wr = BufWriter::new(File::create(dst)?);
let mut size = rd.getbits(64)?; // ファイルサイズの取得
if size == 0 { return Ok(()); }
let mut buffer = [0u8; SW_SIZE];
let mut rp: usize = 0;
while size > 0 {
let mut num = rd.gamma_decode()?;
if num > 0 {
num = num - 1 + MIN_LEN as u64;
let mut pos = (rd.getbits(POS_BITS)? + 1) as usize;
pos = if rp >= pos { rp - pos } else { (rp + SW_SIZE) - pos };
for _ in 0 .. num {
let c = buffer[pos];
wr.write(&[c])?;
buffer[rp] = c;
pos += 1;
rp += 1;
if pos >= SW_SIZE { pos = 0; }
if rp >= SW_SIZE { rp = 0; }
}
} else {
num = 1;
let c = rd.getbits(8)? as u8;
wr.write(&[c])?;
buffer[rp] = c;
rp += 1;
if rp >= SW_SIZE { rp = 0}
}
size -= num;
}
Ok(())
}
fn main() {
let args: Vec<_> = std::env::args().collect();
if args.len() < 3 {
println!("usage: lzb_decode input_file output_file");
} else {
match decode_file(&args[1], &args[2]) {
Ok(_) => (),
Err(err) => println!("{}", err.to_string())
}
}
}
それでは簡単な実行例として、Canterbury Corpus で配布されているテストデータ The Large Corpus と The Canterbury Corpus の ptt5 を圧縮してみましょう。
| ファイル名 | サイズ | LZB(18) | LZB(256) | LZSS | Huffman |
|---|---|---|---|---|---|
| bible.txt | 4,047,392 | 1,503,191 | 1,467,703 | 1,523,519 | 2,218,536 |
| e.coli | 4,638,690 | 1,585,902 | 1,584,648 | 1,576,480 | 1,159,686 |
| world192.txt | 2,473,400 | 1,136,319 | 1,110,237 | 1,172,800 | 1,558,721 |
| ptt5 | 513,216 | 117,627 | 65,687 | 107,293 | 106,758 |
最大一致長が短い場合、可変長符号を使うと逆効果になることもありますが、最大一致長を長くすると、その効果は大きくなります。特に、ptt5 のように同じ記号が連続するファイルの場合、最大一致長を長くするとファイルの圧縮率はとても高くなります。
次は最大一致長を 256 に固定して、スライド窓の大きさを大きくしてみましょう。
| ファイル名 | サイズ | 8 k | 16 k | 32 k | 64 k |
|---|---|---|---|---|---|
| bible.txt | 4,047,392 | 1,467,703 | 1,390,180 | 1,326,614 | 1,272,164 |
| e.coli | 4,638,690 | 1,584,648 | 1,560,720 | 1,544,914 | 1,535,620 |
| world192.txt | 2,473,400 | 1,110,237 | 876,062 | 801,622 | 747,720 |
| ptt5 | 513,216 | 65,687 | 65,905 | 66,369 | 67,049 |
LZ77 符号の場合、スライド窓を大きくすると圧縮率が高くなることが多いのですが、符号化に時間がかかるようになります。興味のある方はいろいろ試してみてください。
LZSS 符号はスライド窓から最長一致系列を探して、その位置と長さで符号化しました。最長一致系列が見つからなかった場合、LZSS 符号は記号をそのまま出力しています。この場合、可変長の符号語を使って平均符号長を短くすることができれば、圧縮率はさらに良くなるはずです。この二段階目の圧縮にハフマン符号を用いたものを一般に「LZH 符号」といいます。詳しい説明は拙作のページ Algorithms with Python LZB 符号と LZH 符号 をお読みくださいませ。
//
// lzh_encode.rs : LZH 符号 (符号化)
//
// Copyright (C) 2018-2022 Makoto Hiroi
//
extern crate bitio;
extern crate huffman;
use std::fs::{self, File};
use std::io::prelude::*;
use std::io::BufReader;
use std::collections::HashMap;
use bitio::BitWriter;
use huffman::*;
// 定数
const MIN_LEN: usize = 4;
const MAX_LEN: usize = 256;
const POS_BITS: u64 = 16;
const SW_SIZE: usize = 1 << POS_BITS;
const SW_LIMIT: usize = SW_SIZE * 2;
const NIL: usize = SW_LIMIT + MAX_LEN;
const HUFF_BITS: u64 = 14;
const HUFF_SIZE: usize = 1 << HUFF_BITS;
const CODE_SIZE: u64 = 256;
const CODE1_BITS: u64 = 9; // 記号と長さをハフマン符号で符号化するときのビット長
const CODE2_BITS: u64 = 5; // 位置をハフマン符号で符号化するときのビット長
struct SWindow {
reader: BufReader<File>,
buffer: Box<[u8; SW_LIMIT + MAX_LEN]>,
htable: HashMap<u32, usize>,
next: Box<[usize; SW_SIZE]>,
data_size: usize,
match_len: usize,
match_pos: usize
}
impl SWindow {
fn new(filename: &str) -> std::io::Result<SWindow> {
let fs = File::open(filename)?;
let mut sw = SWindow {
reader: BufReader::new(fs),
buffer: Box::new([0u8; SW_LIMIT + MAX_LEN]),
htable: HashMap::new(),
next: Box::new([NIL; SW_SIZE]),
data_size: 0,
match_len: 0,
match_pos: 0,
};
// ファイルの読み込み
sw.data_size = sw.reader.read(&mut *sw.buffer)?;
Ok(sw)
}
// ハッシュ値を求める
fn hash_value(&self, rp: usize) -> u32 {
let mut value = 0u32;
for i in 0 .. MIN_LEN {
value = (value << 8) + self.buffer[rp + i] as u32;
}
value
}
// データの挿入
fn insert(&mut self, rp: usize) {
let value = self.hash_value(rp);
match self.htable.get(&value) {
Some(x) if *x != NIL => self.next[rp & (SW_SIZE - 1)] = *x,
_ => self.next[rp & (SW_SIZE - 1)] = NIL
}
self.htable.insert(value, rp);
}
// 最長一致列の探索
fn search(&mut self, rp: usize) {
let value = self.hash_value(rp);
let limit = if rp < SW_SIZE { 0 } else { rp - SW_SIZE };
self.match_len = 0;
self.match_pos = 0;
if let Some(m) = self.htable.get(&value) {
let mut n = *m;
while n != NIL && n >= limit {
if self.buffer[rp + self.match_len] == self.buffer[n + self.match_len] {
let mut x = 0;
while x < MAX_LEN {
if self.buffer[rp + x] != self.buffer[n + x] {
break;
}
x += 1;
}
if self.match_len < x {
self.match_len = x;
self.match_pos = n;
if x == MAX_LEN { break; }
}
}
n = self.next[n & (SW_SIZE - 1)];
}
// データの終端をチェック
if self.match_len != 0 && self.match_len >= self.data_size - rp {
self.match_len = self.data_size - rp;
}
}
}
// 更新
fn update(&mut self, rp: usize) -> std::io::Result<usize> {
if self.data_size < SW_LIMIT + MAX_LEN {
return Ok(rp);
}
// データの移動
for i in 0 .. SW_SIZE + MAX_LEN {
self.buffer[i] = self.buffer[i + SW_SIZE];
}
self.data_size = SW_SIZE + MAX_LEN + self.reader.read(&mut self.buffer[SW_SIZE + MAX_LEN ..])?;
// ハッシュ表の更新
let mut work = vec![];
for (k, v) in self.htable.iter_mut() {
if *v < SW_SIZE {
work.push(*k);
} else if *v != NIL {
*v -= SW_SIZE;
}
}
for k in work {
self.htable.remove(&k);
}
for i in 0 .. SW_SIZE {
if self.next[i] != NIL && self.next[i] > SW_SIZE {
self.next[i] -= SW_SIZE;
} else {
self.next[i] = NIL;
}
}
Ok(rp - SW_SIZE)
}
}
// ビット数を求める
fn get_bit_num(n: u64) -> u64 {
let mut n1 = 0;
let mut n2 = (n + 1) >> 1;
while n2 > 0 {
n1 += 1;
n2 >>= 1;
}
n1
}
// ハフマン符号化
fn huff_encode(mut wr: &mut BitWriter, huff_buff: &[(u64, u64)], size: usize) -> std::io::Result<()> {
let mut freq1 = vec![0u64; CODE_SIZE as usize + MAX_LEN - MIN_LEN + 1];
let mut freq2 = vec![0u64; (POS_BITS + 1) as usize];
for i in 0 .. size {
freq1[huff_buff[i].0 as usize] += 1;
if huff_buff[i].0 >= CODE_SIZE {
freq2[get_bit_num(huff_buff[i].1) as usize] += 1;
}
}
let tree1 = make_tree(&freq1);
let code1 = make_code(&tree1);
let tree2 = make_tree(&freq2);
let code2 = make_code(&tree2);
wr.putbits(HUFF_BITS, (size - 1) as u64)?; // データサイズ
write_tree(&tree1, CODE1_BITS, &mut wr)?;
write_tree(&tree2, CODE2_BITS, &mut wr)?;
// 符号化
for i in 0 .. size {
let (x, p) = huff_buff[i];
huffman_encode(&code1, x, &mut wr)?;
if x >= CODE_SIZE {
let n = get_bit_num(p);
huffman_encode(&code2, n, &mut wr)?;
if n > 0 { wr.putbits(n, p + 1)?; }
}
}
Ok(())
}
fn encode_file(src: &String, dst: &String) -> std::io::Result<()> {
let mut wr = BitWriter::create(dst)?;
// ファイルサイズ
let metadata = fs::metadata(src)?;
let size = metadata.len();
if size == 0 { return Ok(()); }
wr.putbits(64, size)?;
// ハフマン符号用のバッファ
let mut huff_buff = Box::new([(0u64, 0u64); HUFF_SIZE]);
let mut huff_cnt = 0;
let mut sw = SWindow::new(src)?;
let mut rp = 0;
while rp < sw.data_size {
let num;
sw.search(rp);
if sw.match_len < MIN_LEN {
num = 1;
huff_buff[huff_cnt] = (sw.buffer[rp] as u64, 0);
} else {
num = sw.match_len;
huff_buff[huff_cnt] = (CODE_SIZE + (num - MIN_LEN) as u64, (rp - sw.match_pos - 1) as u64);
}
huff_cnt += 1;
if huff_cnt >= HUFF_SIZE {
huff_encode(&mut wr, & *huff_buff, huff_cnt)?;
huff_cnt = 0;
}
for _ in 0 .. num {
sw.insert(rp);
rp += 1;
if rp >= SW_LIMIT {
rp = sw.update(rp).unwrap();
}
}
}
if huff_cnt > 0 {
huff_encode(&mut wr, & *huff_buff, huff_cnt)?;
}
Ok(())
}
fn main() {
let args: Vec<_> = std::env::args().collect();
if args.len() < 3 {
println!("usage: lzh_encode input_file output_file");
} else {
match encode_file(&args[1], &args[2]) {
Ok(_) => (),
Err(err) => println!("{}", err.to_string())
}
}
}
//
// lzh_decode.rs : LZH 符号 (復号)
//
// Copyright (C) 2018-2022 Makoto Hiroi
//
extern crate bitio;
extern crate huffman;
use std::fs::File;
use std::io::prelude::*;
use std::io::BufWriter;
use bitio::BitReader;
use huffman::*;
// 以下の定数は lzh_enocde.rs と同じにすること
const MIN_LEN: usize = 4;
const POS_BITS: u64 = 16;
const SW_SIZE: usize = 1 << POS_BITS;
const HUFF_BITS: u64 = 14;
const HUFF_SIZE: usize = 1 << HUFF_BITS;
const CODE_SIZE: u64 = 256;
const CODE1_BITS: u64 = 9; // 記号と長さをハフマン符号で符号化するときのビット長
const CODE2_BITS: u64 = 5; // 位置をハフマン符号で符号化するときのビット長
// ハフマン符号の復号
fn huff_decode(huff_buff: &mut [(u64, u64)], mut rd: &mut BitReader) -> std::io::Result<usize> {
let size = (rd.getbits(HUFF_BITS)? + 1) as usize; // データサイズの取得
let tree1 = read_tree(CODE1_BITS, &mut rd)?;
let tree2 = read_tree(CODE2_BITS, &mut rd)?;
for i in 0 .. size {
let c = huffman_decode(&tree1, &mut rd)?;
let p = if c >= CODE_SIZE {
let n = huffman_decode(&tree2, &mut rd)?;
if n > 0 {
(1 << n) + rd.getbits(n)? - 1
} else {
n
}
} else {
0
};
huff_buff[i] = (c, p);
}
Ok(size)
}
fn decode_file(src: &String, dst: &String) -> std::io::Result<()> {
let mut rd = BitReader::open(src)?;
let mut wr = BufWriter::new(File::create(dst)?);
let mut size = rd.getbits(64)?; // ファイルサイズの取得
if size == 0 { return Ok(()); }
// ハフマン符号用
let mut huff_buff = Box::new([(0u64, 0u64); HUFF_SIZE]);
let mut hsize = 0;
let mut hcnt = 0;
// スライド窓
let mut buffer = Box::new([0u8; SW_SIZE]);
let mut rp: usize = 0;
while size > 0 {
let num;
if hsize == hcnt {
hsize = huff_decode(&mut *huff_buff, &mut rd)?;
hcnt = 0;
}
if huff_buff[hcnt].0 >= CODE_SIZE {
num = huff_buff[hcnt].0 - CODE_SIZE + MIN_LEN as u64;
let mut pos = (huff_buff[hcnt].1 + 1) as usize;
pos = if rp >= pos { rp - pos } else { (rp + SW_SIZE) - pos };
for _ in 0 .. num {
let c = buffer[pos];
wr.write(&[c])?;
buffer[rp] = c;
pos += 1;
rp += 1;
if pos >= SW_SIZE { pos = 0; }
if rp >= SW_SIZE { rp = 0; }
}
} else {
num = 1;
let c = huff_buff[hcnt].0 as u8;
wr.write(&[c])?;
buffer[rp] = c;
rp += 1;
if rp >= SW_SIZE { rp = 0}
}
hcnt += 1;
size -= num;
}
Ok(())
}
fn main() {
let args: Vec<_> = std::env::args().collect();
if args.len() < 3 {
println!("usage: lzh_decode input_file output_file");
} else {
match decode_file(&args[1], &args[2]) {
Ok(_) => (),
Err(err) => println!("{}", err.to_string())
}
}
}
それでは簡単な実行例として、Canterbury Corpus で配布されているテストデータ The Large Corpus と The Canterbury Corpus の ptt5 を圧縮してみましょう。
| ファイル名 | サイズ | LZH | LZB |
|---|---|---|---|
| bible.txt | 4,047,392 | 1,147,129 | 1,272,164 |
| e.coli | 4,638,690 | 1,291,234 | 1,535,620 |
| world192.txt | 2,473,400 | 692,173 | 747,720 |
| ptt5 | 513,216 | 56,513 | 67,049 |
LZH 符号のスライド窓の大きさ (64 k) と最大一致長 (256) は LZB 符号と同じです。ただし、最小の一致長 (MIN_LEN) の値を 3 から 4 に変更しています。LZH 符号の場合、記号の符号化にハフマン符号を用いるため、それだけでも圧縮することが可能です。つまり、不一致の場合が多くても、ある程度は圧縮できるわけです。実際に試してみたところ、LZH 符号の場合、MIN_LEN は 3 よりも 4 の方が少しですが圧縮率は高くなります。興味のある方はいろいろ試してみてください。