Сравнение кодирования методом Фано-Шеннона и Хаффмана. с++

Задание на курсовую работу: Статическое кодирование и декодирование текстового файла методами Хаффмана и Фано-Шеннона – демонстрация и исследование. ...

1. Постановка задачи 2
2. Теоретический материал 2
3. Формальная постановка задачи 6
4. Разработка структур данных и алгоритмов 6
5. Спецификация программы 8
6. Тестовые данные 9
7. Анализ результатов и выводы 10
Приложение А. Программа исследования. Листинг 11
Приложение Б. Программа визуализации. Листинг. 22

Алгоритм Шеннона — Фано — один из первых алгоритмов сжатия, который впервые сформулировали американские учёные Шеннон и Роберт Фано. Алгоритм использует коды переменной длины: часто встречающийся символ кодируется кодом меньшей длины, редко встречающийся — кодом большей длины. Коды Шеннона — Фано префиксные, то есть никакое кодовое слово не является префиксом любого другого. Это свойство позволяет однозначно декодировать любую последовательность кодовых слов........

ВыводВ ходе выполнения данной курсовой работы была изучена теория по основным понятиям и приёмам кодирования информации алгоритмами Хаффмана и Фано-Шеннона, а также написана программа, выполняющая требуемые действия по кодированию информации. Были закреплены навыки работы с классами, со структурами данных: бинарное дерево, очередь с приоритетами, которые были реализованы на языке С++. Было проведено исследование по анализу времени работы алгоритмов кодирования методами Хаффмана и Фано-Шеннона. В результате чего было показано, что на заданных тестах алгоритм Хаффмана хоть и не значительно, но быстрее выполнял кодирование\декодирование файлов и эффективнее сжимал заданный файл. С помощью библиотек QT была написана программа, реализующая визуализацию методов кодирования Хаффмана и Фано-Шеннона.Приложение А. Программа исследования. ЛистингCodeTree.h#pragma once#include <iostream>#define MAX_INPUT_LEN 10000000#define MAX_CODE_LEN 1000000000struct Symbol{char c; long long int weight;};bool symbol_less(const Symbol& l, const Symbol& r);bool symbol_greater(const Symbol& l, const Symbol& r);struct CodeTree{Symbol s;CodeTree* parent;CodeTree* left;CodeTree* right;};CodeTree* make_leaf(const Symbol& s);CodeTree* make_node(long long int weight, CodeTree* left, CodeTree* right);bool is_null(const CodeTree* node);bool is_leaf(const CodeTree* node);bool is_root(const CodeTree* node);char* encode(const CodeTree* tree, const char* message);char* decode(const CodeTree* tree, const char* code);void destroy(CodeTree* tree);void print_tree(CodeTree* tree, long long int level, std::ostream& out);fh.h#pragma once#include "CodeTree.h"CodeTree* fanno_shannon(const char* message);CodeTree* fanno_shannon(const Symbol* symbols, long long int len);Huffman.h#pragma once#include "CodeTree.h"CodeTree* huffman(char* message);CodeTree* huffman(const char* keys, const int* w, int len);p_queue.h#include <utility>template <typename T>struct PriorityQueueItem { int key; T data;};template <typename T>struct PriorityQueue { int size_; int capacity_; PriorityQueueItem<T>* heap_;};template <typename T>PriorityQueue<T>* create_pq(int capacity){ PriorityQueue<T>* pq = new PriorityQueue<T>; pq->heap_ = new PriorityQueueItem<T>[capacity]; pq->capacity_ = capacity; pq->size_ = 0; return pq;}template <typename T>int size(PriorityQueue<T>* pq){ return pq->size_;}template <typename T>void sift_up(PriorityQueue<T>* pq, int index){ int parent = (index - 1) / 2; while(parent >= 0 && pq->heap_[index].key < pq->heap_[parent].key) { std::swap(pq->heap_[index], pq->heap_[parent]); index = parent; parent = (index - 1) / 2; }}template <typename T>bool push(PriorityQueue<T>* pq, int key, const T& data){ if(pq->size_ >= pq->capacity_) return false; pq->heap_[pq->size_].key = key; pq->heap_[pq->size_].data = data; pq->size_++; sift_up(pq, pq->size_ - 1); return true;}template <typename T>void sift_down(PriorityQueue<T>* pq, int index){ int l = 2 * index + 1; int r = 2 * index + 2; int min = index; if(l < pq->size_ && pq->heap_[l].key < pq->heap_[min].key) min = l; if(r < pq->size_ && pq->heap_[r].key < pq->heap_[min].key) min = r; if(min != index) { std::swap(pq->heap_[index], pq->heap_[min]); sift_down(pq, min); }}template <typename T>T pop(PriorityQueue<T>* pq){ std::swap(pq->heap_[0], pq->heap_[pq->size_ - 1]); pq->size_--; sift_down(pq, 0); return pq->heap_[pq->size_].data;}template <typename T>void destroy_pq(PriorityQueue<T>* pq){ delete [] pq->heap_; delete pq;}CodeTree.cpp#include "CodeTree.h"#include <climits>#include <cstring>#include <stdio.h>#include <stdlib.h>#include <malloc.h>bool symbol_less(const Symbol& l, const Symbol& r){return l.weight < r.weight;}bool symbol_greater(const Symbol& l, const Symbol& r){return l.weight > r.weight;}CodeTree* make_leaf(const Symbol& s){return new CodeTree{ s, nullptr, nullptr, nullptr };}CodeTree* make_node(long long int weight, CodeTree* left, CodeTree* right){Symbol s{ 0, weight };return new CodeTree{ s, nullptr, left, right };}bool is_leaf(const CodeTree* node){return ((node->left == nullptr) && (node->right == nullptr));}bool is_null(const CodeTree* node){return (node == nullptr);}bool is_root(const CodeTree* node){return node->parent == nullptr;}static void fill_symbols_map(const CodeTree* node, const CodeTree** symbols_map);char* encode(const CodeTree* tree, const char* message){char* code = new char[MAX_CODE_LEN]; long long int len = strlen(message);const CodeTree** symbols_map = new const CodeTree*[UCHAR_MAX]; for (long long int i = 0; i < UCHAR_MAX; ++i){symbols_map[i] = nullptr;}fill_symbols_map(tree, symbols_map); long long int index = 0;char path[UCHAR_MAX]; for (long long int i = 0; i < len; ++i){const CodeTree* node = symbols_map[message[i] - CHAR_MIN]; long long int j = 0;while (!is_root(node)){if (node->parent->left == node)path[j++] = '0';elsepath[j++] = '1';node = node->parent;}while (j > 0) code[index++] = path[--j];}if (index != 0)code[index] = 0;else{ for (long long int i = 0; i < strlen(message); i++)code[i] = '0';code[strlen(message)] = 0;}delete[] symbols_map;return code;}char* decode(const CodeTree* tree, const char* code){ char* message = new char[MAX_INPUT_LEN]; long long int index = 0; long long int len = strlen(code);const CodeTree* v = tree;if (is_leaf(v)){ for (long long int i = 0; i < len; ++i){message[index++] = v->s.c;v = tree;}}else for (long long int i = 0; i < len; ++i){if (code[i] == '0')v = v->left;elsev = v->right;if (is_leaf(v)){message[index++] = v->s.c;v = tree;}}message[index] = 0;return message;}void destroy(CodeTree* tree){if (tree == nullptr) return;destroy(tree->left);destroy(tree->right);delete tree;tree = nullptr;}void fill_symbols_map(const CodeTree* node, const CodeTree** symbols_map){if (is_leaf(node))symbols_map[node->s.c - CHAR_MIN] = node;else {fill_symbols_map(node->left, symbols_map);fill_symbols_map(node->right, symbols_map);}}void print_tree(CodeTree* tree, long long int level, std::ostream& out){if (tree){print_tree(tree->left, level + 1, out); for (long long int i = 0; i < level; i++) out << " ";out << tree->s.weight << std::endl;print_tree(tree->right, level + 1, out);}}fh.cpp#include "fh.h"#include <algorithm>#include <climits>#include <cstring>static long long int middle(const Symbol* symbols, long long int l, long long int sum, long long int& lsum,long long int& rsum);CodeTree* fanno_shannon(const Symbol* symbols,long long int l,long long int r,long long int sum){if (l >= r) return nullptr;if (r - l == 1) return make_leaf(symbols[l]); long long int lsum, rsum; long long int m = middle(symbols, l, sum, lsum, rsum);CodeTree* ltree = fanno_shannon(symbols, l, m + 1, lsum);CodeTree* rtree = fanno_shannon(symbols, m + 1, r, rsum);CodeTree* node = make_node(sum, ltree, rtree);ltree->parent = node;rtree->parent = node;return node;}CodeTree* fanno_shannon(const Symbol* symbols, long long int len){ long long int sum = 0; for (long long int i = 0; i < len; ++i)sum += symbols[i].weight;return fanno_shannon(symbols, 0, len, sum);}CodeTree* fanno_shannon(const char* message){Symbol symbols[UCHAR_MAX]; for (long long int i = 0; i < UCHAR_MAX; ++i) {symbols[i].c = i + CHAR_MIN;symbols[i].weight = 0;}int size = strlen(message); for (long long int i = 0; i < size; ++i)symbols[message[i] - CHAR_MIN].weight++;std::sort(symbols, symbols + UCHAR_MAX, symbol_greater); long long int len = 0;while (symbols[len].weight > 0 && len < UCHAR_MAX) len++;return fanno_shannon(symbols, len);}long long int middle(const Symbol* symbols, long long int l, long long int sum, long long int& lsum, long long int& rsum){ long long int m = l;lsum = symbols[m].weight;rsum = sum - lsum; long long int delta = lsum - rsum;while (delta + symbols[m + 1].weight < 0) {m++;lsum += symbols[m].weight;rsum -= symbols[m].weight;delta = lsum - rsum;}return m;}Huffman.cpp#include "huffman.h"#include "p_queue.h"#include <functional>#include <algorithm>#include <climits>#include <cstring>#include <iostream>CodeTree* huffman(const Symbol* symbols, int len){ PriorityQueue<CodeTree*>* queue = create_pq<CodeTree*>(len); for(int i = 0; i < len; ++i) push(queue, symbols[i].weight, make_leaf(symbols[i])); while(size(queue) > 1) { CodeTree* ltree = pop(queue); CodeTree* rtree = pop(queue); int weight = ltree->s.weight + rtree->s.weight; CodeTree* node = make_node(weight, ltree, rtree); ltree->parent = node; rtree->parent = node; push(queue, weight, node); } CodeTree* result = pop(queue); destroy_pq(queue); return result;}CodeTree* huffman(char* message) { Symbol symbols[UCHAR_MAX]; for(int i = 0; i < UCHAR_MAX; ++i) { symbols[i].c = i + CHAR_MIN; symbols[i].weight = 0; } long long int size = strlen(message); for(int i = 0; i < size; ++i) symbols[message[i] - CHAR_MIN].weight++; std::sort(symbols, symbols + UCHAR_MAX, symbol_greater); int len = 0; while(symbols[len].weight > 0 && len < UCHAR_MAX) len++; return huffman(symbols, len);}main.cpp#include "fh.h"#include "huffman.h"#include <fstream>#include <chrono>#include<iterator>using namespace std;using namespace std::chrono;int main(){ CodeTree* ct_shf;// = nullptr; CodeTree* ct_huff; char *c; std::ifstream fin("input.dat"); std::ofstream fout_encode_huffman("huffman.dat"); std::ofstream fout_encode_shannon_fano("shf.dat"); std::ofstream fout_decode_huffman("huffman_decode.dat"); std::ofstream fout_decode_shannon_fano("shf_decode.dat"); c = new char[MAX_INPUT_LEN]; char *_encode_shf, *_decode_shf; char *_encode_huff, *_decode_huff; long long int i = 1; c[0] = fin.get(); while(fin.peek()!=EOF) {c[i] = fin.get(); i++; } ct_shf = fanno_shannon(c); ct_huff = huffman(c); auto begin_enc_shf = std::chrono::high_resolution_clock::now(); _encode_shf = encode(ct_shf, c); auto end_enc_shf = std::chrono::high_resolution_clock::now(); auto begin_dec_shf = std::chrono::high_resolution_clock::now(); _decode_shf = decode(ct_shf, _encode_shf); auto end_dec_shf = std::chrono::high_resolution_clock::now(); auto begin_enc_huff = std::chrono::high_resolution_clock::now(); _encode_huff = encode(ct_huff, c); auto end_enc_huff = std::chrono::high_resolution_clock::now(); auto begin_dec_huff = std::chrono::high_resolution_clock::now(); _decode_huff = decode(ct_huff, _encode_huff); auto end_dec_huff = std::chrono::high_resolution_clock::now(); std::cout << "Algorithm speed (in nanoseconds):" << std::endl; std::cout << "Encoding sh_f: " << std::chrono::duration_cast<std::chrono::nanoseconds>(end_enc_shf - begin_enc_shf).count() << std::endl; std::cout << "Decoding sh_f: " << std::chrono::duration_cast<std::chrono::nanoseconds>(end_dec_shf - begin_dec_shf).count() << std::endl; std::cout << "Encoding huff: " << std::chrono::duration_cast<std::chrono::nanoseconds>(end_enc_huff - begin_enc_huff).count() << std::endl; std::cout << "Decoding huff: " << std::chrono::duration_cast<std::chrono::nanoseconds>(end_dec_huff - begin_dec_huff).count() << std::endl; //std::cout << "Tree:\n"; //print_tree(ct_shf, 0, std::cout); fout_encode_shannon_fano << _encode_shf << std::endl; fout_decode_shannon_fano << _decode_shf << std::endl; fout_encode_huffman << _encode_huff << std::endl; fout_decode_huffman << _decode_huff << std::endl; destroy(ct_shf); destroy(ct_huff); delete[] c; fout_encode_huffman.close(); fout_encode_shannon_fano.close(); fout_decode_huffman.close(); fout_decode_shannon_fano.close(); fin.close(); return 0;}Приложение Б. Программа визуализации. Листинг.binarytree.cpp#include "binarytree.h"BinaryTree::BinaryTree(char symbol, long long int weight, BinaryTree* left, BinaryTree* right){ this->symbol = symbol; this->weight = weight; this->left = left; this->right = right;}BinaryTree::~BinaryTree(){ if(left != NULL) delete left; if(right != NULL) delete right;}binarytree.h#pragma once// Описание структуры Бинарное дерево#include <iostream>#include <vector>#include <climits>#include <cstring>#include <algorithm>#include <functional>#include <cstdlib>#include <cmath>#include <QMainWindow>#include <QWidget>#include <QLineEdit>#include <QPushButton>#include <QLabel>#include <QTextStream>struct BinaryTree{ char symbol; long long int weight; BinaryTree* left = NULL; BinaryTree* right = NULL; BinaryTree(char symbol, long long int weight, BinaryTree* left, BinaryTree* right); ~BinaryTree();};codetree.cpp#include "codetree.h"bool symbol_less(const Symbol& l, const Symbol& r){ return l.weight < r.weight;}bool symbol_greater(const Symbol& l, const Symbol& r){ return l.weight > r.weight;}CodeTree* make_leaf(const Symbol& s){ return new CodeTree{ "-",s, NULL, NULL, NULL };}CodeTree* make_node(int weight, CodeTree* left, CodeTree* right){ Symbol s{ '-', weight }; return new CodeTree{ "-", s,NULL, left, right };}bool is_leaf(const CodeTree* node){ return node->left == NULL && node->right == NULL;}bool is_root(const CodeTree* node){ return node->parent == NULL;}static void fill_symbols_map(const CodeTree* node, const CodeTree** symbols_map);char* encode( CodeTree* tree, char* message){ char* code = new char[MAX_CODE_LEN]; const CodeTree** symbols_map = new const CodeTree*[UCHAR_MAX]; for(int i = 0; i < UCHAR_MAX; ++i) { symbols_map[i] = NULL; } fill_symbols_map(tree, symbols_map); int len = strlen(message); int index = 0; char path[MAX_CODE_LEN]; for(int i = 0; i < len; ++i) { const CodeTree* node = symbols_map[message[i] - CHAR_MIN]; int j = 0; while(!is_root(node)) { if(node->parent->left == node) path[j++] = '0'; else path[j++] = '1'; node = node->parent; } while(j > 0) code[index++] = path[--j]; } if (index != 0) code[index] = 0; else { for (unsigned i = 0; i < strlen(message); i++) code[i] = '0'; code[strlen(message)] = 0; } delete [] symbols_map; return code;}char* decode(const CodeTree* tree, char* code){ char* message = new char[MAX_CODE_LEN]; int index = 0; int len = strlen(code); const CodeTree* v = tree; if (is_leaf(v)) { for (int i = 0; i < len; ++i) { message[index++] = v->s.c; v = tree; } } else for (int i = 0; i < len; ++i) { if (code[i] == '0') v = v->left; else v = v->right; if (is_leaf(v)) { message[index++] = v->s.c; v = tree; } } message[index] = 0; return message;}void destroy(CodeTree* tree){ if(tree == NULL) return; destroy(tree->left); destroy(tree->right); delete tree; tree = NULL;}void fill_symbols_map(const CodeTree* node, const CodeTree** symbols_map){ if(is_leaf(node)) symbols_map[node->s.c - CHAR_MIN] = node; else { fill_symbols_map(node->left, symbols_map); fill_symbols_map(node->right, symbols_map); }}Trees::Trees(CodeTree *tree,int weight, char symbol){ this->tree = tree; this->weight = weight; this->symbol = symbol; this->root = makeBinaryTree(tree);}Trees::~Trees(){ if(root != NULL)delete root;}BinaryTree* Trees::makeBinaryTree(CodeTree* root){ if(root == NULL) return NULL; return new BinaryTree(root->s.c, root->s.weight, makeBinaryTree(root->left), makeBinaryTree(root->right));}codetree.h#pragma once// Структуры: символ, Кодовое дерево, Trees - для создания бинарного дерева#include "binarytree.h"#define MAX_CODE_LEN 1000000struct Symbol{ char c; int weight;};bool symbol_less(const Symbol& l, const Symbol& r);bool symbol_greater(const Symbol& l, const Symbol& r);struct CodeTree{ char *str; Symbol s; CodeTree* parent; CodeTree* left; CodeTree* right;};CodeTree* make_leaf(const Symbol& s);CodeTree* make_node(int weight, CodeTree* left, CodeTree* right);bool is_leaf(const CodeTree* node);bool is_root(const CodeTree* node);char* encode(CodeTree* tree, char* message);char* decode(const CodeTree* tree, char* code);void destroy(CodeTree* tree);struct Trees{ BinaryTree* root = NULL; CodeTree *tree; int weight; char symbol; Trees(CodeTree *tree, int weight, char symbol); ~Trees(); BinaryTree* makeBinaryTree(CodeTree* root);};fh.cpp#include "fh.h"static long long int middle(const Symbol* symbols, long long int l, long long int sum, long long int& lsum, long long int& rsum);CodeTree* fanno_shannon(std::vector<Trees*> &trees, const Symbol* symbols, long long int l, long long int r, long long int sum){ if (l >= r) return nullptr; if (r - l == 1) return make_leaf(symbols[l]); long long int lsum, rsum; long long int m = middle(symbols, l, sum, lsum, rsum); CodeTree* ltree = fanno_shannon(trees, symbols, l, m + 1, lsum); CodeTree* rtree = fanno_shannon(trees, symbols, m + 1, r, rsum); CodeTree* node = make_node(sum, ltree, rtree); trees.push_back(new Trees(node, node->s.weight, node->s.c)); ltree->parent = node; rtree->parent = node; return node;}CodeTree *fanno_shannon(std::vector<Trees*> &trees, const Symbol* symbols, long long int len){ long long int sum = 0; for (long long int i = 0; i < len; ++i) sum += symbols[i].weight; return fanno_shannon(trees, symbols, 0, len, sum);}CodeTree* fanno_shannon(std::vector<Trees*> &trees, char* message){ if (*message == '\0') return 0; trees.