Алгоритм LZ78 - Анализ алгоритма Лемпеля-Зива
Этот алгоритм генерирует на основе входных данных словарь фрагментов, внося туда фрагменты данных (последовательности байт) по определенным правилам (см. ниже) и присваивает фрагментам коды (номера). При сжатии данных (поступлении на вход программы очередной порции) программа на основе LZ78 пытается найти в словаре фрагмент максимальной длины, совпадающий с данными, заменяет найденную в словаре порцию данных кодом фрагмента и дополняет словарь новым фрагментом. При заполнении всего словаря (размер словаря ограничен по определению) программа очищает словарь и начинает процесс заполнения словаря снова. Реализации этого метода различаются конструкцией словаря, алгоритмами его заполнения и очистки при переполнении [2].
Обычно, при инициализации словарь заполняется исходными (элементарными) фрагментами - всеми возможными значениями байта от 0 до 255. Это гарантирует, что при поступлении на вход очередной порции данных будет найден в словаре хотя бы однобайтовый фрагмент.
Алгоритм LZ78 резервирует специальный код, назовем его "Reset", который вставляется в упакованные данные, отмечая момент сброса словаря. Значение кода Reset обычно принимают равным 256.
Таким образом при начале кодирования минимальная длина кода составляет 9 бит. Максимальная длина кода зависит от объема словаря - количества различных фрагментов, которые туда можно поместить. Если объем словаря измерять в байтах (символах), то очевидно, что максимальное количество фрагментов равно числу символов, а, следовательно, максимальная длина кода равна log2(объем_словаря_в_байтах).
Рассмотрим алгоритм заполнения словаря на примере кодирования фрагмента. Для примера используем данные, состоящие только из символов (букв), кавычки "" не входят в данные: "aaabbabaabaaabab". Пример кодировки приведен в табл. 1
Таблица 1. LZ78-кодирование строки; где запись (i, a) обозначает копирование фразы i перед символом a.
Input: |
A |
Aa |
B |
Ba |
Baa |
Baaa |
Bab |
Phrase number: |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
Output: |
(0,a) |
(1,a) |
(0,b) |
(3,a) |
(4,a) |
(5,a) |
(4,b) |
Дальность продвижения вперед указателя неограниченна (т. е. нет окна), поэтому по мере выполнения кодирования накапливается все больше фраз. Допущение произвольно большого их количества требует по мере разбора увеличения размера указателя. Когда разобрано p фраз, указатель представляется [log p] битами. На практике, словарь не может продолжать расти бесконечно. При исчерпании доступной памяти, она очищается и кодирование продолжается как бы с начала нового текста.
Привлекательным практическим свойством LZ78 является эффективный поиск в дереве цифрового поиска при помощи вставки. Каждый узел содержит номер представляемой им фразы. Т. к. вставляемая фраза будет лишь на один символ длиннее одной из ей предшествующих, то для осуществления этой операции кодировщику будет нужно только спуститься вниз по дереву на одну дугу.
Дополнительных данных для декодирования не требуется. Восстановить исходные данные можно, располагая только кодированной последовательностью. Действительно, если считать, что в качестве входных данных поступает кодированная последовательность, то можно восстанавливать словарь так, что к моменту поступления нового кода на вход, в словаре уже будет соответствующая последовательность символов.
Таким образом, алгоритм упаковки и распаковки методом LZ78 достаточно прост. Основную проблему при реализации этого метода представляет устройство словаря. Очевидно, что чем больше словарь, тем (при прочих равных условиях) большую степень сжатия можно достичь.
С другой стороны, важным практическим моментом является скорость упаковки, этот параметр тоже зависит от устройства словаря. Основные операции при упаковке:
- 1) поиск в словаре фрагмента; 2) вставка в словарь новых фрагментов.
Необходимо, чтобы эти две операции были максимально быстрыми.
Похожие статьи
-
Идея алгоритма Лемпеля-Зива, Алгоритм LZ77 - Анализ алгоритма Лемпеля-Зива
Основная идея алгоритма Лемпеля-Зива состоит в замене появления фрагмента в данных (группы байт) ссылкой на предыдущее появление этого фрагмента....
-
Сжатие данных можно разделить на два основных типа: 1) Сжатие без потерь или полностью обратимое; 2) Сжатие с потерями, когда несущественная часть данных...
-
Модификации алгоритма Лемпеля-Зива, предложенная Терри Уэлчем - Анализ алгоритма Лемпеля-Зива
В 1984 году Терри Уэлч (Terry Welch) предложил адаптивный сброс словаря для алгоритма LZ78 [3]. В этом случае при заполнении словаря сброс словаря не...
-
ЗАКЛЮЧЕНИЕ, СПИСОК ЛИТЕРАТУРЫ - Анализ алгоритма Лемпеля-Зива
В данной курсовой работе был подробно рассмотрен один из алгоритмов Лемпеля-Зива (LZW) для упаковки-распаковки произвольных данных. В процессе изучения...
-
ВВЕДЕНИЕ - Анализ алгоритма Лемпеля-Зива
Одна из задач любой информационной системы обеспечивать хранение и передачу информации. Причем хранение и передача информации занимают определяющее место...
-
Для ускорения процесса конструирования регулятора в пространстве состояний в Matlab была разработана функция, которая, при должной настройке, позволяет...
-
Для иллюстрации последовательности проводимых работ приведем диаграмму Гантта данного проекта, на которой по оси Х изображены календарные дни от начала...
-
Архитектура разрабатываемой системы имеет два уровня: нижний - подсистема управления (датчики, микроконтроллер, исполнительные механизмы и оборудование)...
-
Исходя из контекста решаемой задачи, для сравнительного анализа рассмотренных математических моделей обнаружения аномалий можно выбрать следующие...
-
Предложенный подход к решению задач исследования Используя в качестве основы присутствующее в наличии программное обеспечение, которое применимо к...
-
Формы и характеристики параллелизма Параллелизм -- это возможность одновременного выполнения нескольких арифметико-логических или служебных операций. На...
-
Определение методов реинжиниринга информационных систем Основные задачи, которые стоят перед проектировщиком, занимающимся реинжинирингом информационных...
-
Свойства алгоритмов - Алгоритм
Данное выше определение алгоритма нельзя считать строгим - не вполне ясно, что такое "точное предписание" или "последовательность действий,...
-
Разработаем алгоритм одного из основных методов, используемого в данной программе. Private void pictureBox1_MouseDown(objects sender, MouseEventArgs e)...
-
В работе возникает необходимость выбора предметной области, в которой будет тестироваться каскадный классификатор. Главными вопросами на данном этапе...
-
Введение - Исследование алгоритмов
С недавнего времени такая область кибернетики, как создание искусственных систем распознавания образов, стала представлять особый интерес. Потребность в...
-
Етапи рішення прикладних задач з використанням комп'ютерів 1) Формулювання задачі в термінах певної предметної галузі знань (математика, фізика,...
-
Общее описание программного обеспечения, реализующего разработанный алгоритм Основной идеей дипломного проекта, является реализация алгоритма...
-
Данный алгоритм (англ. Maximal Neighborhood Search - MNS) [7] в отличие от алгоритма BFS позволяет дополнительно упорядочить вершины в найденных...
-
Анализ принципа работы БП адаптера связи ОП - Работка буферной памяти адаптера связи
Буферная память этопамять для промежуточного хранения данных. Применяется при обмене данными между двумя устройствами, обладающими различной скоростью...
-
Для разработки БД автоматизированной системы "Эффективного использования рабочего времени", я выбрала СУБД Microsoft Access 2003. Основное назначение БД...
-
Кейс 1. Реальная новость: "Министр обороны: Италия может направить миротворцев на Украину" Описательная статистика Общее количество упоминаний по всем...
-
Онлайн исследования в социологии: новые методы анализа данных - Распространение новостной информации
На сегодняшний день анализ социальных сетей и медиа, Интернет-сообществ, пользователей в целом используется в основном в маркетинге. Компания может...
-
Прогнозирование оттока клиентов Отделом маркетинга компании ELEMENTAREE было выявлено, что практически все клиенты, у которых отсутствовали заказы в...
-
Для того, чтобы разработать оптимальный метод интеграции сторонних систем в существующую ИТ-инфраструктуру систем компании, требуется точно поставить...
-
Криптография, аутентификация - Анализ средств защиты информации в ЛВС
Проблемой защиты информации путем ее преобразования занимается криптология (kryptos - тайный, logos - наука). Криптология разделяется на два направления...
-
Цель Работы - изучить основные способы работы с пользовательским типом данных "класс", его объектами, методами и способы доступа к ним. - Теоретические...
-
Информационная система крупной организации, как правило, представляет собой исторически сложившуюся совокупность отдельно работающих систем, которые...
-
UML - унифицированный язык моделирования, призванный упростить построение больших информационных систем. Состоит из диаграмм, связей и сущностей....
-
Теоретические предпосылки исследования Системы поддержки принятия решений Системы поддержки принятия решений (СППР), представляют собой приложения узкого...
-
Прямое использование предсказания позволяет воспроизводить звук, но с плохим качеством. Поэтому этот метод имеет много различных разновидностей,...
-
Создадим структурную схему САУ при помощи пакета Simulink. На рисунке представлена разомкнутая система. Рис. 2 Далее, следуя методическим указаниям,...
-
Описание предметной области ООО ИСК "Волгастройинвест" является официальным представителем ряда отечественных и зарубежных фирм, предлагающих на...
-
ИИС "Шлаковые расплавы" позволяет вести моделирование КЭ в нескольких "режимах", с полным набором получаемых свойств. 1. Моделирование комплекса свойств...
-
Программная модель данных, получившая название "MapReduce", была создана несколько лет назад в компании Google, и там же была осуществлена первая...
-
Полное наименование разрабатываемой системы - корпоративная информационная система "Бюджетное планирование и отчетность" группы компаний, занимающейся...
-
Обоснование выбора средств разработки проекта Для реализации корпоративной информационной системы "Бюджетное планирование и отчетность" в исследуемой...
-
В качестве предметной области для дипломного проекта была выбрана организация МКДОУ детский сад №85 "Почемучка". Описание и основные виды деятельности...
-
Основным объектом предметной области является локальная вычислительная сеть (ЛВС). Основными свойствами являются: - Быстродействие; - Масштабируемость; -...
-
Решения компании IBM - Технологии больших данных: анализ и выбор решения для реализации проекта
Технологии анализа больших данных являются прекрасным дополнением к средам хранения больших данных. Множество применений включает в себя, например,...
Алгоритм LZ78 - Анализ алгоритма Лемпеля-Зива