Алгоритмы сжатия без потерь
Автор: vggg • Май 20, 2023 • Лабораторная работа • 6,076 Слов (25 Страниц) • 236 Просмотры
МИНОБРНАУКИ РОССИИ
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ
ЭЛЕКТРОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
«ЛЭТИ» ИМ. В.И. УЛЬЯНОВА (ЛЕНИНА)
Кафедра МОЭВМ
ОТЧЕТ
по лабораторной работе №3
по дисциплине «Алгоритмы и структуры данных»
Студентка гр. 0303 | Герасимова В.Е. | |
Преподаватель | Романов А.В. |
Санкт-Петербург
2022
Постановка задачи
Реализовать следующие алгоритмы сжатия символьных данных:
- Алгоритм Хаффмана (HA)
- Кодирование длин серий (RLE)
- Алгоритм Лемпеля-Зива (LZ78)
- Преобразование Барроуза-Уиллера (BWT)
- MTF
- Арифметическое кодирование (AC)
- PPM
Проанализировать эффективность и время сжатия на датасете enwik8 для процедур сжатия на основе:
- Алгоритма Хаффмана
- Арифметического кодирования
- LZ78
- BWT -> MTF -> HA
- BWT -> MTF -> AC
- RLE -> BWT -> MTF -> RLE -> HA
- RLE -> BWT -> MTF -> RLE -> AC
- PPM
Результаты представить в виде или таблиц. При слишком больших временных затратах на сжатие взять первые 10% enwiki8.
Теоретические сведения
Алгоритм Хаффмана
Алгоритм Хаффмана работает в несколько этапов:
Сначала алгоритм анализирует исходный текст и определяет, какие символы встречаются в нем и как часто они встречаются.
Затем он строит дерево Хаффмана, используя эти частоты. Для этого он создает листья для каждого символа и помещает их в приоритетную очередь, отсортированную по частотам символов. Затем он объединяет два узла с наименьшими частотами в новый узел и добавляет его обратно в очередь. Этот процесс продолжается до тех пор, пока все узлы не будут объединены в один корень дерева.
Далее каждому символу назначается уникальный двоичный код, который формируется путем прохождения от корня дерева к листьям. Каждый левый переход в дереве соответствует биту 0, а каждый правый переход - биту 1.
Затем исходный текст перекодируется с использованием назначенных кодов символов. Это позволяет кодировать часто встречающиеся символы короткими кодами, что приводит к сжатию данных.
Декодирование происходит обратным обходом дерева Хаффмана с использованием закодированных данных. Каждый бит считывается последовательно, и для каждого прочитанного бита происходит переход влево или вправо по дереву, пока не будет достигнут лист, который соответствует символу.
В результате применения алгоритма Хаффмана данные могут быть сжаты до значительно меньшего размера, чем в исходном виде, что позволяет экономить место при их хранении или передаче.
Кодирование длин серий (RLE)
Алгоритм сжатия RLE (Run-Length Encoding) - это простой метод сжатия данных, который основывается на повторяющихся последовательностях символов. Он применяется для сжатия текстовых и графических файлов.
Алгоритм RLE работает следующим образом:
Последовательные повторяющиеся символы заменяются на число повторов и сам символ. Например, последовательность "AAAA" может быть заменена на "4A".
Если последовательность неповторяющихся символов короче, чем два символа, то она остается без изменений.
Для уменьшения размера файла, полученная последовательность кодируется двоичным кодом.
Распаковка данных происходит обратным образом: повторяющиеся последовательности символов расшифровываются в исходные последовательности.
Хотя алгоритм RLE прост в реализации и быстр в работе, он не всегда позволяет добиться высокой степени сжатия, особенно для файлов с небольшим количеством повторяющихся символов.
...