СПОСОБЫ СЖАТИЯ ИНФОРМАЦИИ, АЛГОРИТМЫ СЖАТИЯ БЕЗ ПОТЕРЬ, Обзор алгоритмов - Анализ алгоритма Лемпеля-Зива
Сжатие данных можно разделить на два основных типа:
- 1) Сжатие без потерь или полностью обратимое; 2) Сжатие с потерями, когда несущественная часть данных утрачивается и полное восстановление невозможно.
Первый тип сжатия применяют, когда данные важно восстановить после сжатия в неискаженном виде, это важно для текстов, числовых данных и т. п. Полностью обратимое сжатие, по определению, ничего не удаляет из исходных данных. Сжатие достигается только за счет иного, более экономичного, представления данных.
Второй тип сжатия применяют, в основном, для видеоизображений и звука. За счет потерь удаления несущественной части данных может быть достигнута более высокая степень сжатия. В этом случае потери при сжатии означают незначительное искажение изображения(звука) которые не препятствуют нормальному восприятию (незаметны), но при детальном сличении оригинала и восстановленной после сжатия копии могут быть обнаружены.
АЛГОРИТМЫ СЖАТИЯ БЕЗ ПОТЕРЬ
Обзор алгоритмов
Сжатие информация алгоритм
В настоящее время существует несколько алгоритмов сжатия без потерь, частично это открытые алгоритмы, частично коммерческие алгоритмы. Открытые алгоритмы обычно рассматривают только саму идею, не останавливаясь на проблемах ее реализации в виде программы или реализованы в виде "демонстрационной" (не очень эффективной) программы. Коммерческий алгоритм обычно включает в себя не только идею алгоритма сжатия, но и эффективную реализацию алгоритма в виде программы. Коммерческие алгоритмы не публикуются и познакомится с ними невозможно, за исключением ознакомления с результатами работы программ на базе этих алгоритмов. Соответствующие программы (ZIP, ARJ, RAR, ACE и др.) достаточно известны и с ними можно познакомиться самостоятельно.
Алгоритмы обратимого сжатия данных можно разделить на две группы:
- 1) Алгоритмы частотного анализа для подсчета частоты различных символов в данных и преобразование кодов символов с соответствии с их частотой. 2) Алгоритмы корреляционного анализа для поиска корреляций (в простейшем случае точных повторов) между различными участками данных и замена коррелирующих данных на код(ы), позволяющая восстановить данные на основе предшествующих данных. В простейшем случае точных повторов, кодом является ссылка на начало предыдущего вхождения этой последовательности символов в данных и длина последовательности.
Можно отметить следующие алгоритмы обратимого сжатия данных из первой группы [1]:
- 1) Метод Хаффмана - замена кода равной длины для символов на коды неравной длины в соответствии с частотой появления символов в данных. Коды минимальной длины присваиваются наиболее часто встречающимся символам. Если частоты появления символов являются степенью двойки (2N), то этот метод достигает теоретической энтропийной границы эффективности сжатия для методов такого типа. 2) Метод Шеннона-Фано - сходен с методом Хаффмана, но использует другой алгоритм генерации кодов и не всегда дает оптимальные коды (оптимальный код - код дающий наибольшее сжатие данных из всех возможных для данного типа преобразования). 3) Арифметическое кодирование - усовершенствование метода Хаффмана, позволяющее получать оптимальные коды для данных, где частоты появления символов не являются степенью двойки (2N). Этот метод достигает теоретической энтропийной границы эффективности сжатия этого типа для любого источника.
Для второй группы можно назвать следующие алгоритмы [1]:
- 1) Метод Running (или RLE) - заменяет цепочки повторяющихся символов на код символа и число повторов. Это пример элементарного и очень понятного метода сжатия, но, к сожалению, он не обладает достаточной эффективностью. 2) Методы Лемпеля-Зива - это группа алгоритмов сжатия объединенная общей идеей: поиск повторов фрагментов текста в данных и замена повторов ссылкой (кодом) на первое (или предыдущее) вхождение этого фрагмента в данные. Отличаются друг от друга методом поиска фрагментов и методом генерации ссылок(кодов).
В настоящее время, в различных модификациях и сочетаниях, два алгоритма - метод Хаффмана (или арифметическое кодирование) и метод Лемпеля-Зива - составляют основу всех коммерческих алгоритмов и программ.
Далее будут подробно рассмотрены несколько вариантов алгоритма сжатия Лемпеля-Зива и на основе модификации этого алгоритма Терри Уэлчем разработана действующая программа для архивирования и разархивирования файлов.
Похожие статьи
-
Алгоритм LZ78 - Анализ алгоритма Лемпеля-Зива
Этот алгоритм генерирует на основе входных данных словарь фрагментов, внося туда фрагменты данных (последовательности байт) по определенным правилам (см....
-
ЗАКЛЮЧЕНИЕ, СПИСОК ЛИТЕРАТУРЫ - Анализ алгоритма Лемпеля-Зива
В данной курсовой работе был подробно рассмотрен один из алгоритмов Лемпеля-Зива (LZW) для упаковки-распаковки произвольных данных. В процессе изучения...
-
Идея алгоритма Лемпеля-Зива, Алгоритм LZ77 - Анализ алгоритма Лемпеля-Зива
Основная идея алгоритма Лемпеля-Зива состоит в замене появления фрагмента в данных (группы байт) ссылкой на предыдущее появление этого фрагмента....
-
Модификации алгоритма Лемпеля-Зива, предложенная Терри Уэлчем - Анализ алгоритма Лемпеля-Зива
В 1984 году Терри Уэлч (Terry Welch) предложил адаптивный сброс словаря для алгоритма LZ78 [3]. В этом случае при заполнении словаря сброс словаря не...
-
ВВЕДЕНИЕ - Анализ алгоритма Лемпеля-Зива
Одна из задач любой информационной системы обеспечивать хранение и передачу информации. Причем хранение и передача информации занимают определяющее место...
-
Экономить можно то, что учтено. Сегодня нет масштабной федеральной программы совершенствования учета. До сих пор большинство потребителей пользуется...
-
Выполнения проекта монтажа охранной сигнализации состоит из множества операций, которые складываются в этапы работ проекта. Схематично структура этапов...
-
В работе возникает необходимость выбора предметной области, в которой будет тестироваться каскадный классификатор. Главными вопросами на данном этапе...
-
ПРИНЦИПЫ СЖАТИЯ ИНФОРМАЦИИ - Архивация информации и программы-архиваторы
В основе любого способа сжатия информации лежит модель источника информации, или, более конкретно, модель избыточности. Иными словами для сжатия...
-
Для ускорения процесса конструирования регулятора в пространстве состояний в Matlab была разработана функция, которая, при должной настройке, позволяет...
-
Обзор протокола Multi-Touch технологий передачи данных TUIO [7] - основной кроссплатформенный протокол с открытым исходным кодом Multi-Touch передачи...
-
Криптография, аутентификация - Анализ средств защиты информации в ЛВС
Проблемой защиты информации путем ее преобразования занимается криптология (kryptos - тайный, logos - наука). Криптология разделяется на два направления...
-
Следующей задачей было изучение литературы по теме и ее анализ. Для этого использовались публикации из российских источников с целью учета особенностей...
-
В данной части работы, рассмотрим необходимое программное обеспечение для распознавания и перевода вышеприведенных документов из графического формата в...
-
Онлайн исследования в социологии: новые методы анализа данных - Распространение новостной информации
На сегодняшний день анализ социальных сетей и медиа, Интернет-сообществ, пользователей в целом используется в основном в маркетинге. Компания может...
-
В качестве предметной области для дипломного проекта была выбрана организация МКДОУ детский сад №85 "Почемучка". Описание и основные виды деятельности...
-
Как представлять непрерывную информацию?, Выводы - Информация и способы ее получения
Для представления непрерывной величины могут использоваться самые разнообразные физические процессы. В рассмотренном выше примере весы позволяют величину...
-
На данный момент существует множество аналогов данного приложения, можно выделить такие как стандартный проводник Windows и Total Commander. Заказчику...
-
Анализ фильма "Encounter: Желание жить" - Encounter как способ игрового освоения пространства
Итак, на основе перечисленных постулатов, проанализируем первый фильм - "Encounter: Желание жить"_ Фильмы: [Электронный ресурс] // EncounterTM Ltd....
-
Описание переменных, Способы ввода/вывода информации - Система поиска автобусных маршрутов
В программе описана и используется одна глобальная переменная Town: TTown. Данная переменная содержит список остановок и автобусных маршрутов. Остальные...
-
ЗАКЛЮЧЕНИЕ - Анализ потерь рабочего времени сорудников предприятия
Создание системы анализа эффективного использования рабочего времени, а также постоянное присутствие Контролеров Заказчика на стройплощадках позволили...
-
Предложенный подход к решению задач исследования Используя в качестве основы присутствующее в наличии программное обеспечение, которое применимо к...
-
Разработаем алгоритм одного из основных методов, используемого в данной программе. Private void pictureBox1_MouseDown(objects sender, MouseEventArgs e)...
-
Формы и характеристики параллелизма Параллелизм -- это возможность одновременного выполнения нескольких арифметико-логических или служебных операций. На...
-
ОСНОВНЫЕ ПРОГРАММЫ АРХИВАТОРЫ И ИХ ФУНКЦИИ - Архивация информации и программы-архиваторы
Назначение программ-архиваторов заключается в экономии места на диске за счет сжатия (упаковки) одного или нескольких файлов в архивный файл....
-
Входная информация разделяется на условно-постоянную и оперативно-учетную информацию. - Условно-постоянная информация включает в себя справочные данные о...
-
Обзор модулей системы - Моделирование и анализ процессов внутреннего документооборота предприятия
Структурно модули системы представляют собой наборы компонент различных типов. Компоненты имеют характерный интерфейс и наборы данных, определяемые их...
-
Трудоемкость производство алгоритм excel Трудоемкость годовой производственной программы Трудоемкость по профессии и разряду, ч. 4145,00 Структура...
-
Необходимо исследовать зависимость влияния различных факторов на параметр, характеризующий производство. В качестве такого параметра было выбрано...
-
Графический способ описания алгоритмов
Графический способ описания алгоритмов Цель практической работы Цель работы: изучение графического способа описания алгоритма для решения задачи. Задачи...
-
Преобразование коэффициентов Основным набором передаваемых параметров в вокодере с линейным предсказанием являются М коэффициентов фильтра с...
-
Что объединяет непрерывные и дискретные величины? - Информация и способы ее получения
В качестве простого примера, иллюстрирующего наши рассуждения, рассмотрим пружинные весы. Масса тела, измеряемая на них, - величина непрерывная по своей...
-
Для разработки БД автоматизированной системы "Эффективного использования рабочего времени", я выбрала СУБД Microsoft Access 2003. Основное назначение БД...
-
Антивирусные программы Для обнаружения, удаления и защиты от компьютерных вирусов разработано несколько видов специальных программ, которые позволяют...
-
ВВЕДЕНИЕ - Анализ средств защиты информации в ЛВС
Вопрос защиты информации поднимается уже с тех пор, как только люди научились письменной грамоте. Всегда существовала информация, которую не должны знать...
-
Современные технологии обработки Больших данных Большой проект бюджетирование автоматизация С приходом новых технологий, инструментов и средств...
-
ВЫБОР ПРОГРАММНО-ТЕХНИЧЕСКИХ СРЕДСТВ - Анализ потерь рабочего времени сорудников предприятия
Платформа СУБД Microsoft Access 2003 функционирует на платформе IBM PC, т. к. создана для операционной системы Windows. В настоящее время данная...
-
Кейс 1. Реальная новость: "Министр обороны: Италия может направить миротворцев на Украину" Описательная статистика Общее количество упоминаний по всем...
-
Аппаратный брандмауэр - Анализ средств защиты информации в ЛВС
Информация в век цифровых технологий приравнена к деньгам, а раз так -- ее нужно охранять. В Интернете всегда найдутся желающие поинтересоваться...
-
Сетевой анализ как метод изучения виртуального пространства - Распространение новостной информации
Анализ социальных сетей как отдельное направление появилось в конце 20 века, основоположниками которого считаются такие ученые как Милгрэм ("феномен...
СПОСОБЫ СЖАТИЯ ИНФОРМАЦИИ, АЛГОРИТМЫ СЖАТИЯ БЕЗ ПОТЕРЬ, Обзор алгоритмов - Анализ алгоритма Лемпеля-Зива