http://npc-news.ru/

Алгоритм RLE, алгоритм сжатия данных, краткая информация

Алгоритм RLE является, наверное, самым простейшим из всех: суть его заключается в кодировании повторов. Другими словами, мы берём последовательности одинаковых элементов, и «схлопываем» их в пары «количество/значение». Например, строка вида «AAAAAAAABCCCC» может быть преобразована в запись вроде «8×A, B, 4×C». Это, в общем-то, всё, что надо знать об алгоритме.

Идея алгоритма Хаффмана состоит в том, что обычно в входном сообщении (входном файле) некоторые символы (байты) встречаются чаще, а некоторые — реже. Если кодировать символы, которые встречаются чаще, меньшим количеством бит, а символы, которые встречаются реже — большим, то можно уменьшить объем исходного сообщения (файла).

При этом получившиеся коды должны обладать свойством, что закодированное сообщение можно однозначно декодировать обратно в исходное сообщение. Хаффман предложил схему кодирования на основе двоичных кодирующих деревьев. Коды Хаффмана являются префиксными, т.е. никакое кодовое слово (та последовательность, которая получается в результате кодирования символа входного алфавита ) не является началом другого кодового слова. Префиксный код всегда может быть однозначно декодирован.


Добавить комментарий

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>