Форум программистов, компьютерный форум, киберфорум
Наши страницы
Visual C++
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.50/4: Рейтинг темы: голосов - 4, средняя оценка - 4.50
nomyac
2 / 9 / 7
Регистрация: 12.10.2013
Сообщений: 43
1

Не работает должным образом LZ-78 (компрессор) c++

13.10.2013, 12:48. Просмотров 819. Ответов 7
Метки нет (Все метки)

Приветствую, форумчане! Прошу помочь с небольшим проектом. Есть код на 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
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
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
/#include <stdlib.h>
//#include <memory.h>
//#include <stdio.h>
//#include <string.h>
 
#include <io.h>
#include <fcntl.h>
#include <sys/stat.h>
 
#define OFFS_LN 8
#define BYTE_LN 8
 
//#define DICT_SIZE 254
#define DICT_SIZE ((1 << OFFS_LN) - 2)
//=========================================================
// Класс для ввода-вывода
class TPackedFile
{
    int handle;
    unsigned char buffer, mask;
public:
    void assign_read(int h);  // связывание для чтения
    void assign_write(int h); // связываение для записи
    void flush(); // заполнение нулями
 
    void putbit(bool val); // запись бита
    bool getbit(); //чтенние бита
 
    void putbits(int val, int n); // запись n битов
    int getbits(int n); // чтение n битов
};
//---------------------------------------------------------
// заполнение нулями
void TPackedFile::flush()
{
    for (int i = 0; i < 7; i++) putbit(0);
}
//---------------------------------------------------------
// связываение для записи
void TPackedFile::assign_write(int h)
{
    handle = h;
    buffer = 0;
    mask = 128;
}
//---------------------------------------------------------
// связывание для чтения 
void TPackedFile::assign_read(int h)
{
    handle = h;
    buffer = 0;
    mask = 0;
}
//---------------------------------------------------------
//чтенние бита
bool TPackedFile::getbit()
{
    if ((mask >>= 1) == 0) 
    {
        read(handle, &buffer, 1);
        mask = 128;//двоичное 10000000
    }
    return (buffer & mask) != 0;
}
//---------------------------------------------------------
// запись бита
void TPackedFile::putbit(bool val)
{
    if (val) buffer |= mask;
    if ((mask >>= 1) == 0) 
    {
        write(handle, &buffer, 1);
        buffer = 0;  
        mask = 128; //двоичное 10000000
    }
}
//---------------------------------------------------------
// запись n битов
void TPackedFile::putbits(int val, int n)
{
    int m = 1;
    for (int i = 0; i < n; i++)
    {
        putbit((val & m) != 0);
        m <<= 1;
    }
}
//---------------------------------------------------------
// чтение n битов
int TPackedFile::getbits(int n)
{
    int result = 0;
    for (int i = 0; i < n; i++)
        result |= getbit() << i;
    return result;
}
//=========================================================
 
/*
    0 - конец файла, 1 - пустая фраза
    ==> первая фраза имеет номер 2
*/
#define PHRASE_END 0
#define PHRASE_EMPTY 1
#define PHRASE_1ST 2
 
int in_file; // входной файл
int out_file; // выходной файл
int dict_pos = 0; // текущая позиция в словаре
 
static TPackedFile archive;
//=========================================================
// структура для словаря
struct dict_entry
{
    char *data; // данные
    int len; // длина
public:
    dict_entry(dict_entry *src, char c);
    dict_entry(char c);
    ~dict_entry();
    bool match(dict_entry *entry, char c); // поиск
};
//---------------------------------------------------------
dict_entry::dict_entry(char c)
{
    data = (char*)malloc(1);
    *data = c;
    len = 1;
}
//---------------------------------------------------------
dict_entry::dict_entry(dict_entry *entry, char c)
{
    len = entry->len + 1;
    data = (char*)malloc(len);
    memcpy(data, entry->data, entry->len);
    data[entry->len] = c;
}
//---------------------------------------------------------
dict_entry::~dict_entry()
{
    free(data);
}
//---------------------------------------------------------
bool dict_entry::match(dict_entry *entry, char c)
{
    if (len != (entry->len + 1)) return false;
    return data[entry->len] == c && 
        memcmp(entry->data, data, entry->len) == 0;
}
//=========================================================
dict_entry *dict[DICT_SIZE];
 
//---------------------------------------------------------
// очистка словаря
void free_dict()
{
    for (int i = 0; i < DICT_SIZE; i++)
        if (dict[i]) 
        {
            delete dict[i];
            dict[i] = 0;
        }
}
//---------------------------------------------------------
// поиск фразы
int find_phrase(int val, char c)
{
    for (int i = 0; i < dict_pos; i++)
        if ((val >= PHRASE_1ST && dict[i]->match(dict[val
            - PHRASE_1ST], c))
            || (val == PHRASE_EMPTY && dict[i]->len
            == 1 && *dict[i]->data == c))
            return i + PHRASE_1ST;
    return PHRASE_EMPTY;
}
//---------------------------------------------------------
// добавление фразы в словарь
void add_phrase(int n, char c)
{
    if (dict_pos < DICT_SIZE)
    {
        if (n == PHRASE_EMPTY)
            dict[dict_pos] = new dict_entry(c);
        else dict[dict_pos] =
            new dict_entry(dict[n - PHRASE_1ST], c);
        dict_pos++;
    }
}
//---------------------------------------------------------
// компрессия
void encode()
{
    char c;
    int num = PHRASE_EMPTY;
    while (!eof(in_file))
    {
        read(in_file, &c, 1);
        int val = find_phrase(num, c);
        if (val != PHRASE_EMPTY) num = val;
        else
        {
            archive.putbits(num, OFFS_LN);
            archive.putbits(c, BYTE_LN);
            add_phrase(num, c);
            num = PHRASE_EMPTY;
        }
    }
    if (num != PHRASE_EMPTY)
        for (int i = 0; i < dict[num - PHRASE_1ST]->len; i++)
        {
            archive.putbits(PHRASE_EMPTY, OFFS_LN);
            archive.putbits(dict[num - PHRASE_1ST]->data[i],
                BYTE_LN);
        }
    //write(out_file, "\0", 1);
    archive.putbits(PHRASE_END, OFFS_LN);
    archive.flush();
}
//---------------------------------------------------------
// декомпрессия
void decode()
{
    unsigned char num;
    char c;
    for(;;)
    {
        num = archive.getbits(OFFS_LN);
        if (num == PHRASE_END) break;
        c = archive.getbits(BYTE_LN);
        if (num >= PHRASE_1ST)
            write(out_file, dict[num - PHRASE_1ST]->data,
                dict[num - PHRASE_1ST]->len);
        write(out_file, &c, 1);
        add_phrase(num, c);
    }
}
//---------------------------------------------------------
// главная процедура
int _tmain(int argc, _TCHAR* argv[])
{
    // проверка аргументов
    if (argc < 4)
    {
        printf("Usage:\nLZ78 e in out - Encode in to out"
            "\nLZ78 d in out - decode in to out\n");
        return -1;
    }
 
    // открытие входного и выходного файлов
    in_file = open(argv[2], _O_BINARY | _O_RDWR, 
        _S_IREAD | _S_IWRITE);
    out_file = open(argv[3], _O_BINARY | _O_WRONLY | _O_CREAT
        | _O_TRUNC, _S_IREAD | _S_IWRITE);
 
    
    if (stricmp(argv[1], "e") == 0) // компрессия
    {
        archive.assign_write(out_file);
        encode();
        printf("Encoded %s to %s\n", argv[2], argv[3]);
    }
    else if (stricmp(argv[1], "d") == 0) // декомпрессия
    {
        archive.assign_read(in_file);
        decode();
        printf("Decoded %s to %s\n", argv[2], argv[3]);
    }
    else printf("Unknown command - nothing to do\n");
    
    free_dict();
    close(in_file);
    close(out_file);
 
    return 0;
}
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.10.2013, 12:48
Ответы с готовыми решениями:

PeekMessage не работает должным образом
#include&lt;windows.h&gt; #include &lt;iostream&gt; HHOOK _hook; HINSTANCE hinstDLL; int a; LRESULT...

Z-index не работает должным образом
Доброго времени суток уважаемые форумчане! Прошу совета по решению проблемы с перекрытием слоев....

Не работает должным образом клавиатура
Привет всем.Столкнулся вот с какой проблемой... девушке обновил графический драйвер ати , и тут...

Не работает меню должным образом
Здравствуйте, помогите пожалуйста!Создал категории, подкатегории..добавил товар, вывел меню, но...

Не работает должным образом тачпад
После обновления до Aniversary update пропали жесты тремя пальцами ( тремя пальцами влево/враво для...

7
XRuZzz
Антикодер
1816 / 789 / 46
Регистрация: 15.09.2012
Сообщений: 2,900
13.10.2013, 12:51 2
не пробывали классы в отдельные файлы вынести?
0
nomyac
2 / 9 / 7
Регистрация: 12.10.2013
Сообщений: 43
13.10.2013, 12:53  [ТС] 3
Цитата Сообщение от XRuZzz Посмотреть сообщение
не пробывали классы в отдельные файлы вынести?
Пока только на втором курсе, самообразованием занимаюсь, но такого ещё не умею.
0
castaway
Эксперт С++
4945 / 3051 / 455
Регистрация: 10.11.2010
Сообщений: 11,146
Записей в блоге: 10
Завершенные тесты: 1
13.10.2013, 13:16 4
Похоже что это исходник для Linux.
А тебя именно алгоритм LZ78 интересует? Или любой из LZ77, LZ78, LZW, LZSS, LZMA ?
0
13.10.2013, 13:16
gazlan
3163 / 1922 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
13.10.2013, 13:26 5
Цитата Сообщение от nomyac Посмотреть сообщение
на весь интернет нет ни одного рабочего исходника
Всё о сжатии данных, изображений и видео

Не говоря уже про сайт Марка Нельсона: LZW Revisited

Автор 7z начинал когда-то с переделок именно его программ (сводившихся, главным образом, к затиранию копирайта).
0
castaway
Эксперт С++
4945 / 3051 / 455
Регистрация: 10.11.2010
Сообщений: 11,146
Записей в блоге: 10
Завершенные тесты: 1
13.10.2013, 14:26 6
Вот реализация LZSS на Си. Может пригодиться. Откуда взял уже не помню..
Кликните здесь для просмотра всего текста
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
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
 
#define N               4096        /* size of ring buffer */
#define F               18          /* upper limit for match_length */
#define THRESHOLD       2           /* encode string into position and length if match_length is greater than this */
#define NIL             N           /* index for root of binary search trees */
 
unsigned long int       textsize = 0,                           /* text size counter */
                        codesize = 0,                           /* code size counter */
                        printcount = 0;                         /* counter for reporting progress every 1K bytes */
 
unsigned char           text_buf[N + F - 1];                    /* ring buffer of size N, with extra F-1 bytes to facilitate string comparison */
int                     match_position, match_length,           /* of longest match.  These are set by the InsertNode() procedure. */
                        lson[N + 1], rson[N + 257], dad[N + 1]; /* left & right children & parents -- These constitute binary search trees. */
FILE                    *infile, *outfile;                      /* input & output files */
 
void InsertNode(int r)
        /* Inserts string of length F, text_buf[r..r+F-1], into one of the
           trees (text_buf[r]'th tree) and returns the longest-match position
           and length via the global variables match_position and match_length.
           If match_length = F, then removes the old node in favor of the new
           one, because the old one will be deleted sooner.
           Note r plays double role, as tree node and position in buffer. */
{
        int  i, p, cmp;
        unsigned char  *key;
 
        cmp = 1;  key = &text_buf[r];  p = N + 1 + key[0];
        rson[r] = lson[r] = NIL;  match_length = 0;
        for ( ; ; ) {
                if (cmp >= 0) {
                        if (rson[p] != NIL) p = rson[p];
                        else {  rson[p] = r;  dad[r] = p;  return;  }
                } else {
                        if (lson[p] != NIL) p = lson[p];
                        else {  lson[p] = r;  dad[r] = p;  return;  }
                }
                for (i = 1; i < F; i++)
                        if ((cmp = key[i] - text_buf[p + i]) != 0)  break;
                if (i > match_length) {
                        match_position = p;
                        if ((match_length = i) >= F)  break;
                }
        }
        dad[r] = dad[p];  lson[r] = lson[p];  rson[r] = rson[p];
        dad[lson[p]] = r;  dad[rson[p]] = r;
        if (rson[dad[p]] == p) rson[dad[p]] = r;
        else                   lson[dad[p]] = r;
        dad[p] = NIL;  /* remove p */
}
 
void DeleteNode(int p)  /* deletes node p from tree */
{
        int  q;
       
        if (dad[p] == NIL) return;  /* not in tree */
        if (rson[p] == NIL) q = lson[p];
        else if (lson[p] == NIL) q = rson[p];
        else {
                q = lson[p];
                if (rson[q] != NIL) {
                        do {  q = rson[q];  } while (rson[q] != NIL);
                        rson[dad[q]] = lson[q];  dad[lson[q]] = dad[q];
                        lson[q] = lson[p];  dad[lson[p]] = q;
                }
                rson[q] = rson[p];  dad[rson[p]] = q;
        }
        dad[q] = dad[p];
        if (rson[dad[p]] == p) rson[dad[p]] = q;  else lson[dad[p]] = q;
        dad[p] = NIL;
}
 
void encode()
{
    int i, c, len, r, s, last_match_length, code_buf_ptr;
    unsigned char code_buf[17], mask;
       
    /* initialize trees */
    /* For i = 0 to N - 1, rson[i] and lson[i] will be the right and left children of node i.  These nodes need not be initialized.
    Also, dad[i] is the parent of node i.  These are initialized to NIL (= N), which stands for 'not used.'
    For i = 0 to 255, rson[N + i + 1] is the root of the tree for strings that begin with character i.
    These are initialized to NIL. Note there are 256 trees. */
    for (i = N + 1; i <= N + 256; i++) rson[i] = NIL;
    for (i = 0; i < N; i++) dad[i] = NIL;
 
    code_buf[0] = 0;  /* code_buf[1..16] saves eight units of code, and code_buf[0] works as eight flags, "1" representing that the unit
                            is an unencoded letter (1 byte), "0" a position-and-length pair (2 bytes). Thus, eight units require at most 16 bytes of code. */
    code_buf_ptr = mask = 1;
    s = 0;  r = N - F;
    for (i = s; i < r; i++) text_buf[i] = ' ';  /* Clear the buffer with any character that will appear often. */
    for (len = 0; len < F && (c = getc(infile)) != EOF; len++)
    text_buf[r + len] = c;  /* Read F bytes into the last F bytes of the buffer */
    if ((textsize = len) == 0) return;  /* text of size zero */
    for (i = 1; i <= F; i++) InsertNode(r - i);  /* Insert the F strings, each of which begins with one or more 'space' characters. Note
                                                        the order in which these strings are inserted.  This way, degenerate trees will be less likely to occur. */
 
    InsertNode( r );  /* Finally, insert the whole string just read. The global variables match_length and match_position are set. */
 
        do {
                if (match_length > len) match_length = len;  /* match_length
                        may be spuriously long near the end of text. */
                if (match_length <= THRESHOLD) {
                        match_length = 1;  /* Not long enough match.  Send one byte. */
                        code_buf[0] |= mask;  /* 'send one byte' flag */
                        code_buf[code_buf_ptr++] = text_buf[r];  /* Send uncoded. */
                } else {
                        code_buf[code_buf_ptr++] = (unsigned char) match_position;
                        code_buf[code_buf_ptr++] = (unsigned char)
                                (((match_position >> 4) & 0xf0)
                          | (match_length - (THRESHOLD + 1)));  /* Send position and
                                        length pair. Note match_length > THRESHOLD. */
                }
                if ((mask <<= 1) == 0) {  /* Shift mask left one bit. */
                        for (i = 0; i < code_buf_ptr; i++)  /* Send at most 8 units of */
                                putc(code_buf[i], outfile);     /* code together */
                        codesize += code_buf_ptr;
                        code_buf[0] = 0;  code_buf_ptr = mask = 1;
                }
                last_match_length = match_length;
                for (i = 0; i < last_match_length &&
                                (c = getc(infile)) != EOF; i++) {
                        DeleteNode(s);                /* Delete old strings and */
                        text_buf[s] = c;        /* read new bytes */
                        if (s < F - 1) text_buf[s + N] = c;  /* If the position is
                                near the end of buffer, extend the buffer to make
                                string comparison easier. */
                        s = (s + 1) & (N - 1);  r = (r + 1) & (N - 1);
                                /* Since this is a ring buffer, increment the position
                                   modulo N. */
                        InsertNode(r);        /* Register the string in text_buf[r..r+F-1] */
                }
                if ((textsize += i) > printcount) {
                        printf("%12ld\r", textsize);  printcount += 1024;
                                /* Reports progress each time the textsize exceeds
                                   multiples of 1024. */
                }
                while (i++ < last_match_length) {        /* After the end of text, */
                        DeleteNode(s);                                        /* no need to read, but */
                        s = (s + 1) & (N - 1);  r = (r + 1) & (N - 1);
                        if (--len) InsertNode(r);                /* buffer may not be empty. */
                }
        } while (len > 0);        /* until length of string to be processed is zero */
        if (code_buf_ptr > 1) {                /* Send remaining code. */
                for (i = 0; i < code_buf_ptr; i++) putc(code_buf[i], outfile);
                codesize += code_buf_ptr;
        }
        printf("In : %ld bytes\n", textsize);        /* Encoding is done. */
        printf("Out: %ld bytes\n", codesize);
        printf("Out/In: %.3f\n", (double)codesize / textsize);
}
 
void decode() /* Just the reverse of Encode(). */
{
    int i, j, k, r, c;
    unsigned int flags;
 
    for ( i = 0; i < N - F; i++ ) text_buf[i] = ' ';
 
    r = N - F;
    flags = 0;
    for ( ; ; ) {
        if ( ((flags >>= 1) & 256) == 0 ) {
            if ( (c = getc( infile )) == EOF ) break;
            flags = c | 0xff00; /* uses higher byte cleverly to count eight */
        }
        if ( flags & 1 ) {
            if ( (c = getc( infile )) == EOF ) break;
            putc( c, outfile );
            text_buf[r++] = c;
            r &= (N - 1);
        } else {
            if ( (i = getc( infile )) == EOF ) break;
            if ( (j = getc( infile )) == EOF ) break;
            i |= ((j & 0xf0) << 4);  j = (j & 0x0f) + THRESHOLD;
            for ( k = 0; k <= j; k++ ) {
                c = text_buf[(i + k) & (N - 1)];
                putc( c, outfile );
                text_buf[r++] = c;
                r &= (N - 1);
            }
        }
    }
}
 
int main( int argc, char *argv[] )
{
    char * s;
 
    if ( argc != 4 ) {
        printf("'lzss e file1 file2' encodes file1 into file2.\n"
               "'lzss d file2 file1' decodes file2 into file1.\n");
        return 1;
    }
 
    if ( (s = argv[1], s[1] || strpbrk( s, "DEde" ) == NULL )
      || (s = argv[2], (infile  = fopen( s, "rb" )) == NULL )
      || (s = argv[3], (outfile = fopen( s, "wb" )) == NULL ) ) {
        printf( "%s\n", s );
        return 1;
    }
    if ( toupper( *argv[1] ) == 'E' )
        encode();
    else
        decode();
 
    fclose( infile );
    fclose( outfile );
 
    return 0;
}
0
XRuZzz
Антикодер
1816 / 789 / 46
Регистрация: 15.09.2012
Сообщений: 2,900
13.10.2013, 14:55 7
Цитата Сообщение от nomyac Посмотреть сообщение
Пока только на втором курсе, самообразованием занимаюсь, но такого ещё не умею.
поэтому и проблему локализовать сложно, всё в одной куче
0
gazlan
3163 / 1922 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
13.10.2013, 19:22 8
Цитата Сообщение от castaway Посмотреть сообщение
Откуда взял уже не помню
* LZSS.C -- A Data Compression Program (tab = 4 spaces)
*
* 4/6/1989 Haruhiko Okumura
*
* Use, distribute, and modify this program freely.
*
* Please send me your improved versions.
*
* PC-VAN SCIENCE
*
* NIFTY-Serve PAF01022
*
* CompuServe 74050,1022
Здесь, например: lzss.c
0
13.10.2013, 19:22
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.10.2013, 19:22

Условие цикла не работает должным образом
я добавил коментарий на том цикле ,где начало должно быть с 0 ,а не 5 так в чем собственно ошибка...

Не работает должным образом программа - работа со строками.
нужно реализовать вывод на экран всех строк содержащих двузначные числа . дан исходный текстовый...

Logitech Webcam C160 - работает не должным образом
Проблема в том, что почти всегда, после перезагрузки ПК, камера не работает должным образом. То...


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

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Опции темы

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