Ci-dessous, les différences entre deux révisions de la page.
Les deux révisions précédentesRévision précédenteProchaine révision | Révision précédente | ||
dossier:elements_techniques:lzss [Le 01/06/2009 à 11:23] – myst6re | dossier:elements_techniques:lzss [Le 15/08/2022 à 15:25] (Version actuelle) – modification externe 127.0.0.1 | ||
---|---|---|---|
Ligne 40: | Ligne 40: | ||
La taille réelle est en fait '' | La taille réelle est en fait '' | ||
- | ==== Complications | + | ==== Algorithme |
- | ... | + | Algorithme original (compression et décompression) par Haruhiko Okumura en langage c : |
+ | |||
+ | <code c> | ||
+ | / | ||
+ | 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, | ||
+ | **************************************************************/ | ||
+ | #include < | ||
+ | #include < | ||
+ | #include < | ||
+ | #include < | ||
+ | |||
+ | #define N 4096 /* size of ring buffer */ | ||
+ | #define F 18 /* upper limit for match_length */ | ||
+ | #define THRESHOLD 2 | ||
+ | | ||
+ | #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, | ||
+ | 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, | ||
+ | |||
+ | void InitTree(void) | ||
+ | { | ||
+ | int i; | ||
+ | |||
+ | /* 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; | ||
+ | } | ||
+ | |||
+ | void InsertNode(int r) | ||
+ | /* Inserts string of length F, text_buf[r..r+F-1], | ||
+ | trees (text_buf[r]' | ||
+ | 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 = & | ||
+ | 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]; | ||
+ | dad[lson[p]] = r; dad[rson[p]] = r; | ||
+ | if (rson[dad[p]] == p) rson[dad[p]] = r; | ||
+ | else | ||
+ | dad[p] = NIL; /* remove p */ | ||
+ | } | ||
+ | |||
+ | void DeleteNode(int p) /* deletes node p from tree */ | ||
+ | { | ||
+ | int q; | ||
+ | |||
+ | if (dad[p] == NIL) return; | ||
+ | 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]; | ||
+ | rson[dad[q]] = lson[q]; | ||
+ | lson[q] = lson[p]; | ||
+ | } | ||
+ | rson[q] = rson[p]; | ||
+ | } | ||
+ | dad[q] = dad[p]; | ||
+ | if (rson[dad[p]] == p) rson[dad[p]] = q; else lson[dad[p]] = q; | ||
+ | dad[p] = NIL; | ||
+ | } | ||
+ | |||
+ | void Encode(void) | ||
+ | { | ||
+ | int i, c, len, r, s, last_match_length, | ||
+ | unsigned char code_buf[17], | ||
+ | |||
+ | InitTree(); | ||
+ | code_buf[0] = 0; /* code_buf[1..16] saves eight units of code, and | ||
+ | code_buf[0] works as eight flags, " | ||
+ | is an unencoded letter (1 byte), " | ||
+ | (2 bytes). | ||
+ | code_buf_ptr = mask = 1; | ||
+ | s = 0; r = N - F; | ||
+ | for (i = s; i < r; i++) text_buf[i] = ' '; | ||
+ | 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; | ||
+ | for (i = 1; i <= F; i++) InsertNode(r - i); /* Insert the F strings, | ||
+ | each of which begins with one or more ' | ||
+ | the order in which these strings are inserted. | ||
+ | degenerate trees will be less likely to occur. */ | ||
+ | InsertNode(r); | ||
+ | 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. | ||
+ | code_buf[0] |= mask; /* 'send one byte' flag */ | ||
+ | code_buf[code_buf_ptr++] = text_buf[r]; | ||
+ | } 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; | ||
+ | putc(code_buf[i], | ||
+ | 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); | ||
+ | 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 | ||
+ | | ||
+ | InsertNode(r); | ||
+ | } | ||
+ | if ((textsize += i) > printcount) { | ||
+ | printf(" | ||
+ | /* Reports progress each time the textsize exceeds | ||
+ | | ||
+ | } | ||
+ | while (i++ < last_match_length) { /* After the end of text, */ | ||
+ | DeleteNode(s); | ||
+ | s = (s + 1) & (N - 1); r = (r + 1) & (N - 1); | ||
+ | if (--len) InsertNode(r); | ||
+ | } | ||
+ | } 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; | ||
+ | codesize += code_buf_ptr; | ||
+ | } | ||
+ | printf(" | ||
+ | printf(" | ||
+ | printf(" | ||
+ | } | ||
+ | |||
+ | void Decode(void) / | ||
+ | { | ||
+ | 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 */ | ||
+ | } / | ||
+ | if (flags & 1) { | ||
+ | if ((c = getc(infile)) == EOF) break; | ||
+ | putc(c, outfile); | ||
+ | } 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); | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | |||
+ | int main(int argc, char *argv[]) | ||
+ | { | ||
+ | char *s; | ||
+ | |||
+ | if (argc != 4) { | ||
+ | printf("' | ||
+ | "' | ||
+ | return EXIT_FAILURE; | ||
+ | } | ||
+ | if ((s = argv[1], s[1] || strpbrk(s, " | ||
+ | || (s = argv[2], (infile | ||
+ | || (s = argv[3], (outfile = fopen(s, " | ||
+ | printf("??? | ||
+ | } | ||
+ | if (toupper(*argv[1]) == ' | ||
+ | fclose(infile); | ||
+ | return EXIT_SUCCESS; | ||
+ | } | ||
+ | |||
+ | </ | ||
===== En savoir plus... ===== | ===== En savoir plus... ===== |
Qui sommes-nous ?
Aidez WikiSquare en le faisant connaître !
Sauf mention contraire, tous les textes sont disponibles sous les termes de la GNU Free Documentation License.
Les images sont sous le copyright de leurs auteurs.
Page générée en 0.018202066421509 seconde.