Введение 4
1. Теоретическая часть 6
1.1. История развития сжатия 6
1.3. Статистические методы сжатия: классический и адаптивный методы Хаффмана,
арифметическое кодирования 12
1.3.1. Описание классического метода Хаффмана 12
1.3.2. Описание адаптивного алгоритма Хаффмана 19
1.3.3. Описание арифметического кодирования 21
1.4. Словарные методы сжатия: LZ77, LZ78 22
1.4.1. Описание LZ77(скользящее окно) 22
1.4.2. Описание LZ78 23
2. Практическая часть 25
2.1. Реализация классического метода Хаффмана 25
2.1.1. Как происходит запись в файл закодированного текста 31
2.1.2. Описание декодирования файла 33
2.2. Описание для блочного варианта кодирования 34
2.3. Изучение метрик для нахождения наилучшего сжатия 36
2.4. Выгрузка данных об изменении векторов частот блоков в Excel 38
2.5. Описание реализации адаптивного алгоритма Хаффмана 38
2.5.1. Как происходит запись в файл закодированного текста адаптивного
(динамического) алгоритма Хаффмана 38
2.5.2. Описание декодирования закодированного файла 39
2.6 Описание определения вектора вероятности для блока 39
2.7 Разработка динамической модификации алгоритма Хаффмана. Деление по блокам 40
3. Экспериментальная часть 42
3.1. Исследования программной реализации адаптивного алгоритма Хаффмана 42
3.2. Анализ проведённого исследования и его сравнение 45
3.3. Исследования блочной модификации классического и адаптивного алгоритма
Хаффмана 45
3.4. Исследования изменения расстояния между блоками текста различных языков 50
3.5. Результаты данного эксперимента 67
Заключение 68
Список литературы 70
Приложение 71
Приложение 1. Листинг программы 71
С ростом использования компьютеров в мире бизнеса и персональных компьютеров объём данных, хранящихся в Интернете, значительно вырос. Данное явление привело к необходимости сжатия данных. Передача информации с помощью Интернета имеет решающее значение для всех типов бизнес-структур на всех уровнях. По мере развития технологий скорость передачи данных также может быть достигнута путём улучшения алгоритмов сжатия, через которое передаются данные, или путём изменения формата данных, чтобы данные могли передаваться с низкой стоимостью и максимальной скоростью. Сжатие данных также полезно, поскольку оно помогает снизить потребление дорогостоящих ресурсов, таких как пространство на жёстком диске или пропускная способность передачи данных.
Сжатие данных является очень важной темой для многих приложений. Многие методы сжатия данных были изучены в течение 40 лет. Хотя алгоритмы изменились и улучшились по эффективности, они играют важную роль в повседневной обработке компьютерного бизнеса и в компьютерной науке в целом. Поскольку мы продолжаем использовать компьютеры практически для всех наших задач, потребность в сжатии данных растет с каждым днем. В последние годы компании начали предлагать услуги резервного копирования пользователям персональных компьютеров. Компьютерные данные сжимаются для всего, что мы делаем, от банковских операций до отправки текстовых сообщений. А без технологии сжатия данных все это было бы невозможно. Но поскольку сжатие данных достигло значительных успехов, эта услуга возможна без использования большого пространства на жестком диске.
Целью данной работы является разработка модифицированного адаптивного метода Хаффмана для сжатия текстовой информации за счёт выбора слов как единиц информации. То есть за единицу измерения взято
слово. Это слова, знаки табуляции, знаки препинания, пробелы, знаки переноса строки.
В соответствии с поставленной целью в работе были выявлены следующие задачи:
— обзор методов сжатия текстовой информации;
— реализация классического и адаптивного методов Хаффмана;
— реализация классического и адаптивного алгоритмов Хаффмана для блочного варианта;
— описание определения вектора вероятности для блока;
— реализация сжатия с помощью трёх изученных метрик: Евклидового расстояния, расстояния Чебышёва, метрики городских кварталов;
— тестирование и анализ сжатия классического и адаптивного методов Хаффмана на русских и английских текстах;
— проведение экспериментов улучшенных методов Хаффмана с блочным вариантом на разноязычных текстах;
— сравнение полученной статистики и выбор оптимальных параметров.
В данной выпускной квалификационной работе были рассмотрены классический и адаптивный методы Хаффмана сжатия текстовой информации. Изучены соответствующие источники и необходимая литература. Был проведён анализ нескольких изученных алгоритмов кодирования без потерь.
На основе компьютерных экспериментов блочная модификация адаптивного метода Хаффмана дала наилучшее сжатие по сравнению с классическим блочным вариантом, классическим и адаптивным методами Хаффмана. Но при использовании блочной модификации динамического алгоритма Хаффмана выигрыш в сжатии текста происходит только в случае, когда границы блока примерно совпадает с переходом стилистики текста или переходом на другой язык.
При сравнении блочного классического метода Хаффмана с оптимальным выбором блока, то есть где переход на другой язык, стилистики точно совпадает с размером блока, с просто классическим методом Хаффмана выигрыш в среднем при небольших размерах блока составляет на 1.0048. При средних - на 1.008. При крупных размерах блока лучше на 1.002.
При сравнении адаптивного метода Хаффмана с его модификацией выигрыш при небольших размерах блока, средних и крупных размерах блоках выигрыш в среднем составляет соответственно на 1.009, 1.0187, 1.015.
Также стоит отметить, что при использовании блочной модификации, как и классического, так и адаптивного методов Хаффмана уменьшается время сжатия текста.
По изученным материалам в данной выпускной квалификационной работе были реализованы статистические методы сжатия информации, такие как классический и адаптивный методы Хаффмана. Также была реализована блочная модификация данных методов.
Были изучены три метрики: Евклидова метрика, метрика Чебышёва, Манхэттенская метрика. Были проведены эксперименты с использованием данных метрик, в ходе которых была выявлена оптимальная метрика, а именно Манхэттенская метрика.
Конечная цель в работе - разработка модификации динамического сжатия метода Хаффмана, дающая лучшие результаты на специальных классах текстов, а также разработка рекомендации по применению реализованных алгоритмов - была достигнута.
На будущее хочется заключить, что для блочного варианта классического и адаптивного методов Хаффмана, хотя оно не даёт особо выигрыша или даёт небольшой выигрыш только при угадывании этой границы, будет сжиматься лучше, так как это будет достигаться за счёт того, что дерево не будет таким глубоким и будут использоваться средства для распараллеливания. Кодирование одного блока никак не зависит от другого блока, то есть этот процесс можно распараллелить программно.
