[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

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 Uⁱ theo công thức:

Từ công thức này ta biến đổi ra công thức dễ dàng hơn là:

Bước 3: Tính F(U_i) theo công thức:

Bước 4: Chuyển F(U_i) từ bước 3 sang hệ nhị phân
Bước 5: Lấy n_i ký tự sau dấy thập phân tính được của F(U_i) ta được từ mã của u_i

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:

Đâ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 n_i 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("

%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("
%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("
");
	return 0;
}