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

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

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

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

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

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

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

                                                                                    Выполнил:

                                                                                    студент 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 бита. Большего можно достичь, формируя более точные модели текста. Модель, по существу, есть набор вероятностей распределения, по одному на каждый контекст, на основании которого символ может быть закодирован. Контексты называются классами условий, т.к. они определяют оценки вероятности. Нетривиальная модель может содержать тысячи классов условий.