Реализация алгоритма Лемпеля-Зива 1978 года на Python
Изучение алгоритма сжатия без потерь, опубликованного в статьях А. Лемпеля и Я. Зива в 1978 году. Применение словаря в алгоритме LZ78. Выполнение основного цикла while. Создание временной строки, в которой будет храниться последовательность символов.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | статья |
| Язык | русский |
| Дата добавления | 21.01.2022 |
| Размер файла | 859,5 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
«Математический» Тверской Государственный Университет
Реализация алгоритма лемпеля-зива 1978 года на Python
Смирнова А.С., студент 4 курс, факультет
Россия, г. Тверь
Аннотация
Статья посвящена реализации алгоритма Лемпеля-Зива 1978 года. Алгоритм реализован на языке программирования Python. В статье будет показан и прокомментирован код реализации алгоритма.
Ключевые слова: Алгоритмы, Python, программирование
Annotation
The article is devoted to the implementation of the Lempel-Ziv algorithm of 1978. The algorithm is implemented in the Python programming language. The article will show and comment on the implementation code of the algorithm.
Key words: algorithms, Python, programming.
Алгоритм Лемпеля-Зива - LZ78
LZ78 -- алгоритм сжатия без потерь, опубликованный в статьях Абрахама Лемпеля и Якоба Зива в 1978 году. Эти алгоритмы наиболее известны в семействе LZ*, которое включает в себя также LZW, LZSS, LZMA и другие алгоритмы
В отличие от LZ77, работающего с уже полученными данными, LZ78 ориентируется на данные, которые только будут получены.
Алгоритм LZ78 не использует буфер и скользящее окно. Вместо этого он использует словарь.
Словарь - набор строк, которые встречаются в обрабатываемой последовательности.
Мы получаем начало последовательности и не знаем все остальные символы.
На начальном этапе работы, пока словарь пуст, будем просматривать кодируемую фразу посимвольно и кодировать отдельные символы, формируя словарь.
Далее если при считывании появляется символ или набор символов, которые уже занесены в словарь, то мы пользуемся словарем и уже не кодируем их заново, а делаем ссылку на номер строки словаря, которая позволила добавить это сочетание с словарь.
Результат кодирования записывают в таблицу, содержащую 4 колонки:
Содержимое словаря,
Содержимое текущего пакета данных (содержимое считываемой строки),
Пакет данных в виде <адрес словаря, следующий знак данных> (код),
Адрес пакета данных.
Для реализации алгоритма был выбран Python.
Рис. 1. Код, ч.І
s - здесь хранится передаваемое сообщение. dictionary - создание изначально пустого словаря. i - переменная для передвижения по строке.
arr_for_dict, arr_code, arr_content, arr_adr - в эти массивы будем записывать информацию в ходе выполнения алгоритма и они нам будут нужны в дальнейшем для красивого вывода результата работы алгоритма с помощью библиотеки terminaltables, так как библиотека требует в аргументе массив. алгоритм сжатие символ словарь
Основной цикл while выполняется пока переменная i и не дойдет до последнего символа передаваемого сообщения.
Делаем проверку. Если символа нет в словаре, то тогда добавляем новую пару в словарь. Создаем код. <0, символ>. 0 показывает, что данной буквы еще никогда не было в словаре.
Информацию в массивы добавляем с помощью встроенного метода append else:
Рис. 2. Код, 4.2
Если же символ уже есть в словаре, то тогда создаем временную строку str_temp, в которой будет храниться некоторая последовательность символов. Добавляем в неё первый элемент. К переменной i прибавляем 1, что означает что мы переходим к следующему символу в передаваемом сообщении. Если сочетание символов есть в словаре и переменная i стоит в конце сообщения, тогда формируем код следующим образом <адрес словаря, #>, где # означает конец сообщения.
К str_temp прибавляем следующий символ из передаваемого сообщения. Если такого сочетания символов нет в словаре, тогда добавляем новое сочетание символов в словарь с определенным адресом и формируем код: ставим адрес, соответствующий последнему найденному совпадению в словаре и указываем следующий знак данных.
Перед заходом на новую итерацию в главном цикле while, к адресу прибавляем + 1, и к i тоже, что будет означать сдвиг вправо на единицу в исходном сообщении.
Рис. 3. Код, ч.З
В этой части будем делать красивый вывод результата работы алгоритма. Делаем это с помощью библиотеки terminaltables.
В цикле for key in arr_content добавляем данные в массив arr_for_table, который передадим аргументом в метод AsciiTable, и в результате на экран выведется следующее:
Рис. 4. Результат работы алгоритма.
Использованные источники
1. Теоретическая информатика II Лекция 4. Сжатие данных: метод Лемпеля-Зива, преобразование Берроуза-Вилера, Александр Охотин 4 марта 2019 г.
Размещено на Allbest.ru
...Подобные документы
Суть алгоритму Лемпеля-Зива. Принцип скользящого вікна, яке представлено у вигляді буфера та організовано для запам'ятовування "сказаної" раніше інформації та надання до неї доступ. Механізм кодування збігів. Приклади кодування по алгоритмам LZ78 та LZW.
презентация [59,3 K], добавлен 14.08.2013Краткий обзор основных теорий сжатия. Концепции идей и их реализация. Сжатие данных с использованием преобразования Барроуза-Вилера. Статический алгоритм Хафмана. Локально адаптивный алгоритм сжатия. Алгоритм Зива-Лемпеля (Welch) и метод Шеннона-Фано.
практическая работа [188,5 K], добавлен 24.04.2014Методы кодирования изображения: кодированием длины серии, частотно-зависимое кодирование, метод Лемпеля-Зива. Размер строки при 16-битном цвете. Расчет размера всего исходного изображения. Примеры качественного и некачественного сжатия изображения.
презентация [2,0 M], добавлен 22.10.2013Сущность метода зонного сжатия буквенной информации. Описание классов, определяющих место хранения символов и алфавита. Реализация асимметричного алгоритма RSA. Логика построения шифра и структура ключевой информации в криптографическом алгоритме ГОСТ.
контрольная работа [3,2 M], добавлен 30.11.2013Рассмотрение теоретических подходов к алгоритму сжатия LZW, который по мере поступления информации динамически вычисляет целочисленные признаки частоты появления входных символов. Возможности использования современных GPU. Графические форматы GIF и TIFF.
дипломная работа [559,8 K], добавлен 03.10.2011Основные этапы создания алгоритмов, представление в виде программы. Рассмотрение методов решения задач. Метод поэтапных уточнений. Различие между численными и логическими алгоритмами. Реализация цикла со счетчиком. Процесс разработки сложного алгоритма.
презентация [1,3 M], добавлен 22.10.2013Основные свойства алгоритма. Формальный и неформальный исполнитель алгоритма, система его команд. Способы записи алгоритма. Словесное описание, построчная запись, опорный конспект. Характеристики алгоритмического языка. Выполнение алгоритма компьютером.
презентация [2,0 M], добавлен 04.04.2014Типы сжатия данных: с потерями (lossy) и без потерь (lossless). Сжатие с минимальной избыточностью. Кодирование методом Шеннона-Фано. Проверка работы программы по сжатию файлов формата bmp и xls. Реализация на Delphi алгоритма сжатия Шеннона и Хаффмана.
курсовая работа [2,6 M], добавлен 26.01.2011Составление алгоритма сортировки линейной вставкой. Понятие однонаправленного циклического списка символов, реализация процедуры подсчета суммы элементов и составление алгоритма. Прямое представление дерева, алгоритм работы с ним на абстрактном уровне.
контрольная работа [32,8 K], добавлен 20.01.2012Методы предобработки изображений текстовых символов. Статистические распределения точек. Интегральные преобразования и структурный анализ. Реализация алгоритма распознавания букв. Анализ алгоритмов оптического распознавания символов. Сравнение с эталоном.
курсовая работа [2,1 M], добавлен 20.09.2014Оценка вычислительной сложности программы. Реализация алгоритма кодирования информации Хаффмана. Кодировка теста двоичным кодом и в дереве Хаффмана. Бинарный код символов. Символ и частота его появления в тексте. Вычисление трудоемкости алгоритма.
контрольная работа [21,0 K], добавлен 16.12.2012Состав и принцип работы аппаратуры. Выбор параметров корреляционного анализа и Фурье-анализа. Разработка и применение алгоритма корреляционного анализа. Реализация алгоритма Фурье-анализа на языке С++ и алгоритма корреляционного анализа на языке С#.
дипломная работа [4,6 M], добавлен 30.11.2016Исследование симметричных алгоритмов блочного шифрования. Минусы и плюсы алгоритма IDEA. Разработка программы аутентификации пользователя и сообщений на основе алгоритма IDEA. Выбор языка программирования. Тестирование и реализация программного средства.
курсовая работа [314,2 K], добавлен 27.01.2015Особенности метода неопределенных множителей Лагранжа, градиентного метода и метода перебора и динамического программирования. Конструирование алгоритма решения задачи. Структурная схема алгоритма сценария диалога и описание его программной реализации.
курсовая работа [1010,4 K], добавлен 10.08.2014Обзор существующих программ сжатия данных без потерь. Анализ методов сжатия: алгоритмов группы, KWE, Lossless JPEG, кодирование Хаффмана. Обзор составляющих компонентов. Разработка кода программы-архиватора, работающей на основе алгоритма Хаффмена.
курсовая работа [487,3 K], добавлен 14.07.2011Описание принципа работы генетического алгоритма, проверка его работы на функции согласно варианту на основе готовой программы. Основные параметры генетического алгоритма, его структура и содержание. Способы реализации алгоритма и его компонентов.
лабораторная работа [20,2 K], добавлен 03.12.2014Алгоритмы получения реалистических изображений. Применение алгоритма обратной трассировки лучей, ее математическая основа. Составление матрицы и программная реализация. Формирование отраженного и преломленного луча. Модульная структура программы.
курсовая работа [219,3 K], добавлен 24.06.2009Создание и реализация алгоритма решения транспортной задачи методом наименьших стоимостей. Схема алгоритма основной программы. Основные шаги алгоритма решения транспортной задачи. Инструкция по эксплуатации программы и обзор результатов ее выполнения.
курсовая работа [2,0 M], добавлен 12.02.2013Построение схемы алгоритма и программы для создания графика временной функции, работающей в машинном и реальном времени. Выбор методов решения и их обоснование. Значение коэффициентов и временной функции. Реализация временных задержек в программе.
курсовая работа [6,2 M], добавлен 09.03.2012Задачи, решаемые методом динамического программирования. Основные этапы нахождения деревянного алгоритма решения задачи. Выполнение алгоритма Прима. Построение Эйлерового цикла. Решение задач средствами Excel. Алгоритм основной программы - Derevo.
курсовая работа [586,3 K], добавлен 04.04.2015
