Методы программирования: Методическое пособие для выполнения лабораторных работ, страница 8

Шаг 0. Записать в  массив Т символы в порядке убывания их частот встречаемости. Все вершины дерева пометить как свободные.

К := N;             // —текущее количество вершин в дереве

Начальное состояние массива Т для строки “кол около колокола” из [1] представлено в таблице:

№	символ	свободный	частота	левый	правый	код
1	о	истина		0	0
2	к	истина		0	0
3	л	истина		0	0
4	пробел	истина		0	0
5	а	истина		0	0
6
7
8
9

Шаг 1. Выбрать такие вершины дерева с номерами L и R, что

T[L].свободный = истина И

T[R].свободный = истина

   Т[L].частота,

T[R].частота — минимальные из всех свободных вершин.

Создать новую вершину  дерева:

   K := K + 1;

   T[K].свободный := истина;

T[K].частота := T[L].частота + T[R].частота;

   T[K].левый := L;

   T[K].правый := R;

   T[L].свободный := ложь;

      T[R].свободный := ложь;

Шаг 2.  Если К < 2*N–1 то прейти на Шаг 1

         T[К].код:= ””; // — это корень построенного дерева, код его равен пустой строке

Шаг 3.

// конкатенация строк:

     T[T[K].левый ] := T[K].код + ”0”;   

  T[T[K].правый] := T[K].код + ”1”;

  K := K – 1;

Шаг 4.   Если К > N то перейти на Шаг 3.

В результате для нашего примера  получим следующее состояние

массива T:

№	символ	свободный	частота	левый	правый	код
1	о	ложь		0	0	“10”
2	к	ложь		0	0	“11”
3	л	ложь		0	0	“00”
4	пробел	ложь		0	0	“010”
5	а	ложь		0	0	“011”
6		ложь		4	5	“01”
7		ложь		3	6	“0”
8		ложь		1	2	“1”
9		истина		7	8	“”

В результате работы данного алгоритма для каждого элемента массива с номером от 1 до N в поле код будет записана строка, представляющая собой код Хаффмана для соответствующего символа.

Язык реализации – Си.

Лабораторная работа № 12.  Архивирование

Задание

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

Входные данные

На вход программе подается текстовый файл и код Хаффмана для этого файла.

Код Хаффмана может быть представлен либо в виде строк, записанных в другом файле, либо в виде дерева Хаффмана (как продолжение лабораторной работы №11).

Выходные данные

Нужно вывести в выходной файл закодированный входной текст.

Метод

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

В первой части необходимо указать длину входного файла в байтах и количество различных символов в нем (размер входного алфавита — N).

Таблица кодировки может быть представлена двумя способами.

1) в виде последовательности их N троек <символ, длина кода, код>, где

   символ — ASCII код символа входного алфавита (1 байт),

   длина кода — количество битов в соответствующем кодовом слове (1 байт),

   код — кодовое слово (1 или 2 байта).