Структуры данных

Понятие сжатия информации

Еще одна проблема, тесно связанная с моделями представления информации, — сжатие информации.

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

Разработаны и применяются два типа алгоритмов сжатия: сжатие с изменением структуры данных (оно происходит без потери данных) и сжатие с частичной потерей данных. Алгоритмы первого типа предусматривают две операции: сжатие информации для хранения, передачи и восстановление данных точно в исходном виде, когда их требуется использовать. Такой тип сжатия применяется, например, для хранения текстов (наиболее известны алгоритмы Хаффмена и Лемпеля-Зива). Алгоритмы второго типа не позволяют полностью восстановить оригинал и применяются для хранения графики или звука; для текстов, чисел или программ они неприменимы.

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

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

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

Если элементы списка одной длины, структура называется вектором данных, разделители не требуются. При длине одного элемента — d, зная номер элемента — n, его начало определяется соотношением d (n -1).

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

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

Поиск, аналогично линейной структуре, осуществляется по разделителям. Если элементы таблицы одной длины, структура называется матрицей данных, разделители в ней не требуются. При длине одного элемента — d, зная номер строки — m и номер столбца n, a также строк и столбцов М, N, найдем адрес его начала:

d [N(m – 1) + (n – 1)].

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

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

Иерархическую структуру образуют, например, почтовые адреса.

Адрес одного из домов, расположенных, к примеру, на улице Большая Садовая, может выглядеть следующим образом:

Россия\Ростовская область\Ростов\ул. Большая Садовая\д. 1.

Линейная и табличная структуры более просты, чем иерархические, но если в линейной структуре появляется новый элемент, то упорядоченность сбивается. Например, если в списке студентов появляется новый человек, то расположенный по алфавиту список нарушается.

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

Дата добавления: 2014-01-06