Алгоритмы сжатия данных при передаче через интернет

Федеральное агентство по образованию

ГОУ ВПО «Шадринский государственный педагогический институт»

Кафедра программирования и сетевых технологий

АЛГОРИТМЫ СЖАТИЯ ДАННЫХ ПРИ ПЕРЕДаЧЕ ЧЕРЕЗ ИНТЕРНЕТ

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

по программированию

                                                                                    Выполнил:

                                                                                    студент 388 группы

              факультета информатики

              Пырьев А.В.

              Научный руководитель:

              ассистент кафедры

программирования и                  

сетевых технологий

Михайловских П.Д.

Шадринск, 2009

Содержание

Введение

Глава 1. Организация передачи данных через интернет

   История развития интернет

   Процесс передачи данных

   Синхронная и асинхронная передача данных

   Протоколы передачи данных

Глава 2. Алгоритмы кодирования данных

    Моделирование и энтропия

   Адаптированные и неадаптированные модели

   Алгоритм Хаффмана

   Арифметическое кодирование

   Метод Зива-Лемпела    

   Сравнение алгоритмов компрессии

   Необходимость применения сжатия

   Дальнейшие исследования

Заключение

Введение

Сжатие сокращает объем пространства, требуемого для хранения файлов в ЭВМ, и количество времени, необходимого для передачи информации по каналу установленной ширины пропускания. Это есть форма кодирования. Другими целями кодирования являются поиск и исправление ошибок, а также шифрование. Процесс поиска и исправления ошибок противоположен сжатию, он увеличивает избыточность данных, когда их не нужно представлять в удобной для восприятия человеком форме. Удаляя из данных избыточность, сжатие способствует шифрованию, что затрудняет поиск шифра доступным для взломщика статистическим методом. В зависимости от результата кодирования  сжатие разделяется на обратимое (первоначальные данные могут быть в точности восстановлены из сжатого состояния) и необратимое. Необратимое или ущербное сжатие используется для цифровой записи аналоговых сигналов, таких как человеческая речь или рисунки. Обратимое сжатие особенно важно для текстов, записанных на естественных и на искусственных языках, поскольку в этом случае ошибки обычно недопустимы. Хотя первоочередной областью применения рассматриваемых методов есть сжатие текстов, однако, эта техника может найти применение и в других случаях, включая обратимое кодирование последовательностей дискретных данных. Существует много веских причин выделять ресурсы ЭВМ в расчете на сжатое представление, т.к. более быстрая передача данных и сокращение пространства для их хранения позволяют сберечь значительные средства и зачастую улучшить показатели ЭВМ. Компрессия, вероятно, будет оставаться в сфере внимания из-за возрастающих объемов хранимых и передаваемых в ЭВМ данных, кроме того, его можно использовать для преодоления некоторых физических ограничений, таких как, например, сравнительно низкая ширина пропускания телефонных каналов. Одним из самых ранних и хорошо известных методов сжатия является алгоритм Хаффмана, который был и остается предметом многих исследований. Однако, в конце 70-х годов благодаря двум важным переломным идеям он был вытеснен. Одна заключалась в открытии метода «Арифметического кодирования», имеющего схожую с кодированием Хаффмана функцию, но обладающего несколькими важными свойствами, которые дают возможность достичь значительного превосходства в сжатии. Другим новшеством был метод Зива-Лемпела, дающий эффективное сжатие и применяющий подход, совершенно отличный от двух вышеупомянутых. Обе эти техники со времени своей первой публикации значительно усовершенствовались, развились и легли в основу практических высокоэффективных алгоритмов.

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

Объект: процесс формирования алгоритмов сжатия данных.

Цель исследования: рассмотреть основные алгоритмы сжатия данных и методы передачи данных через интернет.

Задачи:

1) Проанализировать теоретические основы передачи данных через интернет.

2) Рассмотреть основные виды алгоритмов сжатия данных.

3) Выявить принципы дальнейшего исследования в области кодирования данных.

Глава 1. Организация передачи данных через интернет

История развития Интернет

В 1961 году Defence Advanced Research Agensy (DARPA) по заданию министерства обороны  США приступило к проекту по созданию экспериментальной сети передачи пакетов. Эта сеть, названная ARPANET, предназначалась первоначально для изучения методов обеспечения надежной связи между компьютерами различных типов. Многие методы передачи данных через модемы были разработаны в ARPANET. Тогда же были разработаны и протоколы передачи данных в сети - TCP/IP. TCP/IP - это множество коммуникационных протоколов, которые определяют, как компьютеры различных типов могут общаться между собой. Эксперимент с ARPANET был настолько успешен, что многие организации захотели войти в нее, с целью использования для ежедневной передачи данных. И в 1975 году ARPANET превратилась из экспериментальной сети в рабочую сеть. Ответственность за администрирование сети взяло на себя Defence Communication Agency (DCA), в настоящее время называемое Defence Information Systems Agency (DISA). Но развитие ARPANET на этом не остановилось; Протоколы TCP/IP продолжали развиваться и совершенствоваться. В 1971-72 годах вышел первый стандарт для протоколов TCP/IP (разработчик – Internet Working Group), вошедший в Military Standarts (MIL STD), т.е. в военные стандарты, и все, кто работал в сети, обязаны были перейти к этим новым протоколам. Для облегчения этого перехода DARPA обратилась с предложением к руководителям фирмы Berkley Software Design - внедрить протоколы TCP/IP в Berkeley(BSD) UNIX. С этого и начался союз UNIX и TCP/IP. Спустя некоторое время TCP/IP был адаптирован в обычный, то есть в общедоступный стандарт, и термин Internet вошел во всеобщее употребление.  В 1983 году из ARPANET выделилась MILNET, которая стала относиться к Defence Data Network (DDN) министерства обороны США. Термин Internet стал использоваться для обозначения единой сети: MILNET плюс ARPANET. И хотя в 1991 году ARPANET прекратила свое существование, сеть Internet существует, ее размеры намного превышают первоначальные, так как она объединила множество сетей во всем мире. Число хостов, подключенных к сети Internet с 4 компьютеров в 1969 году выросло до 150 миллионов в 2002. Хостом в сети Internet называются компьютеры, работающие в многозадачной  операционной системе (Unix, VMS), поддерживающие протоколы TCP\IP  и предоставляющие пользователям какие-либо сетевые услуги.

Процесс передачи данных

Передача данных – вид электросвязи, обеспечивающий обмен сообщениями между прикладными процессами пользователей, удалённых ЭВМ с целью обработки информации вычислительными средствами.

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

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

Синхронная и асинхронная передача данных

При обмене данными по каналам связи используются три метода передачи данных:

1) Симплексная (однонаправленная)

2) Полудуплексная передача — (приём и передача данных осуществляются поочерёдно);

3) Дуплексная (двунаправленная) – каждая станция одновременно передаёт и принимает данные.

Для передачи данных в информационных системах наиболее часто применяется последовательная (полудуплексная) передача. Она разделяется на два метода:

а) Асинхронная передача;

б) Синхронная передача.

а)

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

Преимущества:

1) Несложная отработанная система;

2) Недорогое интерфейсное оборудование.

Недостатки:

1) Третья часть пропускной способности теряется на передачу служебных битов;

2) Невысокая скорость передачи данных по сравнению с синхронной;

3) При множественной ошибке с помощью бита чётности невозможно определить достоверность полученной информации.

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

б)

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

Преимущества:

1) Высокая эффективность передачи данных;

2) Высокая скорость передачи данных;

3) Надёжный встроенный механизм обнаружения ошибок.

Недостатки:

1) Интерфейсное оборудование более сложное и дорогое.

Протоколы  передачи данных

Все услуги предоставляемые сетью Internet можно условно поделить на две категории: обмен информацией между абонентами сети и использование баз данных сети.

К числу услуг связи между абонентами принадлежат.

Telnet - удаленный доступ. Дает возможность абоненту работать на любой ЭВМ сети Internet как на своей собственной. То есть запускать программы, менять режим работы и т.д.

FTP (File Transfer Protocol) - протокол передачи файлов. Дает возможность абоненту обмениваться файлами с любым компьютером сети. Установив связь с удаленным компьютером, пользователь может скопировать файл с удаленного компьютера на свой или скопировать файл со своего компьютера на удаленный.

NFS (Network File System) - распределенная файловая система. Дает           возможность абоненту пользоваться файловой системой удаленного компьютера, как своей собственной.

Электронная почта – обмен почтовыми сообщениями с любым абонентом сети Internet. Существует возможность отправки как текстовых, так и двоичных файлов. Электронная почта – самая распространенная услуга сети Internet. В настоящее время свой адрес по электронной почте имеют приблизительно 25 миллионов человек. Посылка письма по электронной почте обходится значительно дешевле посылки обычного письма. Кроме того сообщение, посланное по электронной почте дойдет до адресата за несколько часов, в то время как обычное письмо может добираться до адресата несколько дней, а то и недель.

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

WWW или просто Web (Word-Wide Web- всемирная паутина). Это самый популярный сервис Сети и удобный способ работы с информацией. Данный сервис появился в 1992 году и очень быстро стал популярным. Сегодня существует по меньшей мере 40 тыс. серверов WWW. Именно за счет WWW Сеть растёт так стремительно. Пользуясь несложным языком описания, можно составлять гипермедийные документы для их последующей публикации в Сети. Чтобы увидеть содержание документа так, как его представляет себе его автор нужно иметь на компьютере- клиенте программу просмотра – броузер (первый появился в 1993г – Mosaic). Наиболее популярен сегодня Internet Explorer, поддерживающий расширения HTML (Hyper Text Markup Language- язык гипертекстовой разметки документов – именно с его помощью оформляется информация в WWW).

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

HTTP (Hypertext Transfer Protocol - Протокол передачи гипертекста) является протоколом более высокого уровня по отношению к протоколу TCP/IP - протоколом уровня приложения. HTTP был разработан для эффективной передачи по Интернету Web-страниц. Именно благодаря HTTP мы имеем возможность созерцать страницы Сети во всем великолепии. Протокол HTTP является основой системы World Wide Web.

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

Чтобы текст, составляющий содержимое Web-страниц, отображался на них определенным образом - в соответствии с замыслом создателя страницы - он размечается с помощью особых текстовых меток - тегов языка разметки гипертекста (HyperText Markup Language, HTML).

Глава 2. Алгоритмы кодирования данных

Моделирование и энтропия

Одним из наиболее важных достижений в теории сжатия за последнее десятилетие явилась впервые высказанная идея разделения процесса на две части: на кодировщик, непосредственно производящий сжатый поток битов, и на моделировщик, поставляющий ему информацию. Эти две раздельные части названы кодированием и моделированием. Моделирование присваивает вероятности символам, а кодирование переводит эти вероятности в последовательность битов. К сожалению, последнее понятие нетрудно спутать, поскольку «кодирование» часто используют в широком смысле для обозначения всего процесса сжатия (включая моделирование). Существует разница между понятием кодирования в широком смысле (весь процесс компрессии) и в узком (производство потока битов на основании данных модели). Связь между вероятностями и кодами установлена в теореме Шеннона кодирования источника, которая показывает, что символ, ожидаемая вероятность появления которого есть p лучше всего представить –log2p битами. Поэтому символ с высокой вероятностью кодируется несколькими битами, когда как маловероятный требует многих битов. Мы можем получить ожидаемую длину кода посредством усреднения всех возможных символов, даваемого формулой:

Это значение называется энтропией распределения вероятности, т.к. это мера количества порядка (или беспорядка) в символах. Задачей моделирования является оценка вероятности для каждого символа. Из этих вероятностей может быть вычислена энтропия. Очень важно отметить, что энтропия есть свойство модели. В данной модели оцениваемая вероятность символа иногда называется кодовым пространством, выделяемым символу, и соответствует распределению интервала (0,1) между символами, и чем больше вероятность символа, тем больше такого "пространства" отбирается у других символов. Наилучшая средняя длина кода достигается моделями, в которых оценки вероятности как можно более точны. Точность оценок зависит от широты использования знаний о контексте кодируемых данных. Например, вероятность нахождения буквы "o" в тексте, о котором известно только то, что он на английском языке, может быть оценена на основании того, что в случайно выбранных образцах английских текстов 6% символов являются буквами "o". Это сводится к коду для "o", длиной 4.059 бит. Для контраста, если мы имеем фразу "to be or not t", то оценка вероятности появления буквы "o" будет составлять 99% и ее можно закодировать через 0.014 бита. Большего можно достичь, формируя более точные модели текста. Модель, по существу, есть набор вероятностей распределения, по одному на каждый контекст, на основании которого символ может быть закодирован. Контексты называются классами условий, т.к. они определяют оценки вероятности. Нетривиальная модель может содержать тысячи классов условий.

Адаптированные и неадаптированные модели

В порядке функционального соответствия декодер должен иметь доступ к той же модели, что и кодировщик. Для достижения этого есть три способа моделирования: статичное, полуадаптированное и адаптированное.

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

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

Адаптированное (динамическое) моделирование уходит от связанных с этой передачей расходов. Первоначально и кодировщик, и декодер присваивают себе некоторую пустую модель, как если бы все символы были равновероятными. Кодировщик использует эту модель для сжатия очередного символа, а декодер – для его «разворачивания». Затем они оба изменяют свои модели одинаковым образом (например, наращивая вероятность рассматриваемого символа). Следующий символ кодируется уже на основании измененной модели, а затем сам вновь изменяет модель. Кодирование происходит аналогичным раскодированию образом, при этом поддерживает идентичную модель за счет применения такого же алгоритма ее изменения, обеспеченного отсутствием ошибок. Используемая модель, которую к тому же не нужно передавать явно, будет хорошо соответствовать сжатому тексту. Адаптированные модели представляют собой элегантную и эффективный метод, и обеспечивают компрессию, которая, по крайней мере, не уступает сжатию, производимому неадаптированными схемами. Оно может быть даже значительно лучше, чем у плохо соответствующих текстам статичных моделей. Адаптированные модели, в отличии от полуадаптиpованных, не производят их предварительного просмотра, являясь поэтому более привлекательными и лучше сжимающими. Однако описанная схема компрессии имеет связанное с ее спецификой уязвимое место: модель никогда не передается явно, поэтому сбой происходит только в случае нехватки под нее памяти при динамическом проектировании модели.

Важно, чтобы значения вероятностей, присваиваемых моделью, не были бы равны 0, т.к. если символы кодируются –log p битами, то при близости вероятности к 0, длина кода стремится к бесконечности. Нулевая вероятность появляется в том случае, если в образце текста символ не встретился ни разу. Эта ситуация фактически неизбежна для адаптированных моделей на начальной стадии сжатия. Она известна как проблема нулевой вероятности, которую можно решить несколькими способами. Один подход состоит в том, чтобы добавлять 1 к счетчику каждого символа. Практически все альтернативные подходы основаны на идее выделения одного счетчика для всех новых (с нулевой частотой) символов, для последующего использования его значения между ними. Сравнение этих методов показывает, что ни один из них не имеет впечатляющего преимущества над другими.

Кодирование

Задача замещения символа с вероятностью p приблизительно –log2p битами называется кодированием.

Это узкий смысл понятия, а для обозначения более широкого будем использовать термин «сжатие». Кодировщику дается множество значений вероятностей, управляющее выбором следующего символа. Он производит поток битов, на основе которого этот символ может быть затем декодирован, если используется тот же набор вероятностей, что и при кодировании. Вероятность появления любого конкретного символа в разных частях текста может быть разной.

Алгоритм Хаффмана

Этот алгоритм кодиро­вания информации был предложен Д.А. Хаффманом в 1952 году. Идея алгоритма состоит в следующем: зная вероятности вхождения символов в сообщение, можно описать процедуру построения кодов переменной длины, состоящих из целого количества битов. Символам с большей вероятностью присваиваются более короткие коды. Коды Хаффмана имеют уникальный префикс, что и позволяет однозначно их декодировать, несмотря на их переменную длину.

Классический алгоритм Хаффмана на входе получает таблицу частот встречаемости символов в сообщении. Далее на основании этой таблицы строится дерево кодирования Хаффмана (Н-дерево). Алгоритм построения Н-дерева прост и элегантен.

1. Символы входного алфавита образуют список свободных узлов. Каждый лист имеет вес, который может быть равен либо вероятности, либо количеству вхождений символа в сжимаемое сообщение.

2. Выбираются два свободных узла дерева с наименьшими весами.

3. Создается их родитель с весом, равным их суммарному весу.

4. Родитель добавляется в список свободных узлов, а двое его детей удаляются из этого списка.

5. Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой - бит 0.

6. Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева.

Допустим, у нас есть следующая таблица частот:

На первом шаге из листьев дерева выбираются два с наименьшими весами — Г и Д. Они присоединяются к новому узлу-родителю, вес которого устанавливается в 5+6 = 11. Затем узлы Г и Д удаляются из списка свободных. Узел Г соответствует ветви 0 родителя, узел Д — ветви 1.

На следующем шаге то же происходит с узлами Б и В, так как теперь эта пара имеет самый меньший вес в дереве. Создается новый узел с весом 13, а узлы Б и В удаляются из списка свободных. После всего этого дерево кодирования выглядит так, как показано на рис. 1.

Рис. 1. Дерево кодирования Хаффмана после второго шага

На следующем шаге «наилегчайшей» парой оказываются узлы Б/В и Г/Д. Для них еще раз создается родитель, теперь уже с весом 24. Узел Б/В соответствует ветви 0 родителя, Г/Д—ветви 1.

На последнем шаге в списке свободных осталось только два узла — это А и узел (Б/В)/(Г/Д). В очередной раз создается родитель с весом 39 и бывшие свободными узлы присоединяются к разным его ветвям.

Поскольку свободным остался только один узел, то алгоритм построения дерева кодирования Хаффмана завершается. Н-дерево представлено на рис. 2.

Рис. 2. Окончательное дерево кодирования Хаффмана

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

Дня данной таблицы символов коды Хаффмана будут выглядеть следующим образом.

А              0

Б              100

В              101

Г              110

Д              111

Поскольку ни один из полученных кодов не является префиксом другого, они могут быть однозначно декодированы при чтений их из потока. Кроме того, наиболее частый символ сообщения А закодирован наименьшим количеством битов, а наиболее редкий символ Д - наибольшим.

Классический алгоритм Хаффмана имеет один существенный недостаток. Дня восстановления содер­жимого сжатого сообщения декодер должен знать таблицу частот, которой пользовался кодер. Следовательно, длина сжатого сообщения увеличивается на длину таблицы частот, которая должна посылаться впереди данных, что может свести на нет все усилия по сжатию сообщения. Кроме того, необходимость наличия полной частотной статистики перед началом собственно кодирования требует двух проходов по сообщению: одного для построения модели сообщения (таблицы частот и Н-дерева), другого для собственно кодирования.

Арифметическое кодирование

Арифметическое сжатие - достаточно изящный метод, в основе которого лежит очень простая идея. Мы представляем кодируемый текст в виде дроби, при этом строим дробь таким образом, чтобы наш текст был представлен как можно компактнее. Для примера рассмотрим построение такой дроби на интервале [0, 1) (0 - включается, 1 - нет). Интервал [0, 1) выбран потому, что он удобен для объяснений. Мы разбиваем его на подынтервалы с длинами, равными вероятностям появления символов в потоке. В дальнейшем будем называть их диапазонами соответствующих символов.

Пусть мы сжимаем текст "КОВ.КОРОВА" (что, очевидно, означает "коварная корова"). Распишем вероятности появления каждого символа в тексте (в порядке убывания) и соответствующие этим символам диапазоны: