Сжатие данных через алгоритм Лемпеля - Зиива - Веелча
Понятие потоков данных как унифицированного программного интерфейса для чтения, записи файлов, сокетов и передачи данных между процессами. Поддержка потоков, сжатие данных. Применение алгоритма Лемпеля - Зиива - Веелча, кодирование и декодирование данных.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 07.08.2013 |
| Размер файла | 378,0 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Московский Государственный Открытый Университет
Курсовая работа
по дисциплине: "Методы и средства защиты компьютерной информации"
на тему: "Сжатие данных через алгоритм Лемпеля - Зиива - Веелча"
Подготовил: студент 4 курса
Ягодкин А.А.
Принял: Найденов В.В.
Содержание
- Программирование потоком данных
- Сжатие данных
- Алгоритм Лемпеля - Зиива - Веелча
- Кодирование
- Декодирование
- Список литературы
- Приложение
Программирование потоком данных
В программировании, программирование потоком данных представляет собой парадигму программирования, в которой операторы программы описывают подходящие данные и правила их обработки, а не последовательность предпринимаемых шагов. Применение методов конструирования абстрактных типов данных в объектно-ориентированном программировании приводит к архитектуре, управляемой данными. Этот тип архитектуры используется в объектно-ориентированном программировании для определения классов в рамках концепции частей программного обеспечения. Программирование потоком данных приводит к плохому объектно-ориентированному проектированию, в то время как проектирование на базе ответственности считается лучшим подходом.
Поток данных в программировании - абстракция, используемая для чтения или записи файлов, сокетов и т.п. в единой манере.
Потоки являются удобным унифицированным программным интерфейсом для чтения или записи файлов (в том числе специальных и, в частности, связанных с устройствами), сокетов и передачи данных между процессами.
Поддержка потоков включена в большинство языков программирования и едва ли не во все современные (на 2008 год) операционные системы. При запуске процесса ему предоставляются предопределённые стандартные потоки.
Возможность перенаправления потоков позволяет связывать различные программы, и придаёт системе гибкость, являющуюся частью философии Unix.
Абстракция потока особенно важна в языке программирования Си, где он представляет собой источник ввода и/или вывода данных, обычно байтов, связанный с файлом, устройством, либо другим процессом. Работа с потоками перенесена во многие другие языки:
· C++: iostream из стандартной библиотеки C++.
· Языки платформы .net Framework (например, C#): Base Class Library, пространство имен System. IO.
Поток данных в операционных системах
Сжатие данных
Сжатие данных - алгоритмическое преобразование данных, производимое с целью уменьшения их объёма. Применяется для более рационального использования устройств хранения и передачи данных. Синонимы - упаковка данных, компрессия, сжимающее кодирование, кодирование источника. Обратная процедура называется восстановлением данных (распаковкой, декомпрессией).
Сжатие основано на устранении избыточности, содержащейся в исходных данных. Простейшим примером избыточности является повторение в тексте фрагментов (например, слов естественного или машинного языка). Подобная избыточность обычно устраняется заменой повторяющейся последовательности ссылкой на уже закодированный фрагмент с указанием его длины. Другой вид избыточности связан с тем, что некоторые значения в сжимаемых данных встречаются чаще других. Сокращение объёма данных достигается за счёт замены часто встречающихся данных короткими кодовыми словами, а редких - длинными (энтропийное кодирование). Сжатие данных, не обладающих свойством избыточности (например, случайный сигнал или белый шум, зашифрованные сообщения), принципиально невозможно без потерь.
В основе любого способа сжатия лежит модель источника данных, или, точнее, модель избыточности. Иными словами, для сжатия данных используются некоторые априорные сведения о том, какого рода данные сжимаются. Не обладая такими сведениями об источнике, невозможно сделать никаких предположений о преобразовании, которое позволило бы уменьшить объём сообщения. Модель избыточности может быть статической, неизменной для всего сжимаемого сообщения, либо строиться или параметризоваться на этапе сжатия (и восстановления). Методы, позволяющие на основе входных данных изменять модель избыточности информации, называются адаптивными. Неадаптивными являются обычно узкоспециализированные алгоритмы, применяемые для работы с данными, обладающими хорошо определёнными и неизменными характеристиками. Подавляющая часть достаточно универсальных алгоритмов являются в той или иной мере адаптивными.
Все методы сжатия данных делятся на два основных класса:
· Сжатие без потерь
· Сжатие с потерями
При использовании сжатия без потерь возможно полное восстановление исходных данных, сжатие с потерями позволяет восстановить данные с искажениями, обычно несущественными с точки зрения дальнейшего использования восстановленных данных. Сжатие без потерь обычно используется для передачи и хранения текстовых данных, компьютерных программ, реже - для сокращения объёма аудио - и видеоданных, цифровых фотографий и т.п., в случаях, когда искажения недопустимы или нежелательны. Сжатие с потерями, обладающее значительно большей, чем сжатие без потерь, эффективностью, обычно применяется для сокращения объёма аудио - и видеоданных и цифровых фотографий в тех случаях, когда такое сокращение является приоритетным, а полное соответствие исходных и восстановленных данных не требуется.
Коэффициент сжатия
Коэффициент сжатия - основная характеристика алгоритма сжатия. Она определяется как отношение объёма исходных несжатых данных к объёму сжатых, то есть:
,
где k - коэффициент сжатия, So - объём исходных данных, а Sc - объём сжатых. Таким образом, чем выше коэффициент сжатия, тем алгоритм эффективнее. Следует отметить:
· если k = 1, то алгоритм не производит сжатия, то есть выходное сообщение оказывается по объёму равным входному;
· если k < 1, то алгоритм порождает сообщение большего размера, нежели несжатое, то есть, совершает "вредную" работу.
Ситуация с k < 1 вполне возможна при сжатии. Принципиально невозможно получить алгоритм сжатия без потерь, который при любых данных образовывал бы на выходе данные меньшей или равной длины. Обоснование этого факта заключается в том, что поскольку число различных сообщений длиной n бит составляет ровно 2n, число различных сообщений с длиной меньшей или равной n (при наличии хотя бы одного сообщения меньшей длины) будет меньше 2n. Это значит, что невозможно однозначно сопоставить все исходные сообщения сжатым: либо некоторые исходные сообщения не будут иметь сжатого представления, либо нескольким исходным сообщениям будет соответствовать одно и то же сжатое, а значит их нельзя отличить. Однако даже когда алгоритм сжатия увеличивает размер исходных данных, легко добиться того, чтобы их объём гарантировано не мог увеличиться более, чем на 1 бит. Тогда даже в самом худшем случае будет иметь место неравенство:
Делается это следующим образом: если объём сжатых данных меньше объёма исходных, возвращаем сжатые данные, добавив к ним "1", иначе возвращаем исходные данные, добавив к ним "0"). Пример того, как это реализуется на псевдо-C++, показан ниже:
bin_data_t __compess (bin_data_t input) // bin_data_t - тип данных, означающий произвольную последовательность бит переменной длины
{
bin_data_t output = arch (input); // функция bin_data_t arch (bin_data_t input) реализует некий алгоритм сжатия данных
if (output. size () <input. size ()) // если объём сжатых данных меньше объёма исходных, функция bin_data_t:: size () возвращает размер данных
{
output. add_begin (1); // функция bin_data_t:: add_begin (bool __bit__) добавляет бит, равный __bit__ в начало последовательности
return output; // возвращаем сжатую последовательность с добавленной "1"
}
else // иначе (если объём сжатых данных больше или равен объёму исходных)
{
input. add_begin (0); // добавляем "0" к исходной последовательности
return input; // возвращаем исходный файл с добавленным "0"
}
}
Коэффициент сжатия может быть как постоянным (некоторые алгоритмы сжатия звука, изображения и т.п., например А-закон, м-закон, ADPCM, усечённое блочное кодирование), так и переменным. Во втором случае он может быть определён либо для каждого конкретного сообщения, либо оценён по некоторым критериям:
· средний (обычно по некоторому тестовому набору данных);
· максимальный (случай наилучшего сжатия);
· минимальный (случай наихудшего сжатия);
или каким-либо другим. Коэффициент сжатия с потерями при этом сильно зависит от допустимой погрешности сжатия или качества, которое обычно выступает как параметр алгоритма. В общем случае постоянный коэффициент сжатия способны обеспечить только методы сжатия данных с потерями.
Основным критерием различия между алгоритмами сжатия является описанное выше наличие или отсутствие потерь. В общем случае алгоритмы сжатия без потерь универсальны в том смысле, что их применение безусловно возможно для данных любого типа, в то время как возможность применения сжатия с потерями должна быть обоснована. Для некоторых типов данных искажения не допустимы в принципе. В их числе
· символические данные, изменение которых неминуемо приводит к изменению их семантики: программы и их исходные тексты, двоичные массивы и т.п.;
· жизненно важные данные, изменения в которых могут привести к критическим ошибкам: например, получаемые с медицинской измерительной аппаратуры или контрольных приборов летательных, космических аппаратов и т.п.;
алгоритм сжатие поток кодирование
· многократно подвергаемые сжатию и восстановлению промежуточные данные при многоэтапной обработке графических, звуковых и видеоданных.
Системные требования алгоритмов
Различные алгоритмы могут требовать различного количества ресурсов вычислительной системы, на которых они реализованы:
· оперативной памяти (под промежуточные данные);
· постоянной памяти (под код программы и константы);
· процессорного времени.
В целом, эти требования зависят от сложности и "интеллектуальности" алгоритма. Общая тенденция такова: чем эффективнее и универсальнее алгоритм, тем большие требования к вычислительным ресурсам он предъявляет. Тем не менее, в специфических случаях простые и компактные алгоритмы могут работать не хуже сложных и универсальных. Системные требования определяют их потребительские качества: чем менее требователен алгоритм, тем на более простой, а следовательно, компактной, надёжной и дешёвой системе он может быть реализован.
Так как алгоритмы сжатия и восстановления работают в паре, имеет значение соотношение системных требований к ним. Нередко можно усложнив один алгоритм значительно упростить другой. Таким образом, возможны три варианта:
Алгоритм сжатия требует больших вычислительных ресурсов, нежели алгоритм восстановления.
Это наиболее распространённое соотношение, характерное для случаев, когда однократно сжатые данные будут использоваться многократно. В качестве примера можно привести цифровые аудио - и видеопроигрыватели.
Алгоритмы сжатия и восстановления требуют приблизительно равных вычислительных ресурсов.
Наиболее приемлемый вариант для линий связи, когда сжатие и восстановление происходит однократно на двух её концах (например, в цифровой телефонии).
Алгоритм сжатия существенно менее требователен, чем алгоритм восстановления.
Такая ситуация характерна для случаев, когда процедура сжатия реализуется простым, часто портативным устройством, для которого объём доступных ресурсов весьма критичен, например, космический аппарат или большая распределённая сеть датчиков. Это могут быть также данные, распаковка которых требуется в очень малом проценте случаев, например запись камер видеонаблюдения.
Имеется два основных подхода к сжатию данных неизвестного формата.
· На каждом шаге алгоритма сжатия очередной сжимаемый символ либо помещается в выходной буфер сжимающего кодера как есть (со специальным флагом, помечающим, что он не был сжат), либо группа из нескольких сжимаемых символов заменяется ссылкой на совпадающую с ней группу из уже закодированных символов. Поскольку восстановление сжатых таким образом данных выполняется очень быстро, такой подход часто используется для создания самораспаковывающихся программ.
· Для каждой сжимаемой последовательности символов однократно либо в каждый момент времени собирается статистика её встречаемости в кодируемых данных. На основе этой статистики вычисляется вероятность значения очередного кодируемого символа (либо последовательности символов). После этого применяется та или иная разновидность энтропийного кодирования, например, арифметическое кодирование или кодирование Хаффмана, для представления часто встречающихся последовательностей короткими кодовыми словами, а редко встречающихся - более длинными.
Алгоритм Лемпеля - Зиива - Веелча
Алгоритм Лемпеля - Зиива - Веелча - это универсальный алгоритм сжатия данных без потерь, созданный Абрахамом Лемпелем, Якобом Зивом и Терри Велчем. Он был опубликован Велчем в 1984 году, в качестве улучшенной реализации алгоритма LZ78, опубликованного Лемпелем и Зивом в 1978 году. Алгоритм разработан так, чтобы его можно было быстро реализовать, но он не обязательно оптимален, поскольку он не проводит никакого анализа входных данных.
Акроним "LZW" указывает на фамилии изобретателей алгоритма: Лемпель, Зив и Велч, но многие утверждают, что, поскольку патент принадлежал Зиву [кто? ], то метод должен называться алгоритмом Зива - Лемпеля - Велча.
Данный алгоритм при сжатии (кодировании) динамически создаёт таблицу преобразования строк: определённым последовательностям символов (словам) ставятся в соответствие группы бит фиксированной длины (обычно 12-битные). Таблица инициализируется всеми 1-символьными строками (в случае 8-битных символов - это 256 записей). По мере кодирования, алгоритм просматривает текст символ за символом, и сохраняет каждую новую, уникальную 2-символьную строку в таблицу в виде пары код/символ, где код ссылается на соответствующий первый символ. После того как новая 2-символьная строка сохранена в таблице, на выход передаётся код первого символа. Когда на входе читается очередной символ, для него по таблице находится уже встречавшаяся строка максимальной длины, после чего в таблице сохраняется код этой строки со следующим символом на входе; на выход выдаётся код этой строки, а следующий символ используется в качестве начала следующей строки.
Алгоритму декодирования на входе требуется только закодированный текст, поскольку он может воссоздать соответствующую таблицу преобразования непосредственно по закодированному тексту.
1. Инициализация словаря всеми возможными односимвольными фразами. Инициализация входной фразы W первым символом сообщения.
2. Найти в словаре строку W наибольшей длины, которая совпадает с последними принятыми символами.
3. Считать очередной символ K из кодируемого сообщения.
4. Если КОНЕЦ_СООБЩЕНИЯ, то выдать код для W, иначе
5. Если фраза WK уже есть в словаре, присвоить входной фразе W значение WK и перейти к Шагу 3, иначе выдать код W, добавить WK в словарь, присвоить входной фразе W значение K и перейти к Шагу 3.
6. Конец
На момент своего появления алгоритм LZW давал лучший коэффициент сжатия, для большинства приложений, чем любой другой хорошо известный метод того времени. Он стал первым широко используемым на компьютерах методом сжатия данных.
Алгоритм был реализован в программе compress, которая стала более или менее стандартной утилитой Unix-систем приблизительно в 1986 году. Несколько других популярных утилит-архиваторов также используют этот метод или близкие к нему.
В 1987 году алгоритм стал частью стандарта на формат изображений GIF. Он также может (опционально) использоваться в формате TIFF.
В настоящее время, алгоритм содержится в стандарте PDF.
Данный пример показывает алгоритм LZW в действии, показывая состояние выходных данных и словаря на каждой стадии, как при кодировании, так и при раскодировании сообщения. С тем чтобы сделать изложение проще, мы ограничимся простым алфавитом - только заглавные буквы, без знаков препинания и пробелов. Сообщение, которое нужно сжать, выглядит следующим образом:
TOBEORNOTTOBEORTOBEORNOT#
Маркер # используется для обозначения конца сообщения. Тем самым, в нашем алфавите 27 символов (26 заглавных букв от A до Z и #). Компьютер представляет это в виде групп бит, для представления каждого символа алфавита нам достаточно группы из 5 бит на символ. По мере роста словаря, размер групп должен расти, с тем чтобы учесть новые элементы.5-битные группы дают 25 = 32 возможных комбинации бит, поэтому, когда в словаре появится 33-е слово, алгоритм должен перейти к 6-битным группам. Заметим, что, поскольку используется группа из всех нолей 00000, то 33-я группа имеет код 32. Начальный словарь будет содержать:
# = 00000
A = 00001
B = 00010
C = 00011
.
.
.
Z = 11010
Кодирование
Без использования алгоритма LZW, при передаче сообщения как оно есть - 25 символов по 5 бит на каждый - оно займёт 125 бит. Сравним это с тем, что получается при использовании LZW:
Таким образом, используя LZW мы сократили сообщение на 29 бит из 125 - это почти 22 %. Если сообщение будет длиннее, то элементы словаря будут представлять всё более и более длинные части текста, благодаря чему повторяющиеся слова будут представлены очень компактно.
Декодирование
Теперь представим что мы получили закодированное сообщение, приведённое выше, и нам нужно его декодировать. Прежде всего, нам нужно знать начальный словарь, а последующие записи словаря мы можем реконструировать уже на ходу, поскольку они являются просто конкатенацией предыдущих записей.
Единственная небольшая трудность может возникнуть, если новое слово словаря пересылается немедленно. В приведённом выше примере декодирования, когда декодер встречает первый символ, T, он знает, что слово 27 начинается с T, но чем оно заканчивается? Проиллюстрируем проблему следующим примером. Мы декодируем сообщение ABABA:
На первый взгляд, для декодера это неразрешимая ситуация. Мы знаем наперёд, что словом 47 должно быть ABA, но как декодер узнает об этом? Заметим, что слово 47 состоит из слова 29 плюс символ идущий следующим. Таким образом, слово 47 заканчивается на "символ идущий следующим". Но, поскольку это слово посылается немедленно, то оно должно начинаться с "символа идущего следующим", и поэтому оно заканчивается тем же символом что и начинается, в данном случае - A. Этот трюк позволяет декодеру определить, что слово 47 это ABA.
В общем случае, такая ситуация появляется, когда кодируется последовательность вида cScSc, где c - это один символ, а S - строка, причём слово cS уже есть в словаре.
На алгоритм LZW и его вариации был выдан ряд патентов, как в США, так и в других странах. На LZ78 был выдан американский патент U. S. Patent 4 464 650, принадлежащий Sperry Corporation, позднее ставшей частью Unisys Corporation. На LZW в США были выданы два патента: U. S. Patent 4 814 746, принадлежащий IBM, и патент Велча U. S. Patent 4 558 302 (выдан 20 июня 1983 года), принадлежащий Sperry Corporation, позднее перешедший к Unisys Corporation. К настоящему времени, сроки всех патентов истекли.
Список литературы
1. Stutz, Michael Get started with GAWK: AWK language fundamentals. developerWorks. IBM (September 19, 2006). - " [AWK] часто называют языком, управляемым данными - операторы программы описывают подходящие входные данные и их обработку, а не последовательность шагов программы" Архивировано из первоисточника 2 сентября 2012. Проверено 23 октября 2010.
2. (1989)"Object-oriented design: a responsibility-driven approach". Conference Proceedings on Object-Oriented Programming Systems, Languages and Applications (ACM): 71-75. DOI: 10.1145/74877.74885.
3. http://ru. wikipedia.org/wiki/Сжатие_данных
4. http://ru. wikipedia.org/wiki/Алгоритм_Лемпеля_-_Зива_-_Велча
5. http://ru. wikipedia.org/wiki/Событийно_ориентированное_программирование
6. http://ru. wikipedia.org/wiki/Программирование_потоком_данных
Приложение
Листинг программы
#include <stdio. h>
#include <string. h>
#include <stdlib. h>
/************************************************************************
** Демонстрационная программа для LZW-алгоритма сжатия/распаковки данных.
** Mark R. Nelson
*************************************************************************/
#include <stdio. h>
#define BITS 12 /* Установка длины кода равной 12, 13 */
#define HASHING_SHIFT BITS-8 /* или 14 битам. */
#define MAX_VALUE (1 << BITS) - 1/* Отметим, что на MS-DOS-машине при */
#define MAX_CODE MAX_VALUE - 1 /* длине кода 14 бит необходимо компи - */
/* лировать, используя large-модель. */
#if BITS == 14
#define TABLE_SIZE 18041 /* Размер таблицы строк должен быть */
#endif /* простым числом, несколько большим, */
#if BITS == 13 /* чем 2**BITS. */
#define TABLE_SIZE 9029
#endif
#if BITS <= 12
#define TABLE_SIZE 5021
#endif
enum STATES {
NAME, SIZE, DATA
};
typedef struct {
char ** frames;
int n_files;
int i; // current file index
FILE *f; // current file
char buf [1024];
int buf_pos;
int buf_len;
} InArchStream;
typedef struct {
int state; // статус (1,2,3) (1 - читаю имя файла, 2 читаю инфу о длине (4 байта), 3 читаю само тело файла)
char fname [1050]; //
int fname_pos; // позиция на имени
int flen; // длина файла походу (4 байта которые.)
FILE * out; // сам файл
intflen_count; // счетчик по длине файла (от 0 байта до 4 байта)
int out_count; //
} OutArchStream;
struct context
{
/* Это массив для значений кодов */
int *code_value; // izbavlyaemsya ot globalnih peremennyh.
/* Этот массив содержит префиксы кодов */
unsigned int *prefix_code;
/* Этот массив содержит добавочные символы */
unsigned char *append_character;
/* Этот массив содержит декодируемые строки */
unsigned char decode_stack [4000];
};
/*
** Следующие две процедуры управляют вводом/выводом кодов
** переменной длины. Они для ясности написаны чрезвычайно
** простыми и не очень эффективны.
*/
int input_code (FILE *input)
{
unsigned int return_value;
static int input_bit_count=0;
static unsigned long input_bit_buffer=0L;
while (input_bit_count <= 24)
{
input_bit_buffer|= (unsigned long) getc (input) << (24-input_bit_count);
input_bit_count += 8;
}
return_value=input_bit_buffer >> (32-BITS);
input_bit_buffer <<= BITS;
input_bit_count - = BITS;
return (return_value);
}
int output_code (FILE *output,unsigned int code)
{
static int output_bit_count=0;
static unsigned long output_bit_buffer=0L;
output_bit_buffer|= (unsigned long) code<< (32-BITS-output_bit_count);
output_bit_count += BITS;
while (output_bit_count >= 8)
{
putc (output_bit_buffer >> 24,output);
output_bit_buffer <<= 8;
output_bit_count - = 8;
}
}
int arch_get_c (InArchStream * stream) {
while (1) {
int a;
if (stream->buf_pos<stream->buf_len) {
a= (unsigned char) stream->buf [stream->buf_pos];
stream->buf_pos++;
return a;
}
if (stream->f==NULL) {
if (stream->i==stream->n_files)
return - 1;
stream->f=fopen (stream->frames [stream->i], "rb");
if (stream->f==NULL)
return - 1;
strcpy (stream->buf,stream->frames [stream->i]);
fseek (stream->f, 0, SEEK_END);
int size = ftell (stream->f);
fseek (stream->f, 0, SEEK_SET);
int fname_len=strlen (stream->buf);
* (int *) &stream->buf [fname_len+1] = size;
stream->buf_len=fname_len+5;
stream->buf_pos=0;
continue;
}
int n =fread (stream->buf,1,sizeof (stream->buf),stream->f);
stream->buf_pos=0;
stream->buf_len=n;
if (stream->buf_len == 0) {
fclose (stream->f);
stream->f=NULL;
stream->i++;
}
}
}
int arch_put_c (char c, OutArchStream * stream) {
char * bytes;
switch (stream->state) {
case NAME:
stream->fname [stream->fname_pos++] = c;
if (c == 0) {
stream->state = SIZE;
stream->out_count = 0;
}
break;
case SIZE:
bytes = (char *) (&stream->flen);
bytes [stream->out_count++] = c;
if (stream->out_count == 4) {
stream->state = DATA;
stream->out = NULL;
}
break;
case DATA:
if (stream->out == NULL) {
stream->out = fopen (stream->fname, "wb");
stream->flen_count = 0;
}
putc (c, stream->out);
stream->flen_count ++;
if (stream->flen_count == stream->flen) {
fclose (stream->out);
stream->state = NAME;
}
break;
}
}
/*
** Процедура хэширования. Она пытается найти сопоставление для строки
** префикс+символ в таблице строк. Если найдено, возвращается индекс.
** Если нет, то возвращается первый доступный индекс.
*/
int find_match (int hash_prefix,unsigned int hash_character,struct context *ctx) {
int index;
int offset;
index = (hash_character << HASHING_SHIFT) ^ hash_prefix;
if (index == 0)
offset = 1;
else
offset = TABLE_SIZE - index;
while (1)
{
if (ctx->code_value [index] == - 1)
return (index);
if (ctx->prefix_code [index] ==hash_prefix&&ctx->append_character [index] ==hash_character)
return (index);
index - = offset;
if (index < 0)
index += TABLE_SIZE;
}
} // end of find_math;
/*
** Процедура сжатия.
*/
int compress (InArchStream *input, FILE *output, struct context *ctx) {
unsigned int next_code;
unsigned int character;
unsigned int string_code;
unsigned int index;
int i;
next_code=256; /* Next_code - следующий доступный код строки */
for (i=0; i<TABLE_SIZE; i++) /*Очистка таблицы строк перед стартом */
ctx->code_value [i] =-1;
i=0;
printf ("Compressing. \n");
string_code=arch_get_c (input); /* Get the first code*/
/*
** Основной цикл. Он выполняется до тех пор, пока возможно чтение
** входного потока. Отметим, что он прекращает заполнение таблицы
** строк после того, как все возможные коды были использованы.
*/
while ( (character=arch_get_c (input))! = (unsigned) EOF)
{
if (++i==1000) /* Печатает * через каждые 1000 */
{ /* чтений входных символов (для */
i=0; /* умиротворения зрителя). */
printf ("*");
}
/* Смотрит, есть ли строка */
index=find_match (string_code,character,ctx);
if (ctx->code_value [index]! = - 1) /* в таблице. Если есть,*/
string_code=ctx->code_value [index]; /* получает значение кода*/
else /* Если нет, добавляет ее*/
{ /* в таблицу. */
if (next_code <= MAX_CODE)
{
ctx->code_value [index] =next_code++;
ctx->prefix_code [index] =string_code;
ctx->append_character [index] =character;
}
output_code (output,string_code); /*Когда обнаруживается, что*/
string_code=character; /*строки нет в таблице, */
} /*выводится последняя строка*/
} /*перед добавлением новой */
/*
** End of the main loop.
*/
output_code (output,string_code); /* Вывод последнего кода */
output_code (output,MAX_VALUE); /* Вывод признака конца потока */
output_code (output,0); /* Очистка буфера вывода */
printf ("\n");
} // end of compress ();
/*
** Процедура распаковки. Она читает файл LZW-формата и распаковывает
** его в выходной файл.
*/
int expand (FILE *input, struct context *ctx) { // вместо аутпут файла аут архстрим
OutArchStream * output;
output = malloc (sizeof (OutArchStream));
memset (output, 0, sizeof (OutArchStream));
unsigned int next_code;
unsigned int new_code;
unsigned int old_code;
int character;
int counter;
unsigned char *string;
char *decode_string (unsigned char *buffer,unsigned int code,struct context *ctx);
next_code=256;
counter=0;
printf ("Expanding. \n");
old_code=input_code (input);
character=old_code;
arch_put_c (old_code, output);
while ( (new_code=input_code (input))! = (MAX_VALUE)) {
if (++counter==1000) {
counter=0;
printf ("*");
}
if (new_code>=next_code) {
*ctx->decode_stack=character;
string=decode_string (ctx->decode_stack+1,old_code,ctx);
} else {
string=decode_string (ctx->decode_stack,new_code,ctx);
}
character=*string;
while (string >= ctx->decode_stack)
arch_put_c (*string--, output);
if (next_code <= MAX_CODE) {
ctx->prefix_code [next_code] =old_code;
ctx->append_character [next_code] =character;
next_code++;
}
old_code=new_code;
}
printf ("\n");
}
char *decode_string (unsigned char *buffer,unsigned int code,struct context *ctx)
{
int i;
i=0;
while (code > 255)
{
// printf ("Code: %d\n", code);
*buffer++ = ctx->append_character [code];
code=ctx->prefix_code [code];
if (i++>=4094)
{
printf ("Fatal error during code expansion. \n");
// exit ();
}
}
*buffer=code;
return (buffer);
}
InArchStream * createStream (int files, char ** fileNames) {
InArchStream * stream;
stream=malloc (sizeof (InArchStream));
stream->n_files = files;
stream->frames = (char**) malloc (sizeof (char *) * files);
int i;
for (i = 0; i < files; i++) {
int length = strlen (fileNames [i]);
stream->frames [i] = (char*) malloc (length + 1);
strcpy (stream->frames [i], fileNames [i]);
}
stream->i=0;
stream->f=NULL;
stream->buf_pos=0;
stream->buf_len=0;
return stream;
}
int main (int argc, char *argv []) {
int i;
for (i = 0; i < argc; i++) {
puts (argv [i]);
}
if (argc <= 2) {
puts ("Not enough arguments. Format: <output> <input> [<input>.] ");
return 0;
}
InArchStream * stream = createStream (argc - 2, argv + 2);
FILE * out= fopen (argv [1], "wb");
if (out==NULL) {
printf ("cannot open file\n");
return 1;
}
struct context *ctx;
// Эти три буфера необходимы на стадии упаковки.
ctx = malloc (sizeof (struct context));
ctx->code_value=malloc (TABLE_SIZE*sizeof (int));
ctx->prefix_code=malloc (TABLE_SIZE*sizeof (unsigned int));
ctx->append_character=malloc (TABLE_SIZE*sizeof (unsigned char));
if (ctx->code_value==NULL || ctx->prefix_code==NULL || ctx->append_character==NULL) {
printf ("Fatal error allocating table space! \n");
}
compress (stream, out, ctx);
fclose (out);
free (ctx->code_value);
if (argc <= 1) {
puts ("Not enough arguments. Format: <archive>");
return 0;
}
FILE * lzw_file = fopen (argv [1], "rb");
expand (lzw_file, ctx);
fclose (lzw_file);
return 0;
}
Размещено на Allbest.ru
...Подобные документы
Описание использованных структур данных и разработка программы, обеспечивающей сжатие данных по алгоритму LZ77 с пошаговой визуализацией. Описание процедур, функций, структуры приложения и интерфейса пользователя. Тест и анализ работы алгоритма LZ77.
курсовая работа [537,9 K], добавлен 28.06.2011Методы кодирования изображения: кодированием длины серии, частотно-зависимое кодирование, метод Лемпеля-Зива. Размер строки при 16-битном цвете. Расчет размера всего исходного изображения. Примеры качественного и некачественного сжатия изображения.
презентация [2,0 M], добавлен 22.10.2013Типы сжатия данных: с потерями (lossy) и без потерь (lossless). Сжатие с минимальной избыточностью. Кодирование методом Шеннона-Фано. Проверка работы программы по сжатию файлов формата bmp и xls. Реализация на Delphi алгоритма сжатия Шеннона и Хаффмана.
курсовая работа [2,6 M], добавлен 26.01.2011Краткий обзор основных теорий сжатия. Концепции идей и их реализация. Сжатие данных с использованием преобразования Барроуза-Вилера. Статический алгоритм Хафмана. Локально адаптивный алгоритм сжатия. Алгоритм Зива-Лемпеля (Welch) и метод Шеннона-Фано.
практическая работа [188,5 K], добавлен 24.04.2014Типы изображений (черно-белые, полутоновые, цветные) и их форматы. Устройства, создающие цифровые изображения, и их параметры. Применение и характеристики методов сжатия изображений. Поиск по содержимому в базах данных изображений. Структуры баз данных.
презентация [360,4 K], добавлен 11.10.2013Анализ аналогов и выбор прототипа, разработка алгоритма и графического интерфейса, кодирование и тестирование. Логическая модель данных "Нотариальная контора". Особенности реализации в MS SQL. Требования к функциональным характеристикам базы данных.
курсовая работа [1,3 M], добавлен 12.01.2013Общее понятие архивации. Особенности программ архиваторов. Основные методы сжатия информации. Методические основы изучения темы "Архивация данных и сжатие информации" на уроках информатики в базовом курсе. Разработка блока уроков по сжатию информации.
курсовая работа [3,0 M], добавлен 03.06.2012Выбор беспроводной технологии передачи данных. Механизмы управления качеством передачи потоков. Программное обеспечение приемной и передающей станции. Эксперименты, направленные на изучение неравномерности передаваемого потока данных при доступе к среде.
дипломная работа [1,1 M], добавлен 18.05.2012Этапы создания базы данных. Тестирование программной продукции с распечаткой всех используемых форм. Способ хранения данных. Блок-схемы к запросам. Алгоритмы выполнения каждого запроса. Вывод на экран простейшего интерфейса. Открытие файлов для записи.
дипломная работа [549,4 K], добавлен 05.11.2011Принцип действия и назначение факсимильной связи, сферы ее применения, оценка преимуществ и недостатков. Сущность и особенности использования адресно-позиционного кодирования. Алгоритм программы сжатия и восстановления изображения по методу АПК.
курсовая работа [23,3 K], добавлен 16.04.2010Применение алгоритмов, обеспечивающих высокую степень сжатия, для увеличения скорости передачи данных по каналам связи. Особенности и методы нахождения сингулярного разложения. Разработка программы, реализующей сжатие изображения с помощью SVD-сжатия.
дипломная работа [3,3 M], добавлен 13.10.2015Характеристика работы архиватора - компьютерной программы, которая осуществляет сжатие данных в один файл архива для более легкой передачи, компактного их хранения. Особенности процесса архивирования - записи файлов и разархивирования - открытия файлов.
реферат [216,5 K], добавлен 26.03.2010Понятие системы управления базой данных. Создание конструктора запроса. Отчеты по анализу интенсивности движения в узлах и на участках улично–дорожной сети. Связи между таблицами. Добавление данных с помощью форм. Копирование данных из другого источника.
курсовая работа [5,7 M], добавлен 06.08.2013Энтропия и количество информации. Комбинаторная, вероятностная и алгоритмическая оценка количества информации. Моделирование и кодирование. Некоторые алгоритмы сжатия данных. Алгоритм арифметического кодирования. Приращаемая передача и получение.
курсовая работа [325,1 K], добавлен 28.07.2009Разработка информационной базы данных для поликлиники, которая поможет пользователю найти информацию о любом сотруднике или пациенте. Функциональная структура предметной области. Диаграмма потоков данных (DFD-диаграмма). Поддержка целостности данных.
курсовая работа [6,7 M], добавлен 17.09.2014Классификация и основные характеристики метода сжатия данных. Вычисление коэффициентов сжатия и оценка их эффективности. Алгоритмы полиноминальных, экстраполяционных и интерполяционных методов сжатия и их сравнение. Оптимальное линейное предсказание.
курсовая работа [1,1 M], добавлен 17.03.2011Представление (построение, создание) списка данных в виде линейного однонаправленного списка. Формирование массива данных. Вывод данных на экран. Алгоритм удаления, перемещения данных. Сортировка методом вставки. Алгоритм загрузки данных из файла.
курсовая работа [2,1 M], добавлен 16.05.2015Проблемы, связанные с продуктивным распределением и систематизированием больших потоков информации. Основные виды распределенных баз данных, анализ процессов их функционирования. Стратегии распределения данных. Распределение сетевого справочника данных.
курсовая работа [397,5 K], добавлен 09.08.2015Сущность потоков информации, циркулирующих в мире. Особенности создания и система управления базами данных. Общая характеристика правовых информационных структур. Методы и формы распространения баз данных по законодательству в интернете и на CD дисках.
реферат [33,7 K], добавлен 24.12.2008Понятие баз данных, их место в сфере обработки информации. Разработка базы данных транспортных потоков для работы в геоинформационной системе ArcGis. Учет и анализ интенсивности движения на участках улично-дорожной сети на примере г. Ростова-на-Дону.
курсовая работа [4,0 M], добавлен 06.12.2012
