Совмещенный способ построения кода Хаффмана Совмещенный способ построения кода Хаффмана – объединение двух процессов: обычного алгоритма построения и метода дерева.

Код Хаффмана позволяет производить кодирование и при использовании вторичного алфавита с основанием D больше 2, например при D=3.

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

Сжатие информации

Сжатие информации возможно при наличии избыточности в сообщении. Различают следующие виды избыточности.

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

Классификация сжатия по виду информации

1. Побуквенное сжатие

2. Сжатие слов и словосочетаний

3. Сжатие и свертывание текста

4. Сжатие массивов чисел

5. Сжатие графической информации

1) Побуквенное сжатие

 Оптимальные коды (коды Хаффмана)

 Блочное кодирование

 Переход к кодированию с основанием больше двух :

2) Сжатие слов и словосочетаний

 Аббревиатура

 Иероглифы

 Отбрасывание окончаний слов

 Отбрасывание часто повторяющихся букв

 Выборочное отбрасывание букв

КИБЕРНЕТИКА

КБРЕИА

КРИ

 Лексическое кодирование

При лексическом кодировании отдельные лексемы заменяются двоичными кодами

Наименование лексем	Длина в байтах	N-кол. лексем	log2N бит
Фамилия	20	1000	10 бит
Имя	15	100	7 бит
Отчество	20	100	7 бит
Должность	30	50	6 бит
Отдел	50	30	5 бит
	135байт		»5 байт

Таким образом, получили сжатие в 135/5=27 раз.

3) Сжатие и свертывание текста

 Библиогафическое описание (УДК, Автор, наименование, издательство)

 Аннотация (до 2/3 страницы)

 Реферат (до 16 стр., Автореферат - один печатный лист)

4) Сжатие массивов чисел

При сжатии массивов чисел широко используется метод Бабко. На предприятиях номенклатура (это изделия, материалы, инструменты и др.) кодируются десятичными номерами. Массивы таких чисел могут составлять десятки тысяч. Если этот массив чисел упорядочить в порядке возрастания, то последующие числа будут отличаться от предыдущих чисел только младшими разрядами. Тогда можно все повторяющиеся цифры заменить одним символом, например w.

5 5 3 8 1 4 2	5 5 3 8 1 4 2
5 5 3 8 1 4 3	w3 w5 w 6 1
5 5 3 8 1 4 5	w3
5 5 3 8 16 1
5 5 3 8 1 6 3