[Thuật toán] Mã hóa tối ưu – Phương pháp mã hóa Shanon

Nội dung
Thuật toán mã hóa Shanon
Code thuật toán

Trong bài viết này mình chỉ nêu phương pháp mã hóa Shanon và code C/C++ của thuật toán. Mọi khái niệm liên quan mặc định các bạn đã biết, nếu chưa rõ khái niệm nào thì bạn gọi đại ca Google nhé. ^^

Thuật toán mã hóa Shanon

Xét nguồn U với bảng phân phối xác suất

U1 U2 UN
P1 P2 PN

Bước 1: Sắp xếp các tin theo thứ tự giảm dần của xác suất
Bước 2: Tính độ dài từ mã mã hóa tin Ui theo công thức:
2^{-n_{i}} \leq P(U_{i}) \leq 2^{1-n_{i}}
Từ công thức này ta biến đổi ra công thức dễ dàng hơn là:
n_{i} = \left [ -log_{2}P(U_{i}) \right ]
Bước 3: Tính F(Ui) theo công thức:
\begin{cases}  F(U_{i}) = \sum_{j=0}^{i-1}P(U_{i}) = P(U_{i-1}) + F(U_{i-1}) & \text{ khi } i \geqslant 2 \\  F(U_{i}) = 0 & \text{ khi } i = 1  \end{cases}
Bước 4: Chuyển F(Ui) từ bước 3 sang hệ nhị phân
Bước 5: Lấy ni ký tự sau dấy thập phân tính được của F(Ui) ta được từ mã của ui

Ví dụ: Với nguồn vào là một chuỗi nguyenvanquan7826. Sau khi thực hiện các bước trên ta có kết quả như sau:

mã hóa shanon

Đây là kết quả khi chạy chương trình dưới đây. Trong chương trình, việc tính P và F mình không đổi ngay ra số thập phân mà để nó dưới dạng phân số sau đó khi tính ni mới chuyển sang số thập phân để kết quả chính xác hơn.

Code thuật toán

//============================================================================
// Name        : Shanon.cpp
// Author      : nguyenvanquan7826
//============================================================================

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

typedef struct {
	char s1;
	int ni, P, F, b[100];

} nguon;
void doicho(nguon *a, nguon *b) {
	nguon c;
	c = *a;
	*a = *b;
	*b = c;
}

int main() {
	char *s;
	nguon *kitu;
	int i, j, n, k = 1, *a, ni, maxni;

	s = (char *) malloc(100 * sizeof(char));
	a = (int *) malloc(100 * sizeof(int));
	kitu = (nguon *) malloc(100 * sizeof(nguon));

	printf("Moi ban nhap day nguon: ");
	gets(s);
	fflush(stdin);
	puts(s);
	n = strlen(s);

	//Phan loai ki tu va tinh P(Ui)
	for (j = 1; j <= 256; j++) {
		a[k] = 0;
		for (i = 0; i <= n; i++)
			if ((int) s[i] == j) {
				a[k]++;
				kitu[k].s1 = s[i];
			}
		if (a[k] > 0) {
			kitu[k].P = a[k];
			k++;
		}
	}
	for (i = 1; i < k; i++)
		for (j = i; j < k; j++)
			if (kitu[i].P < kitu[j].P)
				doicho(&kitu[i], &kitu[j]);

	//Tinh F(Ui)

	for (i = 1; i <= k; i++) {
		if (i == 1)
			kitu[1].F = 0;
		if (i > 1)
			kitu[i].F = kitu[i - 1].F + kitu[i - 1].P;
	}

	//Tinh ni
	for (i = 1; i < k; i++) {
		float j;
		j = n / kitu[i].P;
		ni = (int) (log(j) / log(2)) + 1;
		kitu[i].ni = ni;
	}
	maxni = kitu[1].ni;
	for (i = 1; i < k; i++)
		if (kitu[i].ni > maxni)
			maxni = kitu[i].ni;

	//Tinh F(Ui) he 2
	int l;
	float F;
	for (i = 1; i < k; i++) {
		l = 1;
		F = (float) kitu[i].F / n;
		while ((l <= maxni) && (F != 0)) {
			F = F * 2;
			kitu[i].b[l] = (int) F / 1;
			l++;
			F = F - (int) F;
		}
	}

	printf("\n\n%5s %10s %10s %7s", "Ui", "P(Ui)", "F(Ui)", "ni");
	for (i = 1; i <= maxni + 1; i++)
		printf(" ");
	printf("%9s", "F(Ui)2");
	for (i = 1; i <= maxni; i++)
		printf(" ");
	printf("%10s", "Ma");
	for (i = 1; i < k; i++) {
		ni = kitu[i].ni;
		printf("\n%5c %7d/%d %7d/%d %7d", kitu[i].s1, kitu[i].P, n, kitu[i].F,
				n, kitu[i].ni);
		for (j = 1; j <= maxni - ni; j++)
			printf(" ");
		printf("%10s", "0.");
		for (j = 1; j <= ni; j++)
			printf("%d", kitu[i].b[j]);
		for (j = 1; j <= maxni - ni; j++)
			printf(" ");
		printf("%10s", " ");
		for (j = 1; j <= ni; j++)
			printf("%d", kitu[i].b[j]);
	}
	printf("\n");
	return 0;
}