Phương pháp ước lượng xác suất thứ cấp dự trên lý thuyết entropy cực địa trong ứng dụng nén dữ liệu

Tuyển tập Báo cáo Hội nghị Sinh viên Nghiên cứu Khoa học lần thứ 7 Đại học Đà Nẵng năm 2010

222

PHƢƠNG PHÁP ƢỚC LƢỢNG XÁC SUẤT THỨ CẤP DỰA TRÊN

LÝ THUYẾT ENTROPY CỰC ĐẠI TRONG ỨNG DỤNG NÉN DỮ LIỆU

SECONDARY PROBABILITY ESTIMATION METHODS BASED ON MAXIMUM

ENTROPY PRINCIPLE IN DATA COMPRESSION APPLICATIONS

SVTH: Nguyễn Hải Triều Anh

Lớp 05DT1, Khoa Điện tử Viễn thông, Trường Đại học Bách khoa

GVHD: ThS. Hoàng Lê Uyên Thục

Khoa Điện tử Viễn thông, Trường Đại học Bách khoa

TÓM TẮT

Mô hình hóa dữ liệu và mã hóa là hai quá trình quan trọng nhất của nén dữ liệu. Mã hóa

được thực hiện tối ưu và hiệu quả với mã hóa số học. Tuy nhiên không thể tính toán mô hình tối

ưu cho một nguồn dữ liệu cho trước. Bài báo sẽ giới thiệu phương pháp ước lượng xác suất thứ

cấp. Trong đó mỗi mô hình sơ cấp ước lượng xác suất bit tiếp theo là bit 1 hoặc bit 0 một cách độc

lập. Các xác suất ước lượng được kết hợp lại với nhau bằng phương pháp tương tự như mạng

nơtron. Sau khi bit được mã hóa, bộ ước lượng được cập nhật theo hướng tối thiểu chi phí mã

hóa thay vì theo hướng giảm sai số dự đoán.

ABSTRACT

Data modeling and coding is two most important processes of data compression. An

optimal and effective coding process can be implemented using arithmetic coding. However,

optimal model is not computable. This paper introduces a secondary probability estimation method.

In this method, each primary model independently estimates the probability that the next bit of data

is 0 or 1. Results of estimation are combined by using a method similar to a neural network. After a

bit is coded, the estimator will be updated in the direction that minimizes coding cost instead of the

direction that minimizes mean square error.

1. Đặt vấn đề

Nén dữ liệu là biện pháp nhằm giảm số bit cần dùng để lưu trữ hoặc truyền dữ liệu.

Các thuật toán nén có hai quá trình thiết yếu nhất là quá trình ước lượng phân bố xác suất

và quá trình mã hóa. Người ta đã chứng minh được rằng không thể tìm ra ước lượng phân

bố xác suất tối ưu cho một nguồn cho trước [1][2]. Tuy nhiên quá trình mã hóa có thể được

thực hiện hiệu quả và tối ưu với mã hóa số học [3]. Độ dài từ mã trung bình mà bộ mã hóa

tạo ra bị giới hạn bởi entropy của nguồn. Giả sử biến ngẫu nhiên x nhận giá trị thuộc tập

X={x1, x2, …}; mỗi giá trị xi có xác suất là pi

, lí thuyết thông tin [4] định nghĩa entropy

của x là:

)

1

( ) log (

2

i i

i

p

H x p

(1)

Entropy của nguồn tin được xác định nếu ta biết trước được phân bố xác suất của nguồn

đó. Tổng quát thì phân bố xác suất của nguồn là không thể biết trước đồng thời phân bố tối

ưu của nguồn là không tính toán được, vì vậy chỉ có thể thực hiện ước lượng các giá trị

pi

.

Do đó tính hiệu quả của một thuật toán nén dữ liệu phụ thuộc chủ yếu vào quá trình ước