文章目录 香农编码 费诺编码 哈夫曼编码 C++版 C语言版 游程编码 算术编码 香农编码 (1) 将信源消息符号按其出现的概率大小依次排列 p 1 ≥ p 2 ≥ … ≥ p n (2) 确定满足下列不等式的整数码长K i 为 -log 2 (p i ) ≤ K i
< -log2 (p i ) + 1 (3) 为了编成唯一可译码, 计算第
i
个消息的累加概率 (4) 将累加概率P i 转换成二进制数。
(5) 取Pi二进数的小数点后Ki位即为该消息符号的二进制码字。
例如: 当
i=4
时, 有-log 2 (0.17) ≤ K 4
< -log2 (0.17) + 1 即: 2.56 ≤ K 4
< 3.56, 所以K4 =3 则 累加概率P4=0.57, 变换成二进制位0.1001… 由于K4=3, 所以第4个消息的香农码为100
#include
#include
#include
#include
using namespace std;
struct Shannon_struct
{
string name; // 信源符号名称
double p; // 符号概率
double sum_p; // 累加概率
int result_length; // 码字长度
vector 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
*/
费诺编码 (1) 将信源消息符号按其出现的概率大小依次排列: p 1 ≥ p 2 ≥ … ≥ p n (2) 将依次排列的信源符号按概率值分为两大组, 使两个组的概率之和近于相同, 并对各组赋予一个二进制符号“0”和“1”。
(3) 将每一大组的信源符号进一步再分成两组, 使划分后的两个组的概率之和近似相同, 并对各组赋予一个二进制符号“0”和“1”。
(4) 如此重复, 直至每个组只剩下一个信源符号为止。
(5) 信源符号所对应的码字即为费诺码。
#include
#include
#include
#include
using namespace std;
struct Fano_struct
{
string name; // 信源符号名称
double p; // 符号概率
int result_length; // 码字长度
vector 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
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