@[TOC](文章目录)
香农编码
(1) 将信源消息符号按其出现的概率大小依次排列 p1 ≥ p2 ≥ ... ≥ pn (2) 确定满足下列不等式的整数码长Ki为 -log2(pi) ≤ Ki < -log2(pi) + 1 (3) 为了编成唯一可译码, 计算第
i个消息的累加概率 (4) 将累加概率Pi转换成二进制数。 (5) 取Pi二进数的小数点后Ki位即为该消息符号的二进制码字。
例如: 当
i=4时, 有-log2(0.17) ≤ K4 < -log2(0.17) + 1 即: 2.56 ≤ K4 < 3.56, 所以K4=3 则累加概率P4=0.57, 变换成二进制位0.1001… 由于K4=3, 所以第4个消息的香农码为100
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
struct Shannon_struct
{
string name; // 信源符号名称
double p; // 符号概率
double sum_p; // 累加概率
int result_length; // 码字长度
vector<int> result; // 香农码
};
/**
* 求解香农码
* 方法: 用计算累加概率sum_p的二进制数的方式, (注意: 0<=sum_p<1)
* 求出该二进制数的小数部分, 只取前n位, n代表码字长度 (注意: 忽略前面的0和小数点)
*/
void shannonCodeing(Shannon_struct* s)
{
int num = 0;
double temp = s->sum_p; // 用temp来暂存累加概率, 防止直接修改s->sum_p的值
for (int i = 0; i < s->result_length; i++)
{
temp = temp * 2; // 乘二取整
if (temp >= 1)
{
num = 1;
temp = temp - 1;
}
else
{
num = 0;
}
s->result.push_back(num);
}
}
/**
* 自定义结构体比较函数
* 按照符号概率p由大到小进行排序
*/
bool cmp(Shannon_struct a, Shannon_struct b)
{
return a.p > b.p;
}
int main()
{
int symbol_num = 0; // 符号的总数
cout << "请输入一共有多少个信源符号: ";
cin >> symbol_num;
Shannon_struct* s = new Shannon_struct[symbol_num];
cout << "请输入信源符号(字符型)和对应的概率: " << endl;
for (int i = 0; i < symbol_num; i++)
{
cin >> s[i].name >> s[i].p;
}
// 将信源符号按照其出现的概率p由大到小进行排序
sort(s, s + symbol_num, cmp);
for (int i = 0; i < symbol_num; i++)
{
if (i == 0)
{
s[i].sum_p = 0;
}
else
{
s[i].sum_p = s[i - 1].p + s[i - 1].sum_p;
}
//cout << -1 * log2(s[i].p) << endl;
s[i].result_length = (int)ceil(-1 * log2(s[i].p)); // log2表示以2为底的对数
shannonCodeing(&s[i]); // 求出对应的香农码
}
// 输出部分
cout << "\n\n信源符号 概率 累加概率 码字长度 香农码" << endl;
for (int i = 0; i < symbol_num; i++)
{
cout << " " << s[i].name << "\t " << s[i].p << "\t " << s[i].sum_p << " \t " << s[i].result_length << "\t";
for (int j = 0; j < s[i].result.size(); j++)
{
cout << s[i].result[j];
}
cout << endl;
}
delete[] s;
return 0;
}
/*
测试数据:
7
a7 0.01
a2 0.19
a4 0.17
a5 0.15
a1 0.20
a6 0.10
a3 0.18
输出结果:
信源符号 概率 累加概率 码字长度 香农码
a1 0.2 0 3 000
a2 0.19 0.2 3 001
a3 0.18 0.39 3 011
a4 0.17 0.57 3 100
a5 0.15 0.74 3 101
a6 0.1 0.89 4 1110
a7 0.01 0.99 7 1111110
*/<!--
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
struct Shannon_struct
{
string name; // 信源符号名称
double p; // 符号概率
double sum_p; // 累加概率
int result_length; // 码字长度
vector<int> result; // 香农码
};
/**
* 求解香农码
* 方法: 用计算累加概率sum_p的二进制数的方式, (注意: 0<=sum_p<1)
* 求出该二进制数的小数部分, 只取前n位, n代表码字长度 (注意: 忽略前面的0和小数点)
*/
void computeBinary(Shannon_struct* s)
{
int num = 0;
double temp = s->sum_p; // 用temp来暂存累加概率, 防止直接修改s->sum_p的值
for (int i = 0; i < s->result_length; i++)
{
temp = temp * 2; // 乘二取整
if (temp >= 1)
{
num = 1;
temp = temp - 1;
}
else
{
num = 0;
}
s->result.push_back(num);
}
}
/**
* 自定义结构体比较函数
* 按照符号概率p由大到小进行排序
*/
bool cmp(Shannon_struct a, Shannon_struct b)
{
return a.p > b.p;
}
int main()
{
int symbol_num = 0; // 符号的总数
cout << "请输入一共有多少个信源符号: ";
cin >> symbol_num;
Shannon_struct* s = new Shannon_struct[symbol_num];
cout << "请输入信源符号(字符型)和对应的概率: " << endl;
for (int i = 0; i < symbol_num; i++)
{
cin >> s[i].name >> s[i].p;
}
// 将信源符号按照其出现的概率p由大到小进行排序
sort(s, s + symbol_num, cmp);
for (int i = 0; i < symbol_num; i++)
{
if (i == 0)
{
s[i].sum_p = 0;
}
else
{
s[i].sum_p = s[i - 1].p + s[i - 1].sum_p;
}
//cout << -1 * log2(s[i].p) << endl;
s[i].result_length = (int)ceil(-1 * log2(s[i].p)); // log2表示以2为底的对数
computeBinary(&s[i]); // 求出对应的香农码
}
// 输出部分
cout << "\n\n信源符号 概率 累加概率 码字长度 香农码" << endl;
for (int i = 0; i < symbol_num; i++)
{
cout << " " << s[i].name << "\t " << s[i].p << "\t " << s[i].sum_p << " \t " << s[i].result_length << "\t";
for (int j = 0; j < s[i].result.size(); j++)
{
cout << s[i].result[j];
}
cout << endl;
}
delete[] s;
return 0;
}
/*
测试数据:
7
a7 0.01
a2 0.19
a4 0.17
a5 0.15
a1 0.20
a6 0.10
a3 0.18
输出结果:
信源符号 概率 累加概率 码字长度 香农码
a1 0.2 0 3 000
a2 0.19 0.2 3 001
a3 0.18 0.39 3 011
a4 0.17 0.57 3 100
a5 0.15 0.74 3 101
a6 0.1 0.89 4 1110
a7 0.01 0.99 7 1111110
*/-->
费诺编码
(1) 将信源消息符号按其出现的概率大小依次排列: p1 ≥ p2 ≥ ... ≥ pn
(2) 将依次排列的信源符号按概率值分为两大组, 使两个组的概率之和近于相同, 并对各组赋予一个二进制符号“0”和“1”。 (3) 将每一大组的信源符号进一步再分成两组, 使划分后的两个组的概率之和近似相同, 并对各组赋予一个二进制符号“0”和“1”。 (4) 如此重复, 直至每个组只剩下一个信源符号为止。 (5) 信源符号所对应的码字即为费诺码。
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
struct Fano_struct
{
string name; // 信源符号名称
double p; // 符号概率
int result_length; // 码字长度
vector<int> result; // 费诺编码
};
/**
* 计算结构体数组s在[start, end)之间的中点下标
* 返回值: 中点mid
*/
int calculate_mid(Fano_struct* s, int start, int end)
{
int i = start;
int j = end;
double part1 = s[start].p;
double part2 = s[end].p;
while (i < j - 1) // 当i与j相差2时, 停止循环, 注意不能是i<j, 因为这样循环结束后, i==j
{
if (part1 > part2)
{
j--;
part2 = part2 + s[j].p;
}
else
{
i++;
part1 = part1 + s[i].p;
}
//cout << part1 << " " << part2 << " " << i << " " << j << endl;
}
return j;
}
/**
* 分组赋值:
* 将依次排列的信源符号按概率分成两组, 使这两个组的概率之和近似相同, 分别赋予一个二进制码0和1,
* 持续分组并赋值, 直到每个组只剩下最后一个信源符号为止。
* start和end是待赋值的起点和终点下标
* mid是calculate_mid()计算得到的中点下标
* 将费诺码往后添加一个0或1
* 即: s[i].result.push_back(0或1)
*/
void groupAssign(Fano_struct* s, int start, int end)
{
if (end - start < 1)
{
return; // 递归终止条件, 当起点和终点相邻时, 此时不需要再分组了
}
int mid = calculate_mid(s, start, end); // 求中点的下标
for (int i = start; i < mid; i++)
{
s[i].result.push_back(0); // 向前一组的费诺码往后添加一个0
}
for (int i = mid; i <= end; i++)
{
s[i].result.push_back(1); // 向后一组的费诺码往后添加一个0
}
groupAssign(s, start, mid - 1);
groupAssign(s, mid, end);
}
/**
* 已知费诺码, 计算码长
*/
void calculate_length(Fano_struct* s, int symbol_num)
{
for (int i = 0; i < symbol_num; i++)
{
s[i].result_length = s[i].result.size();
}
}
/**
* 自定义结构体比较函数
* 按照符号概率p由大到小进行排序
*/
bool cmp(Fano_struct a, Fano_struct b)
{
return a.p > b.p;
}
int main()
{
int symbol_num = 0; // 符号的总数
cout << "请输入一共有多少个信源符号: ";
cin >> symbol_num;
Fano_struct* s = new Fano_struct[symbol_num];
cout << "请输入信源符号(字符型)和对应的概率: " << endl;
for (int i = 0; i < symbol_num; i++)
{
cin >> s[i].name >> s[i].p;
}
// 将信源符号按照其出现的概率p由大到小进行排序
sort(s, s + symbol_num, cmp);
// 计算费诺码
groupAssign(s, 0, symbol_num - 1);
// 计算每个信源符号的码长
calculate_length(s, symbol_num);
// 输出部分
cout << "\n信源符号 概率 码字长度 费诺编码" << endl;
for (int i = 0; i < symbol_num; i++)
{
cout << " " << s[i].name << "\t " << s[i].p << " \t " << s[i].result_length << "\t";
for (unsigned int j = 0; j < s[i].result.size(); j++)
{
cout << s[i].result[j];
}
cout << endl;
}
delete[] s;
return 0;
}
/*
测试数据:
7
a7 0.01
a2 0.19
a4 0.17
a5 0.15
a1 0.20
a6 0.10
a3 0.18
输出结果:
信源符号 概率 码字长度 费诺编码
a1 0.2 2 00
a2 0.19 3 010
a3 0.18 3 011
a4 0.17 2 10
a5 0.15 3 110
a6 0.1 4 1110
a7 0.01 4 1111
*/哈夫曼编码
<!--
参考链接: 懒猫老师-数据结构-(34)哈夫曼树 懒猫老师-数据结构-(35)哈夫曼编码 -->
- 注意: 哈夫曼编码方法得到的码并非唯一的 每次对信源缩减时, 赋予信源最后两个概率最小的符号, 用0和1都是可以的, 所以会得到不同的哈夫曼码, 但不会影响码字的长度。
- 另外, 在下面提供的这两个代码中, 可以把sort()函数删去(目的仅仅是为了输出时按照概率进行排序),则程序也是没有问题的, 因为在selectMin()函数每次就找到了数组中最小和次小的两个元素, 进而合并成一棵子树。
C++版
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
using namespace std;
struct HTNode
{
string name;
double p; // 概率❗
int lchild;
int rchild;
int parent;
};
/**
* 在huffTree数组中找到parent为-1的最小和次小的两个元素, 并将其下标存入s1和s2
*/
void selectMin(HTNode huffTree[], int k, int& s1, int& s2)
{
// 1.查找最小元素的下标s1
for (int i = 0; i < k; i++)
{
if (huffTree[i].parent == -1)
{
s1 = i;
break;
}
}
for (int i = 0; i < k; i++)
{
if (huffTree[i].parent == -1 && huffTree[s1].p > huffTree[i].p)
{
s1 = i;
}
}
// 2.查找次小元素的下标s2
for (int j = 0; j < k; j++)
{
if (huffTree[j].parent == -1 && j != s1)
{
s2 = j;
break;
}
}
for (int j = 0; j < k; j++)
{
if (huffTree[j].parent == -1 && huffTree[s2].p > huffTree[j].p && j != s1)
{
s2 = j;
}
}
}
/**
* 创建哈夫曼树
*/
void HuffmanTree(HTNode huffTree[], int n)
{
// 初始化所有元素的双亲、左右孩子都置为-1;
for (int i = 0; i < 2 * n - 1; i++)
{
huffTree[i].parent = -1;
huffTree[i].lchild = -1;
huffTree[i].rchild = -1;
}
// 构建哈夫曼树
for (int k = n; k < 2 * n - 1; k++)
{
int i1, i2;
selectMin(huffTree, k, i1, i2); // 找到parent为-1的最小和次小的两个元素, 并将其下标存入i1、i2
huffTree[k].p = huffTree[i1].p + huffTree[i2].p;
huffTree[i1].parent = k;
huffTree[i2].parent = k;
huffTree[k].lchild = i1;
huffTree[k].rchild = i2;
}
}
/**
* 打印哈夫曼数组
*/
void printHuffmanArray(HTNode huffTree[], int n)
{
cout << "\n打印构造好的哈夫曼数组的内容: " << endl;
cout << "weight parent lchild rchild " << endl;
cout << left; // 左对齐输出
for (int i = 0; i < 2 * n - 1; i++)
{
cout << setw(6) << huffTree[i].p << " ";
cout << setw(6) << huffTree[i].parent << " ";
cout << setw(6) << huffTree[i].lchild << " ";
cout << setw(6) << huffTree[i].rchild << endl;
}
}
/**
* 从叶子到根逆向求每个字符的哈夫曼编码
*/
void huffmanCoding(HTNode huffTree[], char* huffCode[], int n)
{
char* temp = new char[n]; // 储存临时产生的编码串
temp[n - 1] = '\0';
// 遍历输入的n个信源符号, 生成它们对应的哈夫曼编码
for (int i = 0; i < n; i++)
{
int start = n - 1; // 用来控制temp数组的下标, 先让start为数组末尾, 再从后往前移动
int pos = i;
int parent = huffTree[pos].parent;
while (parent != -1)
{
if (huffTree[parent].lchild == pos)
{
temp[--start] = '0'; // 左子树的编码为0
}
else
{
temp[--start] = '1'; // 右子树的编码为1
}
pos = parent;
parent = huffTree[parent].parent;
}
huffCode[i] = new char[n - start];
strcpy(huffCode[i], &temp[start]);
}
delete[] temp; // 释放工作空间
}
/**
* 自定义结构体比较函数
* 按照符号概率p由大到小进行排序
*/
bool cmp(HTNode a, HTNode b)
{
return a.p > b.p;
}
int main()
{
int num = 0; // 符号的总数
cout << "请输入一共有多少个信源符号: ";
cin >> num;
HTNode* huffTree = new HTNode[2 * num - 1];
cout << "请输入信源符号和对应的概率: " << endl;
for (int i = 0; i < num; i++)
{
cin >> huffTree[i].name >> huffTree[i].p;
}
// 将信源符号按照其出现的概率p由大到小进行排序
sort(huffTree, huffTree + num, cmp);
// 创建哈夫曼树
HuffmanTree(huffTree, num);
// 打印哈夫曼数组
printHuffmanArray(huffTree, num);
// 进行哈夫曼编码
cout << "\n输出哈夫曼编码: " << endl;
char** huffCode = new char* [num];
huffmanCoding(huffTree, huffCode, num);
cout << "信源符号 概率 哈夫曼编码 码字长度" << endl;
cout << left;
for (int i = 0; i < num; i++)
{
cout << " ";
cout << setw(7) << huffTree[i].name << " ";
cout << setw(7) << huffTree[i].p << " ";
cout << setw(7) << huffCode[i] << " ";
cout << setw(7) << strlen(huffCode[i]) << endl;
}
delete[] huffTree;
for (int i = 0; i < num; i++)
{
delete[] huffCode[i];
}
delete[] huffCode;
return 0;
}
/*
测试数据:
7
a7 0.01
a2 0.19
a4 0.17
a5 0.15
a1 0.20
a6 0.10
a3 0.18
*/
C语言版
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX_SIZE 100
struct HTNode
{
char name[MAX_SIZE];
double p; // 概率
int lchild;
int rchild;
int parent;
};
/**
* 在huffTree数组中找到parent为-1的最小和次小的两个元素, 并将其下标存入s1和s2
*/
void selectMin(HTNode huffTree[], int k, int* s1, int* s2)
{
// 1.查找最小元素的下标s1
for (int i = 0; i < k; i++)
{
if (huffTree[i].parent == -1)
{
*s1 = i;
break;
}
}
for (int i = 0; i < k; i++)
{
if (huffTree[i].parent == -1 && huffTree[*s1].p > huffTree[i].p)
{
*s1 = i;
}
}
// 2.查找次小元素的下标s2
for (int j = 0; j < k; j++)
{
if (huffTree[j].parent == -1 && j != *s1)
{
*s2 = j;
break;
}
}
for (int j = 0; j < k; j++)
{
if (huffTree[j].parent == -1 && huffTree[*s2].p > huffTree[j].p && j != *s1)
{
*s2 = j;
}
}
}
/**
* 创建哈夫曼树
*/
void HuffmanTree(HTNode huffTree[], int n)
{
// 初始化所有元素的双亲、左右孩子都置为-1;
for (int i = 0; i < 2 * n - 1; i++)
{
huffTree[i].parent = -1;
huffTree[i].lchild = -1;
huffTree[i].rchild = -1;
}
// 构建哈夫曼树
for (int k = n; k < 2 * n - 1; k++)
{
int i1, i2;
selectMin(huffTree, k, &i1, &i2); // 找到parent为-1的最小和次小的两个元素, 并将其下标存入i1、i2
huffTree[k].p = huffTree[i1].p + huffTree[i2].p;
huffTree[i1].parent = k;
huffTree[i2].parent = k;
huffTree[k].lchild = i1;
huffTree[k].rchild = i2;
}
}
/**
* 打印哈夫曼数组
*/
void printHuffmanArray(HTNode huffTree[], int n)
{
printf("\n打印构造好的哈夫曼数组的内容: \n");
printf("weight parent lchild rchild \n");
for (int i = 0; i < 2 * n - 1; i++)
{
printf("%6.2f ", huffTree[i].p);
printf("%6d ", huffTree[i].parent);
printf("%6d ", huffTree[i].lchild);
printf("%6d\n", huffTree[i].rchild);
}
}
/**
* 从叶子到根逆向求每个字符的哈夫曼编码
*/
void huffmanCoding(HTNode huffTree[], char* huffCode[], int n)
{
char temp[MAX_SIZE]; // 储存临时产生的编码串
temp[n - 1] = '\0';
// 遍历输入的n个信源符号, 生成它们对应的哈夫曼编码
for (int i = 0; i < n; i++)
{
int start = n - 1; // 用来控制temp数组的下标, 先让start为数组末尾, 再从后往前移动
int pos = i;
int parent = huffTree[pos].parent;
while (parent != -1)
{
if (huffTree[parent].lchild == pos)
{
temp[--start] = '0';
}
else
{
temp[--start] = '1';
}
pos = parent;
parent = huffTree[parent].parent;
}
// huffCode[i] = new char[n - start];
huffCode[i] = (char*)malloc((n - start) * sizeof(char));
strcpy(huffCode[i], &temp[start]);
}
}
/**
* 将信源符号按照其出现的概率p由大到小进行排序
*/
void sort(HTNode huffTree[], int symbol_num)
{
for (int i = 0; i < symbol_num; i++)
{
for (int j = 0; j < symbol_num - i - 1; j++)
{
if (huffTree[j].p < huffTree[j + 1].p)
{
// 交换两个结构体的顺序:
// char name[MAX_SIZE];
// double p;
// int lchild; (因为后面的这些还没有输入, 所以可以不交换)
// int rchild;
// int parent;
char tempName[MAX_SIZE];
strcpy(tempName, huffTree[j].name);
strcpy(huffTree[j].name, huffTree[j + 1].name);
strcpy(huffTree[j + 1].name, tempName);
double tempP = huffTree[j].p;
huffTree[j].p = huffTree[j + 1].p;
huffTree[j + 1].p = tempP;
}
}
}
}
int main()
{
int num = 0; // 符号的总数
printf("请输入一共有多少个信源符号: ");
scanf("%d", &num);
HTNode huffTree[MAX_SIZE * 2 - 1];
printf("请输入信源符号和对应的概率: ");
for (int i = 0; i < num; i++)
{
getchar();
scanf("%s %lf", &huffTree[i].name, &huffTree[i].p);
}
// 将信源符号按照其出现的概率p由大到小进行排序
sort(huffTree, num);
// 创建哈夫曼树
HuffmanTree(huffTree, num);
// 打印哈夫曼数组
printHuffmanArray(huffTree, num);
// 进行哈夫曼编码
printf("\n输出哈夫曼编码: \n");
char* huffCode[MAX_SIZE];
huffmanCoding(huffTree, huffCode, num);
printf("信源符号 概率 码字长度 哈夫曼编码\n");
for (int i = 0; i < num; i++)
{
printf(" ");
printf("%s ", huffTree[i].name);
printf("%7.2f ", huffTree[i].p);
printf(" %d ", strlen(huffCode[i]));
printf(" %s\n", huffCode[i]);
}
return 0;
}
/*
测试数据:
7
a7 0.01
a2 0.19
a4 0.17
a5 0.15
a1 0.20
a6 0.10
a3 0.18
*/游程编码
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main()
{
vector<int> vt, result;
string str;
cout << "请输入一个二元序列 (只含有0或1)" << endl;
getline(cin, str);
for (int i = 0; i < str.length(); i++)
{
if (str[i] == '0' || str[i] == '1') // 如果不是0或1, 则跳过
{
int num = str[i] - '0';
vt.push_back(num);
}
}
// 将二元序列转换成为游程序列result中
int value = vt[0];
int num = 1;
vt.push_back(-1); // 加上这个, 可以方便的处理最后一个数字...
for (int i = 1; i < vt.size(); i++)
{
if (vt[i] == value)
{
num++;
}
else
{
result.push_back(num);
num = 1;
value = vt[i];
}
}
// 输出得到的游程序列
cout << "\n得到的游程序列的结果是: " << endl;
for (int i = 0; i < result.size(); i++)
{
if (result[i] > 0 && result[i] < 10)
{
cout << result[i];
}
else
{
cout << " " << result[i] << " "; // 当游程编码超过9后, 输出加上空格
}
}
return 0;
}
/*
测试数据1:
000101110010001
输出:
31132131
测试数据2 (如果游程编码的值>=10, 旁边加个空格):
1010100110100011111100000000001
输出:
11111221136 10 1
测试数据3 (排除0和1以外的数字):
1010100qdv110100dvcd01111110c000000022001
输出:
11111221136 10 1
*/算术编码
例:
#include <iostream>
#include <string>
#include <algorithm>
#include <sstream>
using namespace std;
struct symbol_struct
{
char name; // 信源符号名称
double p; // 符号概率
double sum_p; // 累加概率
};
/**
* 十进制小数转二进制小数:
*/
double doubleToBinary(double num)
{
string str = "0.";
while (num != 1 && str.size() < 18) // 保留16位小数
{
num = num * 2;
if (num >= 1)
{
num = num - 1;
str.push_back('1');
}
else
{
str.push_back('0');
}
}
// str储存了该二进制数, 用atof函数将其转换成double类型并返回
return atof(str.c_str());
}
/**
* 在symbol_struct中, 寻找字符ch, 并返回其下标
*/
int findPos(symbol_struct* s, int symbol_num, char ch)
{
for (int i = 0; i < symbol_num; i++)
{
if (s[i].name == ch)
{
return i;
}
}
exit(-1); // 查找失败, 直接退出
}
/**
* 算术编码
*/
stringstream arithmetic_coding(symbol_struct* s, string input_str, int symbol_num)
{
double start = 0; // 起始值
double length = 1; // 序列长度
for (int i = 0; i < input_str.length(); i++) // 对于待编码的符号,
{
int pos = findPos(s, symbol_num, input_str[i]); // 找到该符号在s数组中的下标 (目的: 得到元素概率和累加概率)
start = start + length * s[pos].sum_p; // 起始 + 序列长度 * 该元素的累加概率❗
length = length * s[pos].p; // 原序列长度 * 该元素概率❗
printf("\n第%d个元素: 起始 = %.16lf --- 序列长度 = %.16lf", i + 1, start, length);
}
// 循环结束后, 二进制形式的start的的纯小数部分就是所求的算术编码
stringstream str;
str.precision(16);
str << doubleToBinary(start); // double --> stringstream
return str;
}
/**
* 自定义结构体比较函数
* 按照符号概率p由大到小进行排序
*/
bool cmp(symbol_struct a, symbol_struct b)
{
return a.p > b.p;
}
int main()
{
int symbol_num = 0; // 符号的总数
cout << "请输入一共有多少个信源符号: ";
cin >> symbol_num;
symbol_struct* s = new symbol_struct[symbol_num];
cout << "请输入信源符号(字符型)和对应的概率: " << endl;
for (int i = 0; i < symbol_num; i++)
{
cin >> s[i].name >> s[i].p;
}
string input_str;
cout << "请输入由这些符号构成的序列: " << endl;
getchar();
getline(cin, input_str);
// 将信源符号按照其出现的概率p由大到小进行排序
sort(s, s + symbol_num, cmp);
// 计算累加概率
for (int i = 0; i < symbol_num; i++)
{
if (i == 0)
{
s[i].sum_p = 0;
}
else
{
s[i].sum_p = s[i - 1].p + s[i - 1].sum_p;
}
}
stringstream result = arithmetic_coding(s, input_str, symbol_num);
// 输出部分
cout << "\n\n信源符号 概率 累加概率" << endl;
for (int i = 0; i < symbol_num; i++)
{
cout << " " << s[i].name << "\t " << s[i].p << "\t " << s[i].sum_p << endl;
}
cout << "\n该序列的算术编码的结果为: \n";
cout << &result.str()[2] << "\n\n" << endl;
delete[] s;
return 0;
}
/*
测试数据:
4
a 0.5
b 0.25
c 0.125
d 0.125
abda
*/
<!--
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
struct symbol_struct
{
char name; // 信源符号名称
double p; // 符号概率
double sum_p; // 累加概率
};
/**
* 在symbol_struct中, 寻找字符ch, 并返回其下标
*/
int findPos(symbol_struct* s, int symbol_num, char ch)
{
for (int i = 0; i < symbol_num; i++)
{
if (s[i].name == ch)
{
return i;
}
}
exit(-1); // 查找失败, 直接退出
}
/**
* 算术编码
*/
void arithmetic_coding(symbol_struct* s, char* input_str, vector<int>& result, int symbol_num)
{
double C = 0;
double A = 1;
for (int i = 0; i < symbol_num; i++)
{
int pos = findPos(s, symbol_num, input_str[i]);
C = C + A * s[pos].sum_p;
A = A * s[pos].p;
cout << "pos " << pos << " ~~~~~~ ";
printf("C = %.10lf ^^^^ A = %.10lf\n", C, A);
}
// C的纯小数部分就是所求的算术编码
char str[100];
sprintf_s(str, "%f", C); // 将C以%f的形式写入到字符串input_str中
// 删除前导的0和小数点即可
for (int i = 2; str[i] != '\0'; i++)
{
result.push_back(str[i] - '0');
}
}
/**
* 自定义结构体比较函数
* 按照符号概率p由大到小进行排序
*/
bool cmp(symbol_struct a, symbol_struct b)
{
return a.p > b.p;
}
int main()
{
int symbol_num = 0; // 符号的总数
cout << "请输入一共有多少个信源符号: ";
cin >> symbol_num;
symbol_struct* s = new symbol_struct[symbol_num];
cout << "请输入信源符号(字符型)和对应的概率: " << endl;
for (int i = 0; i < symbol_num; i++)
{
cin >> s[i].name >> s[i].p;
}
char* input_str = new char[symbol_num];
cout << "请输入由几个符号构成的序列: " << endl;
for (int i = 0; i < symbol_num; i++)
{
cin >> input_str[i];
}
// 将信源符号按照其出现的概率p由大到小进行排序
sort(s, s + symbol_num, cmp);
// 计算累加概率
for (int i = 0; i < symbol_num; i++)
{
if (i == 0)
{
s[i].sum_p = 0;
}
else
{
s[i].sum_p = s[i - 1].p + s[i - 1].sum_p;
}
}
vector<int> result; // 用result来储存算术编码的结果
arithmetic_coding(s, input_str, result, symbol_num);
// 输出部分
cout << "\n信源符号 概率 累加概率" << endl;
for (int i = 0; i < symbol_num; i++)
{
cout << " " << s[i].name << "\t " << s[i].p << "\t " << s[i].sum_p << endl;
}
cout << "\n该序列的算术编码的结果为: \n";
for (unsigned int i = 0; i < result.size(); i++)
{
cout << result[i];
}
cout << endl;
delete[] s;
delete[] input_str;
return 0;
}
/*
测试数据:
4
a 0.1
b 0.01
c 0.001
d 0.001
a b d a
---------------------------------------------------------------
请输入一共有多少个信源符号: 4
请输入信源符号(字符型)和对应的概率:
a 0.1
b 0.01
c 0.001
d 0.001
请输入由几个符号构成的序列:
a b d a
pos 0 ~~~~~~ C = 0.0000000000 ^^^^ A = 0.1000000000
pos 1 ~~~~~~ C = 0.0100000000 ^^^^ A = 0.0010000000
pos 3 ~~~~~~ C = 0.0101110000 ^^^^ A = 0.0000010000
pos 0 ~~~~~~ C = 0.0101110000 ^^^^ A = 0.0000001000
信源符号 概率 累加概率
a 0.1 0
b 0.01 0.1
c 0.001 0.11
d 0.001 0.111
该序列的算术编码的结果为:
010111
*/-->
标签：parent,编码,num,struct,哈夫曼,int,huffTree,symbol,费诺 From： https://blog.51cto.com/u_16057418/6362560