Курсовой работы по дисциплине «Алгоритмы и структуры данных» «Реализация метода Хаффмана»

  • 13 сент. 2011 г.
  • 1104 Слова
Кыргызско-Российский Славянский университет

Кафедра информационных и вычислительных технологий

О выполнении курсовой работы по дисциплине «Алгоритмы и структуры данных»

Тема: «Реализация метода Хаффмана»

Выполнил: Данияр уулу Бектур
Руководитель: ______________

Бишкек 2011

1. Аннотация
Результат выполнения курсовой работы – программа «Sur Archiver» позволяет сжимать файлы,уменьшая их размер, а затем распаковывать, полностью восстанавливая исходную информацию. Программа работает в среде Win32, однако имеется версия под DOS, работающая с аналогичным форматом архивов. Программа имеет удобный интерфейс, позволяющий легко выбирать файлы для сжатия и разархивации. При сжатии программа выводит дополнительную информацию, такую, как частоты появления символов исоответствующие им двоичные коды.

2. Оглавление

1. Аннотация 2
2. Оглавление 3
3. Задание на курсовую работу 4
4. Введение 5
4. Введение 5
5. Разработка программы 6
5.1. Постановка задачи. 6
5.2 Модель и метод решения задачи 6
5.3 Описание структуры данных 7
5.4 Алгоритмическая и программная реализация задачи 7
6. Руководство программиста 9
7. Руководство пользователя 10
8. Тестирование 12
9. Результатыработы программы и их анализ 13
Использованная литература 13
Листинг программы 14


3. Задание на курсовую работу

Разрабатываемая программа должна обеспечить:
- реализацию алгоритма сжатия информации по методу Хаффмана,
- удобный интерфейс, позволяющий выбирать файлы, подлежащие сжатию,
- возможность просмотра файла после сжатия и после разархивации,
- количественную оценкурезультатов архивации;


4. Введение

Сжатие данных всегда было актуальнейшей проблемой информационных технологий. Несмотря на постоянное улучшение и технологический прогресс в способах хранения и передачи данных, потребности общества всегда на порядок опережают возможности техники. В данной ситуации очень полезной оказывается возможность уменьшить объем хранимой и передаваемой информации для экономии времени исредств. Описываемая в отчете программа использует один из наиболее эффективных алгоритмов сжатия данных – метод минимально-избыточных префиксных кодов, предложенный Д. Хаффманом.


5. Разработка программы

5.1. Постановка задачи.

Из необходимости хранить информацию в сжатом (и, соответственно, измененном) виде вытекает необходимость использования, по крайней мере, двух алгоритмов длякодирования и декодирования данных.

5.2 Модель и метод решения задачи

Современная теория предлагает следующий способ реализации алгоритма Хаффмана:
- Кодер
o Проход сжимаемого файла и подсчет частот символов
o Вычисление длин кодов
o Вычисление самих кодов
o 2-й проход файла, во время которого производится сжатие
- Декодер
o Считывание длин кодов из архива
o Заполнение массивов, используемыхпри декодировании без вычисления непосредственно кодов
o Проход и декодирование файла
Необходимо соотносить метод решения с возможностями языка.
Для разработки программы была выбрана среда визуального программирования Borland Delphi 7.0. Данная среда программирования предоставляет достаточно возможностей для хорошего решения поставленной задачи.
5.3 Описание структуры данных

Для решениязадачи использовались следующие структуры данных:
- Массив
- Минимальная пирамида
- Дерево с указателем на предка

5.4 Алгоритмическая и программная реализация задачи

Алгоритм тела программы в виде блок схемы:

Приведем для краткости лишь процедуру декодирования:
procedure Decompress(srcFile,destFile: string);
var fin : file;
var fout : file of char;
var header0 : string[15];
var b,bi:byte;
var i,curCode: longint;
var len: integer;

function GetBit: byte;
begin
if bi=8 then
begin
BlockRead(fin,b,1);
bi:=0;
end;
GetBit:= (b shr bi) and 1;
inc(bi);
end;

begin
assign(fin,srcFile); reset(fin,1);
BlockRead(fin,header0,16);
if header0header then
begin
application.MessageBox(Файл не...
tracking img