Методы программирования: Методическое пособие для выполнения лабораторных работ, страница 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 байта).