Аннотация 2
Abstract 3
Введение 5
1 Теоретические аспекты повышения эффективности алгоритмов сжатия 7
1.1 Основная теория и классификация алгоритмов сжатия 7
1.2 Методы сжатия информации без потерь 9
1.3 Теория эффективности алгоритмов 12
1.4 Теория параллелизации алгоритмов 14
2 Разработка эффективного алгоритма сжатия 20
2.1 Алгоритм сжатия 20
2.2 Параллелизация алгоритма 24
2.3 Практическая оценка эффективности алгоритма сжатия 25
3 Реализация, тестирование и анализ разработанных алгоритмов сжатия .. 27
3.1 Средства и структура программы 27
3.2 Реализация последовательного алгоритма 30
3.3 Реализация параллельного алгоритма 33
3.4 Тестирование и сравнительный анализ эффективности 37
Заключение 42
Список используемой литературы 43
Приложение А Листинг программного кода алгоритмов сжатия 45
Приложение Б Листинг программного кода многопоточного процесса сжатия 53
В связи с постоянным процессом внедрения цифровых технологий во все сферы жизни и отрасли производства, огромное количество информации было перенесено в электронный вид, и сейчас большая часть начинает свое существование в электронном виде. По окончанию процессов генерации и обработки, информация обычно сохраняется в том формате, который максимально упрощает ее дальнейшее применение. Такой формат вовсе не обязательно будет являться максимально компактным. С расширением масштаба хранимых данных, лишний объем будет постепенно накапливаться, и вызывать новые проблемы, как в процессе хранения, так и в процессе загрузки и передачи информации.
Для предупреждения данной проблемы применяются алгоритмы сжатия информации. Цель алгоритма сжатия - представить информацию в виде меньшего количества битов, чем оригинальное представление [11]. В основе алгоритмов лежит тщательный анализ данных на обнаружение и сокращение избыточности - повторяющихся блоков данных. Но в то время как дополнительная сложность анализа позволяет повысить сокращение избыточности, это несёт за собой дополнительные вычислительные затраты. Поэтому в данной работе будет рассмотрен вопрос повышения эффективности классических алгоритмов сжатия.
Вопрос оптимизации процесса сжатия по любым из показателей актуален в настоящее время, и научная сфера имеет поддержку со стороны крупных компаний. В пример можно привести Global Data Compression Competition (GDCC) - всемирное соревнование по инновации и оптимизации в сфере сжатии информации [4].
В ходе выполнения выпускной квалификационной работы было проведено исследование, объектом которого являлись алгоритмы сжатия информации.
Целью работы был анализ эффективности параллелизации комплексного алгоритма сжатия. В ходе работы были поставлены и выполнены следующие задачи:
- изучены и проанализированы теоретические основы в сфере оптимизации вычислительных алгоритмов и сфере сжатия информации;
- разработаны комплексный алгоритм сжатия, состоящий из двух методов предобработки и метода статистической компрессии, многопоточный вариант алгоритма, и описаны условия проводимого анализа;
- реализованы разработанные алгоритмы и проведено исследование на степень повышения его эффективности от параллелизации.
В результате проделанной работы были сделаны следующие выводы
- большая часть эффективности алгоритмов сжатия исходит из корректного совмещения нескольких подходов;
- язык программирования Rust является идеальным инструментов для разработки критически важных компонентов;
- эффективность программы зависит насколько от грамотного подхода к решению задачи, так и от эффективной реализации с использованием соответствующих средств.
