Форум программистов, компьютерный форум CyberForum.ru

LZW сжатие - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.89
Nihau
0 / 0 / 0
Регистрация: 28.02.2011
Сообщений: 27
26.05.2011, 19:10     LZW сжатие #1
Написал компрессию\декомпрессию.Сжатый файл представяет из себя текст(код символов разделенные пробелами).
Проблема в том что сжатый файл превышает размер исходного файла, и мне кажется что его нужно хранить как бинарный(последовательности 1 и 0). Или я что-то не понимаю...
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.05.2011, 19:10     LZW сжатие
Посмотрите здесь:

LZW C++ C++
Сжатие массива C++
C++ сжатие изображения
Сжатие изображения C++
Вероятностное сжатие C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
schdub
 Аватар для schdub
2902 / 1246 / 222
Регистрация: 19.01.2009
Сообщений: 3,215
Завершенные тесты: 1
26.05.2011, 22:57     LZW сжатие #2
Цитата Сообщение от Nihau Посмотреть сообщение
и мне кажется что его нужно хранить как бинарный
Правильно кажется; запостили бы Вы свою чудо программу , а то я впервые слышу об архиваторе, который компрессит в текст, да еще между байтиками пробелы ставит - было бы интересно посмотреть

Сами посчитайте: один байт в бинарном представлении, если представлять hex'ом в тексте уже превращаются в два, добавьте еще количество пробелов - это еще по одному байту, на каждый пробел, да и если используются символы "\r\n" для перевода на новую строку - по два байта на каждую строку. Ну а ежели вы используете UNICODE (wchar_t) для представления текстовых строк, то получившееся на предыдущем шаге, еще нужно умножить на два
Nihau
0 / 0 / 0
Регистрация: 28.02.2011
Сообщений: 27
27.05.2011, 04:36  [ТС]     LZW сжатие #3
предполагается что будет уходить по 32 бита на каждый символ(на самом деле чтото вроде [log(TABLE_SIZE,2)])
main.c:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include <math.h>
#include <time.h>
#include <limits.h>
#include <Windows.h>
#define TABLE_SIZE 5000
#define KEY_LEN 200
#include "tools.h"
void compress(FILE * input,FILE * output,lib * lib)
{
    char str[TABLE_SIZE];
    FILE * inp=malloc(sizeof(FILE));
    char buffer[TABLE_SIZE];
    int i=0;
    char tmp;
    int find_res=0;
    int prev_find_res=0;
    int rItoa;
    int rFind;
    while(1)
    {
        checktable(lib);
        inp->_ptr=input->_ptr;
        inp->_cnt=input->_cnt;
        tmp=fgetc(input);
        str[i]=tmp;
        i++;
        find_res=find(str,i,lib,prev_find_res);
        if (find_res==-1)
        {
            rFind=find(str,i-1,lib,prev_find_res);
            putc_bin(rFind,output);
            add(lib,str,i);
            i=0;   
            input->_ptr=inp->_ptr;
            input->_cnt=inp->_cnt;
            if (tmp==EOF)
            {  
                return;
            }
        }
        prev_find_res=find_res;
    }
}
void decompress(FILE * input, FILE * output, lib * lib)
{
    int code;
    FILE * inp=malloc(sizeof(FILE));
    int i=0;
    int p=0;
    int find;
    int last_free=0;
    char tmp=0;
    char str[TABLE_SIZE+1];
    char oldstr[TABLE_SIZE+1];
    char k;
    int old;
    old=read_code(input);
    fputc(old,output);
    k=lib->table[old].data[0];
    while(1)
    {
        code=read_code(input);
        if (code==-1)
            return;
        find=lib->table[code].data[0];
        if (find<0)
        {
            last_free=copy(str,lib->table[old].data);
            str[last_free]=k;
            last_free++;
        }
        else
        {
            last_free=copy(str,lib->table[code].data);
        }
        for (i=0;i<last_free;i++)
            fputc(str[i],output);
        k=str[0];
        last_free=copy(oldstr,lib->table[old].data);
        oldstr[last_free]=k;
        checktable(lib);
        add(lib,oldstr,last_free+1);
        old=code;
    }
}
void main(int count,char * value[])
{
    lib lib;
    int i;
    int p=-1;
    FILE * input=NULL;
    FILE * output=NULL;
    if (!strcmp(value[1],"help"))
    {
        printf("To compress: -c input_file compressed_file\n");
        printf("To decompress: -u compressed_file output_file\n");
        p=-1;
    }
    if (count==0)
    {
        printf("Enter help");
        p=-1;
    }
    if (!strcmp(value[1],"-c"))&&count
    {
        printf("peedar");
    }
    for(i=0;i<256;i++)
    {
        SafeAr[i]=i;
    }
    lib.table=malloc(sizeof(sAr)*TABLE_SIZE);
    init_lib(&lib);
    switch(p)
    {
    case 0:
        input=fopen("S:\\project\\output.lzw","rb");
        output=fopen("S:\\project\\decode.txt","wb");
        decompress(input,output,&lib);
        break;
    case 1:
        input=fopen("S:\\project\\input.txt","r");  
        output=fopen("S:\\project\\output.lzw","w");
        compress(input,output,&lib);
        break;
    default:
        break;
    }
}
tools.h:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
char SafeAr[256];
typedef
struct sAr{
    unsigned len;
    unsigned hash;
    char data[KEY_LEN];
}sAr;
typedef
struct lib{
    sAr * table;
    unsigned top;
}lib;
void init_lib(lib * lib);
int checktable(lib * lib);
void fill_random(FILE * input,int len);
int read_code(FILE * input);
int copy(char *str1,char *str2);
unsigned jenk(char *key,unsigned len);
int compare(char * str1,int len1,char * str2,int len2);
int find(char * str,unsigned len,lib * lib,unsigned apr_pos);
int add(lib * lib,char * str,int len);
void putc_bin(int code,FILE * output);
int add(lib * lib,char * str,int len)
{
    int i=lib->top;
    int p;
    int exist=0;
    i=lib->top;
    exist=find(str,len,lib,0);
    if (exist!=-1)
        return exist;
    for(p=0;p<len;p++)
    {
        lib->table[i].data[p]=str[p];
    }
 
    lib->table[i].hash=jenk(lib->table[i].data,len);
    lib->top++;
    lib->table[i].len=len;
    return i;
}
int find(char * str,unsigned len,lib * lib,unsigned apr_pos)
{
    unsigned i=0;
    unsigned hash_str=jenk(str,len);
    for(i=apr_pos;i<=lib->top;i++)
    {
        if(hash_str==lib->table[i].hash)
        {
            if (compare(lib->table[i].data,lib->table[i].len,str,len))
                return i;
        }
    }
    for(i=0;i<=apr_pos;i++)
    {
        if(hash_str==lib->table[i].hash)
        {
            if (compare(lib->table[i].data,lib->table[i].len,str,len))
                return i;
        }
    }
    return -1;
}
int compare(char * str1,int len1,char * str2,int len2)
{
    int i;
    if (len1!=len2)
        return 0;
    for (i=0;i<len1;i++)
    {
        if (str1[i]!=str2[i])
            return 0;
    }
    return 1;
}
unsigned jenk(char *key,unsigned len)
{
    unsigned hash = 0;
    unsigned i;
    for (i=0; i<len; i++)
    {
        hash += key[i];
        hash += (hash << 10);
        hash ^= (hash >> 6);
    }
    hash += (hash << 3);
    hash ^= (hash >> 11);
    hash += (hash << 15);
    return hash;
}
int copy(char *str1,char *str2)
{
    int p=0;
    while (str2[p]>-1)
    {
        str1[p]=str2[p];
        p++;
    }
    str1[p]=-52;
    return p;
}
int read_code(FILE * input)
{
    int i=0;
    char tmp;
    char code[TABLE_SIZE+1];
    tmp=fgetc(input);
    if (tmp==EOF)
    {
        return -1;
    }
    while (!isspace(tmp))
    {
        code[i]=tmp;
        i++;
        tmp=fgetc(input);
    }
    code[i+1]=-52;
    return atoi(code);
}
void fill_random(FILE * input,int len)
{
    int i;
    int p;
    srand(time(NULL));
    for (i=0;i<len;i++)
    {
        p=rand();
        p=p%64+64;
        fputc( p,input);
    }
}
int checktable(lib * lib)
{
    //if (table[TABLE_SIZE].i!=-1)
    if (lib->top==TABLE_SIZE)
    {
        init_lib(lib);
        return 0;
    }
    return 1;
}
void init_lib(lib * lib)
{
    int i;
    for(i=0;i<256;i++)
    {
        lib->table[i].data[0]=SafeAr[i];
        lib->table[i].data[1]=-52;
        lib->table[i].len=1;
        lib->table[i].hash=jenk(lib->table[i].data,1);
    }
    lib->top=256;
    for(i=256;i<=TABLE_SIZE;i++)
    {
        lib->table[i].data[0]=-52;
        lib->table[i].len=0;
    }
}
void putc_bin(int code,FILE * output)
{
 
    int i=0;
    int p;
    int s_Ar[32];
    while (i<32)
    {
        s_Ar[i]=(code&1);
        code=code>>1;
        i++;
    }
    fwrite(s_Ar,sizeof(int),32,output);
}
PB
27.05.2011, 11:13     LZW сжатие
  #4

Не по теме:

Цитата Сообщение от Nihau Посмотреть сообщение
предполагается что будет уходить по 32 бита на каждый символ
Это как-то не очень согласуется со словом "сжатие" в заголовке темы.
Это скорее расширение.

Yandex
Объявления
27.05.2011, 11:13     LZW сжатие
Ответ Создать тему
Опции темы

Текущее время: 04:03. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru