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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.89
Nihau
0 / 0 / 0
Регистрация: 28.02.2011
Сообщений: 27
#1

LZW сжатие - C++

26.05.2011, 19:10. Просмотров 2561. Ответов 3
Метки нет (Все метки)

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

LZW C++ - C++
Кто знает где можно скачать исходники программы для компрессии/декомпрессии текстовых файлов использующую алгоритм сжатия LZW ?

LZW-алгоритм и бинарные файлы - C++
Добрый день. Вы не могли бы мне помочь разобраться с одной деталью? Суть вот в чём: На днях я нашёл полезный исходник алгоритма lzw ...

Разработать архиватор по алгоритму LZW - C++
Нужно разработать архиватор по алгоритму LZW!!! Помогите плиз!!! срочно,курсовая!

сжатие изображения - C++
хочу написать программку на C++ , желательно C++ Builder 6 которая сжимает изображение и востанавливает с помощью вейвлетов, но не знаю как.

Вероятностное сжатие - C++
Здравствуйте, мне нужно реализовать вероятностное сжатие. Но я даже не знаю с какой стороны подойти, а гугл ни чего толкогово мне не...

Сжатие изображения - C++
У меня есть массив байт изображения. Изображение в ARGB формате. Размер известен и постоянен 256 на 256. Как мне эту картинке уменьшить...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
schdub
2946 / 1290 / 238
Регистрация: 19.01.2009
Сообщений: 3,385
Завершенные тесты: 1
26.05.2011, 22:57 #2
Цитата Сообщение от Nihau Посмотреть сообщение
и мне кажется что его нужно хранить как бинарный
Правильно кажется; запостили бы Вы свою чудо программу , а то я впервые слышу об архиваторе, который компрессит в текст, да еще между байтиками пробелы ставит - было бы интересно посмотреть

Сами посчитайте: один байт в бинарном представлении, если представлять hex'ом в тексте уже превращаются в два, добавьте еще количество пробелов - это еще по одному байту, на каждый пробел, да и если используются символы "\r\n" для перевода на новую строку - по два байта на каждую строку. Ну а ежели вы используете UNICODE (wchar_t) для представления текстовых строк, то получившееся на предыдущем шаге, еще нужно умножить на два
Nihau
0 / 0 / 0
Регистрация: 28.02.2011
Сообщений: 27
27.05.2011, 04:36  [ТС] #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 бита на каждый символ
Это как-то не очень согласуется со словом "сжатие" в заголовке темы.
Это скорее расширение.

MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.05.2011, 11:13
Привет! Вот еще темы с ответами:

Сжатие кода - C++
Добрый день. Есть код:if((globalReplace = edit-&gt;replacement()).isEmpty()) { for(j = 0; j &lt;...

Сжатие Хаффмана - C++
Есть прога, реализующая сжатие Хаффмана: #include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;map&gt; #include...

Сжатие Хаффмана - C++
Как изменить данный алгоритм, чтобы ограничить длину кода символа заданным числом Nmax? Спасибо! #include &quot;stdafx.h&quot; #include...

Сжатие массива - C++
В одномерном массиве, состоящем из n вещественных элементов, вычислить: максимальный элемент массива; сумму элементов массива,...


Искать еще темы с ответами

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru