lzw_compressor.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct{
    int* comped;
    int len;
} lzw_comped;

/*
目標: LZW圧縮アルゴリズム https://kano.arkoak.com/2014/07/27/lzw/
*/

//プロトタイプ宣言

char* substr(char* string, int start, int length);
lzw_comped lzw_c(char raw_c[], int length);
int getDicpage(char* dic_str,int* dic_len, int dic_pages, char* target, int target_len);

//メイン

int main(){
    char raw[] = "01230123012";
    //char raw[] = "10010010";

    lzw_comped comped = lzw_c(raw, sizeof(raw) / sizeof(char));
    //printf("%d\n", sizeof(comped) / sizeof(int));

    //free(comped);

    return 0;
}

//ユーザー定義関数

lzw_comped lzw_c(char raw_c[], int length){//※freeすること(output)
    printf("==================================\n");
    printf("lzw_c |Raw: %s\n", raw_c);

    printf("lzw_c |Compressed: ");

    //出力
    int output_len = 0;
    int* output = malloc(sizeof(int));

    //辞書
    int dic_pages = 0;//ページ数
    int str_len = 0;//dic_strの長さ
    int *dic_len = malloc(sizeof(int));//各文字列の長さ記録用配列
    char *dic_str = calloc(1 ,sizeof(char));//文字配列
    int exist_flag = 0;

    /*辞書の初期化(手順0)*/
    for(int i = 0; i < length && raw_c[i] != '\0'; i++){
        exist_flag = 0;
        for(int j = 0; j < dic_pages; j++){
            if(dic_str[j] == raw_c[i]){
                exist_flag = 1;
                break;
            }
        }
        if(!exist_flag){
            //printf("dic   ||Rgister <%c> to page[%d]\n", raw_c[i], dic_pages);
            dic_pages++;
            int *temp_len = realloc(dic_len, sizeof(int) * dic_pages);
            if(temp_len == NULL){
                printf("ERROR|dic_len realloc failed\n");
                exit(1);
            }
            char *temp_str = realloc(dic_str, sizeof(char) * dic_pages);
            if(temp_str == NULL){
                printf("ERROR|dic_str realloc failed\n");
                exit(1);
            }
            dic_len = temp_len;
            dic_str = temp_str;
            str_len += 1;
            dic_len[dic_pages - 1] = 1;
            dic_str[dic_pages - 1] = raw_c[i];
        }
    }
    //printf("dic   |Initializing Finished\n");

    /*手順1 先頭の一文字を読み込んで、変数 w に格納する*/
    int w_len = 1;
    int w_page = 0;
    char *w = calloc(1, sizeof(char));
    w[0] = raw_c[0];

    char k;
    int output_page;

    int temp_page;
    for(int i = 1; i < length && raw_c[i] != '\0'; i++){
        k = raw_c[i];

        int wk_len = w_len + 1;
        char *wk = calloc(wk_len, sizeof(char));

        for(int i = 0; i < w_len; i++){
            wk[i] = w[i];
        }
        wk[wk_len - 1] = k; 

        temp_page = getDicpage(dic_str, dic_len, dic_pages, wk, wk_len);
        if(temp_page != -1){//存在する
            free(w);
            char* w = malloc(sizeof(char) * wk_len);
            w_len = wk_len;
            memcpy(w, wk, wk_len);
            if(!(i+1 < length && raw_c[i+1] != '\0')){
                //出力
                printf("%d", temp_page);
            }
        }else{//存在しない
            //printf("dic   ||Rgister <%s> to page[%d]\n", wk, dic_pages);
            dic_pages++;
            str_len += wk_len;

            int *temp_len = realloc(dic_len, sizeof(int) * dic_pages);
            if(temp_len == NULL){
                printf("dic   |dic_len realloc failed\n");
                exit(1);
            }
            char *temp_str = realloc(dic_str, sizeof(char) * str_len);
            if(temp_str == NULL){
                printf("dic   |dic_str realloc failed\n");
                exit(1);
            }
            dic_len = temp_len;
            dic_str = temp_str;

            dic_len[dic_pages - 1] = wk_len;
            for(int j = 0; j < wk_len; j++){
                dic_str[str_len - wk_len + j] = wk[j];
            }

            /*出力*/
            printf("%d", getDicpage(dic_str, dic_len, dic_pages, w, w_len));

            //wを次へ進める
            free(w);
            w_len = 1;
            w = calloc(1, sizeof(char));
            w[0] = raw_c[i];
        }

        free(wk);
    }

    printf("\n");

    /*int str_start = 0;
    for(int i = 0; i < dic_pages; i++){
        printf("dic   ||Page[%d]: ", i);
        for(int j = 0; j < dic_len[i]; j++) printf("%c", dic_str[str_start + j]);
        printf("\n");
        str_start += dic_len[i];
    }*/

    //printf("dic   |Indexing Finished\n");

    //メモリの開放
    free(dic_len);
    free(dic_str);
    free(w);

    printf("==================================\n");

    lzw_comped comped;

    return comped;
}

int getDicpage(char* dic_str,int* dic_len, int dic_pages, char* target, int target_len){//存在しない場合は-1、それ以外はページ数を返す
    int page = -1;
    int str_start = 0;//dic_str内調べるページの最初のキー
    for(int j = 0; j < dic_pages; j++){//wkが辞書内にあるか確認
        if(dic_len[j] != target_len){
            str_start += dic_len[j];
            continue;
        }
        char* item = substr(dic_str, str_start, dic_len[j]);
        if(memcmp(item, target, sizeof(char) * dic_len[j]) == 0){
            page = j;
            free(item);
            break;
        }
        free(item);
        str_start += dic_len[j];
    }

    return page;
}

char* substr(char* string, int start, int length){//※free()すること
    if(start < 0 || length < 0 || (strlen(string) - start) < length){
        return "";
    }
    char *text = malloc(sizeof(char) * length);
    for(int i = 0; i < length; i++){
        text[i] = string[start + i];
    }
    return text;
}

出力

==================================
lzw_c |Raw: 01230123012
----------------------------------
dic   ||Rgister <0> to page[0]
dic   ||Rgister <1> to page[1]
dic   ||Rgister <2> to page[2]
dic   ||Rgister <3> to page[3]
dic   |Initializing Finished
----------------------------------
dic   ||Output <0>
dic   ||Output <1>
dic   ||Output <2>
dic   ||Output <x>
dic   ||Output <x>
dic   ||Output <x>
dic   ||Output <・
dic   ||Output <x>
dic   ||Output <x>
----------------------------------
dic   ||Page[0]: 0
dic   ||Page[1]: 1
dic   ||Page[2]: 2
dic   ||Page[3]: 3
dic   ||Page[4]: 01
dic   ||Page[5]: 12
dic   ||Page[6]: 230
dic   ||Page[7]: x1
dic   ||Page[8]: x2
dic   ||Page[9]: x3
dic   ||Page[10]: ・
dic   ||Page[11]: x1
dic   ||Page[12]: x2
dic   |Indexing Finished
==================================
Not implemented

出力4個目、辞書のインデックス[6]からの挙動がおかしいため修正したい

実装目標
https://kano.arkoak.com/2014/07/27/lzw/

wk = "23" のとき、辞書に登録されていないにもかかわらずexist_flag == 1 となり、登録されている判定になっている
判定処理を要確認

上記処理の修正、その他ポインター関連の修正をしたところ、全てうまくいった(Revisions参照)

TODO: Outputの実装を行う

出力
https://kano.arkoak.com/2014/07/27/lzw/
のLZW アルゴリズムの例　その2によると、成功している様子。

==================================
lzw_c |Raw: 01230123012
lzw_c |Compressed: 0123468        
==================================

一応おおまかな理解ができたので一旦終了
しかし、実装しきれてない上ソースガバガバなのでいつか直したい
(outputにreallocかけると他の配列の要素の値が変わるバグが有ったので、このような無理やりな形にした)