简介翻译LZSS压缩算法实验报告

2021年1月20日发(作者：luke)
实验名称：
LZSS
压缩算法实验报告

一、

实验内容

使用
Visual 6..0 C++
编程实现
LZ77
压缩算法。

二、

实验目的

用
LZSS
实现文件的压缩。

三、

实验原理

LZSS
压缩算法是词典编码无损压缩技 术的一种。
LZSS
压缩算
法的字典模型使用了自适应的方式，也就是说，将已经编码 过
的信息作为字典，

四、

实验环境

1
、软件环境：
Visual C++ 6.0
2
、编程语言：
C++
五、

实验代码

#include
#include
#include
#include

/* size of ring buffer */
#define
N

4096
/* index for root of binary search trees */
#define NIL

N
/* upper limit for g_match_len. Changed from 18 to 16 for binary
compatability with Microsoft and
#define
F

18 */
#define
F

16
/* encode string into position and length
if match_length is greater than this: */
#define
THRESHOLD
2


/* these assume little-endian CPU like Intel x86
-- need byte-swap function for big endian CPU */
#define
READ_LE32(X)
*(uint32_t *)(X)
#define
WRITE_LE32(X,Y)
*(uint32_t *)(X) = (Y)

/* this assumes sizeof(long)==4 */
typedef unsigned long
uint32_t;

/* text (input) size counter, code (output) size counter,
and counter for reporting progress every 1K bytes */
static unsigned long g_text_size, g_code_size, g_print_count;
/* ring buffer of size N, with extra F-1 bytes
to facilitate string comparison */
static unsigned char g_ring_buffer[N + F - 1];
/* position and length of longest match; set by insert_node() */
static unsigned g_match_pos, g_match_len;
/* left & right children & parent -- these constitute binary search tree */
static unsigned g_left_child[N + 1], g_right_child[N + 257], g_parent[N + 1];
/* input & output files */
static FILE *g_infile, *g_outfile;
/*** ************************************************** ************************
initialize trees
************************************************** ***************************/
static void init_tree(void)
{

unsigned i;

/* For i = 0 to N - 1, g_right_child[i] and g_left_child[i] will be the right and



left children of node i.

These nodes need not be initialized.



Also, g_parent[i] is the parent of node i.

These are initialized to



NIL (= N), which stands for 'not used.'



For i = 0 to 255, g_right_child[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++)


g_right_child[i] = NIL;

for(i = 0; i < N; i++)


g_parent[i] = NIL;
} < br>/********************************************** *******************************
Inserts string of length F, g_ring_buffer[r..r+F-1], into one of the
trees (g_ring_buffer[r]'th tree) and returns the longest-match position
and length via the global variables g_match_pos and g_match_len.
If g_match_len = 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.
************************************** ***************************************/
static void insert_node(int r)
{

unsigned char *key;

unsigned i, p;

int cmp;


cmp = 1;

key = &g_ring_buffer[r];

p = N + 1 + key[0];

g_right_child[r] = g_left_child[r] = NIL;

g_match_len = 0;

while(1)

{


if(cmp >= 0)


{



if(g_right_child[p] != NIL)




p = g_right_child[p];



else



{




g_right_child[p] = r;




g_parent[r] = p;




return;



}


}


else


{



if(g_left_child[p] != NIL)




p = g_left_child[p];



else



{




g_left_child[p] = r;




g_parent[r] = p;




return;



}


}


for(i = 1; i < F; i++)


{



cmp = key[i] - g_ring_buffer[p + i];



if(cmp != 0)




break;


}


if(i > g_match_len)


{



g_match_pos = p;



g_match_len = i;



if(g_match_len >= F)




break;


}

}

g_parent[r] = g_parent[p];

g_left_child[r] = g_left_child[p];

g_right_child[r] = g_right_child[p];

g_parent[g_left_child[p]] = r;

g_parent[g_right_child[p]] = r;

if(g_right_child[g_parent[p]] == p)


g_right_child[g_parent[p]] = r;

else


g_left_child[g_parent[p]] = r;

g_parent[p] = NIL;

/* remove p */
}
/*************************************** **************************************
deletes node p from tree
***************************** ************************************************/
static void delete_node(unsigned p)
{

unsigned q;


if(g_parent[p] == NIL)


return; /* not in tree */

if(g_right_child[p] == NIL)


q = g_left_child[p];

else if(g_left_child[p] == NIL)


q = g_right_child[p];

else

{


q = g_left_child[p];


if(g_right_child[q] != NIL)


{



do q = g_right_child[q];



while(g_right_child[q] != NIL);



g_right_child[g_parent[q]] = g_left_child[q];



g_parent[g_left_child[q]] = g_parent[q];



g_left_child[q] = g_left_child[p];



g_parent[g_left_child[p]] = q;


}


g_right_child[q] = g_right_child[p];


g_parent[g_right_child[p]] = q;

}

g_parent[q] = g_parent[p];

if(g_right_child[g_parent[p]] == p)


g_right_child[g_parent[p]] = q;

else


g_left_child[g_parent[p]] = q;

g_parent[p] = NIL;
}
/**************** ************************************************** ***********
********************************** *******************************************/
static void compress(void)
{

unsigned i, len, r, s, last_match_length, code_buf_ptr;

unsigned char code_buf[17], mask;

int c;


init_tree();

/* initialize trees */
/* code_buf[1..16] saves eight units of code, and code_buf[0] works as
eight flags,

16 bytes of code. */

code_buf[0] = 0;

code_buf_ptr = mask = 1;

s = 0;

r = N - F;
/* Clear the buffer with any character that will appear often. */

memset(g_ring_buffer + s, ' ', r - s);
/* Read F bytes into the last F bytes of the buffer */

for(len = 0; len < F; len++)

{


c = getc(g_infile);


if(c == EOF)



break;


g_ring_buffer[r + len] = c;

}

g_text_size = len;

if(g_text_size == 0) /* text of size zero */


return;
/* 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. */

for(i = 1; i <= F; i++)


insert_node(r - i);