1

Я реализовал алгоритм Хаффмана приведенный в коде ниже. Однако, я столкнулся с проблемой кодирования "лепестков" полученного дерева. Я не могу найти ошибку, почему алгорим кодирования проходит только 1 раз.

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <functional>
#include <queue>
#include "string.h"
using namespace std;
struct Node //Звено дерева
{
int x; //То, что записываем в дерево
char s[1]; //Символ
Node *l,*r,*p; //Это указатели на новые звенья
char code[256]; //Код символа
};

class CompareLastDigits   { 
public:
bool operator()(Node x, Node y)
{   return x.x > y.x ;
} 
};

void TraverseDFS(Node* node)
{
//We concatenate a 0 for each step to the left
if (node->l != NULL)
{
    TraverseDFS(node->l);   
}
//We concatenate a 1 for each step to the right
if(node->r != NULL)
{
    TraverseDFS(node->r);       
}  
while (node->l == NULL && node->r == NULL)
{
    Node* par = node;
    while (par->p != NULL) {
        strcat(node->code, par->p->s); //
        par = par->p;
    }
}

};

int main()
{
Node node[5];
priority_queue <Node, vector<Node>, CompareLastDigits > P;
int n = 5, i =0, j=0;
Node* nodeXY;
for (i=0;i<4;i++) {
    node[i].x = i;
    node[i].l = NULL;
    node[i].r = NULL;
    node[i].p = NULL;
    node[i].code[0] = '\0';
}
for (i=0;i<4;i++) {
    P.push(node[i]);
}
Node x[4], y[4];
i = 0;
while (P.size()!=1) { 
    x[i] = P.top();
    P.pop();
    y[i] = P.top();
    P.pop();
    nodeXY = new Node;
    (*nodeXY).x = x[i].x + y[i].x;
    if (x[i].x == y[i].x) {
        Node temp = x[i];
        x[i] = y[i];
        y[i] = temp;
    }
    (*nodeXY).l = &x[i];
    x[i].p = nodeXY;
    y[i].p = nodeXY;
    x[i].s[0] = '0';
    y[i].s[0] = '1';
    x[i].s[1] = '\0';
    y[i].s[1] = '\0';
    x[i].code[0] = '\0';
    y[i].code[0] = '\0';
    (*nodeXY).r = &y[i];
    (*nodeXY).p = NULL;
    //cout << "Retrieved element: " << (*nodeXY).x <<" " << (*nodeXY).l->x   <<" " << (*nodeXY).r->x << endl;
    P.push(*nodeXY);
    ++i;
}   
nodeXY->s[0] = '\0'; //у вершины дерево заверш символ
TraverseDFS(nodeXY);

cout<<nodeXY->l->l->code; // по идее должен выдавать 00

cin.get();
return 0;
}

Так же не могли бы вы подсказать существует ли более простая реализация алгоритма?

1
  • 1
    Спроси у @huffman - он судя по нику должен разбираться в теме :)
    – Barmaley
    21 ноя 2013 в 10:19

2 ответа 2

2

Честно говоря, я не смог понять, в чём идея Вашего кодирования дерева и что значит "алгорим кодирования проходит только 1 раз". По идее, дерево следует кодировать примерно так:

WriteTree(Node *pNode)
{
  if (pNode->l)
  {
    WriteBit(1);
    WriteTree(pNode->l);
  }
  else  WriteBit(0);

  if (pNode->r)
  {
    WriteBit(1);
    WriteTree(pNode->r);
  }
  else  
  {
    WriteBit(0);
    if (!pNode->l)
      WriteCode(pNode->code);  // Какому символу соответствует данный лист
  }
}

Но, возможно, это не самый оптимальный вариант по объёму записываемых данных.

В принципе, кода у Вас немного, так что проще алгоритм вряд ли найдётся

0

Я делал так: брал алфавит, считал вероятности, записывал в Map, сортировал по возрастанию. Каждый узел хранил в себе ссылки на те буквы, которые ему принадлежат. Дерево строилось следующим образом: создаем узел, берем группу элементов родителя, отсортированную по убыванию, и добавляем в группу нового узла по одному, пока их суммарная вероятность не превысит 1/2 суммы вероятностей группы родителя. Поскольку дерево бинарное, тут же указывалось, что левый это 1, а правый 0. Как только длинна группы родителя ровна 1 - значит тупик. Затем приходимся по узлам и заполняем Map кодовой таблицы Хаффмана. Ну, и все в отдельные функции, а не в main, что бы было проще разбираться на каком этапе ошибка.

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.