Оптимизированный алгоритм сжатия на основе бинарного анализа независимых компонент
ВведениеВ настоящее время используется цифровой вид представления информации во многих сферах жизнедеятельности общества. При этом большой объем информации требует высокой пропускной способности каналов передачи данных и сокращения времени на их использование. Очевидно, что задача сжатия данных является актуальной во многих приложениях обработки и передачи информации.
Сжатие (компрессия) данных (Data Compression) - алгоритмическое преобразование данных, производимое с целью уменьшения занимаемого ими объёма. Применяется для более рационального использования устройств хранения и передачи данных. Иногда в литературе используются синонимы - «упаковка данных», «компрессия», «сжимающее кодирование», «кодирование источника». Обратная процедура сжатия данных называется восстановлением данных или распаковкой и декомпрессией.
Оглавление
Введение 8
1. Актуальность разработка алгоритма сжатия информации 12
1.1 Концептуальное обоснование задачи сжатия информации………….…12
1.2 Техническое обоснование актуальности задачи сжатия информация…14
1.2.1 Виды и методы кодирования…………………………………………..19
1.2.2 Классификация алгоритмов…………………………………................29
1.2.3 Проблемы рассмотренных алгоритмов сжатия…..…………………..37
1.2.4 Существующее решение проблем алгоритмов сжатия…………...…38
1.3 Экономическое обоснование актуальности задачи сжатия информации……………………………………………………………………...40
1.4 Вывод о целесообразности разработки оптимизированного алгоритма сжатия……………………………………………………………………………42
2. Математическая модель оптимизированного алгоритма сжатия…………45
2.1 Математические величины……………………………………………….45
2.2 Математическая постановка задач……………………………………….45
2.3 Бинарный анализ независимых компонент……………………………...47
2.3.1 Метод BICA с лежащими в основе независимыми компонентами..48
2.3.2 Обобщенный BICA с помощью алгоритма на основе дерева поиска……………………………………………………………………………50
2.3.3 Обобщенный BICA с помощью алгоритма кусочно-линейной релаксации………………………………………………………………………52
2.3.4 Обобщенный BICA с помощью умножения вектора на матрицу….54
2.4 Эффективность алгоритма BICA………………………………………..56
2.5 Вейвлет-преобразования…………………………………………………57
2.6. Выводы по выбору математического аппарата………………………..64
3. Оптимизированный алгоритм сжатия……………………………………...65
4. Технико-экономическое обоснование……………………………………...70
4.1. Описание оптимизированного алгоритма сжатия…………………….70
4.2. Сравнение оптимизированного алгоритма с аналогами, присутствующими на рынке 70
4.3. Состав затрат на внедрение программного продукта для собственных нужд 73
4.4. Оценка рисков и угроз 74
4.5. Определение трудоемкости разработки оптимизированного алгоритма 75
4.6. Определение заработной платы и социальных отчислений 76
4.7. Расчет расходов на используемые материалы 77
4.8. Расчет трат на услуги сторонних организаций 78
4.9. Расчет расходов на содержание и эксплуатацию оборудования 79
4.10. Расчет амортизационных отчислений 80
4.11. Совокупные затраты 82
4.12. Оценка затрат на разработку алгоритма 82
4.13. Оценка эффективности работы алгоритма 83
ЗАКЛЮЧЕНИЕ 84
ЛИТЕРАТУРА 86
1. Н. Ватолин Д., Ратушняк А., Смирнов М. Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео// -М. – ДиалогМИФИ. -2003. - 384 с. (дата обращения: 10.11.2022).
2. Сэломон Д. Сжатие данных, изображений и звука// – М. – Техносфера. - 2004. – 368 с. (дата обращения: 13.11.2022).
3. Ватолин Д., Ратушняк А., Смирнов М. Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео// -М. – ДиалогМИФИ. -2003. - 384 с. (дата обращения: 15.11.2022).
4. Гонсалес Р., Вудс Р. Цифровая обработка изображений.// Пер. с англ.- Москва.- Техносфера. – 2006. -1072 с. (дата обращения: 20.11.2022).
5. Aapo Hyvärinen, Juha Karhunen, Erkki Oja. Independent component analysis. - 1st.- New York: John Wiley & Sons, 2001. - ISBN 0-471-22131-7. (дата обращения: 01.12.2022).
6. Amichai Painsky, Member, IEEE, Saharon Rosset and Meir Feder, Fellow, IEEE. Generalized Independent Component Analysis Over Finite Alphabets, 2015 (дата обращения: 05.12.2022).
7. Amichai Painsky, Member, IEEE, Saharon Rosset and Meir Feder, Fellow, IEEE. Large Alphabet Source Coding using Independent Component Analysis, 2016 (дата обращения: 05.12.2022).
Дельта-кодирование делает невозможным произвольный доступ к данным, так как для обращения к элементу массива необходимо просуммировать значения всех предыдущих. Если это все же необходимо, применяется блочный вариант дельта-кодирования, в котором кодируются блоки некоторой заданной длины. Тогда необходимо лишь просуммировать значения с начала блока, которому принадлежит искомый элемент, но не всего файла. Размер блока выбирается в зависимости от приложения, обычно по результатам хронометража. 1.2.2 Классификация алгоритмов.
Алгоритмы, применяемые при использовании техник сжатия, можно разделить на следующие:
- алгоритмы, применяющие метод «скользящего окна»;
- алгоритмы с использованием словаря;
- алгоритмы, не использующие словарь
Алгоритмы, применяющие метод «скользящего окна».