35. Основные понятия теории информации

Теория информации – раздел математики, исследующий процесс хранения, преобразования и передачи информации.

Теория информации базируется на фундаментальной работе американского инженера и математика Клода Элвуда Шеннона, и она тесно сопряжена со статистической теорией связи.

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

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

Процесс изменения параметров сигнала на передающей стороне, происходящий в соответствии с содержанием передаваемого сообщения, называется модуляцией

Линией связи называется физическая среда, используемая  для транспортировки сигналов от передатчика к приемнику. 

36. Префиксные коды, коды Хаффмена

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

Алгоритм основан на том факте, что некоторые символы из стандартного 256-символьного набора в произвольном тексте могут встречаться чаще среднего периода повтора, а другие соответственно – реже.

Сжимая файл алгоритмом Хаффмана, первое, что мы должны сделать – это необходимо прочитать файл полностью и подсчитать сколько раз встречается каждый символ из расширенного набора ISCII.

37. Статическое и адаптивное кодирование

Адаптивное сжатие позволяет не передавать модель сообщения вместе с ним самим и ограничиться одним проходом по сообщению как при кодировании, так и при декодировании.

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

38. Арифметическое кодирование

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

Предполагаемая последовательность символов при сжатии методом арифметического кодирования рассматривается как некоторая двоичная дробь из интервала [0;1).Результат сжатия представляется как последовательность двоичных цифр из записи этой дроби.

39. Алгоритмы Лемпела-Зива

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

алгоритм Лемпела-Зива преобразует один поток исходных символов в два параллельных потока длин и индексов в таблице.

схема двухступенчатого кодирования - наиболее эффективная из практически используемых в настоящее время.