Алгоритм сжатия Deflation

20.06.12

✎

10:07

Народ, у меня через 15 минут защита, сижу прорабатываю вопросы которые могут задать, Deflation в сжатии данных как работает? Ниче нормального не могу нагуглить.

1 Voronve

20.06.12

✎

10:11

(0) Не судьба тебе видать стать дипломированным спецом раз нагуглить не можешь... сантехником будешь )

2 eduspec82

20.06.12

✎

10:12

акцентируй внимание комиссии на важности этого алгоритма широкой применимости подорбных алгоритмов в науке и технике
и т.п. не забудь упомянуть раз 10 модернизацию интенсификацию и нанотехнологии

3 Rizhij_Nikitos

20.06.12

✎

10:14

дайте ссылку где есть принцип работы)

4 proger2011

20.06.12

✎

10:15

(3) Расскажи про DES или ARS какойнить один хрен старпёры экзаменаторы ничё не рубят...

5 МихаилМ

20.06.12

✎

10:16

The deflation algorithm used by gzip (also zip and zlib) is a variation of
LZ77 (Lempel-Ziv 1977, see reference below). It finds duplicated strings in
the input data. The second occurrence of a string is replaced by a
pointer to the previous string, in the form of a pair (distance,
length). Distances are limited to 32K bytes, and lengths are limited
to 258 bytes. When a string does not occur anywhere in the previous
32K bytes, it is emitted as a sequence of literal bytes. (In this
description, `string' must be taken as an arbitrary sequence of bytes,
and is not restricted to printable characters.)

Literals or match lengths are compressed with one Huffman tree, and
match distances are compressed with another tree. The trees are stored
in a compact form at the start of each block. The blocks can have any
size (except that the compressed data for one block must fit in
available memory). A block is terminated when deflate() determines that
it would be useful to start another block with fresh trees. (This is
somewhat similar to the behavior of LZW-based _compress_.)

Duplicated strings are found using a hash table. All input strings of
length 3 are inserted in the hash table. A hash index is computed for
the next 3 bytes. If the hash chain for this index is not empty, all
strings in the chain are compared with the current input string, and
the longest match is selected.

The hash chains are searched starting with the most recent strings, to
favor small distances and thus take advantage of the Huffman encoding.
The hash chains are singly linked. There are no deletions from the
hash chains, the algorithm simply discards matches that are too old.

To avoid a worst-case situation, very long hash chains are arbitrarily
truncated at a certain length, determined by a runtime option (level
parameter of deflateInit). So deflate() does not always find the longest
possible match but generally finds a match which is long enough.

deflate() also defers the selection of matches with a lazy evaluation
mechanism. After a match of length N has been found, deflate() searches for
a longer match at the next input byte. If a longer match is found, the
previous match is truncated to a length of one (thus producing a single
literal byte) and the process of lazy evaluation begins again. Otherwise,
the original match is kept, and the next match search is attempted only N
steps later.

The lazy match evaluation is also subject to a runtime parameter. If
the current match is long enough, deflate() reduces the search for a longer
match, thus speeding up the whole process. If compression ratio is more
important than speed, deflate() attempts a complete second search even if
the first match is already long enough.

The lazy match evaluation is not performed for the fastest compression
modes (level parameter 1 to 3). For these fast modes, new strings
are inserted in the hash table only when no match was found, or
when the match is not too long. This degrades the compression ratio
but saves time since there are both fewer insertions and fewer searches.

6 Rizhij_Nikitos

20.06.12

✎

10:16

Ладно просто умолчу о том что сжимаю данные

7 qeos

20.06.12

✎

10:18

http://en.wikipedia.org/wiki/DEFLATE_(algorithm)

8 forforumandspam

20.06.12