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

Кодирование Хаффмана

04.05.2015, 00:07. Показов 2971. Ответов 3
Метки нет (Все метки)

Есть дерево Хаффана, с помощью функции, приведенной ниже прохожусь по дереву и "выписываю" 0 и 1, получившиеся коды символов записываю в "vector<bool> code;", с помощью "map<char, vector<bool> > table;" связываю символы и их коды, затем посимвольно прохожу по тексту и вывожу в консоль коды, соответсвующие символам, но появляются лишние 0. В чем ошибка? Спасибо=)

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
vector<bool> code;// вектор из 0 и 1
map<char, vector<bool> > table;//  ассоциация символа с кодом
 
void MakingTable(Node *peak)
{
    if (peak->left != NULL)//если слева не ноль
    {
        //cout << endl << "Checking_ONE(____0____)" << endl;
        code.push_back(0);//ставим в вектор 0
        MakingTable(peak->left);//запускаем функцию вновь рекурсивно
        
    }
 
    if (peak->right != NULL)//если справа не 0
    {
        //cout << endl << "Checking_TWO(____1____)" << endl;
        code.push_back(1);//ставим в вектор 1
        MakingTable(peak->right);//запускаем рекурсивно
        
    }
    
    if (peak->c)
    {
        table[peak->c] = code;//если находится буква, то ассоциируем ее с кодом
        code.pop_back();//код сокращаем на единицу, чтобы подняться на узел выше
    }
        
    
    
}

в файле записано abcd и код должен выглядеть как 00011011
но получается вот так: 0001010011

Добавлено через 11 минут
скрин
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
04.05.2015, 00:07
Ответы с готовыми решениями:

кодирование хаффмана
здравствуйте! я пишу программу сжатия jpeg. написала код для кодирования хаффмана по дереву. и...

Кодирование Хаффмана
Добрый вечер. Я за эту неделю малость зафлудил форум наверно. Прошу прощения за это. Просто уже не...

Кодирование алгоритмом Хаффмана
Проблема - такая : Есть рабочая программа, которая кодирует текстовый файл алгоритмом хаффмана....

Кодирование алгоритма Хаффмана
Доброго времени суток. У меня есть на руках рабочий код. Вопрос стоит следующим образом: Нужно...

3
0 / 0 / 1
Регистрация: 28.02.2015
Сообщений: 65
04.05.2015, 00:08  [ТС] 2
______
Миниатюры
Кодирование Хаффмана  
0
1386 / 1016 / 323
Регистрация: 28.07.2012
Сообщений: 2,804
04.05.2015, 01:55 3
Цитата Сообщение от bkeSevn Посмотреть сообщение
Node *peak
А где строится дерево?

Цитата Сообщение от bkeSevn Посмотреть сообщение
if (peak->c) { table[peak->c] = code;//если находится буква, то ассоциируем ее с кодом
code.pop_back();//код сокращаем на единицу, чтобы подняться на узел выше
}
В таком случае код будет сокращаться только для листьев дерева. Если, конечно, peak->c != 0 только для листьев твоего дерева.

Цитата Сообщение от bkeSevn Посмотреть сообщение
map<char, vector<bool> > table;
Раз ты выбрал такой спорный подход для кодировании по хаффману, то стоит задуматься и о декодировании.
Тебе придется построить таблицу обратных преобразований из vector<bool> в char.
Я думаю, что будет это не так просто.
0
0 / 0 / 1
Регистрация: 28.02.2015
Сообщений: 65
04.05.2015, 02:15  [ТС] 4
Создание дерева

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
list<Node*> t;//создаем лист указателей на Node
 
    map<char, int>::iterator iter; //создаем итератор
    for (iter = m.begin(); iter != m.end(); ++iter) //m.begin - от начала и пока не конец m.end
    {
        cout << iter->first << "=" << iter->second << endl; //first-первый элемент m, second-второй; выводим все это
 
 
        Node *p = new Node;//создаем указатель на Node, т.е. создаем в динамической памяти новый узел
        p->c = iter->first;//его "C" становится first
        p->a = iter->second;//его "A" становится second
        t.push_back(p);//указатель на все это добро пишу в list, т.е. я загрузил его первоначальными узлами
 
    }
 
    while (t.size() != 1)// пока в list'e не останется 1 элемент
    {
        t.sort(MyCompare());//сортирую list
        Node *SonL = t.front();//присваиваю первый элемент list'a
        t.pop_front();//удаляю первый элемент list'a
        Node *SonR = t.front();//присваиваю второй, который встал на первое место
        t.pop_front();//его тоже удаляю
 
 
        Node *parent = new Node(SonL, SonR);//создаю отца на основании SonL и SonR,ложу его в список 
        t.push_back(parent);//кладу отца в список
    }
 
    Node *peak = t.front();//вершина дерева
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
04.05.2015, 02:15
Помогаю со студенческими работами здесь

Декодирование и Кодирование Кода Хаффмана
Здравствуйте уважаемые! Мне нужно написать декодер кода Хаффмана. Но я столкнулся, наверное, с...

Кодирование текста методом Хаффмана
Вроде бы всё правильно , НО : 1)вылезает &quot;ё&quot; в самом начале , хотя сортируется map по умолчанию по...

Кодирование Хаффмана (bmp в свой формат)
Дообры день! Подскажите как реализовать следующее: Есть программа кодирования/декодирования...

кодировка Хаффмана
Дорогие программисты. Вот был написан код &quot;кодировка Хаффмана&quot;, и тут мы вводим количество данных и...


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

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

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