本を読む

• データの圧縮と展開 どう書く？org

データを圧縮するcompress、展開するdecompressという関数やメソッドなどを書いてください。データはバイト列でもストリームでもそれ以外の形式でもOKです。

圧縮形式は問いませんが、できるだけ一般的なフォーマット(zip,lzhなど)でお願いします。

　お題を満たしてはいませんが、bashでハフマン符号化の表を作るところまでスクリプトを作ってみます。

#!/bin/bash

function get_bytestat() {
    od -tx1 -An | tr ' ' '\n' | grep -v '^$'| sort | uniq -c | sort -n
}

function mkhuftable() {
    local file1=$1
    local file2=$2
    local n1 n2 cs1 cs2
    while [ "$(wc -l < $file1)" -gt 1 ]; do
        {
            read -r n1 cs1
            list2fhash 1 $cs1
            read -r n2 cs2
            list2fhash 0 $cs2

            printf '%7d ' $((n1 + n2))
            echo $cs1 $cs2
            cat
        } < $file1 > $file2
        sort -n $file2 > $file1
    done
}

function list2fhash() {
    local pre=$1
    shift
    local e
    for e; do
        eval _huf_$e=$pre\$_huf_$e
    done
}

function dmupfhash() {
    local v
    for v in ${!_huf_*}; do
        echo "${v#_huf_}: ${!v}"
    done
}

tmpfile1=$(mktemp '/tmp/tmp.huf1.XXXXXXXX')
tmpfile2=$(mktemp '/tmp/tmp.huf2.XXXXXXXX')
trap 'rm -f $tmpfile1 $tmpfile2' EXIT

get_bytestat > $tmpfile1
mkhuftable $tmpfile1 $tmpfile2
dmupfhash

　外部コマンドはod、tr、grep、sort、uniq、catを使用。効率はよくありませんが、再帰にならないように、かつパイプを使って処理してみました。

　標準入力から与えられたデータから1バイト単位でハフマン符号化の表を作り、元のデータ（16進）と符号化データ（2進）を出力します。

$ echo abrakadabra | bash ./huf.bash
0a: 0101
61: 1
62: 001
64: 0100
6b: 011
72: 000