設計の追加

ハフマン符号化をするとファイルサイズがバイト単位からビット単位となります
終端の位置を知るため, 圧縮したファイルの先頭にファイルサイズを追加します

実装編

圧縮によってファイルをbit単位で扱うので, ファイルの入出力が少し面倒になります
bit単位のファイル入力の方はまだ需要がありそうなので,
切り出して紹介します

bit_reader.cpp


#include<iostream>
#include<fstream>
#include<string.h>
#include<vector>
#include<assert.h>
using namespace std;
void bit_reader(ifstream *ip, int read_size, unsigned int* read_bit, int *buffer_size,unsigned int *buffer, int max_buffer_size, int fread_min_size);

int main(int argc, char** argv){
    char *infilename ="input1.txt";

    ifstream infp;
    infp.open( infilename, ios::in | ios::binary );
    if(!infp){
        cout << "open failed " << infilename << endl;
        return 1;
    }

    /*読み出すbit単位, この場合4bitずつ16回読み出す*/
    vector<int> read_bits(16,4);

    unsigned int buffer = 0;
    const int max_buffer_size = sizeof(unsigned int)*8;
    int buffer_size = 0;
    const int fread_min_size = sizeof(unsigned char)*8;
    for(int i=0;i<max_buffer_size/fread_min_size;++i){
        if(!infp.eof()){
            unsigned char c;
            infp.read((char*)&c, sizeof(unsigned char));
            buffer <<= fread_min_size;
            buffer |= (unsigned int)c;
            buffer_size += fread_min_size;          
        }else{
            break;
        }
    }

    for(auto i=read_bits.begin();i!= read_bits.end();++i){
        unsigned int read_bit;
        bit_reader(&infp, (*i), &read_bit, &buffer_size, &buffer, max_buffer_size, fread_min_size);
        cout << read_bit << " ";
    }
}

/*
read_size: 読み出すbit数
read_bit: 読み出したbitを格納する変数
buffer_size: bufferに入ってるbitの数
buffer: buffer本体
max_buffer_size: bufferのbit数(unsigned intなので32)
fread_min_size: ファイルから読み出すbit数(unsigned charなので8)
*/
void bit_reader(ifstream *ip, int read_size, unsigned int* read_bit, int *buffer_size,unsigned int *buffer, int max_buffer_size, int fread_min_size){
    assert((*buffer_size) > read_size);
    (*read_bit) = (*buffer) >> (max_buffer_size - read_size);
    (*buffer) <<= read_size;
    (*buffer_size) -= read_size;
    int ref = (max_buffer_size - (*buffer_size)) / fread_min_size;
    if(ref>0){
        for(int i=0;i<ref;++i){
            if(!ip->eof()){
                unsigned char c;
                ip->read((char*)&c, sizeof(unsigned char));
                (*buffer) |= ((unsigned int)c) << (max_buffer_size - (*buffer_size) - fread_min_size);
                (*buffer_size) += fread_min_size;
            }else{
                return;
            }
        }
    } 
}

ファイルからバイト単位で読み出した値をいったんバッファリングして,
bit単位で読み出しています

使い方

% cat input1.txt
abcdefghijk
% ./a.out
6 1 6 2 6 3 6 4 6 5 6 6 6 7 6 8

解凍編

解凍のコードも書けたので, 追記します
githubにもpushしてあります


% cat test1.txt
aaabbbbcccccaaaaabbbbccc

% ./comp test1.txt test
test1.txt size: 26byte
after LZSS size: 15byte
output tree size: 8byte
output tree size: 9byte
not tree huffman size: 13byte
after Huffman size: 31byte

% ./decomp  test test2.txt
test size: 31byte
huff size: 15byte
after Huffman size: 15byte
after LZSS size: 26byte

% cat test2.txt
aaabbbbcccccaaaaabbbbccc

おさぼりハンドメイクZIP続き(bit単位での入出力)

設計の追加

実装編

解凍編