Главная
страница 1
Содержание

Программирование потоком данных…………………………………………4

Сжатие данных ………………………………………………………………...5

Алгоритм Лемпеля - Зиива – Веелча………………………………………….9

Список литературы…………………………………………………………….10

Блок-схема……………………………………………………………………...13

Листинг программы……………………………………………………………14

Программирование потоком данных


В программировании, программирование потоком данных представляет собой парадигму программирования, в которой операторы программы описывают подходящие данные и правила их обработки, а не последовательность предпринимаемых шагов. Применение методов конструирования абстрактных типов данных в объектно-ориентированном программировании приводит к архитектуре, управляемой данными. Этот тип архитектуры используется в объектно-ориентированном программировании для определения классов в рамках концепции частей программного обеспечения. Программирование потоком данных приводит к плохому объектно-ориентированному проектированию, в то время как проектирование на базе ответственности считается лучшим подходом.

Поток данных в программировании — абстракция, используемая для чтения или записи файлов, сокетов и т. п. в единой манере.

Потоки являются удобным унифицированным программным интерфейсом для чтения или записи файлов (в том числе специальных и, в частности, связанных с устройствами), сокетов и передачи данных между процессами.

Поддержка потоков включена в большинство языков программирования и едва ли не во все современные (на 2008 год) операционные системы. При запуске процесса ему предоставляются предопределённые стандартные потоки.

Возможность перенаправления потоков позволяет связывать различные программы, и придаёт системе гибкость, являющуюся частью философии Unix.

Абстракция потока особенно важна в языке программирования Си, где он представляет собой источник ввода и/или вывода данных, обычно байтов, связанный с файлом, устройством, либо другим процессом. Работа с потоками перенесена во многие другие языки:


  • C++: iostream из стандартной библиотеки C++.

  • Языки платформы .NET Framework (например, C#): Base Class Library, пространство имен System.IO.

Поток данных в операционных системах

http://upload.wikimedia.org/wikipedia/commons/thumb/5/52/process_output_chaining_via_pipes.ru.svg/300px-process_output_chaining_via_pipes.ru.svg.png


Сжатие данных

Сжатие данных— алгоритмическое преобразование данных, производимое с целью уменьшения их объёма. Применяется для более рационального использования устройств хранения и передачи данных. Синонимы — упаковка данных, компрессия, сжимающее кодирование, кодирование источника. Обратная процедура называется восстановлением данных (распаковкой, декомпрессией).

Сжатие основано на устранении избыточности, содержащейся в исходных данных. Простейшим примером избыточности является повторение в тексте фрагментов (например, слов естественного или машинного языка). Подобная избыточность обычно устраняется заменой повторяющейся последовательности ссылкой на уже закодированный фрагмент с указанием его длины. Другой вид избыточности связан с тем, что некоторые значения в сжимаемых данных встречаются чаще других. Сокращение объёма данных достигается за счёт замены часто встречающихся данных короткими кодовыми словами, а редких — длинными (энтропийное кодирование). Сжатие данных, не обладающих свойством избыточности (например, случайный сигнал или белый шум, зашифрованные сообщения), принципиально невозможно без потерь.

В основе любого способа сжатия лежит модель источника данных, или, точнее, модель избыточности. Иными словами, для сжатия данных используются некоторые априорные сведения о том, какого рода данные сжимаются. Не обладая такими сведениями об источнике, невозможно сделать никаких предположений о преобразовании, которое позволило бы уменьшить объём сообщения. Модель избыточности может быть статической, неизменной для всего сжимаемого сообщения, либо строиться или параметризоваться на этапе сжатия (и восстановления). Методы, позволяющие на основе входных данных изменять модель избыточности информации, называются адаптивными. Неадаптивными являются обычно узкоспециализированные алгоритмы, применяемые для работы с данными, обладающими хорошо определёнными и неизменными характеристиками. Подавляющая часть достаточно универсальных алгоритмов являются в той или иной мере адаптивными.

Все методы сжатия данных делятся на два основных класса:



  • Сжатие без потерь

  • Сжатие с потерями

При использовании сжатия без потерь возможно полное восстановление исходных данных, сжатие с потерями позволяет восстановить данные с искажениями, обычно несущественными с точки зрения дальнейшего использования восстановленных данных. Сжатие без потерь обычно используется для передачи и хранения текстовых данных, компьютерных программ, реже — для сокращения объёма аудио- и видеоданных, цифровых фотографий и т. п., в случаях, когда искажения недопустимы или нежелательны. Сжатие с потерями, обладающее значительно большей, чем сжатие без потерь, эффективностью, обычно применяется для сокращения объёма аудио- и видеоданных и цифровых фотографий в тех случаях, когда такое сокращение является приоритетным, а полное соответствие исходных и восстановленных данных не требуется.

Коэффициент сжатия


Коэффициент сжатия — основная характеристика алгоритма сжатия. Она определяется как отношение объёма исходных несжатых данных к объёму сжатых, то есть: k=\frac{s_o}{s_c}, где k — коэффициент сжатия, So — объём исходных данных, а Sc — объём сжатых. Таким образом, чем выше коэффициент сжатия, тем алгоритм эффективнее. Следует отметить:

  • если k = 1, то алгоритм не производит сжатия, то есть выходное сообщение оказывается по объёму равным входному;

  • если k < 1, то алгоритм порождает сообщение большего размера, нежели несжатое, то есть, совершает «вредную» работу.

Ситуация с k < 1 вполне возможна при сжатии. Принципиально невозможно получить алгоритм сжатия без потерь, который при любых данных образовывал бы на выходе данные меньшей или равной длины. Обоснование этого факта заключается в том, что поскольку число различных сообщений длиной n бит составляет ровно 2n, число различных сообщений с длиной меньшей или равной n (при наличии хотя бы одного сообщения меньшей длины) будет меньше 2n. Это значит, что невозможно однозначно сопоставить все исходные сообщения сжатым: либо некоторые исходные сообщения не будут иметь сжатого представления, либо нескольким исходным сообщениям будет соответствовать одно и то же сжатое, а значит их нельзя отличить. Однако даже когда алгоритм сжатия увеличивает размер исходных данных, легко добиться того, чтобы их объём гарантировано не мог увеличиться более, чем на 1 бит. Тогда даже в самом худшем случае будет иметь место неравенство:
k\geqslant\frac{s_o}{s_o+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()

{

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:

Символ: Битовый код: Новая запись словаря:

(на выходе)


T 20 = 10100

O 15 = 01111 27: TO

B 2 = 00010 28: OB

E 5 = 00101 29: BE

O 15 = 01111 30: EO

R 18 = 10010 31: OR <--- со следующего символа начинаем использовать 6-битные группы

N 14 = 001110 32: RN

O 15 = 001111 33: NO

T 20 = 010100 34: OT

TO 27 = 011011 35: TT

BE 29 = 011101 36: TOB

OR 31 = 011111 37: BEO

TOB 36 = 100100 38: ORT

EO 30 = 011110 39: TOBE

RN 32 = 100000 40: EOR

OT 34 = 100010 41: RNO

# 0 = 000000 42: OT#
Общая длина = 6*5 + 11*6 = 96 бит.

Таким образом, используя LZW мы сократили сообщение на 29 бит из 125 — это почти 22 %. Если сообщение будет длиннее, то элементы словаря будут представлять всё более и более длинные части текста, благодаря чему повторяющиеся слова будут представлены очень компактно.



Декодирование

Теперь представим что мы получили закодированное сообщение, приведённое выше, и нам нужно его декодировать. Прежде всего, нам нужно знать начальный словарь, а последующие записи словаря мы можем реконструировать уже на ходу, поскольку они являются просто конкатенацией предыдущих записей.

Данные: На выходе: Новая запись:

Полная: Частичная:

10100 = 20 T 27: T?

01111 = 15 O 27: TO 28: O?

00010 = 2 B 28: OB 29: B?

00101 = 5 E 29: BE 30: E?

01111 = 15 O 30: EO 31: O?

10010 = 18 R 31: OR 32: R? <---- начинаем использовать 6-битные группы

001110 = 14 N 32: RN 33: N?

001111 = 15 O 33: NO 34: O?

010100 = 20 T 34: OT 35: T?

011011 = 27 TO 35: TT 36: TO? <---- для 37, добавляем только первый элемент

011101 = 29 BE 36: TOB 37: BE? следующего слова словаря

011111 = 31 OR 37: BEO 38: OR?

100100 = 36 TOB 38: ORT 39: TOB?

011110 = 30 EO 39: TOBE 40: EO?

100000 = 32 RN 40: EOR 41: RN?

100010 = 34 OT 41: RNO 42: OT?

000000 = 0 #

Единственная небольшая трудность может возникнуть, если новое слово словаря пересылается немедленно. В приведённом выше примере декодирования, когда декодер встречает первый символ, T, он знает, что слово 27 начинается с T, но чем оно заканчивается? Проиллюстрируем проблему следующим примером. Мы декодируем сообщение ABABA:

Данные: На выходе: Новая запись:

Полная: Частичная:

.

.

.



011101 = 29 AB 46: (word) 47: AB?

101111 = 47 AB? <--- что нам с этим делать?

На первый взгляд, для декодера это неразрешимая ситуация. Мы знаем наперёд, что словом 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

#include

#include

/************************************************************************

** Демонстрационная программа для LZW-алгоритма сжатия/распаковки данных.

** Mark R. Nelson

*************************************************************************/

#include

#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; // сам файл

int flen_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_posbuf_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

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: [...]");

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: ");

return 0;

}

FILE * lzw_file = fopen(argv[1], "rb");

expand(lzw_file, ctx);

fclose(lzw_file);

return 0;

}

Московский Государственный Открытый Университет

Курсовая работа

по дисциплине:«Методы и средства защиты компьютерной информации»

на тему: «Сжатие данных через алгоритм Лемпеля - Зиива – Веелча»

Подготовил: студент 4 курса

Группа 2

609396


Ягодкин А.А.

Принял:


Найденов В. В.


Смотрите также:
Программирование потоком данных Сжатие данных
223.56kb.
1 стр.
Слайд №5 (Сжатие данных) Сжатие
49.93kb.
1 стр.
Б. Нойес Привязка данных в Windows Forms Книга охватывает все аспекты привязки данных в Windows Forms. Описываются средства, обеспечивающие связь с базой данных, такие, как типизированные наборы данных и адапт
69.76kb.
1 стр.
Программирование, объектно-ориентированное программирование. Оценка сложности алгоритмов. Классы P, np. Np – полные задачи
3210.51kb.
16 стр.
Тест по дисциплине «Базы данных». Вариант База данных – это
65.02kb.
1 стр.
Поиск информации в базе данных
62.37kb.
1 стр.
Отчет о лаботарорной работе методы и средства анализа данных по теме: «Система анализа данных weka»
383.87kb.
2 стр.
«база данных access»
297.79kb.
1 стр.
Политика безопасности персональных данных, обрабатываемых в информационных системах персональных данных в
227.68kb.
1 стр.
Параллельное программирование задач визуализации научных данных
243.08kb.
1 стр.
Лекция Понятие модели данных. Обзор разновидностей моделей данных
443.99kb.
1 стр.
1. Термины и определения (документы фстэк россии) Безопасность персональных данных
153.09kb.
1 стр.