Задание № 2 (10) Сжатие информации с побуквенным сдвигом.

2.1 Задание

Придумать комбинацию, аналогичную приведённой в примере, и сжать её.

2.2 Краткие теоретические сведения

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

Первая строка сжимаемой последовательности переписывается полностью - она становится опорной строкой. Эта строка, будет оставаться опорной, пока не появится строка, в которой первый символ изменится.

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

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

Отметим, что под цифрами, представленными в примере, для удобства, приняты двоичные биты МТК-2 (5 бит), ASCII (8 бит) или другого кода.

2.3 Пример.

Исходная битовая последовательность 9 5 7 0 1 2 4 9 5 7 0 1 2 5 9 5 7 0 1 2 5 9 5 7 0 3 8 6 9 5 7 0 3 9 0 1 2 3 4 5 6 7 1 2 3 4 5 9 1 1 2 3 4 5 9 3

Сжатая битовая Представление в последовательность памяти ЭВМ 9 5 7 0 1 2 4 9 5 7 0 1 2 4 р 5 р 5 р р 3 8 6 р р 9 0 1 2 3 4 р 3 8 6 5 6 7 р 9 1 р р 9 0 3 1 2 3 4 5 6 7 р 9 1 р 3

Рисунок 1 – Сжатие информации

Вывод. Данный метод позволяет сжать исходную информацию почти в два раза - из 56 символов до 29.

Задание №3 (11). Эффективное кодирование методом Хаффмана

3.1 Задание

Сформировать кодовые комбинации для передачи последовательности знаков алфавита в соответствии со своими ФИО и закодировать полученный алфавит:

а) краткая теория о методе и алгоритме кодирования;

б) выбрать из ФИО любое слово, имеющее максимальное количество повторяющихся букв (если в Вашем ФИО нет такого слова выберите любую фамилию, имя, отчество);

в) расчёт вероятности появления знаков алфавита, при учёте того что все буквы это 100% (таблица 4);

Таблица 4. Удельный вес буквы, встречающейся N раз в слове

Количество букв в слове	1 раз	2 раза	3 раза	4 раза	5 раз	6 раз
3	0,333	0,667	1,000
4	0,250	0,500	0,750	1,000
5	0,200	0,400	0,600	0,800	1,000
6	0,167	0,333	0,500	0,667	0,833	1,000
7	0,143	0,286	0,429	0,571	0,714	0,857
8	0,125	0,250	0,375	0,500	0,625	0,750
9	0,111	0,222	0,333	0,444	0,556	0,667
10	0,100	0,200	0,300	0,400	0,500	0,600
11	0,091	0,182	0,273	0,364	0,455	0,545
12	0,083	0,167	0,250	0,333	0,417	0,500
13	0,077	0,154	0,231	0,308	0,385	0,462
14	0,071	0,143	0,214	0,286	0,357	0,429
15	0,067	0,133	0,200	0,267	0,333	0,400

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

г) построение кодовых комбинаций;

д) построение дерева кодовых слов;

е) построение кодовых комбинаций для каждой буквы;

ж) построение битовой последовательности, передаваемой в канал связи;

з) определить энтропию источника сообщений;

и) определить среднюю длину кодовой комбинации;

к) составить кодовую комбинацию при передаче заданной последовательности сообщений;

л) ввести ошибку в 8 разряд (бит) кодовой комбинации;

м) сравните переданную и принятую последовательность сообщений;

н) рассчитать число бит при кодировании равномерным кодом (табл. 1) и кодом Хаффмана. Сделать вывод.