Ktl-icon-tai-lieu

Mã hoá Nguồn

Được đăng lên bởi Khánh Vi
Số trang: 3 trang   |   Lượt xem: 223 lần   |   Lượt tải: 0 lần
Thuật toán Shannon-Fano:
Các bước thực hiện mã hoá theo thuật toán Shanon-Fano:
Bước 1: Sắp xếp các ký tự theo thứ tự giảm dần.
- Bước 2: Tính xác suất
- Bước 3: Đệ quy làm hai phần, mỗi phần có tống xác suất gần bằng nhau.
Mã hoá phần trên bằng bit 0 (hoặc bit 1), phần dưới bằng bit l(hoặc bit 0).
- Bước 4: Vẽ sơ đồ cây.
- Bước 5: Tính Entropy, so bit mã hoá trung bình và số bit mã hoá thông
thường.
-

❖

Ví dụ mô tả thuật toán Thống kê lượng
tin:
Ký hiệu
Số lần xuất hiện

A
15

B
7

c
6

D
5

Mã hóa lượng tin:
Ký hiệu Đêm
Log2(l/p¡)
Mã
Pi
A
15
15/39
1.38
0
0
B
7
7/39
2.48
0
1
6
6/39
2.7
1
0
c
E
6
6/39
2.7
1
1
D
5
5/39
2.96
1
1
So bits sử dụng trung bình: (tống bits/ số lần xuất hiện).

E
6

0
1

Tông bits
30
14
12
18
15

R = (30+14+12+18+15) / 39 = 2.29 bits
Thuật toán Huffman
Thuật toán Huffman có un điếm là hệ số nén tương đối cao, phương pháp thực hiện
tương đối đơn giản, đòi hỏi ít bộ nhớ, có thế xây dựng dựa trên các mảng bé hơn 64KB.
Nhược điếm của nó là phải chứa cả bảng mã vào tập tin nén thì phía nhận mới có thể
giải mã được do đó hiệu suất nén chỉ cao khi ta thực hiện nén các tập tin lớn.
4- Nguyên lý:
Nguyên lý của phương pháp Huffman là mã hóa các bytes trong tệp dữ liệu nguồn

bằng biến nhị phân. Nó tạo mã độ dài biến thiên là một tập hợp các bits. Đây là phương
pháp nén kiểu thống kê, những ký tự xuất hiện nhiều hơn sẽ có mã ngắn hơn (gần giống
Shannon-Fano).
4- Thuật toán;
•

Thuật toán nén:
Bước 1 : Tìm hai ký tự có trọng số nhỏ nhất ghép lại thành một, trọng số của ký
tự’ mới bằng tống trọng số của hai ký tụ' đem ghép.
- Bước 2: Trong khi số lượng ký tự' trong danh sách còn lớn hơn một thì thực hiện
bước một, nếu không thì thực hiện bước ba.
- Bước 3: Tách ký tự cuối cùng và tạo cây nhị phân với quy ước bên trái mã 0, bên
phải mã 1.
-

❖

Xét ví dụ.

Thong kê lượng tin:
Ký hiệu
Số lần xuất hiện

A
15

B
7

c
6

D
5

E
6

Mã hóa lượng tin:
Ký hiệu Xác suât
Mã
Tông bit
A
15/39
]
1
15
B
7/39
|-0- - 13/39 0
000
21
6/39
1
001
18
c
_E
6/39
0
1 ¿H/ôy u
010
18
D
5/39
1 1 1 no
011
15
1 í/jy
- Số bit trung bình: 87/39 =2.23 (<2.28) Hiệu quả hơn Shannon - Fano.

•

Thuật toán giải nén:

Bước 1: Đọc lần lượt từng bit trong tập tin nén và duyệt cây nhị phân đã
được xác định cho đến khi hết một lá. Lấy ký tự ở lá đó ghi ra tệp giải nén.
Bước 2: Trong khi chưa hết tập tin nén thì quay lại thực hiện bước một,
ngược lại thì thực hiện bước tiếp theo.
Bước 3: Khi hết tập tin, kết thúc thuật toán.

...
Thuật toán Shannon-Fano:
Các bước thực hiện mã hoá theo thuật toán Shanon-Fano:
- Bước 1: Sắp xếp các ký tự theo thứ tự giảm dần.
- Bước 2: Tính xác suất
- Bước 3: Đệ quy làm hai phần, mỗi phần có tống xác suất gần bằng nhau.
Mã hoá phần trên bằng bit 0 (hoặc bit 1), phần dưới bằng bit l(hoặc bit 0).
- Bước 4: Vẽ sơ đồ cây.
- Bước 5: Tính Entropy, so bit mã hoá trung bình và số bit mã hoá thông
thường.
Ví dụ mô tả thuật toán Thống kê lượng
tin:
Ký hiệu A B
c
D E
Số lần xuất hiện 15 7 6 5 6
Mã hóa lượng tin:
R = (30+14+12+18+15) / 39 = 2.29 bits
Thuật toán Huffman
Thuật toán Huffman có un điếm là hệ số nén tương đối cao, phương pháp thực hiện
tương đối đơn giản, đòi hỏi ít bộ nhớ, có thế xây dựng dựa trên các mảng bé hơn 64KB.
Nhược điếm của nó là phải chứa cả bảng mã vào tập tin nén thì phía nhận mới có thể
giải mã được do đó hiệu suất nén chỉ cao khi ta thực hiện nén các tập tin lớn.
4- Nguyên lý:
Nguyên lý của phương pháp Huffman là mã hóa các bytes trong tệp dữ liệu nguồn
Ký hiệu Đêm
Pi
Log
2
(l/p¡) Tông bits
A 15 15/39 1.38 0 0 30
B 7 7/39 2.48 0 1 14
c
6 6/39 2.7 1 0 12
E 6 6/39 2.7 1 1 0 18
D 5 5/39 2.96 1 1 1 15
So bits sử dụng trung bình: (tống bits/ số lần xuất hiện).
Mã hoá Nguồn - Trang 2
Mã hoá Nguồn - Người đăng: Khánh Vi
5 Tài liệu rất hay! Được đăng lên bởi - 1 giờ trước Đúng là cái mình đang tìm. Rất hay và bổ ích. Cảm ơn bạn!
3 Vietnamese
Mã hoá Nguồn 9 10 343