C++: пытаемся посчитать коды Хаффмана...

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

Увы, мне так и не удалось в имеющиеся для этого пару-тройку часиков получить того, что я хотел, размещаю две "недоделки" здесь для памяти.

Первое приложение довольно примитивно, зато умеет показывать результаты своей работы в простом и понятном виде. Обратите внимание на "странную" функцию index в коде, зачем она нужна - станет ясно в конце статьи.

Вот листинг и результат его прогона.

#define _CRT_SECURE_NO_WARNINGS
#include <Windows.h> /*Библиотека Studio, а не из стандарта*/
#include <clocale>
#include <cstdio>
#include <cstring>

typedef struct node_t {
 struct node_t *left, *right;
 int freq;
 char c;
} *node;

struct node_t pool[256] = { { 0 } };
node qqq[255], *q = qqq - 1;
int n_nodes = 0, qend = 1;
char *code[256] = { 0 }, buf[2048];

int index(char c) { //!!!
 return c < 0 ? c + 256 : c;
}

node createNode (int freq, char c, node a, node b) {
 node n = pool + n_nodes++;
 if (freq) n->c = c, n->freq = freq;
 else {
  n->left = a, n->right = b;
  n->freq = a->freq + b->freq;
 }
 return n;
}

void insertNode (node n) {
 int j, i = qend++;
 while ((j = i / 2)) {
  if (q[j]->freq <= n->freq) break;
  q[i] = q[j], i = j;
 }
 q[i] = n;
}

node removeNode() {
 int i, l;
 node n = q[i = 1];
 if (qend < 2) return 0;
 qend--;
 while ((l = i * 2) < qend) {
  if (l + 1 < qend && q[l + 1]->freq < q[l]->freq) l++;
  q[i] = q[l]; 
  i = l;
 }
 q[i] = q[qend];
 return n;
}

void buildTree(node n, char *s, int len) {
 static char *out = buf;
 if (n->c) {
  s[len] = 0;
  strcpy(out, s);
  code[index(n->c)] = out;
  out += len + 1;
  return;
 }
 s[len] = '0'; buildTree(n->left, s, len + 1);
 s[len] = '1'; buildTree(n->right, s, len + 1);
}

void initTree (const char *s) {
 int i, freq[256] = { 0 };
 char c[16];
 
 for (int i = 0; i < strlen(s); i++) freq[index(s[i])]++;
 //while (*s) freq[(int)*s++]++;

 for (i = 0; i < 256; i++) if (freq[i]) insertNode (createNode(freq[i], i, 0, 0));

 while (qend > 2) insertNode (createNode(0, 0, removeNode(), removeNode()));
 buildTree (q[1], c, 0);
}

void encodeData(const char *s, char *out) {
 while (*s) {
  strcpy(out, code[index(*s)]);
  out += strlen(code[index(*s++)]);
 }
}

void decodeData(const char *s, node t) {
 node n = t;
 while (*s) {
  if (*s++ == '0') n = n->left;
  else n = n->right;
  if (n->c) putchar(n->c), n = t;
 }
 putchar('\n');
 if (t != n) printf("Неверные данные для decodeData\n");
}

int main () {
 setlocale (LC_ALL, "Rus");
 SetConsoleCP (1251); SetConsoleOutputCP(1251); //Эти функции - только в Studio

 int i;
 const char *str = "Носорожек, носорожек, пробежался вдоль дорожек!"; //данные для кодирования
 char buf[1024];

 initTree (str);
 for (i = 0; i < 256; i++) if (code[i]) printf("'%c': %s\n", i, code[i]);

 encodeData(str, buf);
 printf("Закодировано: %s\n", buf);

 printf("Декодировано: ");
 decodeData(buf, q[1]);

 getchar();  return 0;
}

' ': 0010
'!': 100101
',': 00011
'Н': 100100
'а': 01001
'б': 01000
'в': 10110
'д': 00010
'е': 1000
'ж': 0111
'к': 0011
'л': 1010
'н': 10111
'о': 11
'п': 10011
'р': 0110
'с': 0000
'ь': 01011
'я': 01010
Закодировано: 100100110000110110110111100000110001100101011111000011011011011110
00001100011001010011011011010001000011101001101000000101000101011000010111010010
1100100001011011011011110000011100101
Декодировано: Носорожек, носорожек, пробежался вдоль дорожек!

Второй листинг формирует дерево в формате, пригодном для отображения средствами Google API, однако, добиться автоматического запуска браузера и передачи в него данных мне не удалось из-за двойных кавычек, мои попытки задокументированы внизу листинга в многострочном комментарии /* ... */.

#include <Windows.h> /*Библиотека Studio, а не из стандарта*/
#include <queue>
#include <iostream>
#include <sstream>
#include <algorithm>
using namespace std;

class Node {
public:
 string value, code;
 unsigned amount;
 Node *left, *right;

 bool operator() (const Node& x, const Node& y) const { //сравнение
  return x.amount > y.amount;
 }

 Node(const string& value = "", unsigned amount = 0, Node * left = 0, Node * right = 0) {
  this->value = value; //исходная строка
  this->code = ""; //битовое представление
  this->amount = amount; //частота встречаемости
  this->left = left; //потомки
  this->right = right;
 }

 string toString() { //Описание дерева для Гугля
  ostringstream ss;
  if (left != 0 || right != 0) { //Есть или оба потомка, или не одного
   ss << "\t\"" << code << ": " << value << "[" << amount <<
    "]\" -> \"" << left->code << ": " << left->value << "[" << left->amount << "]\";\n";
   ss << left->toString();
   ss << "\t\"" << code << ": " << value << "[" << amount <<
    "]\" -> \"" << right->code << ": " << right->value << "[" << right->amount << "]\";\n";
   ss << right->toString();
  }
  else {
   ss << "\t\"" << code << ": " << value << "[" << amount <<
    "]\" [shape=box, style=filled, fillcolor=green];\n";
  }
  return ss.str();
 }

 Node * join(Node x) { //Объединение деревьев
  return new Node(x.value + value, x.amount + amount, new Node(x), this);
 }
 
 static Node * buildTree(priority_queue<Node, vector<Node>, Node> graph) { //Построитель дерева
  while (graph.size() > 1) {
   Node *n = new Node(graph.top());
   graph.pop();
   graph.push(*n->join(*new Node(graph.top())));
   graph.pop();
  }
  return new Node(graph.top());
 }

 void generateCode (string code) { //Сгенерировать битовые коды
  this->code = code;
  if (left != 0 || right != 0) {
   left->generateCode(code + "1");
   right->generateCode(code + "0");
  }
 }
};

unsigned int amounts[256]; // Массив частоты встречаемости символов

int main() {
 setlocale(LC_ALL, "Rus");
 SetConsoleCP(1251); SetConsoleOutputCP(1251); //Эти функции - только в Studio

 string s("Кодировали-кодировали и выкодировали"); //Исходная строка

                                                   /* char в Studio - знаковые! */
 for (int i = 0; i < s.size(); i++) amounts[s[i]<0 ? s[i] + 256 : s[i]]++;

 priority_queue <Node, vector<Node>, Node> graphData;
 for (int i = 0; i < 256; i++) // Записываем в очередь с приоритетами 
  if (amounts[i] > 0) graphData.emplace(s = (char)i, amounts[i]);
 Node *n = Node::buildTree(graphData);
 n->generateCode("");
 
 //Данные для Google API и открытие ссылки
 string str = "http://chart.apis.google.com/chart?cht=gv&chl=\nDigraph G {\n" +
  n->toString() + "}";
 cout << str << endl; //Ссылка выводится в консоль

 /*
 std::replace(str.begin(),str.end(),'\n', ' '); //избавляемся от переводов строки
 //std::replace(str.begin(), str.end(), string("\""), string("\\"""));
 str = "cmd /c start \"link\" \"" + str + "\""; //пытаемся передать данные в браузер
 //не вышло из-за двойных кавычек
 system(str.c_str()); //Пытаемся вывести команду в браузер
 
 //ShellExecute (0, "open", str.c_str(), 0, 0, SW_SHOWNORMAL); Sleep(1000);
 //так тоже не работает
*/
 cin.sync(); cin.get(); return 0;
}

Однако если скопировать из окна консоли вывод программы (щёлкнуть на кнопку системного меню окна, выбрать подменю Изменить, пункт Пометить, при зажатой Shift клавишами со стрелками выделить весь прямоугольник с текстом в окне, нажать Enter, переключиться в браузер, нажать Ctrl+V в пустой адресной строке, скорее всего, сработает в любом браузере, кроме Internet Explorer), то проблема снимается и мы увидим картинку с деревом, для тестового примера она будет вот такой:

картинка, полученная с URL, формируемого второй программой

На этой картинке показан режим выделения в окне консоли, момент перед нажатием Enter для копирования кода диаграммы в буфер обмена.

момент перед нажатием Enter :)

Ещё одно узкое место программы, как ни странно, формирование массива частот встречаемости символов amounts. Дело в том, что тип char в Studio - знаковый, и коды букв из второй половины кодовой таблицы ASCII (имеющие числовые значения от 128 до 255) могут оказаться отрицательными значениями, а с явно указанным типом данных unsigned char в Studio не будет работать ряд стандартных функций, да хоть та же strcpy. В стандарте, вообще говоря, ясно не сказано, должен ли тип данных char быть знаковым или беззнаковым.

Оба приложения выполнялись в консоли Studio 2015.

26.10.2017, 16:01 [5250 просмотров]