• 岚岚岚1
    了解作者
  • C/C++
    开发工具
  • 11KB
    文件大小
  • rar
    文件格式
  • 0
    收藏次数
  • 1 积分
    下载积分
  • 2
    下载次数
  • 2020-11-15 12:45
    上传日期
压缩算法,LZW ,数据压缩的LZW算法,c语言实现。
LZW.rar
  • LZW
  • data_structure.h
    2.5KB
  • decompress_func.h
    671B
  • DCT.c
    3.6KB
  • decompress.c
    1.6KB
  • compress_func.h
    650B
  • file.h
    384B
  • compress.c
    3.3KB
  • compress_func.c
    2.4KB
  • Makefile
    496B
  • util.c
    892B
  • data_structure.c
    9.2KB
  • util.h
    437B
  • decompress_func.c
    4.7KB
  • file.c
    868B
内容介绍
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <assert.h rel='nofollow' onclick='return false;'> #include "data_structure.h" // define the hash table capacity // 4096 (12 bits) * capacity factor // in order to reduce hash collision #define CAPACITY (SIZE_LIMIT * CAPACITY_FACTOR) // dictionary, create an empty node Node node_create(const Key k, const CodeWord cw, Node next); // dictionary, delete the node Node node_delete(Node); // calculate the hash value Index calculate_index(const char* s){ assert(s != NULL); Index val = 0; int ch; // iterate around the string, extract char one by one while (*s != '\0'){ // extract this char, make sure it is positive ch = *s; if (ch < 0){ ch += 256; } // left shift the last value and then add the new char val = (val << 3) + ch; // move to the next char s += 1; } // extract the index, index must be >= 0 val = val % CAPACITY; while (val < 0){ val += CAPACITY; } return val; } // create the dictionary, insert 256 chars + 1 for EOF and 1 for reflux // so that the 256 and 257 index are reserved // size = 4096, current_num = 258, so next index start at 258 during insert Dictionary dictionary_create(void){ Dictionary d = (struct _Dictionary*) malloc (sizeof(struct _Dictionary)); assert(d != NULL); d->nodes = (Node*) malloc (CAPACITY * sizeof(Node)); assert(d->nodes != NULL); for (Index i = 0; i < CAPACITY; i++){ d->nodes[i] = NULL; } // fill the hash table with initial values 0 - 255 d->current_num = 256 + 2; // initially 256 char + 1 for EOF + 1 for reflush return d; } // release memory of the dictionary Dictionary dictionary_destroy(Dictionary d){ assert(d != NULL); // use recursion to free all nodes for (Index i = 0; i < CAPACITY; i++){ if (d->nodes[i] != NULL){ node_delete(d->nodes[i]); } } free(d->nodes); d->nodes = NULL; free(d); d = NULL; return d; } // reset dictionary if it is full, // to reflect more local characteristics. // reset = destroy + create Dictionary dictionary_reset(Dictionary d){ assert(d != NULL); d = dictionary_destroy(d); d = dictionary_create(); return d; } // check if is full, if full, need reset bool dictionary_is_full(Dictionary d){ assert(d != NULL); // note that the capacity is a multiple of 4096 // but when we reach 4096 items, we do the reflush !!! return d->current_num == SIZE_LIMIT; } // check if the key exist, // if exist return the index, if not return -1 CodeWord dictionary_search(Dictionary d, const Key k){ assert(d != NULL && k != NULL); CodeWord result; // if it is a single char, simply return its int if (strlen(k) == 1){ int idx = k[0]; if (idx < 0){ idx += 256; } result = idx; } else{ // for string of length >= 2 Index hidx = calculate_index(k); if (d->nodes[hidx] == NULL){ result = -1; } else{ // if see the exact key, then return the index Node n = d->nodes[hidx]; while (n != NULL && strcmp(n->k, k) != 0){ n = n->next; } if (n == NULL){ result = -1; } else{ result = n->cw; // find the key, return the codeword } } } return result; } // insert key-cw pair into the dictionary // if hash index position is null, insert // if not null, find the end of the linked table, then insert CodeWord dictionary_insert(Dictionary d, const Key k){ assert(d != NULL && k != NULL); // calculate the hash index Index hidx = calculate_index(k); assert(hidx >= 0); // assign the codeword CodeWord cw = d->current_num; if (d->nodes[hidx] == NULL){ d->nodes[hidx] = node_create(k, cw, NULL); } else{ Node n = d->nodes[hidx]; while (n->next != NULL){ n = n->next; } n->next = node_create(k, cw, NULL); } // update the counter d->current_num += 1; return cw; } // debug use: print the dictionary void dictionary_print(Dictionary d){ assert(d != NULL); fprintf(stdout, "-----Dictionary print-----\n"); fprintf(stdout, "Size = %d, current_num = %ld\n", SIZE_LIMIT, d->current_num); for (Index i = 0; i < CAPACITY; i++){ if (i <= 255){ // single char range fprintf(stdout, "[%ld] %c => %ld ", i, (int)i, i); if (d->nodes[i] != NULL){ Node n = d->nodes[i]; while (n != NULL){ fprintf(stdout, "%s => %ld ", n->k, n->cw); n = n->next; } } fprintf(stdout, "\n"); } else if (d->nodes[i] != NULL){ Node n = d->nodes[i]; fprintf(stdout, "[%ld] ", i); while (n != NULL){ fprintf(stdout, "%s => %ld ", n->k, n->cw); n = n->next; } fprintf(stdout, "\n"); } } fprintf(stdout, "-----End-----\n"); return; } // create a node, initialize with NULL next pointer Node node_create(const Key k, const CodeWord cw, Node next){ Node n = (Node) malloc (sizeof(struct _Node)); assert(n != NULL); // allocate memory n->k = (char*)malloc((strlen(k)+1)*sizeof(char)); // add 1 for \0 assert(n->k != NULL); // copy the key strcpy(n->k, k); // create the index and next pointer n->cw = cw; n->next = next; return n; } // recursive to delete all nodes of the dictionary Node node_delete(Node n){ if (n == NULL){ return n; } else{ node_delete(n->next); free(n->k); free(n); n = NULL; return n; } } // array functions // create // 0-255 leaves empty, also reserve 256 for EOF and 257 for Reflush Array array_create(void){ Array a = (struct _Array*) malloc (sizeof(struct _Array)); assert(a != NULL); // occupy the first 258+2 positions, but do not set anything // so that the whole ram usage can be smaller a->current_num = 256 + 2; // here we only need 4096 items // since here we do not perform hash, so no hash collision a->nodes = (char**) malloc (SIZE_LIMIT * sizeof(char*)); assert(a->nodes != NULL); for (Index i = 0; i < SIZE_LIMIT; i++){ a->nodes[i] = NULL; } return a; } // clean the array Array array_destroy(Array a){ assert(a != NULL); for (Index i = 0; i < SIZE_LIMIT; i++){ if (a->nodes[i] != NULL){ free(a->nodes[i]); a->nodes[i] = NULL; } } free(a->nodes); free(a); a = NULL; return a; } // reset = destroy + create Array array_reset(Array a){ assert(a != NULL); a = array_destroy(a); a = array_create(); return a; } // check if full bool array_is_full(const Array a){ assert(a != NULL); return a->current_num == SIZE_LIMIT; } // search using index, return the string // Key prev is included to avoid the unseen mistake // that during compression, the key is created then used straight away // without any time gap. // Also need to take care with the return key // if simply print it, it is fine // but if need to modify, make sure use strcpy first // do not change on the returned pointer directly // // malloc and copy for all answers. Key array_search(Array a, const Index idx){ assert(a != NULL && idx >= 0); Key result; // if the index <= 255, create the key and return // since the bucket is actually NULL if (idx <= 255){ result = (Key) malloc (2 * sizeof(char)); assert(result != NULL); result[0] = idx; result[1] = '\0'; } else{ as
评论
    相关推荐
    • lzw.zip
      lzw编码实现对英文文本的压缩和解压,基于c语言
    • lzw数据压缩算法C语言源码
      c语言实现lzw数据压缩算法。该代码压缩效果强于rar与zip。该代码已经封装好了,包含后直接调用函数lzw_compress(name)就可以对name文件进行压缩。
    • lzw压缩算法
      本压缩算法采用C语言,是经典的LZW算法实现,代码简练,占用资源很少,便于移植到嵌入式系统中。
    • clzw:LZW压缩算法在C语言中的实现-开源
      在C中简单,快速地实现LZW(Lempel–Ziv–Welch)数据压缩算法。-控制台编码器/解码器工具-与OS无关-可以在嵌入式项目中使用-可以与原始码流LZW功能一起使用:-硬编码的字典大小-可变代码大小-通过哈希表执行代码...
    • c语言实现lzw算法
      信息论作业 B.6输入:任意的数据文件 输出:压缩后的数据
    • lzw.rar
      可运行的C程序,采用lzw方法压缩,压缩率视文件内容,本人压缩bmp图像压缩率高达14%
    • C语言编写的LZW算法的压缩程序
      用c编写的LZW压缩程序,在dos下运行,如果文件较大的话压缩率还不错
    • GIF的C语言解码程序
      GIF的C语言解码程序,GIF的C语言解码程序
    • LZW.c.zip
      实现对LZW的编码,它的特点是不需要知道符号的概率即可进行编码
    • lzw_soft.zip
      lzw压缩解压算法源码