TR NG Đ I H C ĐI N L CƯỜ Ạ Ọ Ệ Ự
Khoa Đi n T Vi n Thôngệ ử ễ
----------
BÀI TẬP NHÓM MÔN LÝ THUYẾT THÔNG TIN
Đ TÀI Ề: “Lempel-ziv Encoding”
Giảng viên bộ môn: Vũ
Ngọc Châm
Nh óm Sinh Viên Thực Hiên:
Nhóm 10
Sinh vi ên lớp: Đ5.ĐTVT1
Tr ng Đ i H c Đi n L c Khoa Đi n T Vi n Thôngườ ạ ọ ệ ự ệ ử ễ
Nhóm 10
TR NG ĐAI H C ĐI N L CƯỜ Ọ Ệ Ự
Khoa Đi n T Vi n Thôngệ ử ễ
Môn Lý THUYÊT thông tin
LEMPEL-ZIV ENCODING
Danh Sách Các Thành Viên Nhóm S 10ố
1 : NGUY N QU C QUÂN Ễ Ố
2: NGUY N VĂN HÙNGỄ
3: NGUY N VĂN KHOÁI Ễ
4: HOÀNG VĂN LÂM
5: NGUY N VĂN TI N LÂM Ễ Ế
Hà n i ngày 11 tháng 9 năm 2012ộ
Tr ng Đ i H c Đi n L c Khoa Đi n T Vi n Thôngườ ạ ọ ệ ự ệ ử ễ
Nhóm 10
M c L c ụ ụ
1.Danh sách thành viên trong nhóm 10……………………….. 1
2.L i gi i thi u………………………………………………....2ờ ớ ệ
3.T ng quan v nén gi li u …………………………………...4ổ ề ữ ệ
4. C s m t s ph ng pháp nén………..…………………….5ơ ở ộ ố ươ
5. T ng quan v Lempel-ziv coding …………………………...6ổ ề
6.T đi n mã hóa……………………………………………….7ừ ể
7. H thu t toán Lempel-Ziv…………………………………..8ọ ậ
+Thu t toán LZ78……………………………………………...8ậ
+Thu t toán LZW ……………………………………………..11ậ
8.K t Lu n……………………………………………………..19ế ậ
9.Tài li u tham kh o……………………………………………21ệ ả
2.M c l c……………………………………………………….22ụ ụ
Tr ng Đ i H c Đi n L c Khoa Đi n T Vi n Thôngườ ạ ọ ệ ự ệ ử ễ
Nhóm 10
Lời giới thiệu.
Ngày nay thông tin là một phần gắn kết không th thiếu c a con ngể ủ ười trong cuộc
sống hiện đại. việc trao đi thông tin là công việc thổ ường xuyên và được coi như là
bình thường c a mỗi chúng ta.Có rất nhiều hình thức th hiện khác nhau c a thôngủ ể ủ
tin như âm thanh, hình nh,tiếng nói,chữ viết và các loại ký tự……. Chính vì vậyả
mà cũng n y sinh ra rất nhiều vấn ảđề bức thiết xung quanh việc chuyền t i thông tinả
từ người này tới người khác cũng như đến vấn đề lưu trữ bạn không th b 250ể ỏ
Gigabyte dung lượng nhớ máy vi tính c a bạn ra ch ổ ủ ỉ đ lể ưu trữ và ghi nhớ một
thông tin không quan trọng lắm, hoặc trong việc lưu trữ nó. Ví dụ như dung lượng
tập tin mà quá lớn nó sẽ nh hả ư ng vân ởđề trao đi thông tin bạn không th chờ cổ ể ả
ngày đ cập nhập một lể ượng tin quá lớn mà không cần thiết lắm cho cuộc sống c aủ
bạn.Chính vì vậy mà người ta mới nghĩ ra một thuật toán mà làm thế nào đó đ cóể
th ểgi m dung lả ượng thông tin cần trao đi ổđó xuống nhằm mục đích đơn gi n vàả
thuận tiện hơn trong việc trao đi và lổ ưu trữ thông tin. Để giải quyết vấn đề đó,
các thuật toán nén đã được ra đời.
Ban đầu với phương pháp mã hóa loạt dài RLC (Run Length Coding), phát hiện
một loạt các bít lặp lại. Đây là phương pháp đơn giản nhất. Nguyên tắc cơ bản
của phương pháp này là phát hiện một ký tự có số lần xuất hiện liên tiếp vượt
qua một ngưỡng cố định nào đó. Trong trường hợp này dãy sẽ được thay thế
bằng 3 ký tự: Ký tự thứ nhất là ký tự đặc biệt,thông báo dãy tiếp là dãy đặc biệt.
Ký tự thứ hai chỉ số lần lặp. Ký tự thứ ba chỉ ký tự lặp.Như vậy tư tưởng của
phương pháp này là thay thế một dãy bằng một dãy khác ngắn hơn tuân theo một
ngưỡng nào đó, và thông thường ngưỡng có giá trị là 4.Kế đến là phương pháp
Huffman, dựa vào mô hình thống kê, tính tần suất xuất hiện của các ký tự, rồi gán
cho các ký tự có tần suất cao một từ mã ngắn, các ký tự tần suất thấp từ mã dài.
Phương pháp này phải lưu giữ lại bảng mã gắn kèm cùng với dữ liệu nén.
Một phương pháp nén hoàn toàn khác là thuật toán nén dữ liệu theo từ điển cơ
s:ở (Dictionary-based compression)
Tr ng Đ i H c Đi n L c Khoa Đi n T Vi n Thôngườ ạ ọ ệ ự ệ ử ễ
Nhóm 10
Có 2 loại:
Mã hóa từ điển tĩnh (static dictionary coding)
Mã hóa từ điển động (dynamic dictionary coding)
Có rất nhiều thuật toán áp dụng kỹ thuật này như LZ77, LZR, LZSS, LZH…
nhưng trong nội dung bài báo cáo này, chúng ta chỉ đề cập đến hai thuật toán chình
là:
+Thuât Toán LZ78
+ Thuât toán LZW.
Nhìn chung không có phương pháp nén t ng quát nào cho kết qu là tốt ổ ả đối với
tất c các loại tập tin mà ta cần mã hóa c .Nả ả ăm 1983 Sperry nộp một bằng sáng chế
cho một thuật toán phát tri n b i Terry Welch, một nhân viên tại Trung tâm nghiênể ở
cứu Sperry. Thuật toán này là biến th trên một kỹ thuật nén dữ liệu lần ểđầu tiên
được đề xuất b i Jakob Ziv và Abraham Lempel nởăm 1978 c a Welch. Kỹ thuật c aủ ủ
Welch là c hai ảđơn gi n hả ơn và nhanh hơn. Ông đã xuất b n một bài báo trong vấnả
đề 1984 c a Tạp chí máy tính IEEE mô t kỹ thuật. Kỹ thuật này củ ả a ủTerry Welch
tr nên rất ph biến và ở ổ được chấp nhận rộng rãi. Đó chính là thuật toán mã hóa mà
ngày nay người ta gọi nó với cái tên là Lempel-Ziv-Welch.
Hà nội ngày 11 tháng 9 năm 2012
Các thành viên nhóm 10
I: T NG QUAN V NÉN GI LI UỔ Ề Ữ Ệ
I.1:Nén gi li u là gì?.ữ ệ
Nén gi li u đ c đ nh nghĩa đ n gi n nh sauữ ệ ượ ị ơ ả ư : Nén d li u là quáữ ệ
trình làm gi m l ng thông tin “d th a” trong d li u g c và doả ượ ư ừ ữ ệ ố
v y, thông tin thu đ c sau nén th ng nh h n d li u g c r tậ ượ ườ ỏ ơ ữ ệ ố ấ
nhi u. Ngoài thu t ng “nén d li u”, do b n ch t c a k thu tề ậ ữ ữ ệ ả ấ ủ ỹ ậ
này nó còn có m t s tên g i khác nh : gi m đ d th a, mã hóaộ ố ọ ư ả ộ ư ừ
nh g c…ả ố
Tr ng Đ i H c Đi n L c Khoa Đi n T Vi n Thôngườ ạ ọ ệ ự ệ ử ễ
Nhóm 10