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

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

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

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

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

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

Для упорядочивания данных применяют структуры данных. Основных структур три линейная (список), табличная, иерархическая (дерево). Часто основные структуры комбинируются, например, элементами иерархической структуры могут быть линейные, а элементами линейной могут быть таблицы.

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

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

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

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

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

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

d [N(m-1)+(n-1)]

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

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

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

Россия

К раснодарский край Ростовская область Ставропольский край

С емикорокорский район Ростов Красносулинский район Белокалитвенский район

Ворошиловский Большая Садовая Будёновский

Рис. 1.6. Пример иерархической структуры.

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

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

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

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