Введение
ТЕОРЕТИЧЕСКАЯ ЧАСТЬ 5
1.1. Классификация задачи сжатия информации 5
1.2. Методы сжатия текстовой информации без потерь 7
1.3. Словарный метод LZ-77 11
1.4. Статистический метод Хаффмана 14
2. ПРАКТИЧЕСКАЯ ЧАСТЬ 17
2.1. Реализация классического алгоритма LZ-77 17
2.2. Анализ процесса кодирования и структуры закодированных данных.
Модификация алгоритма LZ-77 22
2.3. Реализация классического алгоритма Хаффмана 25
3. ЭКСПЕРИМЕНТАЛЬНАЯ ЧАСТЬ 27
3.1. Комбинирование модифицированного алгоритма LZ-77 и алгоритма
Хаффмана для достижения лучшей степени сжатия и анализ полученных результатов 27
3.2. Исследование комбинированного алгоритма сжатия 30
ЗАКЛЮЧЕНИЕ 32
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 33
ПРИЛОЖЕНИЕ
Жизнь человека в современном мире невозможна без электронных устройств, компьютеров, смартфонов. Как правило использование этих устройств неразрывно связано с обработкой, хранением и передачей различных данных. Причем с течением времени объем этих данных неуклонно растет. На сегодняшний день смартфоны могут хранить сотни гигабайт информации, а компьютеры тысячи, скорость передачи данных между устройствами измеряется мегабайтами в секунду. Для того, чтобы удовлетворить растущие потребности улучшаются физические характеристики устройства, таких как процессор или память, а также изобретаются более быстрые каналы передачи информации. Однако, не всегда технический прогресс происходит так же быстро, как рост потребностей. Поэтому не менее важной областью разработок остается сжатие информации, ведь сжатые данные проще хранить и передавать.
В рамках выпускной квалификационной работы речь пойдет именно о сжатии информации и оптимизации используемой памяти. Прежде чем говорить о сжатии информации, методах и алгоритмах, необходимо определить понятие сжатия.
Сжатие данных - это процесс преобразования входного потока данных (исходного потока или исходных необработанных данных) в другой поток данных (выходной или сжатый поток), который имеет меньший размер. Поток - это файл или буфер в памяти. Сжатие данных популярно по двум причинам:
1. Люди любят накапливать данные и ненавидят выбрасывать что-либо. Независимо от того, насколько велико устройство хранения, рано или поздно оно переполнится. Сжатие данных кажется полезным, потому что оно задерживает эту неизбежность;
2. Люди ненавидят долго ждать передачи данных. Сидя за компьютером, ожидая, когда появится веб-страница или файл для загрузки, мы, естественно, чувствуем, что что-нибудь дольше, чем несколько секунд, это долго ждать;
Существует много известных способов сжатия данных. Они основаны на разных идеях, подходят для разных типов данных и дают разные результаты, но все они основаны на одном и том же принципе, а именно они сжимают данные, удаляя избыточность из исходных данных в исходном файле. Любые неслучайные данные имеют некоторую структура, и эта структура может быть использована для достижения меньшего представления данных.
Таким образом, избыточность является важной концепцией в любом обсуждении сжатия данных.
Например, в типичном английском тексте буква E встречается очень часто, а буква Z встречается редко. Это называется буквенной избыточностью и предлагает присваивать буквам переменные коды, причем E - самый короткий код, а Z - самый длинный.
Другой тип избыточности, контекстуальная избыточность, иллюстрируется тем фактом, что за буквой Q почти всегда следует буква U (то есть, что некоторые диаграммы и триграммы чаще встречаются в простом английском языке, чем другие).
Для оценки работы алгоритма используется коэффициент сжатия. Коэффициент сжатия - это отношение размера исходного фала к размеру сжатого. Этот коэффициент позволит сравнивать различные алгоритмы друг с другом.
Целью выпускной квалификационной работы было исследование того, как влияет на коэффициент сжатия использование нескольких алгоритмов сжатия, а именно алгоритма словарного сжатия LZ-77 и статистического алгоритма Хаффмана.
Достижение поставленной цели возможно при решение следующих задач:
1. Разработка модификации алгоритма LZ-77 с достаточно хорошим коэффициентом сжатия.
2. Разработка классического алгоритма Хаффмана.
3. Исследование последовательной работы двух алгоритмов.
В данной работе удалось реализовать классические алгоритмы LZ-77 и Хаффмана, оценить и проанализировать их работу, разработать модификацию алгоритма LZ-77.
Также было реализованы комбинированные алгоритмы, сжимающие данные лучше, чем каждый по отдельности. Был проведен анализ и найдена лучшая комбинация.
На основе многовариантных вычислительных экспериментов были проведены исследования, которые показали, что
- модификация алгоритма LZ-77 позволяет лучше сжимать необработанные данные с редкими символами;
- хорошие методы сжатия информации сами по себе не могут полностью избавить информацию от избыточности;
- не любое комбинирование даже хороших алгоритмов дает положительных результат, при сжатии важную роль играет именно структура данных;
Исходя из того, что структура данных играет важную роль в сжатии, можно определить дальнейшие пути для улучшения алгоритмов и создания новых:
- структурирование данных перед началом сжатия, сортировка, которая позволит алгоритмам находить большие повторения;
- можно научить алгоритм предсказывать следующий символ или бит;
Все поставленные цели были достигнуты.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
