Файл: Методы кодирования данных (Основные типы данных и их кодирование).pdf

Несмотря на то, что для каждой структуры я привожу код реализации на JavaScript, вам вероятно, никогда не придется делать этого самостоятельно, только если вы не будете использовать низкоуровневый язык вроде С. JavaScript (как и большинство языков высокого уровня) имеет встроенные реализации многих из этих структур данных.^[6]

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

Связные списки

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

Рисунок 2 Связные списки

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

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

Стеки

Стек — это базовая структура данных, в которой вы можете только вставлять или удалять элементы в начале стека.^[7] Он напоминает стопку книг. Если вы хотите взглянуть на книгу в середине стека, вы сначала должны взять книги, лежащие сверху.

Стек считается LIFO (Last In First Out) — это означает, что последний элемент, который добавлен в стек, — это первый элемент, который из него выходит.

Рисунок 3 Стеки

Существует три основных операции, которые могут выполняться в стеках: вставка элемента в стек (называемый «push»), удаление элемента из стека (называемое «pop») и отображение содержимого стека (иногда называемого «pip»).

Очереди

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

Рисунок 4 Очереди

Если рассматривать очередь с точки доступа к данным, то она является FIFO (First In First Out). Это означает, что после добавления нового элемента все элементы, которые были добавлены до этого, должны быть удалены до того, как новый элемент будет удален.
В очереди есть только две основные операции: enqueue и dequeue. Enqueue означает вставить элемент в конец очереди, а dequeue означает удаление переднего элемента.

Рисунок 5 Множества

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

• Union (Объединение). Объединяет все элементы из двух разных множеств и возвращает результат, как новый набор (без дубликатов).
• Intersection (Пересечение). Если заданы два множества, эта функция вернет другое множество, содержащее элементы, которые имеются и в первом и во втором множестве.
• Difference  (Разница). Вернет список элементов, которые находятся в одном множестве, но НЕ повторяются в другом.
• Subset(Подмножество) — возвращает булево значение, показывающее, содержит ли одно множество все элементы другого множества.

Map

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

Map’ы позволяют сделать следующее:

• Добавление пары в коллекцию
• Удаление пары из коллекции
• Изменение существующей пары
• Поиск значения, связанного с определенным ключом

Рисунок 6 Хэш-таблицы

Хэш-таблица — это структура данных, реализующая интерфейс map, который позволяет хранить пары ключ / значение. Она использует хеш-функцию для вычисления индекса в массиве, по которым можно найти желаемое значение.

Хеш-функция обычно принимает строку и возвращает числовое значение. Хеш-функция всегда должна возвращать одинаковое число для одного и того же ввода. Когда два ввода хешируются с одним и тем же цифровым выходом, это коллизия. Суть в том, чтобы их было как можно меньше. Поэтому, когда вы вводите пару ключ / значение в хеш-таблице, ключ проходит через хеш-функцию и превращается в число.^[8]

Это числовое значение затем используется в качестве фактического ключа, в котором значение хранится. Когда вы снова попытаетесь получить доступ к тому же ключу, хеширующая функция обработает ключ и вернет тот же числовой результат. Затем число будет использовано для поиска связанного значения. Это обеспечивает очень эффективное время поиска O (1) в среднем.

1.3 Способы кодирования данных

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

1 способ. Двоичное кодирование. Одним из самых популярных и распространенных методов представления информации считается именно двоичное кодирование. В работе с вычислительными машинами, роботами и станками с числовым программным управлением чаще всего кодируют информацию в форме слов двоичного алфавита.

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

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

В процессе работы с цифровой информацией особенное значение получает синхронизация. В момент считывания либо записи информации немаловажным остается точное определение времени каждой смены знака. Если синхронизации нет, то период смены знака может определяться неправильно. В итоге этого неизбежной будет потеря или искажение данных. 4 способ. Run Length Limited — RLL. На сегодняшний день одни из самых популярных методов является кодирование информации с ограничением длины поля записи. Благодаря этому способу на диске можно разместить в полтора раза больше данных, нежели в процессе записи по методу MFM. Используя этот метод происходит кодирование не отдельного бита, а целой группы.

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

Глава 2. Осуществление кодирования данных

2.1 Передача информации в компьютерных сетях

Протоколы, предназначенные для маршрутизации в мобильной беспроводной сети, подразделяются на три основные категории. Это проактивные, реактивные и гибридные протоколы маршрутизации. В каждой категории существуют несколько протоколов: Реактивные протоколы маршрутизации начинают создавать маршруты только по требованию. Протокол маршрутизации будет пытаться установить маршрут в том случае, когда какой-либо узел захочет установить связь с другим узлом к которому он не имеет маршрута. Этот тип протоколов обычно основывается на заполнении сети сообщениями типа Route Request (RREQ) и Route Reply (REPL).^[9]

При помощи со общений Route Request маршрут определяется от источника к необходимому узлу (цель), и как только необходимый узел получает RREQ сообщение, он отправляет REPL сообщения для подтверждения того, что маршрут установлен. Этот тип протоколов как правило эффективен в сетях с одинаковыми характеристиками и параметрами. Он обычно уменьшает количество прыжков выбранного маршрута.

Однако в больших сетях с множественными характеристиками количество хапов не такой важный показатель как пропускная способность в построенном маршруте.

Примеры реактивных протоколов маршрутизации: AODV (Ad hoc OnDemand Distance Vector Routing Protocol) DSR (Dynamic Source Routing Protocol) ACOR (Admission Control enabled On demand Routing Protocol) ABR (Associative Based Routing Protocol). Проактивные протоколы маршрутизации MANET также называют таблично-ориентированными протоколами, которые активно определяют уровень состояния сети.

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

Таким образом, в результате повышения мобильности, существует недостаток, выраженный в увеличении объема трафика, генерирующегося при построении ненужных маршрутов. Особенно это заметно при значительном увеличении размера сети. Часть общего трафика управления, который состоит из актуальных практических данных, уменьшается.^[10] Наконец, если узлы передают данные нечасто, то большая часть маршрутной информации рассматривается как избыточная.

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

Таким образом, проактивные протоколы маршрутизации лучше работают в сетях с низкой мобильностью или в сетях с часто генерируемым трафиком. Примеры проактивных протоколов маршрутизации: OLSR (Optimized Link State Routing Protocol) FSR (Fisheye State Routing Protocol) DSDV (Destination Sequenced Distance Vector Routing Protocol). CGSR (ClusterHead Gateway Switch Routing Protocol).

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

Примеры гибридных протоколов маршрутизации: TORA (Temporallyordered Routing Algorithm Protocol) HSR (Hierarchical State Routing Protocol) ARPAM (Adhoc Routing Protocol for Aeronautical Mobile AdHoc Networks) OORP (OrderOne Routing Protocol) качестве средства имитационного моделирования использовался сете вой симулятор OPNET (Optimized Network Engineering Tool) Modeler вер сии 14.0. Это наиболее широко используемый коммерческий симулятор, работающий под операционной системой Microsoft Windows и включающий в себя реализацию исследуемых нами протоколов маршрутизации.^[11]

Данный программный продукт не только поддерживает MANET маршрутизацию, но и также предоставляет параллельное ядро для поддержки увеличения стабильности и мобильности в сети. Функции интенсивного анализа OPNET обеспечивают лучшие условия для сравнения, вычисления и координации выходных данных. В рамках Opnet Modeler пользователи могут использовать графическую среду для того, чтобы создать, выполнить и проанализировать событийное моделирование сетей связи.

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

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