BÀI TẬP NHÓM MÔN LÝ THUYẾT THÔNG TIN - ĐỀ TÀI : 'Lempel-ziv Encoding'

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ự…….
Nội dung trích xuất từ tài liệu:
BÀI TẬP NHÓM MÔN LÝ THUYẾT THÔNG TIN - ĐỀ TÀI : “Lempel-ziv Encoding” 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 I.2:Tỷ Số Nén ( Compression rate )  Compression rate được định nghĩa như sau: Tỷ số nén là tỷ lệ giữa kích thướcfile đã nén và kích thước file khi mà chưa nén. + Công thức tỷ số nén như sau: Chú ...