Способы представления (кодирования) информации.

В этом разделе мы будем рассматривать просто кодировки. (То есть такие, когда одно слово представляется в виде другого слова).

Во всех случаях рассматривается следующая модель. Есть два алфавита

А = (а ₁, …, а_n) иB = (b ₁, …, b_q).

Кодирование φ это отображение словα в алфавите А в слова β=φ(α) в алфавите В.

Кодирование будет дешифруемым, если по слову β однозначно восстанавливаетсяα. Тогда отображение φ – биекция.

Кодирование слов и поиск минимального кода

Пусть у нас есть кодируемые объекты x - слова в алфавите A.

Везде далее булев куб размерности n будем обозначать через Bⁿ.

Нельзя ли найти минимальную длину K(x) кода объектаx, пусть даже в другом алфавите B?

Оказывается, эта задача алгоритмически неразрешима.

Теорема: Не существует МТ, которая строит код минимальной длины.

Доказательство. От противного.

Упорядочим все элементы всех булевых кубов Bⁿ (сначала по увеличению размерности, а потом в лексикографическом порядке):

0, 1, 00, 01, 11, 000, 001… (*)

Пусть есть МТ Т ₁, которая умеет по х строить К (х). Используя Т ₁, строим другую МТ Т ₂ = F (T 1, …). Эта машина переводит натуральное m в первое по порядку (слева направо в последовательности (*) слово x такое, что K (x)> m. (T ₂ в (*)идет слева направо и на каждом шаге применяет Т ₁.) Следовательно, m – код х, так как по m однозначно восстанавливается x. При этом длинаmравна l(m)= log m, но K (x) – наименьшая возможная длина кода. Значит, K (x) ≤ log m.

Получили противоречие.

Теорема доказана.

Если информация связана с кодом объекта, то одной из мер информации является длина этого кода. Аналогичной мерой для алгоритма является его сложность.

Пример. Задача: Требуется найти количество единиц в двоичной записи целого числа.

Если число n задается в виде n+1 единицы *1...1*, то длина входа n+3. Если число задается в десятичной форме, это уже lg n. К этим двум способам добавим двоичную запись числа n. Ее длина log ₂n. Трудоемкость решения пропорциональная длине входа.

Но рассмотрим еще один подход к решению задачи. Пусть у нас есть 2ⁿ перенумерованных ячеек памяти, в каждой из которых содержится число, равное количеству единиц в двоичной записи номера ячейки. Тогда длина входа задачи для числа n равна 2ⁿ log ₂n.Трудоемкость решения равна константе.

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

Признаковое кодирование.

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

 

Субъект

Множество объектов

Код

s1

sm

p1

pk

 

Признаки:

 

 

Рассматривается множество объектовs₁,…,s_m (люди, болезни, месторождения и т.п.), которое нужно кодировать, т.е. каждому объекту нужно сопоставить слово в алфавите. При этом есть другое множество объектов, называемых признаками, которые мы умеем кодировать. Тогда кодом объекта при признаковом кодировании является вектор, компонентами которого являются коды (значения) признаков, применительно к данному объекту.

При признаковом кодировании объекта признаком называется отображение , где D_f— множество допустимых значений признака. Если заданы признакиf₁,…,f_n, то вектор x=(f₁(x),…,f_n(x)) называется признаковым описанием объекта x. Если признаковые описания отождествляют с самими объектами, то множество называют признаковым пространством.

В зависимости от множества признаки делятся на следующие типы:

1. бинарный признак: D_f=(0,1);

2. номинальный признак: D_f- конечное множество;

3. порядковый признак: D_f - конечное упорядоченное множество;

4. количественный признак: D_f - множество действительных чисел.

Можно использовать характеристические вектора признаков, например,

α (s_i) = (α ₁, …, α_k) .

Пример. s ₁ … s_n – люди.

Признаки:

1. Цвет волос

2. Рост

1. Вес
2. p ₄ … p_n – размеры частей тела человека.

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

Опр. Тест - это множество столбцов в T (A) такое, что все строки в подматрице, образованной этим множеством, попарно различны.

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

Длина теста – количество столбцов в тесте.

Тест будет тупиковым, если никакое его подмножество уже не будет тестом.

Минимальный тест – тест с минимальным количеством столбцов. Длину минимального теста обозначим через t(A).

Когда таблица T (A) – это признаковая таблица множества объектов (строки таблицы – вектора признаков объектов), то длина теста указывает на количество признаков, которых достаточно для различения объектов. Эти признаки соответствуют стобцам теста. Но будет ли их достаточно, если количество объектов увеличиться? В связи с этим вопросом тестовая тематика возникает и при определении качества выбора множества признаков.

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

Для получения содержательных результатов в области построения минимальных тестов необходимо накладывать ограничение на вид и структуру векторов признаков. В качестве примеров приведем несколько утверждений, доказательство которых либо очевидно, либо является несложным упражнением.(Обозначение приведены выше. Если не оговорено обратное – основание логарифма равно двум).

Утв. Справедливо неравенство

t(A)≥logm.

Заметим, что данное утверждение тесно связано с приведенным ниже понятием энтропия по Хартли. Оно означает, что если объектам даются битовые идентификаторы, то число бит в таком идентификаторе для различения mобъектов не может быть меньше log m.

Утв. Пусть строки матрицы Т(А) устроены так, что вместе с любой парой строк в матрице есть и строка, равная сумме этой пары по модулю два, тогда в такой матрице любой тупиковый тест будет минимальным и

t(A)=logm.

Данное утверждение станет для вас совершенно очевидным, если заметить, что в данном случае множество строк матрицы – подпространство булева куба.

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

Утв. Число тупиковых тестов таблицы не превосходит .

Утв. Если строками матрицы являются все наборы с четным числом единиц, то число тупиковых тестов такой таблицы равно числу ее столбцов.

Утв. Если строками матрицы являются все наборы с фиксированным числом единиц, то число тупиковых тестов такой таблицы равно числу ее столбцов.