Кодирование Шеннона-Фано




 

Методы эффективного кодирования сообщений для передачи по дискретному каналу без помех, предложенные Шенноном и Фано, заложили основу статистических методов сжатия данных. Код Шеннона-Фано строится следующим образом: символы алфавита выписывают в таблицу в порядке убывания вероятностей. Затем их разделяют на две группы так, чтобы суммы вероятностей в каждой из групп были максимально близки (по возможности, равны). В кодах всех символов верхней группы первый бит устанавливается равным 0, в нижней группы – 1. Затем каждую из групп разбивают на две подгруппы с одинаковыми суммами вероятностей, и процесс назначения битов кода продолжается по аналогии с первым шагом. Кодирование завершается, когда в каждой группе останется по одному символу.

Качество кодирования по алгоритму Шеннона-Фано сильно зависит от выбора разбиений на подгруппы: чем больше разность сумм вероятностей подгрупп, тем более избыточным оказывается код. Для дальнейшего уменьшения избыточности, используют кодирование крупными блоками – в качестве “символов” используются комбинации исходных символов сообщения, но и этот подход имеет те же ограничения. От указанного недостатка свободна методика кодирования Хаффмана.

 

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

 

Алгоритм Хаффмана гарантирует однозначное построение кода с наименьшим для данного распределения вероятностей средним числом символов кода на символ сообщения. На первом шаге подсчитываются частоты всех символов в исходных данных. На втором шаге строятся новые коды (битовые последовательности) для каждого символа, так, чтобы никакие две разные последовательности не имели общего начала, например, три последовательности 0, 10, 110. удовлетворяют этому требованию. Хаффман предложил строить двоичное дерево символов, в корне которого находится наиболее частый символ, на расстоянии 1 от корня – следующие по частоте символы, и так далее. На основе такого дерева коды для символов получаются путем выполнения простой процедуры обхода дерева. Код представляет собой путь от корня до символа, в котором 1 означает переход по левой ветви, а 0 – по правой. Такой способ построения гарантирует нужное свойство кодов. Наконец, на последнем шаге в выходные данные записывается построенное дерево, а за ним следуют закодированные данные.

Алгоритм Хаффмана обеспечивает высокую скорость упаковки и распаковки, но степень сжатия, достигаемая при его использовании, довольно невелика. Одним из недостатков этого алгоритма является необходимость двух проходов по данным – на первом проходе подсчитываются частоты, строится дерево и формируются коды, а на втором выполняется собственно кодирование. Этого недостатка лишен адаптивный алгоритма Хаффмана, пересчитывающий частоты символов (и, соответственно, изменяющий коды) по мере поступления данных.

 


СЕТЕВОЕ ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ

 

Архитектура СПО

 

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

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

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

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

Каждый уровень взаимодействует с соседними уровнями формально описанным способом. Говорят, что определен интерфейс (interface) между каждыми двумя уровнями. Интерфейс определяет набор услуг, служб или сервисов (service), которые нижележащий уровень предоставляет вышележащему. Каждый уровень состоит из сущностей (entities), выполняющих некие действия или активности (activities). Для получения услуги вышележащий уровень обращается к точке доступа к сервису (service access point, SAP).

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

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

 



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-02-16 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: