M.Hiroi's Home Page

Linux Programming

お気楽 Rust プログラミング超入門

Copyright (C) 2018-2024 Makoto Hiroi
All rights reserved.

ファイルの圧縮

●LZW 符号

今回は J.Zip と A.Lempel が開発したもう一つのデータ圧縮アルゴリズムである「LZ78 符号」を取り上げます。LZ77 符号と同様に LZ78 符号にも多数のバリエーションが存在します。その中で、最も基本的で広く用いられている符号が、1984 年 T. Welch によって開発された「LZW 符号」です。

LZSS 符号はスライド窓を辞書として使っていました。スライド窓の大きさは一定なので、記号を読み込むたびに古い記号から捨てていかなくてはいけません。つまり、LZ77 符号は局所的な辞書を構成していると考えることができます。したがって、同じ記号列がファイル内に分散している状態では、それを効果的に圧縮することはできません。

この問題点を解決するため、LZW 符号ではスライド窓の使用をやめて、これまでに出現した記号列を辞書に登録することで大域的な辞書を作成します。詳しい説明は拙作のページ「Algorithms with Python: LZ78 符号 (LZW 符号)」をお読みくださいませ。

●LZW 符号の符号化

//
// lzw_encode.rs : LZW 符号 (符号化)
//
//                 Copyright (C) 2018-2024 Makoto Hiroi
//
extern crate bitio;

use std::fs::{self, File};
use std::io::prelude::*;
use std::io::BufReader;
use std::collections::HashMap;
use std::cell::UnsafeCell;
use bitio::BitWriter;

// 定数
const DIC_BITS: u64 = 16;
const DIC_SIZE: u64 = 1 << DIC_BITS;

// 辞書は「トライ (trie)」を使う
// 子は HashMap に格納する
struct Node {
    code: u64, // 辞書番号
    child: UnsafeCell<HashMap<u8, Node>>  // 子
}

impl Node {
    fn new(m: u64) -> Node {
        Node { code: m, child: UnsafeCell::new(HashMap::new()) }
    }
}

// ファイルの符号化
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)?;

    // 記号 (0 - 255) を辞書に登録する
    let mut buff = vec![];
    for x in 0 .. 256 {
        buff.push(Node::new(x));
    }

    // 符号化
    let rd = BufReader::new(File::open(src)?);
    let mut iter = rd.bytes();
    let mut p = &buff[iter.next().unwrap()? as usize];
    let mut num = 256;
    loop {
        match iter.next() {
            None => {
                wr.putbits(DIC_BITS, p.code)?;
                break;
            }
            Some(r) => {
                let c = r?;
                let ht = p.child.get();
                if let Some(q) = unsafe { (*ht).get(&c) } {
                    p = q;
                } else {
                    wr.putbits(DIC_BITS, p.code)?;
                    if num < DIC_SIZE {
                        unsafe { (*ht).insert(c, Node::new(num)) };
                        num += 1;
                    }
                    p = &buff[c as usize];
                }
            }
        } 
    }    
    Ok(())
}

fn main() {
    let args: Vec<_> = std::env::args().collect();
    if args.len() < 3 {
        println!("usage: lzw_encode input_file output_file");
    } else {
        match encode_file(&args[1], &args[2]) {
            Ok(_) => (),
            Err(err) => println!("{}", err.to_string())
        }
    }
}

●LZW 符号の復号

//
// lzw_decode.rs : LZW 符号 (復号)
//
//                 Copyright (C) 2018-2024 Makoto Hiroi
//
extern crate bitio;

use std::fs::File;
use std::io::prelude::*;
use std::io::BufWriter;
use bitio::BitReader;

// 定数
const DIC_BITS: u64 = 16;
const DIC_SIZE: u64 = 1 << DIC_BITS;
const NIL: u64 = DIC_SIZE;

// 出力
fn output(buff: &Vec<(u8, u64)>, n: u64, wr: &mut BufWriter<File>) -> std::io::Result<(u8, u64)> {
    let (c, p) = buff[n as usize];
    if p == NIL {
        wr.write(&[c])?;
        Ok((c, 1))
    } else {
        let x = output(buff, p, wr)?;
        wr.write(&[c])?;
        Ok((x.0, x.1 + 1))
    }
}

// 復号
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(()); }

    // 記号 (0 - 255) を辞書に登録
    // 復号の場合、トライを構成する必要はない
    let mut buff =vec![];
    for x in 0 .. 256 {
        buff.push((x as u8, NIL));
    }

    let mut p = rd.getbits(DIC_BITS)?;
    let mut c;
    let mut l;
    let (x, n) = output(&buff, p, &mut wr)?;
    c = x;
    l = n;
    size -= l;
    while size > 0 {
        let q = rd.getbits(DIC_BITS)?;
        let k = buff.len() as u64;
        if q < k {
            let (x, n) = output(&buff, q, &mut wr)?;
            if k < DIC_SIZE {
                buff.push((x, p));
            }
            c = x;
            l = n;
        } else {
            buff.push((c, p));
            let (x, n) = output(&buff, q, &mut wr)?;
            c = x;
            l = n;
        }
        p = q;
        size -= l;
    }
    Ok(())
}

fn main() {
    let args: Vec<_> = std::env::args().collect();
    if args.len() < 3 {
        println!("usage: lzw_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 を圧縮してみましょう。

表：The Large Corpus と ptt5 の評価結果
ファイル名サイズLZWLZSSHuffman
bible.txt 4,047,3921,729,8991,523,5192,218,536
e.coli 4,638,6901,238,4831,576,4801,159,686
world192.txt 2,473,4001,297,6281,172,8001,558,721
ptt5 513,21666,105 107,293 106,758

テキストファイルの場合、ファイル全体を通して同じ単語が繰り返し使われているので、LZW 符号で効率的に圧縮することができますが、一般的には LZSS 符号のほうが高い圧縮率になることが多いようです。

次は辞書サイズを大きくしてみましょう。

表：The Large Corpus と ptt5 の評価結果 (2)
ファイル名サイズ8 k16 k32 k64 k
bible.txt 4,047,3921,729,8991,607,6481,522,0791,425,644
e.coli 4,638,6901,238,4831,227,8141,223,4371,221,486
world192.txt 2,473,4001,297,6281,142,2961,027,595933,710
ptt5 513,21666,10565,66165,86070,124

LZW 符号の場合、辞書を表す符号語（辞書番号）は固定長なので、辞書を大きくすれば圧縮率が向上するとは限りません。これは LZSS 符号と同じ欠点です。このような場合、辞書番号を可変長符号で表すと圧縮率を改善することができます。

●CBT 符号による改良

基本的な考え方は LZB 符号と同じです。辞書番号が 511 以下であれば 9 bit で、1023 以下であれば 10 bit で符号化することができます。符号語を出力するたびに辞書番号は一つずつ増えていくので、その値によって符号語長を変化させればいいわけです。ここで CBT 符号を使用すると、圧縮率をさらに向上させることができます。

●符号化

//
// lzwc_encode.rs : LZW 符号 + CBT 符号 (符号化)
//
//                  Copyright (C) 2018-2024 Makoto Hiroi
//
extern crate bitio;

use std::fs::{self, File};
use std::io::prelude::*;
use std::io::BufReader;
use std::collections::HashMap;
use std::cell::UnsafeCell;
use bitio::BitWriter;

// 定数
const DIC_BITS: u64 = 16;
const DIC_SIZE: u64 = 1 << DIC_BITS;

// 辞書は「トライ (trie)」を使う
// 子は HashMap に格納する
struct Node {
    code: u64, // 辞書番号
    child: UnsafeCell<HashMap<u8, Node>>  // 子
}

impl Node {
    fn new(m: u64) -> Node {
        Node { code: m, child: UnsafeCell::new(HashMap::new()) }
    }
}

// 辞書番号の符号化
fn encode(code: u64, num: u64, dic_bits: u64, wr: &mut BitWriter) -> std::io::Result<()> {
    if dic_bits < DIC_BITS {
        wr.cbt_encode(code, num, dic_bits)?;
    } else {
        wr.putbits(DIC_BITS, code)?;
    }
    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 buff = vec![];
    for x in 0 .. 256 {
        buff.push(Node::new(x));
    }

    // 符号化
    let rd = BufReader::new(File::open(src)?);
    let mut iter = rd.bytes();
    let mut p = &buff[iter.next().unwrap()? as usize];
    let mut num = 256;
    let mut dic_bits = 9;
    loop {
        match iter.next() {
            None => {
                encode(p.code, num, dic_bits, &mut wr)?;
                break;
            }
            Some(r) => {
                let c = r?;
                let ht = p.child.get();
                if let Some(q) = unsafe { (*ht).get(&c) } {
                    p = q;
                } else {
                    encode(p.code, num, dic_bits, &mut wr)?;
                    if num < DIC_SIZE {
                        unsafe { (*ht).insert(c, Node::new(num)) };
                        num += 1;
                        if dic_bits < DIC_BITS && num > (1 << dic_bits) - 1 { 
                            dic_bits += 1;
                        }
                    }
                    p = &buff[c as usize];
                }
            }
        } 
    }    
    Ok(())
}

fn main() {
    let args: Vec<_> = std::env::args().collect();
    if args.len() < 3 {
        println!("usage: lzw_encode input_file output_file");
    } else {
        match encode_file(&args[1], &args[2]) {
            Ok(_) => (),
            Err(err) => println!("{}", err.to_string())
        }
    }
}

●復号

//
// lzwc_decode.rs : LZW 符号 + CBT 符号 (復号)
//
//                  Copyright (C) 2018-2024 Makoto Hiroi
//
extern crate bitio;

use std::fs::File;
use std::io::prelude::*;
use std::io::BufWriter;
use bitio::BitReader;

// 定数
const DIC_BITS: u64 = 16;
const DIC_SIZE: u64 = 1 << DIC_BITS;
const NIL: u64 = DIC_SIZE;

// 出力
fn output(buff: &Vec<(u8, u64)>, n: u64, wr: &mut BufWriter<File>) -> std::io::Result<(u8, u64)> {
    let (c, p) = buff[n as usize];
    if p == NIL {
        wr.write(&[c])?;
        Ok((c, 1))
    } else {
        let x = output(buff, p, wr)?;
        wr.write(&[c])?;
        Ok((x.0, x.1 + 1))
    }
}

// 復号
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 buff =vec![];
    for x in 0 .. 256 {
        buff.push((x as u8, NIL));
    }

    let mut dic_bits = 9;
    let mut num = 256;
    let mut p = rd.cbt_decode(num, dic_bits)?;
    num += 1;    
    let mut c;
    let mut l;
    let (x, n) = output(&buff, p, &mut wr)?;
    c = x;
    l = n;
    size -= l;
    while size > 0 {
        let q;
        if dic_bits < DIC_BITS {
            q = rd.cbt_decode(num, dic_bits)?;
            num += 1;
            if num > (1 << dic_bits) - 1 { dic_bits += 1; }
        } else {
            q = rd.getbits(DIC_BITS)?;
        }
        let k = buff.len() as u64;
        if q < k {
            let (x, n) = output(&buff, q, &mut wr)?;
            if k < DIC_SIZE {
                buff.push((x, p));
            }
            c = x;
            l = n;
        } else {
            buff.push((c, p));
            let (x, n) = output(&buff, q, &mut wr)?;
            c = x;
            l = n;
        }
        p = q;
        size -= l;
    }
    Ok(())
}

fn main() {
    let args: Vec<_> = std::env::args().collect();
    if args.len() < 3 {
        println!("usage: lzw_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 を圧縮してみましょう。

表：The Large Corpus と ptt5 の評価結果
ファイル名サイズ8 k16 k32 k64 k
bible.txt 4,047,3921,728,8961,605,4621,517,4811,416,231
e.coli 4,638,6901,237,5041,225,6491,218,8621,212,039
world192.txt 2,473,4001,296,5921,140,0301,022,902924,140
ptt5 513,21665,08863,42861,10560,337

辞書番号を CBT 符号で符号化したことにより、ptt5 の圧縮率は高くなりました。ほかのファイルでも圧縮率は改善されているので、CBT 符号を用いた効果は十分に出ていると思います。

●レンジコーダ (range coder)

ハフマン符号は各記号の出現確率を調べ、頻繁に現れる記号は短いビットで表し、あまり現れない記号は長いビットで表すことで、データを圧縮する古典的な方法です。古典的とはいっても、ほかのアルゴリズムと簡単に組み合わせることができるため、ハフマン符号は今でも現役のアルゴリズムです。

記号の出現確率だけを利用してデータを圧縮する方法は、ハフマン符号のほかに「算術符号」という方法があります。一般に、算術符号はハフマン符号よりも性能が良いのですが、実装方法が難しくて実行速度がハフマン符号よりも遅いという欠点があります。これに対し、「レンジコーダ (range coder)」は、原理的には算術符号と同じ方法ですが、実装方法はとても簡単で実行速度も算術符号より高速です。性能は算術符号に比べるとわずかに劣化しますが、ハフマン符号よりも高性能です。

レンジコーダの詳細は拙作のページ「Algorithms with Python: レンジコーダ [1] [2]」をお読みくださいませ。今回は適応型レンジコーダ (桁上がりなし) のプログラムを Rust で作ります。

●Binary Indexed Tree (BIT)

適応型レンジコーダの場合、単純な累積度数分布表を用いると、その更新処理に時間がかかってしまいます。今回は累積度数の取得と更新を比較的高速に行うことができる Binary Indexed Tree というデータ構造を使います。詳しい説明は拙作のページ「レンジコーダ [3]」をお読みくださいませ。

構造体の名前は BITree とし、以下のメソッドを作成します。

コンパイルは rustc -O --crate-type=lib bitree.rs とします。 

//
// bitree.rs : Binary Indexed Tree
//
//             Copyright (C) 2018-2024 Makoto Hiroi
//

// 構造体の定義
pub struct BITree {
    table: Vec<u32>,
    sum: u32,
    mid: usize
}

impl BITree {
    pub fn new(n: usize) -> BITree {
        let mut m = 1;
        while m < n / 2 { m *= 2; }
        let mut tree = BITree { table: vec![0; n], sum: 0, mid: m };
        for i in 0 .. n as u32 { tree.inc(i, 1); }
        tree
    }

    // 合計値を求める
    pub fn get_sum(&self) -> u32 { self.sum }

    // 累積度数を求める
    pub fn cumul(&self, mut c: u32) -> u32 {
        let mut n = 0;
        if c > 0 {
            n = self.table[0];
            c -= 1;
            while c > 0 {
                n += self.table[c as usize];
                c = c & (c - 1);
            }
        }
        n
    }

    // 出現頻度を求める
    pub fn get_prob(&self, mut c: u32) -> u32 {
        let mut val = self.table[c as usize];
        if c > 0 && c & 1 == 0 {
            let p = c & (c - 1);
            c -= 1;
            while c != p {
                val -= self.table[c as usize];
                c = c & (c - 1);
            }
        }
        val
    }

    // 出現頻度の更新
    pub fn inc(&mut self, c: u32, n: u32) {
        let mut c = c as i32;
        if c > 0 {
            let k = self.table.len() as i32;
            while c < k {
                self.table[c as usize] += n;
                c += c & (- c);
            }
        } else {
            self.table[0] += n;
        }
        self.sum += n;
    }

    pub fn dec(&mut self, c: u32, n: u32) {
        if c > 0 {
            let mut c = c as i32;
            let k = self.table.len() as i32;
            while c < k {
                self.table[c as usize] -= n;
                c += c & (- c);
            }
        } else {
            self.table[0] -= n;
        }
        self.sum -= n;
    }

    pub fn halve(&mut self) {
        for i in 0 .. self.table.len() as u32 {
            let n = self.get_prob(i) / 2;
            if n > 0 {
                self.dec(i, n);
            }
        }
    }

    // 記号の探索
    pub fn search_code(&self, value: u32) -> (u32, u32) {
        let mut c = 0;
        let mut n = 0;
        if self.table[0] <= value {
            let mut h = self.mid;
            n = self.table[0];
            while h > 0 {
                if c + h < self.table.len() && n + self.table[c + h] <= value {
                    n += self.table[c + h];
                    c += h;
                }
                h /= 2;
            }
            c += 1;
        }
        (c as u32, n)
    }
}

●適応型レンジコーダ

decode(), encode() の引数 n は記号の度数の増分値を表します。コンパイルは rustc -L . -O --crate-type=lib rangecoder.rs とします。 

//
// rangecoder.rs : 適応型レンジコーダ
//
//                 Copyright (C) 2018-2024 Makoto Hiroi
//
extern crate bitree;

use std::fs::File;
use std::io::{Result, BufReader, Read, BufWriter, Write};
use bitree::BITree;

// 定数
const MAX_RANGE: u32 = 0xffffffff;
const MIN_RANGE: u32 = 0x10000;
const MASK1: u32     = 0xff000000;
const SHIFT: u32     = 24;

//
// 桁上がりのないレンジコーダ
//

// 符号化
pub struct Encoder {
    writer: BufWriter<File>,
    range: u32,
    low: u32
}

impl Encoder {
    // ライトオープン
    pub fn create(filename: &str) -> std::io::Result<Encoder> {
        let fs = File::create(filename)?;
        Ok(Encoder { writer: BufWriter::new(fs), range: MAX_RANGE, low: 0})
    }

    // 正規化
    fn normalize(&mut self) -> std::io::Result<()> {
        while self.low & MASK1 == (self.low + self.range) & MASK1 {
            self.writer.write(&mut [(self.low >> SHIFT) as u8])?;
            self.low = self.low << 8;
            self.range <<= 8;
        }
        while self.range < MIN_RANGE {
            self.range = (MIN_RANGE - (self.low & (MIN_RANGE - 1))) << 8;
            self.writer.write(&mut [(self.low >> SHIFT) as u8])?;
            self.low = self.low << 8;
        }
        Ok(())
    }

    // 符号化
    pub fn encode(&mut self, freq: &mut BITree, c: u32, n: u32) -> std::io::Result<()> {
        let temp = self.range / freq.get_sum();
        self.low += freq.cumul(c) * temp;
        self.range = freq.get_prob(c) * temp;
        self.normalize()?;
        freq.inc(c, n);
        if freq.get_sum() >= MIN_RANGE { freq.halve(); }
        Ok(())
    }
}

impl Drop for Encoder {
    fn drop(&mut self) {
        self.writer.write(&mut [((self.low >> 24) & 0xff) as u8]).unwrap();
        self.writer.write(&mut [((self.low >> 16) & 0xff) as u8]).unwrap();
        self.writer.write(&mut [((self.low >> 8) & 0xff) as u8]).unwrap();
        self.writer.write(&mut [(self.low & 0xff) as u8]).unwrap();
    }
}

pub struct Decoder {
    reader: BufReader<File>,
    code: u32,
    range: u32,
    low: u32
}

impl Decoder {
    // リードオープン
    pub fn open(filename: &str) -> Result<Decoder> {
        let fs = File::open(filename)?;
        let mut rd = BufReader::new(fs);
        let mut c = 0;
        for _ in 0 .. 4 {
            let mut buff = [0u8; 1];
            rd.read(&mut buff)?;
            c = (c << 8) + buff[0] as u32;
        }
        Ok(Decoder { reader: rd, code: c, range: MAX_RANGE, low: 0 })
    }

    // 正規化
    fn normalize(&mut self) -> std::io::Result<()> {
        let mut buff = [0u8; 1];
        while self.low & MASK1 == (self.low + self.range) & MASK1 {
            self.reader.read(&mut buff)?;
            self.code = (self.code << 8) + buff[0] as u32;
            self.low = self.low << 8;
            self.range <<= 8;
        }
        while self.range < MIN_RANGE {
            self.reader.read(&mut buff)?;
            self.range = (MIN_RANGE - (self.low & (MIN_RANGE - 1))) << 8;
            self.code = (self.code << 8) + buff[0] as u32;
            self.low = self.low << 8;
        }
        Ok(())
    }

    // 復号
    pub fn decode(&mut self, freq: &mut BITree, n: u32) -> std::io::Result<u32> {
        let temp = self.range / freq.get_sum();
        let (c, m) = freq.search_code((self.code - self.low) / temp);
        self.low += temp * m;
        self.range = temp * freq.get_prob(c);
        self.normalize()?;
        freq.inc(c, n);
        if freq.get_sum() >= MIN_RANGE {
            freq.halve();
        }
        Ok(c)
    }
}

●符号化

コンパイルは rustc -L . -O rc_encode.rs とします。

//
// rc_encode.rs : 適応型レンジコーダ (符号化)
//
//                Copyright (C) 2018-2024 Makoto Hiroi
//
extern crate bitree;
extern crate rangecoder;

use std::fs::File;
use std::io::prelude::*;
use std::io::BufReader;
use bitree::BITree;
use rangecoder::Encoder;

fn encode_file(src: &String, dst: &String) -> std::io::Result<()> {
    let mut freq = BITree::new(257);
    let mut wr = Encoder::create(dst)?;
    let rd = BufReader::new(File::open(src)?);
    for r in rd.bytes() {
        wr.encode(&mut freq, r? as u32, 1)?;
    }
    // EOF を書き込む
    wr.encode(&mut freq, 256, 1)?;
    Ok(())
}

fn main() {
    let args: Vec<_> = std::env::args().collect();
    if args.len() < 3 {
        println!("usage: rc_encode input_file output_file");
    } else {
        match encode_file(&args[1], &args[2]) {
            Ok(_) => (),
            Err(err) => println!("{}", err.to_string())
        }
    }
}

●復号

コンパイルは rustc -L . -O rcdecode.rs とします。

//
// rc_decode.rs : 適応型レンジコーダ (復号)
//
//                Copyright (C) 2018-2024 Makoto Hiroi
//
extern crate bitree;
extern crate rangecoder;

use std::fs::File;
use std::io::prelude::*;
use std::io::BufWriter;
use bitree::BITree;
use rangecoder::Decoder;

fn decode_file(src: &String, dst: &String) -> std::io::Result<()> {
    let mut rd = Decoder::open(src)?;
    let mut wr = BufWriter::new(File::create(dst)?);
    let mut freq = BITree::new(257);
    loop {
        let c = rd.decode(&mut freq, 1)?;
        if c == 256 { break; }
        wr.write(&mut [c as u8])?;
    }
    Ok(())
}

fn main() {
    let args: Vec<_> = std::env::args().collect();
    if args.len() < 3 {
        println!("usage: rc_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 を圧縮してみましょう。

表：The Large Corpus と ptt5 の評価結果
ファイル名サイズRangeHuffman
bible.txt 4,047,3922,196,4082,218,536
e.coli 4,638,6901,165,7011,159,686
world192.txt 2,473,4001,543,9041,558,721
ptt5 513,216 76,816 106,758

e.coli を除き、適応型レンジコーダのほうが高い圧縮率になりました。特に ptt5 の圧縮率は、レンジコーダの方がとても高くなります。記号に 1 ビット未満の符号語を割り当てることができるレンジコーダ (算術符号) の特徴が結果に出ていると思います。

●有限文脈モデル

有限文脈モデルは、直前に出現した記号列によって記号の出現確率を定める、という簡単なモデルです。直前に出現した記号列の長さを「次数 (order)」といいます。有限文脈モデルは 1 次 (order-1) がいちばん簡単です。直前に出力した記号を覚えておいて、それに従って出現頻度表を切り替えるという単純な方法で実現できます。つまり、各記号ごとに出現頻度表を用意しておいて、直前に出力した記号が a であれば、a の出現頻度表を使って符号化を行うわけです。詳しい説明は拙作のページ「Algorithms with Python: 有限文脈モデル」をお読みくださいませ。

ところで、適応型レンジコーダには、出現しない記号が多数あると圧縮率が少し劣化する、という欠点があります。たとえば、記号が 0 と 1 しかないデータを符号化してみましょう。適応型符号化では記号 0 - 255 の出現頻度を 1 に初期化しています。このため、記号数が少ないうちは記号 2 - 255 の出現頻度の影響が大きくなり、圧縮率はどうしても劣化してしまいます。ようするに、記号をたくさん読み込まないと、その出現頻度表の確率はあてにならないというわけです。

高次の有限文脈モデルになればなるほど、多数の出現頻度表を使うことになるので、この欠点の影響はとても大きなものになりますが、この影響を緩和する簡単な方法が 2 つあります。一つは出現頻度表の累積度数の上限値を小さな値に設定することです。もう一つは、出現頻度表の更新時で記号数の増分値を +1 より大きくすることです。今回は後者の方法を使うことにします。

●order-1

//
// rc1_encode.rs : 有限文脈モデル (order-1, 符号化)
//
//                 Copyright (C) 2018-2024 Makoto Hiroi
//
extern crate bitree;
extern crate rangecoder;

use std::fs::File;
use std::io::prelude::*;
use std::io::BufReader;
use bitree::BITree;
use rangecoder::Encoder;
use std::collections::HashMap;

fn encode_file(src: &String, dst: &String) -> std::io::Result<()> {
    let mut ht = HashMap::new();
    let mut wr = Encoder::create(dst)?;
    let rd = BufReader::new(File::open(src)?);
    let mut c0 = 0;
    for r in rd.bytes() {
        let c = r?;
        if !ht.contains_key(&c0) {
            ht.insert(c0, BITree::new(257));
        }
        // 増分値は +16
        wr.encode(ht.get_mut(&c0).unwrap(), c as u32, 16)?;
        c0 = c;
    }
    // EOF を書き込む
    if !ht.contains_key(&c0) {
        ht.insert(c0, BITree::new(257));
    }
    wr.encode(ht.get_mut(&c0).unwrap(), 256, 16)?;
    Ok(())
}

fn main() {
    let args: Vec<_> = std::env::args().collect();
    if args.len() < 3 {
        println!("usage: rc1_encode input_file output_file");
    } else {
        match encode_file(&args[1], &args[2]) {
            Ok(_) => (),
            Err(err) => println!("{}", err.to_string())
        }
    }
}

//
// rc1_decode.rs : 有限文脈モデル (order-1, 復号)
//
//                 Copyright (C) 2018-2024 Makoto Hiroi
//
extern crate bitree;
extern crate rangecoder;

use std::fs::File;
use std::io::prelude::*;
use std::io::BufWriter;
use bitree::BITree;
use rangecoder::Decoder;
use std::collections::HashMap;

fn decode_file(src: &String, dst: &String) -> std::io::Result<()> {
    let mut rd = Decoder::open(src)?;
    let mut wr = BufWriter::new(File::create(dst)?);
    let mut ht = HashMap::new();
    let mut c0 = 0;
    loop {
        if !ht.contains_key(&c0) {
            ht.insert(c0, BITree::new(257));
        }
        // 増分値は +16
        let c = rd.decode(ht.get_mut(&c0).unwrap(), 16)?;
        if c == 256 { break; }
        wr.write(&mut [c as u8])?;
        c0 = c;
    }
    Ok(())
}

fn main() {
    let args: Vec<_> = std::env::args().collect();
    if args.len() < 3 {
        println!("usage: rc1_decode input_file output_file");
    } else {
        match decode_file(&args[1], &args[2]) {
            Ok(_) => (),
            Err(err) => println!("{}", err.to_string())
        }
    }
}

●order-2

//
// rc2_encode.rs : 有限文脈モデル (order-2, 符号化)
//
//                 Copyright (C) 2018-2024 Makoto Hiroi
//
extern crate bitree;
extern crate rangecoder;

use std::fs::File;
use std::io::prelude::*;
use std::io::BufReader;
use bitree::BITree;
use rangecoder::Encoder;
use std::collections::HashMap;

fn encode_file(src: &String, dst: &String) -> std::io::Result<()> {
    let mut ht = HashMap::new();
    let mut wr = Encoder::create(dst)?;
    let rd = BufReader::new(File::open(src)?);
    let mut c0: u16 = 0;
    for r in rd.bytes() {
        let c = r?;
        if !ht.contains_key(&c0) {
            ht.insert(c0, BITree::new(257));
        }
        // 増分値は +32
        wr.encode(ht.get_mut(&c0).unwrap(), c as u32, 32)?;
        c0 = (c0 << 8) + c as u16;
    }
    // EOF を書き込む
    if !ht.contains_key(&c0) {
        ht.insert(c0, BITree::new(257));
    }
    wr.encode(ht.get_mut(&c0).unwrap(), 256, 32)?;
    Ok(())
}

fn main() {
    let args: Vec<_> = std::env::args().collect();
    if args.len() < 3 {
        println!("usage: rc2_encode input_file output_file");
    } else {
        match encode_file(&args[1], &args[2]) {
            Ok(_) => (),
            Err(err) => println!("{}", err.to_string())
        }
    }
}

//
// rc2_decode.rs : 有限文脈モデル (order-2, 復号)
//
//                 Copyright (C) 2018-2024 Makoto Hiroi
//
extern crate bitree;
extern crate rangecoder;

use std::fs::File;
use std::io::prelude::*;
use std::io::BufWriter;
use bitree::BITree;
use rangecoder::Decoder;
use std::collections::HashMap;

fn decode_file(src: &String, dst: &String) -> std::io::Result<()> {
    let mut rd = Decoder::open(src)?;
    let mut wr = BufWriter::new(File::create(dst)?);
    let mut ht = HashMap::new();
    let mut c0: u16 = 0;
    loop {
        if !ht.contains_key(&c0) {
            ht.insert(c0, BITree::new(257));
        }
        // 増分値は +32
        let c = rd.decode(ht.get_mut(&c0).unwrap(), 32)?;
        if c == 256 { break; }
        wr.write(&mut [c as u8])?;
        c0 = (c0 << 8) + c as u16;
    }
    Ok(())
}

fn main() {
    let args: Vec<_> = std::env::args().collect();
    if args.len() < 3 {
        println!("usage: rc2_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 を圧縮してみましょう。

表：The Large Corpus と ptt5 の評価結果
ファイル名サイズorder-0order-1order-2
bible.txt 4,047,3922,196,4081,640,9401,250,370
e.coli 4,638,6901,165,7011,154,0271,143,803
world192.txt 2,473,4001,543,9041,127,912882,226
ptt5 513,216 76,81653,96058,164

有限文脈モデルはテキストファイルとの相性が良く、次数を上げると圧縮率が大幅に向上します。ただし、ptt5 のように order-1 のほうが高い圧縮率になることもあります。興味のある方はいろいろ試してみてください。

●プログラムの改訂

今までは構造体 Encoder と Decoder にメソッド encode() と decode() を持たせていましたが、それを出現頻度表を表す構造体に移すことにします。そして、クレート bitree を frequency に、構造体 BITree を Freq に変更します。

メソッド encode() には Encoder を渡し、decode() には Decoder を渡すように修正します。

●適応型レンジコーダ (桁上がりなし)

//
// rangecoder.rs : 適応型レンジコーダ
//
//                 Copyright (C) 2018-2024 Makoto Hiroi
//
use std::fs::File;
use std::io::{Result, BufReader, Read, BufWriter, Write};

// 定数
const MAX_RANGE: u32 = 0xffffffff;
const MIN_RANGE: u32 = 0x10000;
const MASK1: u32     = 0xff000000;
const SHIFT: u32     = 24;

//
// 桁上がりのないレンジコーダ
//

// 符号化
pub struct Encoder {
    writer: BufWriter<File>,
    pub range: u32,
    pub low: u32
}

impl Encoder {
    // ライトオープン
    pub fn create(filename: &str) -> std::io::Result<Encoder> {
        let fs = File::create(filename)?;
        Ok(Encoder { writer: BufWriter::new(fs), range: MAX_RANGE, low: 0})
    }

    // 正規化
    pub fn normalize(&mut self) -> std::io::Result<()> {
        while self.low & MASK1 == (self.low + self.range) & MASK1 {
            self.writer.write(&mut [(self.low >> SHIFT) as u8])?;
            self.low = self.low << 8;
            self.range <<= 8;
        }
        while self.range < MIN_RANGE {
            self.range = (MIN_RANGE - (self.low & (MIN_RANGE - 1))) << 8;
            self.writer.write(&mut [(self.low >> SHIFT) as u8])?;
            self.low = self.low << 8;
        }
        Ok(())
    }
}

impl Drop for Encoder {
    fn drop(&mut self) {
        self.writer.write(&mut [((self.low >> 24) & 0xff) as u8]).unwrap();
        self.writer.write(&mut [((self.low >> 16) & 0xff) as u8]).unwrap();
        self.writer.write(&mut [((self.low >> 8) & 0xff) as u8]).unwrap();
        self.writer.write(&mut [(self.low & 0xff) as u8]).unwrap();
    }
}

pub struct Decoder {
    reader: BufReader<File>,
    pub code: u32,
    pub range: u32,
    pub low: u32
}

impl Decoder {
    // リードオープン
    pub fn open(filename: &str) -> Result<Decoder> {
        let fs = File::open(filename)?;
        let mut rd = BufReader::new(fs);
        let mut c = 0;
        for _ in 0 .. 4 {
            let mut buff = [0u8; 1];
            rd.read(&mut buff)?;
            c = (c << 8) + buff[0] as u32;
        }
        Ok(Decoder { reader: rd, code: c, range: MAX_RANGE, low: 0 })
    }

    // 正規化
    pub fn normalize(&mut self) -> std::io::Result<()> {
        let mut buff = [0u8; 1];
        while self.low & MASK1 == (self.low + self.range) & MASK1 {
            self.reader.read(&mut buff)?;
            self.code = (self.code << 8) + buff[0] as u32;
            self.low = self.low << 8;
            self.range <<= 8;
        }
        while self.range < MIN_RANGE {
            self.reader.read(&mut buff)?;
            self.range = (MIN_RANGE - (self.low & (MIN_RANGE - 1))) << 8;
            self.code = (self.code << 8) + buff[0] as u32;
            self.low = self.low << 8;
        }
        Ok(())
    }
}

●出現頻度表 (Binary Indexed Tree)

//
// frequency.rs : 出現頻度表 (Binary Indexd Tree)
//
//                Copyright (C) 2018-2024 Makoto Hiroi
//
extern crate rangecoder;
use rangecoder::{Encoder, Decoder};

// 定数
const LIMIT: u32 = 0x8000;    // rangecoder::MIN_RANGE (0x10000) 以下の値を選ぶこと

// 出現頻度表 (BIT)
pub struct Frequency {
    table: Vec<u32>,
    sum: u32,
    mid: usize
}

impl Frequency {
    pub fn new(n: usize) -> Frequency {
        let mut m = 1;
        while m < n / 2 { m *= 2; }
        let mut tree = Frequency { table: vec![0; n], sum: 0, mid: m };
        for i in 0 .. n as u32 { tree.inc(i, 1); }
        tree
    }

    // 累積度数を求める
    fn cumul(&self, mut c: u32) -> u32 {
        let mut n = 0;
        if c > 0 {
            n = self.table[0];
            c -= 1;
            while c > 0 {
                n += self.table[c as usize];
                c = c & (c - 1);
            }
        }
        n
    }

    // 出現頻度を求める
    fn get_prob(&self, mut c: u32) -> u32 {
        let mut val = self.table[c as usize];
        if c > 0 && c & 1 == 0 {
            let p = c & (c - 1);
            c -= 1;
            while c != p {
                val -= self.table[c as usize];
                c = c & (c - 1);
            }
        }
        val
    }

    // 出現頻度の更新
    fn inc(&mut self, c: u32, n: u32) {
        let mut c = c as i32;
        if c > 0 {
            let k = self.table.len() as i32;
            while c < k {
                self.table[c as usize] += n;
                c += c & (- c);
            }
        } else {
            self.table[0] += n;
        }
        self.sum += n;
    }

    fn dec(&mut self, c: u32, n: u32) {
        if c > 0 {
            let mut c = c as i32;
            let k = self.table.len() as i32;
            while c < k {
                self.table[c as usize] -= n;
                c += c & (- c);
            }
        } else {
            self.table[0] -= n;
        }
        self.sum -= n;
    }

    fn halve(&mut self) {
        for i in 0 .. self.table.len() as u32 {
            let n = self.get_prob(i) / 2;
            if n > 0 {
                self.dec(i, n);
            }
        }
    }

    // 記号の探索
    fn search_code(&self, value: u32) -> (u32, u32) {
        let mut c = 0;
        let mut n = 0;
        if self.table[0] <= value {
            let mut h = self.mid;
            n = self.table[0];
            while h > 0 {
                if c + h < self.table.len() && n + self.table[c + h] <= value {
                    n += self.table[c + h];
                    c += h;
                }
                h /= 2;
            }
            c += 1;
        }
        (c as u32, n)
    }

    // 符号化
    pub fn encode(&mut self, rc: &mut Encoder, c: u32, n: u32) -> std::io::Result<()> {
        let temp = rc.range / self.sum;
        rc.low += self.cumul(c) * temp;
        rc.range = self.get_prob(c) * temp;
        rc.normalize()?;
        self.inc(c, n);
        if self.sum >= LIMIT { self.halve(); }
        Ok(())
    }
    
    // 復号
    pub fn decode(&mut self, rc: &mut Decoder, n: u32) -> std::io::Result<u32> {
        let temp = rc.range / self.sum;
        let (c, m) = self.search_code((rc.code - rc.low) / temp);
        rc.low += temp * m;
        rc.range = temp * self.get_prob(c);
        rc.normalize()?;
        self.inc(c, n);
        if self.sum >= LIMIT {
            self.halve();
        }
        Ok(c)
    }
}
初版 2018 年 1 月 28 日
改訂 2024 年 12 月 30 日