0 / 0 / 1
Регистрация: 28.02.2015
Сообщений: 65
1

Сжатие Хаффмана

08.04.2015, 02:34. Показов 3951. Ответов 2
Метки нет (Все метки)

Есть прога, реализующая сжатие Хаффмана:

C++
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
#include "stdafx.h"
#include <iostream>
#include <vector>
#include <map>
#include <list>
#include <fstream>
using namespace std;
 
class Node
{
    public:
     int a;
     char c;
     Node *left, *right;
     
     Node(){left=right=NULL;}
 
     Node(Node *L, Node *R) 
     {  left =  L;
        right = R;
        a = L->a + R->a;  }
};
 
 
struct MyCompare
{
    bool operator()(const Node* l, const Node* r) const { return l->a < r->a; }
};
 
 
vector<bool> code;                
map<char,vector<bool> > table;    
 
void BuildTable(Node *root)
{   
    if (root->left!=NULL) 
                      { code.push_back(0);
                      BuildTable(root->left);}
     
    if (root->right!=NULL)
                       { code.push_back(1);
                       BuildTable(root->right);}
   
    if (root->c) table[root->c]=code;     
    
    code.pop_back();
}
 
 
int main (int argc, char *argv[])
{
////// считаем частоты символов   
    
    ifstream f("C:\\1.txt");
    
    map<char,int> m;
 
    while (!f.eof())
    { char c = f.get(); 
       m[c]++;}
    
  
////// записываем начальные узлы в список list
                 
   list<Node*> t;
   for( map<char,int>::iterator itr=m.begin(); itr!=m.end(); ++itr)
   {  
      Node *p = new Node;
      p->c = itr->first;
      p->a = itr->second;  
      t.push_back(p);      }    
    
 
//////  создаем дерево     
 
  while (t.size()!=1)
  {  
     t.sort(MyCompare());
    
     Node *SonL = t.front();
     t.pop_front();
     Node *SonR = t.front(); 
     t.pop_front();
     
     Node *parent = new Node(SonL,SonR); 
     t.push_back(parent);
 
  }
    
    Node *root = t.front();   //root - указатель на вершину дерева
 
////// создаем пары 'символ-код':           
 
    BuildTable(root);   
        
////// Выводим коды в файл output.txt
 
    f.clear(); f.seekg(0); // перемещаем указатель снова в начало файла
    
    ofstream g("output.txt", ios::out | ios::binary);
        
    int count=0; char buf=0;
    while (!f.eof())
    { char c = f.get();
      vector<bool> x = table[c];
      for(int n=0; n<x.size(); n++)
       {buf = buf | x[n]<<(7-count);   
        count++;   
        if (count==8) { count=0;   g<<buf; buf=0; } 
       }
    }
 
    f.close();
    g.close(); 
    
///// считывание из файла output.txt и преобразование обратно
 
    ifstream F("output.txt", ios::in | ios::binary);
 
    setlocale(LC_ALL,"Russian"); // чтоб русские символы отображались в командной строке
    
    Node *p = root;
    count=0; char byte; 
    byte = F.get();
    while(!F.eof())
    {   bool b = byte & (1 << (7-count) ) ; 
        if (b) p=p->right; else p=p->left;
        if (p->left==NULL && p->right==NULL) {cout<<p->c; p=root;}
        count++;
        if (count==8) {count=0; byte = F.get();}
    }
    
    F.close();  
 
    return 0;
}


Вопрос: Что происходит в этой части кода?:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Node
{
    public:
     int a;
     char c;
     Node *left, *right;
     
     Node(){left=right=NULL;}
 
     Node(Node *L, Node *R) 
     {  left =  L;
        right = R;
        a = L->a + R->a;  }
};
Спасибо!
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
08.04.2015, 02:34
Ответы с готовыми решениями:

Сжатие Хаффмана
Как изменить данный алгоритм, чтобы ограничить длину кода символа заданным числом Nmax? Спасибо! ...

Сжатие методом Хаффмана
Хочу реализовать алгоритм &quot;Сжатие методом Хаффмана&quot; но столкнулся с такой проблемой. Проблема вот в...

Код Хаффмана
Всем доброго дня! имеется код хафманна, работает, но считает неправильно! кто может объяснить в чем...

Алгоритм Хаффмана
Доброго времени суток, пишу сюда, так как отчаялся найти ошибку сам. Собственно проблема состоит в...

2
2548 / 1207 / 358
Регистрация: 30.11.2013
Сообщений: 3,826
08.04.2015, 02:51 2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Node
{
    public:
     int a;
     char c;
     Node *left, *right;
     
     Node(){left=right=NULL;}  // создают узел без параметров тоесть пустой (новый)
 
     Node(Node *L, Node *R)  // создают узел где-то в середине и поэтому уже известны его ветви левая и правая
     {  left =  L;
        right = R;
        a = L->a + R->a;  } // переменная а наверно количество элементов на ветве
};
1
20 / 20 / 14
Регистрация: 07.02.2015
Сообщений: 145
08.04.2015, 03:00 3
Описан класс Node ("узел"). left, right - указатели на левый и правый элементы в цепочке таких узлов. В конструкторе по умолчанию указатели просто зануляются. В конструкторе с параметрами передаются адреса левого и правого элемента списка. Целочисленное значение (int a) левого и правого элемента суммируются. Сумма присваивается переменной нового элемента.
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
08.04.2015, 03:00
Помогаю со студенческими работами здесь

Метод Хаффмана
Есть метод Хаффмана, но при выполнение в кодировании где-то добавляються переносы строк и из-за...

Алгоритм Хаффмана
Возможно и наболевшая тема на форуме, но всё же есть реализация алгоритма Хаффмана. Допустим, у...

Псевдоалгоритм Хаффмана
есть алгоритм n – количество символов исходного алфавита P – массив вероятностей,...

Шифрование Хаффмана
Ребята есть код шифрования Хаффмана, он почему-то пропускает букву Н. Помогите пожалуйста...


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

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru