信源编码的代码实现 (香农编码、费诺编码、哈夫曼编码、游程编码、算术编码)

#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
*/

#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
*/

#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
*/

#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
*/