圧縮で固定長のビットを可変長に変える。

## LZSS圧縮
 LZSS圧縮とはなんぞやと思った方は詳しく説明しているサイトがあったのでURL貼っておきます。
 http://fussy.web.fc2.com/algo/compress5_lz.htm

 僕なりの解釈で簡単に説明すると、
 `単一の文字` or `既出文字列` で出力ファイルに出力する圧縮方法です。
 あまり詳しく知らないので違う、という方がいましたらコメントお願いします。

## したいこと。
 既出の文字列を符号化するときに3つの種類を出力します。
 `文字列かどうか`、`文字列の位置情報`、`文字列の長さ`です。
 単一文字の場合は
 `文字列かどうか`、`7ビット2進数の文字情報`で8bitで構成されております。

 私が参考にしたサンプルコードは上記のようになっており、
 復号化の際は、8bitの中の1bit目が`１→単一バイト`で`0→文字列`でした。

 そして文字列の場合は`[0][文字列の位置][文字列の長さ(4bit)]`が出力されます。
 上記4bitなのは先読みバッファが4bitのため、また、読み込み中のバッファは12bitとします。
 文字列の長さ2~17です。そのため2の時は文字列は`0000`と表現され17は`1111`と表現されます。
 どの文字列の長さでも4bit使用するのはロスがあるのでここを可変長に変えたいと思います。
 (要するに文字列の長さを固定長→可変長に変更するということ)

## サンプルソースコード
 このソースコードはC言語で構成されており`main.c`から`lzss.c`が呼び出されるという構成です。
 実際に圧縮しているのは`lzss.c`です。

```c:lzss.c

// 実際に圧縮するところだけ抜粋しています。
void compression( input, output, argc, argv )
FILE *input;
BIT_FILE *output;
int argc;
char *argv[];
{
    int i;
    int c;
    int look_ahead_bytes;
    int current_position;
    int replace_count;
    int match_length;
    int match_position;

    current_position = 1;
    for ( i = 0 ; i < 17 ; i++ ) {
        // windowにファイルから読み込んだ文字を格納(EOFがきたらbreak)
        if ( ( c = getc( input ) ) == EOF )
            break;
        window[ current_position + i ] = (unsigned char) c;
    }
    look_ahead_bytes = i;
    InitTree( current_position );
    match_length = 0;
    match_position = 0;
    while ( look_ahead_bytes > 0 ) {
        if ( match_length > look_ahead_bytes )
            match_length = look_ahead_bytes;

        // ~~~~~~~~~~ここから下が圧縮しているところ~~~~~~~~~~~~~ //
        if ( match_length <= BREAK_EVEN ) {
            replace_count = 1;
            OutputBit( output, 1 );
            OutputBits( output,
                        (unsigned long) window[ current_position ], 8 );
        } else {
            OutputBits( output,
                        (unsigned long) ( match_length - ( 1 + 1 ) ),
                        12 );
            OutputBits( output,
                        (unsigned long) match_position, 12 );
            replace_count = match_length;
        }

        // ~~~~~~~~~~~ここまで、下のfor文でバッファの移動をしている~~~~~~~~~~ //

        for ( i = 0 ; i < replace_count ; i++ ) {
            DeleteString( MOD_WINDOW( current_position + 17 ) );
            if ( ( c = getc( input ) ) == EOF )
                look_ahead_bytes--;
            else
                window[ MOD_WINDOW( current_position + 17 ) ]
                        = (unsigned char) c;
            current_position = MOD_WINDOW( current_position + 1 );
            if ( look_ahead_bytes )
                match_length = AddString( current_position, &match_position );
        }
    };
    OutputBit( output, 0 );
    OutputBits( output, (unsigned long) 0, 12 );
    while ( argc-- > 0 )
        printf( "Unknown argument: %s\n", *argv++ );
}
```

 こちらがサンプルコードで実際に変更するのは`ここから下が圧縮しているところ`である。
 下が、改良コード

```c:lzss_2.c

        if ( match_length <= BREAK_EVEN ) { //単一文字を出力
            replace_count = 1;
            OutputBit( output, 1 );
            OutputBits( output,
                        (unsigned long) window[ current_position ], 8 );
        } else { // 文字列を出力
            OutputBit( output, 0 );
            if (match_length >= 12) { // 12~17ビットの時
                OutputBits( output, 3, 2);
                OutputBits( output, (unsigned long) ( match_length - ( 1 + 1 ) ), 4 );
            } else if (match_length >= 4) { // 4~11ビットの時
                OutputBits( output, 2, 2);
                OutputBits( output, (unsigned long) ( match_length - ( 1 + 1 ) ), 3 );
            } else { // 2~3ビットの時
                OutputBit( output, 0);
                OutputBits( output, (unsigned long) ( match_length - ( 1 + 1 ) ), 1 );
            }
            OutputBits( output,
                        (unsigned long) match_position, 12 );           
            replace_count = match_length;
        }
```

 このように符号化することで復号化の際は

```c
if ( InputBit( input ) ) 
```
 で条件分岐ができるはずです。
 この課題、意図を理解するのに時間がかかったので、備忘録として残しておきます。
 がんばれ。