4 / 4 / 4
Регистрация: 03.01.2015
Сообщений: 449
1

Реализовать алгоритм оптимального кодирования Хаффмана

07.11.2015, 15:18. Показов 1899. Ответов 3
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Добрый день! Нужно реализовать алгоритма Хаффмана.
Помогите, пожалуйста.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
07.11.2015, 15:18
Ответы с готовыми решениями:

Алгоритм оптимального кодирования Хаффмена
Добрый день! Помогите, пожалуйста, написать алгоритм оптимального кодирования Хаффмена.

Реализовать алгоритм шифрования Хаффмана
2. Шифрование Хаффмана namespace System.Algorithm { public static class Huffman { ///...

Помогите реализовать алгоритм Хаффмана на JavaScript
Помогите пожалуйста новичку. Просто мой уровень знания языка не позволяет реализовать алгоритм...

Реализовать алгоритм А* для поиска оптимального пути из начальной вершины в конечную на графе
Привет Нужно реализовать этот алгоритм для поиска оптимального пути из начальной вершины в...

3
1779 / 757 / 153
Регистрация: 03.06.2009
Сообщений: 5,927
08.11.2015, 09:59 2
Кодирование Хаффмана: Хаффман с++
0
4 / 4 / 4
Регистрация: 03.01.2015
Сообщений: 449
19.12.2015, 11:45  [ТС] 3
Добрый день!

Не до конца понимаю как работает алгоритма Хаффмана. Поняла, что в начале просматривается строка. Берется символ. Если он уже был записан, то увеличивается count на 1. Если не было, тогда добавляется и count присваивается единица. То есть в начале считается количество каждого символа в строке. А вот как работает дальше не пойму. Помогите, пожалуйста
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
#include<vector>
#include<iostream>
#include<string>
 
using namespace std;
 
struct charC{
    char chr;
    int count;
    float prop;
};
 
void main(){
    vector<string> tmpS, res;
    vector<charC> voc;
    charC *tmpCChr;
    string srcStr;
    vector<vector<float>> mas1;
    vector<float> tmpM;
    vector<int> poses;
    int i, j, Count, tmpV;
    float tmpInt;
    setlocale(LC_ALL, "rus");
    //cin >> noskipws >> srcStr;
    srcStr = "мама мыла раму";
    bool add;
 
    for (i = 0; i < srcStr.length(); i++){
        add = true;
        for (j = 0; j < voc.size(); j++){
            tmpCChr = &voc[j];
            if (tmpCChr->chr == srcStr[i]){
                tmpCChr->count = tmpCChr->count + 1;
                add = false;
            }
        }
        if (add){
            tmpCChr = new charC;
            tmpCChr->chr = srcStr[i];
            tmpCChr->count = 1;
            voc.push_back(*tmpCChr);
        }
    }
    tmpM.clear();
    mas1.push_back(tmpM);
    Count = srcStr.length();
    for (i = 0; i < voc.size(); i++){
        tmpCChr = &voc[i];
        tmpCChr->prop = tmpCChr->count*1.0 / Count;
        mas1[0].push_back(tmpCChr->prop);
    }
 
    /*
    tmpM.clear();
    mas1.push_back(tmpM);
    for(i=0;i<12;i++){
    cin>>tmpInt;
    mas1[0].push_back(tmpInt);
    }
    */
    while (i<mas1[0].size() - 1){
        if (mas1[0][i] < mas1[0][i + 1]){
            tmpV = mas1[0][i];
            mas1[0][1] = mas1[0][i + 1];
            mas1[0][i + 1] = tmpV;
            i = 0;
        }
        else{
            i++;
        }
    }
 
 
    //poses.push_back(0);
    i = 0;
    while (mas1[i].size()>2){
        tmpInt = mas1[i][mas1[i].size() - 1] + mas1[i][mas1[i].size() - 2];
        for (j = 0; j < mas1[i].size() - 2; j++){
            tmpM.push_back(mas1[i][j]);
        }
        j = tmpM.size() - 1;
        add = false;
        while (j >= 0){
            if (tmpM[j]>tmpInt){
                tmpM.insert(tmpM.begin() + j + 1, tmpInt);
                poses.push_back(j + 1);
                j = -1;
                add = true;
            }
            j--;
        }
        if (!add){
            tmpM.insert(tmpM.begin(), tmpInt);
            poses.push_back(0);
        }
        mas1.push_back(tmpM);
        tmpM.clear();
        i++;
    }
    res.push_back("0");
    res.push_back("1");
    i = mas1.size() - 1;
    while (i>0){
        for (j = 0; j <= mas1[i].size() - 1; j++){
            if (poses[i - 1] != j){
                tmpS.push_back(res[j]);
            }
        }
        tmpS.push_back(res[poses[i - 1]] + "0");
        tmpS.push_back(res[poses[i - 1]] + "1");
        res = tmpS;
        tmpS.clear();
        i--;
    }
    cout << "\nКодировка:\n";
    for (i = 0; i < res.size(); i++){
        tmpCChr = &voc[i];
        cout << tmpCChr->chr << ": " << res[i] << "\n";
    }
    cout << "\n Закодированое сообщение:\n";
    for (i = 0; i<srcStr.length(); i++){
        for (j = 0; j<voc.size(); j++){
            tmpCChr = &voc[j];
            if (tmpCChr->chr == srcStr[i]){
                cout << res[j] << " ";
            }
        }
    }
    system("pause");
}
0
161 / 122 / 85
Регистрация: 16.10.2013
Сообщений: 1,738
19.12.2015, 12:02 4
Maray, вот здесь прекрасно описан алгоритм
http://neerc.ifmo.ru/wiki/inde... 0%BD%D0%B0

Добавлено через 26 секунд
А так же здесь
http://habrahabr.ru/post/144200/
0
19.12.2015, 12:02
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
19.12.2015, 12:02
Помогаю со студенческими работами здесь

Адаптивный (динамический) алгоритм Хаффмана: Не получается реализовать функцию обновления дерева
Всем привет При реализации сабжа столкнулся с проблемой того, как задать дерево Хаффмана. ...

Программа для кодирования сообщений по методу Хаффмана. Invalid floating point operation
Короче прикол в следующем. Делаю прогу для кодирования сообщений по методу Хаффмана и параллельно...

Алгоритм кодирования LZ77
привет мальчики помогите пожалуйста мне дописать 3 строчки в функции def makeLZ77. препод сказал...

Алгоритм кодирования RLE
Какова длина последовательности, после кодирования которой методом RLE получится следующее?...


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

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

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