Алгоритмы сжатия информации - Студенческий научный форум

XII Международная студенческая научная конференция Студенческий научный форум - 2020

Алгоритмы сжатия информации

Глазкрицкая М.А. 1
1ФГБОУ ВО БГУ
 Комментарии
Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF

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

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

без потерь

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

с потерями

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

Сжатие с потерями применяется в основном для графики (JPEG), звука (MP3), видео (MPEG), то есть там, где мелкие отклонения от оригинала незаметны или несущественны, а степень сжатия в силу огромных размеров файлов очень важна. Сжатие без потерь применяется во всех остальных случаях - для текстов, исполняемых файлов, высококачественного звука и графики и т.д. и т.п.

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

Основные способы сжатия:

статистический

Kаждому символу присваивается код, основанный на вероятности его появления в тексте. Высоко вероятные символы получают короткие коды и наоборот. Одним из самых ранних и широко известных статистических методов является алгоритм Хаффмана, при котором символы заменяются кодом, состоящим из целого количества битов.

словарный

При словарном способе группы последовательных символов или «фраз» заменяются кодом. Замененная фраза может быть найдена в некотором словаре. В 1977 году Лемпель и Зив предложили свою модификацию словарного метода, отличающуюся от Хаффмановского и арифметического методов в которой сжатие основано на свойстве «потока символов» иметь повторяющиеся участки. Поток символов - это исходные данные для сжатия (например текстовый файл, массив). Основная идея алгоритма Лемпеля и Зива состоит в том, что второе и последующие вхождения некоторой строки символов в сообщении заменяются ссылкой на ее первое появление в сообщении.

Одним из наиболее простых и наглядных является метод сжатия последовательностей одинаковых символов, не относящийся к названным основным методам.

Метод основан на представлении последовательности одинаковых символов в виде двух величин K и S, где K - количество повторяющихся символов, S - код этого символа. Основным недостатком данного метода является то, что он обеспечивает сжатие лишь в случае, когда в исходном файле основную часть составляют повторяющиеся символы. В противном случае сжатый файл может занимать больше места, чем исходный неуплотненный файл. Наиболее эффективно метод сжатия последовательностей одинаковых символов работает в случае двоичных файлов .

Рассмотренные выше алгоритмы в «чистом виде» на практике не применяются из-за того, что эффективность каждого из них сильно зависит от начальных условий.

Цель сжатия данных - обеспечить компактное представление данных, вырабатываемых источником, для их более экономного сохранения и передачи по каналам связи.

Просмотров работы: 42