close

Вход

Забыли?

вход по аккаунту

?

naydenov kursach lzv

код для вставкиСкачать
??????????
???????????????? ??????? ??????................................................4
?????? ?????? ...........................................................................5
???????? ??????? - ????? - ??????.................................................9
?????? ??????????......................................................................10
????-?????.................................................................................13
??????? ?????????.....................................................................14
???????????????? ??????? ??????
? ????????????????, ???????????????? ??????? ?????? ???????????? ????? ????????? ????????????????, ? ??????? ????????? ????????? ????????? ?????????? ?????? ? ??????? ?? ?????????, ? ?? ?????????????????? ??????????????? ?????. ?????????? ??????? ??????????????? ??????????? ????? ?????? ? ????????-??????????????? ???????????????? ???????? ? ???????????, ??????????? ???????. ???? ??? ??????????? ???????????? ? ????????-??????????????? ???????????????? ??? ??????????? ??????? ? ?????? ????????? ?????? ???????????? ???????????. ???????????????? ??????? ?????? ???????? ? ??????? ????????-???????????????? ??????????????, ? ?? ????? ??? ?????????????? ?? ???? ??????????????? ????????? ?????? ????????.
????? ?????? ? ???????????????? - ??????????, ???????????? ??? ?????? ??? ?????? ??????, ??????? ? ?. ?. ? ?????? ??????.
?????? ???????? ??????? ??????????????? ??????????? ??????????? ??? ?????? ??? ?????? ?????? (? ??? ????? ??????????? ?, ? ?????????, ????????? ? ????????????), ??????? ? ???????? ?????? ????? ??????????.
????????? ??????? ???????? ? ??????????? ?????? ???????????????? ? ???? ?? ?? ?? ??? ??????????? (?? 2008 ???) ???????????? ???????. ??? ??????? ???????? ??? ??????????????? ???????????????? ??????????? ??????.
??????????? ??????????????? ??????? ????????? ????????? ????????? ?????????, ? ??????? ??????? ????????, ?????????? ?????? ????????? Unix.
?????????? ?????? ???????? ????? ? ????? ???????????????? ??, ??? ?? ???????????? ????? ???????? ????? ?/??? ?????? ??????, ?????? ??????, ????????? ? ??????, ???????????, ???? ?????? ?????????. ?????? ? ???????? ?????????? ?? ?????? ?????? ?????:
* C++: iostream ?? ??????????? ?????????? C++.
* ????? ????????? .NET Framework (????????, C#): Base Class Library, ???????????? ???? System.IO.
????? ?????? ? ???????????? ????????
?????? ??????
?????? ??????- ??????????????? ?????????????? ??????, ???????????? ? ????? ?????????? ?? ??????. ??????????? ??? ????? ????????????? ????????????? ????????? ???????? ? ???????? ??????. ???????? - ???????? ??????, ??????????, ????????? ???????????, ??????????? ?????????. ???????? ????????? ?????????? ??????????????? ?????? (???????????, ?????????????).
?????? ???????? ?? ?????????? ????????????, ???????????? ? ???????? ??????. ?????????? ???????? ???????????? ???????? ?????????? ? ?????? ?????????? (????????, ???? ????????????? ??? ????????? ?????). ???????? ???????????? ?????? ??????????? ??????? ????????????? ?????????????????? ??????? ?? ??? ?????????????? ???????? ? ????????? ??? ?????. ?????? ??? ???????????? ?????? ? ???, ??? ????????? ???????? ? ????????? ?????? ??????????? ???? ??????. ?????????? ?????? ?????? ??????????? ?? ???? ?????? ????? ????????????? ?????? ????????? ???????? ???????, ? ?????? - ???????? (??????????? ???????????). ?????? ??????, ?? ?????????? ????????? ???????????? (????????, ????????? ?????? ??? ????? ???, ????????????? ?????????), ????????????? ?????????? ??? ??????.
? ?????? ?????? ??????? ?????? ????? ?????? ????????? ??????, ???, ??????, ?????? ????????????. ????? ???????, ??? ?????? ?????? ???????????? ????????? ????????? ???????? ? ???, ?????? ???? ?????? ?????????. ?? ??????? ?????? ?????????? ?? ?????????, ?????????? ??????? ??????? ????????????? ? ??????????????, ??????? ????????? ?? ????????? ????? ?????????. ?????? ???????????? ????? ???? ???????????, ?????????? ??? ????? ?????????? ?????????, ???? ????????? ??? ????????????????? ?? ????? ?????? (? ??????????????). ??????, ??????????? ?? ?????? ??????? ?????? ???????? ?????? ???????????? ??????????, ?????????? ???????????. ????????????? ???????? ?????? ?????????????????????? ?????????, ??????????? ??? ?????? ? ???????, ??????????? ?????? ????????????? ? ??????????? ????????????????. ??????????? ????? ?????????? ????????????? ?????????? ???????? ? ??? ??? ???? ???? ???????????.
??? ?????? ?????? ?????? ??????? ?? ??? ???????? ??????:
* ?????? ??? ??????
* ?????? ? ????????
??? ????????????? ?????? ??? ?????? ???????? ?????? ?????????????? ???????? ??????, ?????? ? ???????? ????????? ???????????? ?????? ? ???????????, ?????? ??????????????? ? ????? ?????? ??????????? ????????????? ??????????????? ??????. ?????? ??? ?????? ?????? ???????????? ??? ???????? ? ???????? ????????? ??????, ???????????? ????????, ???? - ??? ?????????? ?????? ?????- ? ???????????, ???????? ?????????? ? ?. ?., ? ???????, ????? ????????? ??????????? ??? ????????????. ?????? ? ????????, ?????????? ??????????? ???????, ??? ?????? ??? ??????, ??????????????, ?????? ??????????? ??? ?????????? ?????? ?????- ? ??????????? ? ???????? ?????????? ? ??? ???????, ????? ????? ?????????? ???????? ????????????, ? ?????? ???????????? ???????? ? ??????????????? ?????? ?? ?????????.
??????????? ??????
??????????? ?????? - ???????? ?????????????? ????????? ??????. ??? ???????????? ??? ????????? ?????? ???????? ???????? ?????? ? ?????? ??????, ?? ????: , ??? k - ??????????? ??????, So - ????? ???????? ??????, ? Sc - ????? ??????. ????? ???????, ??? ???? ??????????? ??????, ??? ???????? ???????????. ??????? ????????:
* ???? k = 1, ?? ???????? ?? ?????????? ??????, ?? ???? ???????? ????????? ??????????? ?? ?????? ?????? ????????;
* ???? k < 1, ?? ???????? ????????? ????????? ???????? ???????, ?????? ????????, ?? ????, ????????? "???????" ??????.
???????? ? k < 1 ?????? ???????? ??? ??????. ????????????? ?????????? ???????? ???????? ?????? ??? ??????, ??????? ??? ????? ?????? ??????????? ?? ?? ?????? ?????? ??????? ??? ?????? ?????. ??????????? ????? ????? ??????????? ? ???, ??? ????????? ????? ????????? ????????? ?????? n ??? ?????????? ????? 2n, ????? ????????? ????????? ? ?????? ??????? ??? ?????? n (??? ??????? ???? ?? ?????? ????????? ??????? ?????) ????? ?????? 2n. ??? ??????, ??? ?????????? ?????????? ??????????? ??? ???????? ????????? ??????: ???? ????????? ???????? ????????? ?? ????? ????? ??????? ?????????????, ???? ?????????? ???????? ?????????? ????? ??????????????? ???? ? ?? ?? ??????, ? ?????? ?? ?????? ????????. ?????? ???? ????? ???????? ?????? ??????????? ?????? ???????? ??????, ????? ???????? ????, ????? ?? ????? ????????????? ?? ??? ??????????? ?????, ??? ?? 1 ???. ????? ???? ? ????? ?????? ?????? ????? ????? ????? ???????????:
???????? ??? ????????? ???????: ???? ????? ?????? ?????? ?????? ?????? ????????, ?????????? ?????? ??????, ??????? ? ??? "1", ????? ?????????? ???????? ??????, ??????? ? ??? "0"). ?????? ????, ??? ??? ??????????? ?? ??????-C++, ??????? ????:
bin_data_t __compess(bin_data_t input) // bin_data_t - ??? ??????, ?????????? ???????????? ?????????????????? ??? ?????????? ?????
{
bin_data_t output = arch(input); // ??????? bin_data_t arch(bin_data_t input) ????????? ????? ???????? ?????? ??????
if (output.size()<input.size()) // ???? ????? ?????? ?????? ?????? ?????? ????????, ??????? bin_data_t::size() ?????????? ?????? ??????
{
output.add_begin(1); // ??????? bin_data_t::add_begin(bool __bit__) ????????? ???, ?????? __bit__ ? ?????? ??????????????????
return output; // ?????????? ?????? ?????????????????? ? ??????????? "1"
}
else // ????? (???? ????? ?????? ?????? ?????? ??? ????? ?????? ????????)
{
input.add_begin(0); // ????????? "0" ? ???????? ??????????????????
return input; // ?????????? ???????? ???? ? ??????????? "0"
}
}
??????????? ?????? ????? ???? ??? ?????????? (????????? ????????? ?????? ?????, ??????????? ? ?. ?., ???????? ?-?????, �-?????, ADPCM, ????????? ??????? ???????????), ??? ? ??????????. ?? ?????? ?????? ?? ????? ???? ????????? ???? ??? ??????? ??????????? ?????????, ???? ?????? ?? ????????? ?????????:
* ??????? (?????? ?? ?????????? ????????? ?????? ??????);
* ???????????? (?????? ?????????? ??????);
* ??????????? (?????? ?????????? ??????);
??? ?????-???? ??????. ??????????? ?????? ? ???????? ??? ???? ?????? ??????? ?? ?????????? ??????????? ?????? ??? ????????, ??????? ?????? ????????? ??? ???????? ?????????. ? ????? ?????? ?????????? ??????????? ?????? ???????? ?????????? ?????? ?????? ?????? ?????? ? ????????.
???????? ????????? ???????? ????? ??????????? ?????? ???????? ????????? ???? ??????? ??? ?????????? ??????. ? ????? ?????? ????????? ?????? ??? ?????? ???????????? ? ??? ??????, ??? ?? ?????????? ?????????? ???????? ??? ?????? ?????? ????, ? ?? ????? ??? ??????????? ?????????? ?????? ? ???????? ?????? ???? ??????????. ??? ????????? ????? ?????? ????????? ?? ????????? ? ????????. ? ?? ?????
* ????????????? ??????, ????????? ??????? ????????? ???????? ? ????????? ?? ?????????: ????????? ? ?? ???????? ??????, ???????? ??????? ? ?. ?.;
* ???????? ?????? ??????, ????????? ? ??????? ????? ???????? ? ??????????? ???????: ????????, ?????????? ? ??????????? ????????????? ?????????? ??? ??????????? ???????? ???????????, ??????????? ????????? ? ?. ?.;
* ??????????? ???????????? ?????? ? ?????????????? ????????????? ?????? ??? ???????????? ????????? ???????????, ???????? ? ???????????.
????????? ?????????? ??????????
????????? ????????? ????? ????????? ?????????? ?????????? ???????? ?????????????? ???????, ?? ??????? ??? ???????????:
* ??????????? ?????? (??? ????????????? ??????);
* ?????????? ?????? (??? ??? ????????? ? ?????????);
* ????????????? ???????.
? ?????, ??? ?????????? ??????? ?? ????????? ? "??????????????????" ?????????. ????? ????????? ??????: ??? ??????????? ? ????????????? ????????, ??? ??????? ?????????? ? ?????????????? ???????? ?? ???????????. ??? ?? ?????, ? ????????????? ??????? ??????? ? ?????????? ????????? ????? ???????? ?? ???? ??????? ? ?????????????. ????????? ?????????? ?????????? ?? ??????????????? ????????: ??? ????? ???????????? ????????, ??? ?? ????? ???????, ? ?????????????, ??????????, ???????? ? ??????? ??????? ?? ????? ???? ??????????.
??? ??? ????????? ?????? ? ?????????????? ???????? ? ????, ????? ???????? ??????????? ????????? ?????????? ? ???. ??????? ????? ???????? ???? ???????? ??????????? ????????? ??????. ????? ???????, ???????? ??? ????????:
???????? ?????? ??????? ??????? ?????????????? ????????, ?????? ???????? ??????????????.
??? ???????? ???????????????? ???????????, ??????????? ??? ???????, ????? ?????????? ?????? ?????? ????? ?????????????? ???????????. ? ???????? ??????? ????? ???????? ???????? ?????- ? ??????????????????.
????????? ?????? ? ?????????????? ??????? ?????????????? ?????? ?????????????? ????????.
???????? ?????????? ??????? ??? ????? ?????, ????? ?????? ? ?????????????? ?????????? ?????????? ?? ???? ?? ?????? (????????, ? ???????? ?????????).
???????? ?????? ??????????? ????? ????????????, ??? ???????? ??????????????.
????? ???????? ?????????? ??? ???????, ????? ????????? ?????? ??????????? ???????, ????? ??????????? ???????????, ??? ???????? ????? ????????? ???????? ?????? ????????, ????????, ??????????? ??????? ??? ??????? ?????????????? ???? ????????. ??? ????? ???? ????? ??????, ?????????? ??????? ????????? ? ????? ????? ???????? ???????, ???????? ?????? ????? ???????????????.
??????? ??? ???????? ??????? ? ?????? ?????? ???????????? ???????.
* ?? ?????? ???? ????????? ?????? ????????? ????????? ?????? ???? ?????????? ? ???????? ????? ?????????? ?????? ??? ???? (?? ??????????? ??????, ??????????, ??? ?? ?? ??? ????), ???? ?????? ?? ?????????? ????????? ???????? ?????????? ??????? ?? ??????????? ? ??? ?????? ?? ??? ?????????????? ????????. ????????? ?????????????? ?????? ????? ??????? ?????? ??????????? ????? ??????, ????? ?????? ????? ???????????? ??? ???????? ????????????????????? ????????.
* ??? ?????? ????????? ?????????????????? ???????? ?????????? ???? ? ?????? ?????? ??????? ?????????? ?????????? ?? ????????????? ? ?????????? ??????. ?? ?????? ???? ?????????? ??????????? ??????????? ???????? ?????????? ??????????? ??????? (???? ?????????????????? ????????). ????? ????? ??????????? ?? ??? ???? ????????????? ???????????? ???????????, ????????, ?????????????? ??????????? ??? ??????????? ????????, ??? ????????????? ????? ????????????? ??????????????????? ????????? ???????? ???????, ? ????? ????????????? - ????? ????????.
???????? ??????? - ????? - ??????
???????? ??????? - ????? - ?????? - ??? ????????????? ???????? ?????? ?????? ??? ??????, ????????? ????????? ????????, ?????? ????? ? ????? ??????. ?? ??? ??????????? ?????? ? 1984 ????, ? ???????? ?????????? ?????????? ????????? LZ78, ??????????????? ???????? ? ????? ? 1978 ????. ???????? ?????????? ???, ????? ??? ????? ???? ?????? ???????????, ?? ?? ?? ??????????? ?????????, ????????? ?? ?? ???????? ???????? ??????? ??????? ??????.
??????? "LZW" ????????? ?? ??????? ????????????? ?????????: ???????, ??? ? ????, ?? ?????? ??????????, ???, ????????? ?????? ??????????? ????[????], ?? ????? ?????? ?????????? ?????????? ???? - ??????? - ?????.
* ?????? ???????? ??? ?????? (???????????) ??????????? ??????? ??????? ?????????????? ?????: ???????????? ??????????????????? ???????? (??????) ???????? ? ???????????? ?????? ??? ????????????? ????? (?????? 12-??????). ??????? ???????????????? ????? 1-??????????? ???????? (? ?????? 8-?????? ???????? - ??? 256 ???????). ?? ???? ???????????, ???????? ????????????? ????? ?????? ?? ????????, ? ????????? ?????? ?????, ?????????? 2-?????????? ?????? ? ??????? ? ???? ???? ???/??????, ??? ??? ????????? ?? ??????????????? ?????? ??????. ????? ???? ??? ????? 2-?????????? ?????? ????????? ? ???????, ?? ????? ?????????? ??? ??????? ???????. ????? ?? ????? ???????? ????????? ??????, ??? ???? ?? ??????? ????????? ??? ????????????? ?????? ???????????? ?????, ????? ???? ? ??????? ??????????? ??? ???? ?????? ?? ????????? ???????? ?? ?????; ?? ????? ???????? ??? ???? ??????, ? ????????? ?????? ???????????? ? ???????? ?????? ????????? ??????.
????????? ????????????? ?? ????? ????????? ?????? ?????????????? ?????, ????????? ?? ????? ?????????? ??????????????? ??????? ?????????????? ??????????????? ?? ??????????????? ??????.
1. ????????????? ??????? ????? ?????????? ??????????????? ???????. ????????????? ??????? ????? W ?????? ???????? ?????????.
2. ????? ? ??????? ?????? W ?????????? ?????, ??????? ????????? ? ?????????? ????????? ?????????.
3. ??????? ????????? ?????? K ?? ??????????? ?????????.
4. ???? ?????_?????????, ?? ?????? ??? ??? W, ?????
5. ???? ????? WK ??? ???? ? ???????, ????????? ??????? ????? W ???????? WK ? ??????? ? ???? 3, ????? ?????? ??? W, ???????? WK ? ???????, ????????? ??????? ????? W ???????? K ? ??????? ? ???? 3.
6. ?????
?? ?????? ?????? ????????? ???????? LZW ????? ?????? ??????????? ??????, ??? ??????????? ??????????, ??? ????? ?????? ?????? ????????? ????? ???? ???????. ?? ???? ?????? ?????? ???????????? ?? ??????????? ??????? ?????? ??????.
???????? ??? ?????????? ? ????????? compress, ??????? ????? ????? ??? ????? ??????????? ???????? Unix-?????? ?????????????? ? 1986 ????. ????????? ?????? ?????????? ??????-??????????? ????? ?????????? ???? ????? ??? ??????? ? ????.
? 1987 ???? ???????? ???? ?????? ????????? ?? ?????? ??????????? GIF. ?? ????? ????? (???????????) ?????????????? ? ??????? TIFF.
? ????????? ?????, ???????? ?????????? ? ????????? PDF.
?????? ?????? ?????????? ???????? LZW ? ????????, ????????? ????????? ???????? ?????? ? ??????? ?? ?????? ??????, ??? ??? ???????????, ??? ? ??? ?????????????? ?????????. ? ??? ????? ??????? ????????? ?????, ?? ??????????? ??????? ????????? - ?????? ????????? ?????, ??? ?????? ?????????? ? ????????. ?????????, ??????? ????? ?????, ???????? ????????? ???????:
TOBEORNOTTOBEORTOBEORNOT#
?????? # ???????????? ??? ??????????? ????? ?????????. ??? ?????, ? ????? ???????? 27 ???????? (26 ????????? ???? ?? A ?? Z ? #). ????????? ???????????? ??? ? ???? ????? ???, ??? ????????????? ??????? ??????? ???????? ??? ?????????? ?????? ?? 5 ??? ?? ??????. ?? ???? ????? ???????, ?????? ????? ?????? ?????, ? ??? ????? ?????? ????? ????????. 5-?????? ?????? ???? 25 = 32 ????????? ?????????? ???, ???????, ????? ? ??????? ???????? 33-? ?????, ???????? ?????? ??????? ? 6-?????? ???????. ???????, ???, ????????? ???????????? ?????? ?? ???? ????? 00000, ?? 33-? ?????? ????? ??? 32. ????????? ??????? ????? ?????????:
# = 00000
A = 00001
B = 00010
C = 00011
.
.
.
Z = 11010
???????????
??? ????????????? ????????? LZW, ??? ???????? ????????? ??? ??? ???? - 25 ???????? ?? 5 ??? ?? ?????? - ??? ?????? 125 ???. ??????? ??? ? ???, ??? ?????????? ??? ????????????? LZW:
??????: ??????? ???: ????? ?????? ???????:
(?? ??????)
T 20 = 10100
O 15 = 01111 27: TO
B 2 = 00010 28: OB
E 5 = 00101 29: BE
O 15 = 01111 30: EO
R 18 = 10010 31: OR <--- ?? ?????????? ??????? ???????? ???????????? 6-?????? ?????? N 14 = 001110 32: RN
O 15 = 001111 33: NO
T 20 = 010100 34: OT
TO 27 = 011011 35: TT
BE 29 = 011101 36: TOB
OR 31 = 011111 37: BEO
TOB 36 = 100100 38: ORT
EO 30 = 011110 39: TOBE
RN 32 = 100000 40: EOR
OT 34 = 100010 41: RNO
# 0 = 000000 42: OT#
????? ????? = 6*5 + 11*6 = 96 ???.
????? ???????, ????????? LZW ?? ????????? ????????? ?? 29 ??? ?? 125 - ??? ????? 22 %. ???? ????????? ????? ???????, ?? ???????? ??????? ????? ???????????? ??? ????? ? ????? ??????? ????? ??????, ????????? ???? ????????????? ????? ????? ???????????? ????? ?????????.
?????????????
?????? ?????????? ??? ?? ???????? ?????????????? ?????????, ??????????? ????, ? ??? ????? ??? ????????????. ?????? ?????, ??? ????? ????? ????????? ???????, ? ??????????? ?????? ??????? ?? ????? ???????????????? ??? ?? ????, ????????? ??? ???????? ?????? ????????????? ?????????? ???????.
??????: ?? ??????: ????? ??????:
??????: ?????????:
10100 = 20 T 27: T?
01111 = 15 O 27: TO 28: O?
00010 = 2 B 28: OB 29: B?
00101 = 5 E 29: BE 30: E?
01111 = 15 O 30: EO 31: O? 10010 = 18 R 31: OR 32: R? <---- ???????? ???????????? 6-?????? ??????
001110 = 14 N 32: RN 33: N?
001111 = 15 O 33: NO 34: O?
010100 = 20 T 34: OT 35: T?
011011 = 27 TO 35: TT 36: TO? <---- ??? 37, ????????? ?????? ?????? ???????
011101 = 29 BE 36: TOB 37: BE? ?????????? ????? ???????
011111 = 31 OR 37: BEO 38: OR?
100100 = 36 TOB 38: ORT 39: TOB?
011110 = 30 EO 39: TOBE 40: EO?
100000 = 32 RN 40: EOR 41: RN?
100010 = 34 OT 41: RNO 42: OT?
000000 = 0 #
???????????? ????????? ????????? ????? ??????????, ???? ????? ????? ??????? ???????????? ??????????. ? ??????????? ???? ??????? ?????????????, ????? ??????? ????????? ?????? ??????, T, ?? ?????, ??? ????? 27 ?????????? ? T, ?? ??? ??? ?????????????? ??????????????? ???????? ????????? ????????. ?? ?????????? ????????? ABABA:
??????: ?? ??????: ????? ??????:
??????: ?????????:
.
.
.
011101 = 29 AB 46: (word) 47: AB?
101111 = 47 AB? <--- ??? ??? ? ???? ???????
?? ?????? ??????, ??? ???????? ??? ???????????? ????????. ?? ????? ???????, ??? ?????? 47 ?????? ???? ABA, ?? ??? ??????? ?????? ?? ????? ???????, ??? ????? 47 ??????? ?? ????? 29 ???? ?????? ?????? ?????????. ????? ???????, ????? 47 ????????????? ?? "?????? ?????? ?????????". ??, ????????? ??? ????? ?????????? ??????????, ?? ??? ?????? ?????????? ? "??????? ??????? ?????????", ? ??????? ??? ????????????? ??? ?? ???????? ??? ? ??????????, ? ?????? ?????? - A. ???? ???? ????????? ???????? ??????????, ??? ????? 47 ??? ABA.
? ????? ??????, ????? ???????? ??????????, ????? ?????????? ?????????????????? ???? cScSc, ??? c - ??? ???? ??????, ? S - ??????, ?????? ????? cS ??? ???? ? ???????.
?? ???????? LZW ? ??? ???????? ??? ????? ??? ????????, ??? ? ???, ??? ? ? ?????? ???????. ?? LZ78 ??? ????? ???????????? ?????? U.S. Patent 4 464 650, ????????????? Sperry Corporation, ??????? ??????? ?????? Unisys Corporation. ?? LZW ? ??? ???? ?????? ??? ???????: U.S. Patent 4 814 746, ????????????? IBM, ? ?????? ????? U.S. Patent 4 558 302 (????? 20 ???? 1983 ????), ????????????? Sperry Corporation, ??????? ?????????? ? Unisys Corporation. ? ?????????? ???????, ????? ???? ???????? ???????.
?????? ??????????
1. Stutz, Michael Get started with GAWK: AWK language fundamentals. developerWorks. IBM (September 19, 2006). - "[AWK] ????? ???????? ??????, ??????????? ??????? -- ????????? ????????? ????????? ?????????? ??????? ?????? ? ?? ?????????, ? ?? ?????????????????? ????? ?????????" ???????????? ?? ?????????????? 2 ???????? 2012. ????????? 23 ??????? 2010.
2. (1989) "Object-oriented design: a responsibility-driven approach". Conference Proceedings on Object-Oriented Programming Systems, Languages and Applications (ACM): 71-75. DOI:10.1145/74877.74885.
3. http://ru.wikipedia.org/wiki/??????_??????
4. http://ru.wikipedia.org/wiki/????????_???????_-_????_-_?????
5. http://ru.wikipedia.org/wiki/?????????_???????????????_????????????????
6. http://ru.wikipedia.org/wiki/????????????????_???????_??????
????-?????
??????? ?????????
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
/************************************************************************
** ???????????????? ????????? ??? LZW-????????? ??????/?????????? ??????.
** Mark R. Nelson
*************************************************************************/
#include <stdio.h>
#define BITS 12 /* ????????? ????? ???? ?????? 12, 13 */
#define HASHING_SHIFT BITS-8 /* ??? 14 ?????. */
#define MAX_VALUE (1 << BITS) - 1/* ???????, ??? ?? MS-DOS-?????? ??? */
#define MAX_CODE MAX_VALUE - 1 /* ????? ???? 14 ??? ?????????? ?????- */
/* ????????, ????????? large-??????. */
#if BITS == 14
#define TABLE_SIZE 18041 /* ?????? ??????? ????? ?????? ???? */
#endif /* ??????? ??????, ????????? ???????, */
#if BITS == 13 /* ??? 2**BITS. */
#define TABLE_SIZE 9029
#endif
#if BITS <= 12
#define TABLE_SIZE 5021
#endif
enum STATES {
NAME, SIZE, DATA
};
typedef struct {
char ** frames;
int n_files;
int i; // current file index
FILE *f; // current file
char buf[1024];
int buf_pos;
int buf_len;
} InArchStream;
typedef struct {
int state; // ?????? (1,2,3) (1- ????? ??? ?????, 2 ????? ???? ? ?????(4 ?????), 3 ????? ???? ???? ?????)
char fname [1050]; //
int fname_pos;// ??????? ?? ?????
int flen;// ????? ????? ??????(4 ????? ???????.)
FILE * out;// ??? ????
intflen_count; // ??????? ?? ????? ?????(?? 0 ????? ?? 4 ?????)
int out_count; //
} OutArchStream;
struct context
{
/* ??? ?????? ??? ???????? ????? */
int *code_value; //izbavlyaemsya ot globalnih peremennyh. /* ???? ?????? ???????? ???????? ????? */
unsigned int *prefix_code; /* ???? ?????? ???????? ?????????? ??????? */
unsigned char *append_character; /* ???? ?????? ???????? ???????????? ?????? */
unsigned char decode_stack[4000];
};
/*
** ????????? ??? ????????? ????????? ??????/??????? ?????
** ?????????? ?????. ??? ??? ??????? ???????? ??????????? ** ???????? ? ?? ????? ??????????.
*/
int input_code(FILE *input)
{
unsigned int return_value;
static int input_bit_count=0;
static unsigned long input_bit_buffer=0L;
while (input_bit_count <= 24)
{
input_bit_buffer|=(unsigned long)getc(input)<<(24-input_bit_count);
input_bit_count += 8;
}
return_value=input_bit_buffer >> (32-BITS);
input_bit_buffer <<= BITS;
input_bit_count -= BITS;
return(return_value);
}
int output_code(FILE *output,unsigned int code)
{
static int output_bit_count=0;
static unsigned long output_bit_buffer=0L;
output_bit_buffer|=(unsigned long)code<<(32-BITS-output_bit_count);
output_bit_count += BITS;
while (output_bit_count >= 8)
{
putc(output_bit_buffer >> 24,output);
output_bit_buffer <<= 8;
output_bit_count -= 8;
}
}
int arch_get_c(InArchStream * stream){
while (1) {
int a;
if (stream->buf_pos<stream->buf_len){
a=(unsigned char)stream->buf[stream->buf_pos];
stream->buf_pos++;
return a;
}
if (stream->f==NULL){
if (stream->i==stream->n_files)
return -1;
stream->f=fopen(stream->frames[stream->i], "rb");
if(stream->f==NULL)
return -1;
strcpy(stream->buf,stream->frames[stream->i]);
fseek(stream->f, 0, SEEK_END); int size = ftell(stream->f);
fseek(stream->f, 0, SEEK_SET);
int fname_len=strlen(stream->buf);
*(int *)&stream->buf[fname_len+1] = size;
stream->buf_len=fname_len+5;
stream->buf_pos=0;
continue;
}
int n =fread(stream->buf,1,sizeof(stream->buf),stream->f);
stream->buf_pos=0;
stream->buf_len=n;
if (stream->buf_len == 0) {
fclose(stream->f);
stream->f=NULL;
stream->i++;
}
}
}
int arch_put_c(char c, OutArchStream * stream) {
char * bytes;
switch (stream->state) {
case NAME:
stream->fname[stream->fname_pos++] = c;
if (c == 0) {
stream->state = SIZE;
stream->out_count = 0;
}
break;
case SIZE:
bytes = (char *)(&stream->flen);
bytes[stream->out_count++] = c;
if (stream->out_count == 4) {
stream->state = DATA;
stream->out = NULL;
}
break;
case DATA:
if (stream->out == NULL) {
stream->out = fopen(stream->fname, "wb");
stream->flen_count = 0;
}
putc(c, stream->out);
stream->flen_count ++;
if (stream->flen_count == stream->flen) {
fclose(stream->out);
stream->state = NAME;
}
break;
}
}
/*
** ????????? ???????????. ??? ???????? ????? ????????????? ??? ??????
** ???????+?????? ? ??????? ?????. ???? ???????, ???????????? ??????.
** ???? ???, ?? ???????????? ?????? ????????? ??????.
*/
int find_match(int hash_prefix,unsigned int hash_character,struct context *ctx){
int index;
int offset; index = (hash_character << HASHING_SHIFT) ^ hash_prefix;
if (index == 0)
offset = 1;
else
offset = TABLE_SIZE - index;
while (1)
{
if (ctx->code_value[index] == -1)
return(index);
if (ctx->prefix_code[index]==hash_prefix&&ctx->append_character[index]==hash_character)
return(index);
index -= offset;
if (index < 0)
index += TABLE_SIZE;
}
}// end of find_math;
/*
** ????????? ??????.
*/
int compress(InArchStream *input, FILE *output, struct context *ctx){
unsigned int next_code;
unsigned int character;
unsigned int string_code;
unsigned int index;
int i; next_code=256; /* Next_code - ????????? ????????? ??? ?????? */
for (i=0;i<TABLE_SIZE;i++)/*??????? ??????? ????? ????? ??????? */
ctx->code_value[i]=-1;
i=0;
printf("Compressing...\n");
string_code=arch_get_c(input); /* Get the first code*/
/*
** ???????? ????. ?? ??????????? ?? ??? ???, ???? ???????? ??????
** ???????? ??????. ???????, ??? ?? ?????????? ?????????? ???????
** ????? ????? ????, ??? ??? ????????? ???? ???? ????????????.
*/
while ((character=arch_get_c(input)) != (unsigned)EOF)
{
if (++i==1000) /* ???????? * ????? ?????? 1000 */
{ /* ?????? ??????? ???????? (??? */
i=0; /* ????????????? ???????). */
printf("*");
}
/* ???????, ???? ?? ?????? */
index=find_match(string_code,character,ctx);
if (ctx->code_value[index] != -1) /* ? ???????. ???? ????,*/
string_code=ctx->code_value[index];/* ???????? ???????? ????*/
else /* ???? ???, ????????? ??*/
{ /* ? ???????. */
if (next_code <= MAX_CODE)
{
ctx->code_value[index]=next_code++;
ctx->prefix_code[index]=string_code;
ctx->append_character[index]=character;
}
output_code(output,string_code);/*????? ??????????????, ???*/
string_code=character; /*?????? ??? ? ???????, */
} /*????????? ????????? ??????*/
} /*????? ??????????? ????? */
/*
** End of the main loop.
*/
output_code(output,string_code); /* ????? ?????????? ???? */
output_code(output,MAX_VALUE); /* ????? ???????? ????? ?????? */
output_code(output,0); /* ??????? ?????? ?????? */
printf("\n");
} //end of compress();
/*
** ????????? ??????????. ??? ?????? ???? LZW-??????? ? ?????????????
** ??? ? ???????? ????.
*/
int expand(FILE *input, struct context *ctx){// ?????? ?????? ????? ??? ????????
OutArchStream * output;
output = malloc(sizeof(OutArchStream));
memset(output, 0, sizeof(OutArchStream));
unsigned int next_code;
unsigned int new_code;
unsigned int old_code;
int character;
int counter;
unsigned char *string;
char *decode_string(unsigned char *buffer,unsigned int code,struct context *ctx);
next_code=256;
counter=0;
printf("Expanding...\n");
old_code=input_code(input);
character=old_code;
arch_put_c(old_code, output);
while ((new_code=input_code(input)) != (MAX_VALUE)) {
if (++counter==1000) {
counter=0;
printf("*");
}
if (new_code>=next_code) {
*ctx->decode_stack=character;
string=decode_string(ctx->decode_stack+1,old_code,ctx);
} else {
string=decode_string(ctx->decode_stack,new_code,ctx);
}
character=*string;
while (string >= ctx->decode_stack)
arch_put_c(*string--, output);
if (next_code <= MAX_CODE) {
ctx->prefix_code[next_code]=old_code;
ctx->append_character[next_code]=character;
next_code++;
}
old_code=new_code;
}
printf("\n");
}
char *decode_string(unsigned char *buffer,unsigned int code,struct context *ctx)
{
int i;
i=0;
while (code > 255)
{
//printf("Code: %d\n", code);
*buffer++ = ctx->append_character[code]; code=ctx->prefix_code[code];
if (i++>=4094)
{
printf("Fatal error during code expansion.\n");
//exit();
}
}
*buffer=code;
return(buffer);
}
InArchStream * createStream(int files, char ** fileNames) {
InArchStream * stream;
stream=malloc(sizeof(InArchStream));
stream->n_files = files;
stream->frames = (char**) malloc(sizeof(char * ) * files);
int i;
for (i = 0; i < files; i++) {
int length = strlen(fileNames[i]);
stream->frames[i] = (char*) malloc(length + 1);
strcpy(stream->frames[i], fileNames[i]);
}
stream->i=0;
stream->f=NULL;
stream->buf_pos=0;
stream->buf_len=0;
return stream;
}
int main(int argc, char *argv[]) {
int i;
for (i = 0; i < argc; i++) {
puts(argv[i]);
}
if (argc <= 2) {
puts("Not enough arguments. Format: <output> <input> [<input>...]");
return 0;
}
InArchStream * stream = createStream(argc - 2, argv + 2);
FILE * out= fopen(argv[1], "wb");
if (out==NULL){
printf ("cannot open file\n");
return 1;
}
struct context *ctx;
// ??? ??? ?????? ?????????? ?? ?????? ????????.
ctx = malloc(sizeof(struct context));
ctx->code_value=malloc(TABLE_SIZE*sizeof(int));
ctx->prefix_code=malloc(TABLE_SIZE*sizeof(unsigned int));
ctx->append_character=malloc(TABLE_SIZE*sizeof(unsigned char));
if (ctx->code_value==NULL || ctx->prefix_code==NULL || ctx->append_character==NULL) {
printf("Fatal error allocating table space!\n");
}
compress(stream, out, ctx);
fclose(out);
free(ctx->code_value);
if (argc <= 1) {
puts("Not enough arguments. Format: <archive>");
return 0;
}
FILE * lzw_file = fopen(argv[1], "rb");
expand(lzw_file, ctx);
fclose(lzw_file);
return 0;
}
?????????? ??????????????? ???????? ???????????
???????? ??????
?? ??????????:"?????? ? ???????? ?????? ???????????? ??????????"
?? ????: "?????? ?????? ????? ???????? ??????? - ????? - ??????"
??????????: ??????? 4 ?????
?????? 2
609396
??????? ?.?.
??????: ???????? ?. ?.
Документ
Категория
Без категории
Просмотров
20
Размер файла
80 Кб
Теги
naydenov_kursach_lzv
1/--страниц
Пожаловаться на содержимое документа