Кодування методом Шенона-Фано
Автор: viktor09823 • Май 28, 2021 • Доклад • 3,783 Слов (16 Страниц) • 252 Просмотры
Написати с++ программу “Кодування методом Шенона-Фано”
Вхідні данні:
Випадкова строка випадкової довжини
Вихідні данні
Строка бітів закодованого тексту
Виконання
#include <iostream>
#include <fstream>
#include <map>
#include <bitset>
#include <stdlib.h>
#include <string>
using namespace std;
string inStr;
string out;
class algFano
{
private:
struct node
{
char ch;
float p;
};
int tsize;
node* ptable;
map<char, string> bits;
static int compare_probs(const void* elem1, const void* elem2)
{
const node a = *(node*)elem1;
const node b = *(node*)elem2;
if (a.p < b.p)
return 1;
else if (a.p > b.p)
return -1;
return 0;
}
void encodeRecursize(int start, int end)
{
if (start == end)
{
return;
}
else if (end - start == 1)
{
bits[ptable[start].ch] += '0';
bits[ptable[end].ch] += '1';
}
else
{
float p = 0, splitIndex = -1, total = 0;
for (int i = start; i <= end; ++i)
{
total += ptable[i].p;
}
total /= 2;
for (int i = start; i <= end; ++i)
{
p += ptable[i].p;
if (p <= total)
{
bits[ptable[i].ch] += '0';
}
else
{
bits[ptable[i].ch] += '1';
if (splitIndex < 0)
splitIndex = i;
}
}
if (splitIndex < 0)
splitIndex = start + 1;
encodeRecursize(start, splitIndex - 1);
encodeRecursize(splitIndex, end);
}
}
public:
void Encode(string inStr)
{
char ch;
...