Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
В общих чертах смысл сжатия без потерь таков. В исходных данных находят какую-либо закономерность и с учётом этой закономерности генерируют вторую последовательность, которая полностью описывает исходную. Например, для кодирования двоичных последовательностей, в которых много нулей и мало единиц, мы можем использовать такую замену:
00 → 001 → 1010 → 11011 → 111В таком случае шестнадцать битов
00 01 00 00 11 10 00 00будут преобразованы в тринадцать битов
0 10 0 0 111 110 0 0Такая подстановка является префиксным кодом, то есть обладает такой особенностью: если мы запишем сжатую строку без пробелов, мы всё равно сможем расставить в ней пробелы — а значит, восстановить исходную последовательность. Наиболее известным префиксным кодом является код Хаффмана.
Большинство алгоритмов сжатия без потерь работают в две стадии: на первой генерируется статистическая модель для входящих данных, вторая отображает входящие данные в битовом представлении, используя модель для получения «вероятностных» (то есть часто встречаемых) данных, которые используются чаще, чем «невероятностные».
Статистические модели алгоритмов для текста (или текстовых бинарных данных, таких как исполняемые файлы) включают:
· Преобразование Барроуза — Уилера (блочно-сортирующая пре-обработка, которая делает сжатие более эффективным)
· LZ77 и LZ78 (используется DEFLATE)
· LZW
Алгоритмы кодирования через генерирование битовых последовательностей:
· Алгоритм Хаффмана (также используется DEFLATE)
· Арифметическое кодирование
Дата публикования: 2015-01-26; Прочитано: 246 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!