huffman_decoder
ハフマンデコーダができました。
<hamigaki/iostreams/utility/huffman.hpp>
huffman_decoderはこんな感じのクラスです。
template<
class Value, // 符号化前の値の型
std::size_t Bits // 符号長
>
class huffman_decoder
{
public:
typedef typename boost::uint_t<Bits>::least code_type;
typedef Value value_type;
huffman_decoder();
// 内部のベクタのメモリ確保する
void reserve(std::size_t n);
// ハフマンツリーが作成できない場合用
// デコード結果が常にxになるようにする
void assign(const value_type& x);
// code -> value の対応を登録する
void push_back(code_type code, const value_type& value);
// push_back()が終わったら呼ぶ(かっこ悪いけど)
void sort();
// ビットストリームbsからハフマンコードを読み出し、
// デコードした結果を返す
template<class InputBitStream>
value_type decode(InputBitStream& bs) const;
};ハフマン符号と値の対応をpush_back()で１個ずつベクタに追加していき、終わったらsort()でソートしておきます。
decode()はビットストリームから1ビットずつ読み込み、ベクタを二分探索しながら値を決定します。
二分探索の都合上、ハフマンコードは最上位ビットを揃える形にシフトして渡します。
以前にも書いたとおり、LHAではハフマン符号と値のペアの替わりに符号長のみを記録しています。
huffman_code_length_decoderは、この符号長からハフマンツリーを復元するクラスです。
template<
class Length // 符号長の型
>
class huffman_code_length_decoder
{
public:
typedef Length length_type;
huffman_code_length_decoder();
// 内部のベクタのメモリ確保する
void reserve(std::size_t n);
// 符号長=xを追加する
void push_back(length_type x);
// 符号長=0をn個追加する
void skip(std::size_t n);
// ハフマンツリーを復号する
template<class Value, std::size_t Bits>
void decode(huffman_decoder<Value,Bits>& decoder) const;
};作った後で知りましたが、これは「Canonical Huffman Code」と呼ばれるものらしいです。
↓解説はここが詳しいです。
http://homepage3.nifty.com/DO/chc.htm
これらを使うと、LHAのハフマンデコード処理はこうなります。
#include <hamigaki/iostreams/utility/huffman.hpp>
namespace io_ex = hamigaki::iostreams;
namespace io = boost::iostreams;
// コード長の簡易圧縮をデコードする
template<class InputBitStream>
boost::uint16_t decode_code_length(InputBitStream& bs)
{
boost::uint16_t n = bs.read_bits(3);
// 7以降は0終端の単進符号
if (n == 7)
{
while (bs.get_bit())
++n;
}
return n;
}
// 符号長のハフマンツリーを復号する
template<class InputBitStream>
void decode_code_length_huffman_tree(
InputBitStream& bs,
io_ex::huffman_decoder<boost::uint16_t,16>& tree)
{
io_ex::huffman_code_length_decoder<boost::uint16_t> decoder;
std::size_t size = bs.read_bits(5);
// ハフマンツリーを構築できない特殊ケース
if (size == 0)
{
tree.assign(bs.read_bits(5));
return;
}
decoder.reserve(size);
for (std::size_t i = 0; i < size; ++i)
{
// 0のランレングス圧縮に対する特殊処理
if (i == 3)
{
// 連続する0の数
std::size_t count = bs.read_bits(2);
decoder.skip(count);
i += count;
if (i > size)
throw std::runtime_error("LZH invalid zero-run-length");
if (i == size)
break;
}
decoder.push_back(decode_code_length(bs));
}
decoder.decode(tree);
}
// 記号(不一致文字or一致長)のハフマンツリーを復号する
template<class InputBitStream>
void decode_symbol_huffman_tree(
InputBitStream& bs,
io_ex::huffman_decoder<boost::uint16_t,16>& length_table,
io_ex::huffman_decoder<boost::uint16_t,16>& tree)
{
io_ex::huffman_code_length_decoder<boost::uint16_t> decoder;
std::size_t size = bs.read_bits(9);
// ハフマンツリーを構築できない特殊ケース
if (size == 0)
{
tree.assign(bs.read_bits(9));
return;
}
decoder.reserve(size);
for (std::size_t i = 0; i < size; )
{
// 0のランレングス圧縮に対する特殊処理
boost::uint16_t n = length_table.decode(bs);
if (n == 0)
{
decoder.skip(1);
++i;
}
else if (n == 1)
{
std::size_t count = bs.read_bits(4) + 3;
decoder.skip(count);
i += count;
}
else if (n == 2)
{
std::size_t count = bs.read_bits(9) + 20;
decoder.skip(count);
i += count;
}
else
{
decoder.push_back(n-2);
++i;
}
}
decoder.decode(tree);
}
// 符号長のハフマンツリーを復号して、記号のハフマンツリーを復号する
template<class InputBitStream>
void decode_symbol_huffman_tree(
InputBitStream& bs,
io_ex::huffman_decoder<boost::uint16_t,16>& tree)
{
io_ex::huffman_decoder<boost::uint16_t,16> decoder;
decode_code_length_huffman_tree(bs, decoder);
decode_symbol_huffman_tree(bs, decoder, tree);
}
// 一致位置のビット長のハフマンツリーを復号する
template<class InputBitStream>
void decode_offset_size_huffman_tree(
InputBitStream& bs,
io_ex::huffman_decoder<boost::uint16_t,16>& tree)
{
io_ex::huffman_code_length_decoder<boost::uint16_t> decoder;
std::size_t size = bs.read_bits(4);
// ハフマンツリーを構築できない特殊ケース
if (size == 0)
{
tree.assign(bs.read_bits(4));
return;
}
decoder.reserve(size);
for (std::size_t i = 0; i < size; ++i)
decoder.push_back(decode_code_length(bs));
decoder.decode(tree);
}
#include <boost/iostreams/detail/adapter/direct_adapter.hpp>
#include <boost/iostreams/device/array.hpp>
#include <iostream>
int main()
{
typedef io::detail::direct_adapter<io::array_source> source_type;
// "aaaaaaaaaaa"の圧縮イメージ
source_type src(
io::array_source("\x00\x03\x20\x04\x30\x71\x36\x48\x40\x08", 10)
);
io_ex::input_bit_stream<io_ex::left_to_right,source_type> bs(src);
// LZSSの出力数
std::size_t count = static_cast<boost::uint16_t>(bs.read_bits(16));
// 記号のハフマンツリー
io_ex::huffman_decoder<boost::uint16_t,16> symbol_decoder;
decode_symbol_huffman_tree(bs, symbol_decoder);
// 不一致長のビット長のハフマンツリー
io_ex::huffman_decoder<boost::uint16_t,16> offset_decoder;
decode_offset_size_huffman_tree(bs, offset_decoder);
// デコードしたLZSSの出力をとりあえずプリントアウト
for (std::size_t i = 0; i < count; ++i)
{
boost::uint16_t symbol = symbol_decoder.decode(bs);
if (symbol < 256)
{
char literal =
static_cast<char>(static_cast<unsigned char>(symbol));
// 英数/記号以外は化けます
std::cout << "literal=" << literal << std::endl;
}
else
{
boost::uint16_t length = symbol - 256 + 3;
boost::uint16_t size = offset_decoder.decode(bs);
boost::uint16_t offset = size;
if (size > 1)
offset = (1 << (size-1)) | bs.read_bits(size-1);
std::cout
<< "offset=" << offset
<< ", length=" << length
<< std::endl;
}
}
}huffman_decoderとhuffman_code_length_decoderは、コンストラクタでvectorをコピーしたくなかったので変なインタフェースになってますが、swap()でmoveすれば問題ないことにあとで気が付きました。
