Форум программистов, компьютерный форум, киберфорум
Pascal (Паскаль)
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.62/13: Рейтинг темы: голосов - 13, средняя оценка - 4.62
0 / 0 / 0
Регистрация: 28.03.2015
Сообщений: 18
1

Создание дерева для алгоритма Хаффмана

18.01.2016, 08:10. Показов 2344. Ответов 4
Метки нет (Все метки)

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

Начало алгоритма я написал. Это до просчета частоты вывода и сортировка методом пузырька по массиву.
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
var mas:array [1..1000] of string;
arr:array [1..1000] of real;
i,j,h:integer;
f: text;
s,c,e: string;
a: char;
k,d: real;
 
  
begin
 assign (f,'in.txt');
 reset (f);
 read (f,s);
 close (f);
 
 //Вывод вероятностей для каждой буквы
 
c:=s;
i:=1;
while i<=length(c) do
 begin
  a:=c[i];
  for j:=length(c) downto i+1 do
  if c[j]=a then delete(c,j,1);
  i:=i+1;
 end;
 for j:=1 to length(c) do
 begin
 mas[j]:=c[j];
 end;
//---------------------
for i:=1 to length(c) do
 begin
   for j:=1 to length(s) do
   begin
   if c[i]=s[j] then
   h:=h+1;
   end;
   k:=h/length(s);
   k:= round (k*100);
   k:=k/100;
   arr[i]:=k;
   k:=0;
   h:=0;
 end; 
//Конец вывода вероятностей для каждой буквы
 
//Метод пузырька
   for h:=1 to  length(c)-1 do
    begin
      for j:=1 to length(c)-1 do
      begin
      if arr[j]<arr[j+1] then
       begin
       d:=arr[j+1];
       arr[j+1]:=arr[j];
       arr[j]:=d;
       
       e:=mas[j+1];
       mas[j+1]:=mas[j];
       mas[j]:=e;
       end;
      end;
    end;
 
writeln;
 
for j:=1 to length(c) do
begin
 write (mas[j]:4);
end;
 
writeln;
 
for j:=1 to length(c) do
begin
 write (arr[j],' ');
end;
 
 writeln;
//Конец метода пузырька
 end.
Но вот есть проблемы с созданием бинарного дерево. Так сказать я просто не умею это самое дерево создавать. Помогите если сможете буду невероятно благодарен.

Добавлено через 16 часов 10 минут
Походу дело до ответа не дойдёт ...
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
18.01.2016, 08:10
Ответы с готовыми решениями:

Написать программу дешифровки алгоритма Хаффмана
Написать программу дешифровки алгоритма Хаффмана. Алфавит зашивается в коде программы. В алфавите...

Как исправить пример программы работы Алгоритма Хаффмана?
Доброго времени суток! Дан код программы на языке Паскаль - пример работы алгоритма Хаффмана. Есть...

Реализация алгоритма построения минимального остовного дерева для графа
Срочно помогите пожалуйста!!! Очень срочно нужно сделать прогу Тема: Реализация алгоритма...

Реализация Алгоритма Хаффмана
Здравствуйте. Прошу помочь, есть программа на ABC паскале, но необходимо чтобы было написано в...

4
28 / 28 / 23
Регистрация: 26.12.2015
Сообщений: 154
18.01.2016, 21:30 2
Лучший ответ Сообщение было отмечено dinaf2000 как решение

Решение

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
program Project1;
 
{$APPTYPE CONSOLE}
 
uses
  SysUtils;
 
type
  Tvesa=record
  symbols:string; //узел (что в узле)
  ves:integer;
  end;
 
  Tcode=record
  symbol:char;
  code:string; // ну можно конечно для наглядности в бинарку загнать
  end;
 
 
var VesArr:array of Tvesa; // массив весов символов
    CodeArr:array of Tcode; // массив кодовых слов
    f:Textfile ;
    s,st:string;
    i,j:integer;
    l:integer;
 
 
procedure sortVesarr;//процедура сортирует Vesarr в порядке убывания
var i,j:integer;
    prom:Tvesa;
begin
for i:=0 to length(vesarr)-2 do
  for j:=i+1 to length(vesarr)-1 do
    if VesArr[j].ves>vesarr[i].ves then
      begin
      prom.symbols:=vesarr[i].symbols;
      prom.ves:=vesarr[i].ves;
      vesarr[i].symbols:=vesarr[j].symbols;
      vesarr[i].ves:=vesarr[j].ves;
      vesarr[j].symbols:= prom.symbols;
      vesarr[j].ves:=prom.ves;
      end;
 
end;
 
 
 
/////////////////////////
begin
assign (f,'in.txt');
reset (f);
while not EOF(f) do
begin
readln (f,st);
s:=s+st;
end;
close (f);
 
//// считаем частоту встречи
for i:=1 to length(s) do
  for j:=0 to length(vesarr) do
    begin
    if j=length(vesarr) then
      begin
      setlength(vesarr,length(vesarr)+1);
      vesarr[length(vesarr)-1].symbols:=s[i];
      vesarr[length(vesarr)-1].ves:=1;
      break;
      end
    else
      if s[i]=vesarr[j].symbols[1] then
        begin
        vesarr[j].ves:=vesarr[j].ves+1;
        break;
        end;
    end;
//  vesarr содержит веса
 
sortVesarr;
 
setlength(CodeArr,length(vesarr));
for i:=0 to Length(VesArr)-1 do
    begin
    CodeArr[i].symbol:=vesarr[i].symbols[1];
    CodeArr[i].code:='';
    end;
 
 
//Формируем Дерево
 
 
 
 
while length(VesArr)>1 do
  begin
 
  if length(vesarr[length(vesarr)-1].symbols)=1 then
    begin
      for i:=0 to Length(CodeArr)-1 do
        if vesarr[length(vesarr)-1].symbols[1]=codearr[i].symbol then
            begin
            CodeArr[i].code:='0'+codearr[i].code;
            break;
            end;
    end
    else
       for i:=1 to length(vesarr[length(vesarr)-1].symbols) do
        for j:=0 to Length(CodeArr)-1 do
        if vesarr[length(vesarr)-1].symbols[i]=CodeArr[j].symbol then
          CodeArr[j].code:='0'+CodeArr[j].code;
 
   if length(vesarr[length(vesarr)-2].symbols)=1 then
    begin
      for i:=0 to Length(CodeArr)-1 do
        if vesarr[length(vesarr)-2].symbols[1]=codearr[i].symbol then
            begin
            CodeArr[i].code:='1'+codearr[i].code;
            break;
            end;
    end
    else
       for i:=1 to length(vesarr[length(vesarr)-2].symbols) do
        for j:=0 to Length(CodeArr)-1 do
        if vesarr[length(vesarr)-2].symbols[i]=CodeArr[j].symbol then
          CodeArr[j].code:='1'+CodeArr[j].code;
 
 
  vesarr[length(vesarr)-2].symbols:=vesarr[length(vesarr)-2].symbols+vesarr[length(vesarr)-1].symbols;
  vesarr[length(vesarr)-2].ves:=vesarr[length(vesarr)-2].ves+vesarr[length(vesarr)-1].ves  ;
  setlength(VesArr,length(VesArr)-1);
  sortVesarr;
  end;
 
 
 
  l:=0;
  writeln('ishodny text:');
  writeln(s);
  writeln('');
  writeln('Kodirovanny text:');
for i:=1 to length(s) do
begin
  for j:=0 to length(CodeArr)-1 do
  if s[i]=codearr[j].symbol then
    begin
    write(codearr[j].code+' ');
    l:=l+length(codearr[j].code);
    end;
end;
  writeln('');
   writeln('');
  writeln('Dlina zacodirovannogo: ',l);
 
readln;
end.
Для декодирования нужна таблица CodeArr, кстати тут, результат несколько отличается от Википедии - там в примере почему-то не прослеживается логика присвоения "0" или "1" той или иной ветке так на предпоследнем шаге "rcd" повесилась на "1" потому что имеет больший вес а на последнем "brcd" повесилась на 0 хотя тоже имеет больший чем "a" вес.
Вложения
Тип файла: rar Хаффман.rar (25.5 Кб, 33 просмотров)
1
0 / 0 / 0
Регистрация: 28.03.2015
Сообщений: 18
21.01.2016, 18:10  [ТС] 3
Спасибо за решение !!!!! + в репу.
На счет построения дерева, есть какие-нибудь уроки ?
Я бы не прочь и самому научиться
0
28 / 28 / 23
Регистрация: 26.12.2015
Сообщений: 154
21.01.2016, 18:40 4
На самом деле фактического "дерева" программа не строит - если построчно посмотреть происходит следующее:
шаг1:
массив vesarr= a,b,c,d,e

массив codearr='','','','','' (пустые значения по количеству элементов vesarr)
шаг2:
среди двух последних элементов массива vesarr находим состоящий из одного символа, если он последний кидаем в codearr на его позицию 0, если предпоследний то 1

шаг3:
находим среди двух последних элементов vesarr тот чья длина больше одного и всем элементам codearr из которых он состоит добавляем в начало 0, если предпоследний то 1
шаг 5
Объединяем в vesarr два последних элемента, суммируя вес
шаг 5
сортируем vesarr по убыванию веса
шаг 6
переходим к шагу 1, если длина vesarr больше одного

, как строить именно "дерево", используя наследование в pascal - не знаю (в ООП языках все проще), хотя для данной задачи это может быть и не нужно
0
0 / 0 / 0
Регистрация: 28.03.2015
Сообщений: 18
21.01.2016, 19:18  [ТС] 5
Спасибо за алгоритм.
Завтра сам попробую скину, если получится .
0
21.01.2016, 19:18
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
21.01.2016, 19:18
Помогаю со студенческими работами здесь

Построение дерева Хаффмана для одноименного алгоритма
Отсортированные по частотности повторений ссылки на символы имеются. Читал про алгоритм построения...

Построение дерева Хаффмана
Не могли бы вы мне помочь, объяснив сам принцип построения дерева? Выбираем из массива два...

Обход дерева Хаффмана
Добрый вечер. Имеем кодовое дерево Хаффмана.(в изображении) До каждого узла данного дерева...

Исходник алгоритма Хаффмана на C
Пожалуйсто дайте исходник алгоритма Хаффмана на C.


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru