Luận Văn Đề tài: Chạy và phân tích trình LZW 15

Đề tài: Chạy và phân tích trình LZW 15

LỜI NÓI ĐẦU

Ngày nay, cùng với sự phát triển không ngừng của khoa học và công nghệ thì máy tính đóng vai trò không thể thiếu trong cuộc sống xã hội loài người.
Việc trao đổi thông tin của con người trong tất cả các ngành, các lĩnh vực của đời sống ngày càng trở nên cấp thiết và quan trọng, chính vì thế mà các thiết bị thông tin mới liên tục ra đời nhằm đáp ứng các yêu cầu này. Tuy nhiên, vì một số phần mềm đòi hỏi rất nhiều bộ nhớ để hoạt động trao đổi thông tin nên người ta đã nghĩ ra một phương pháp nhằm giải quyết vấn đề này, đó là phương pháp nén dữ liệu mà vẫn bảo toàn thông tin.
Nén dữ liệu là một kỹ thuật quan trọng trong rất nhiều lĩnh vực khác nhau. Chính nhờ có kỹ thuật nén dữ liệu mà ngày nay chúng ta có những phương tiện truyền thông hiện đại phục vụ cho cuộc sống như truyền hình cáp, điện thoại, thư điện tử . và rất nhiều khía cạnh khác. Do đó kỹ thuật nén dữ liệu ngày càng được quan tâm và phát triển nhiều hơn. ở Việt Nam, hầu hết các trường Đại học đều quan tâm đến việc nén dữ liệu và điều này được thể hiện ở việc đưa kỹ thuật nén trở thành môn học chính thức trong giai đoạn chuyên ngành .
Trong phạm vi môn học “ Mã - mã nén” . Tôi đưa ra bài phân tích trình LZW 15 nhằm mô phỏng thuật toàn kỹ thuật nén dữ liệu.
Tuy nhiên do trình độ còn hạn chế, thời gian và kinh nghiệm chưa nhiều, nên bài phân tích này không thể tránh khỏi sự sai sót trong quá trình phân tích. Do vậy tôi rất mong được sự quan tâm tham gia góp ý Thầy Cô cũng như cùng toàn thể các bạn Sinh Viên để bài phân tích này rõ dàng hơn.
Cuối cùng Em xin chân thành cảm ơn thày Nguyễn Lê Anh đã hướng dẫn và giảng dạy Em trong thời gian qua.

Thuật toán nén LZW
Bước 1 Cắt văn bản mới thành các đoạn copy nếu bảng chữ cái có m chữ thì các chữ cái là m đoạn copy đầu tiên được đánh số từ 0 đến m-1.
Bước 2 Bỏ tất cả phần chữ thu được mã nén.
Lưu ý rằng các đoạn copy lần lượt được tạo ra và phần số của nó luôn nhỏ hơn số hiệu cột mà nó đứng.
Thuật toán giải nén LZW.
Bắt đầu là các cột đầu tiên (trong ví dụ là cột thứ 2) lặp lại thao tác sau cho đến hết.

Lấy hai số liên tiếp của bản mã ví dụ là X, Y thay nó về dạng X+? và Y+$. Trong đó kí tự đầu tiên của Y+$ là kí tự cuối cùng của X+?. Dấu ? và $ là thay cho một kí tự chưa biết. Vì X và Y không thể lớn hơn chỉ số cột mà nó đứng cho nên chúng ta hoàn toàn tìm được giá trị đoạn copy ứng với cột có chỉ số X, Y và thay đoạn copy vào X+? và Y+$ tương ứng. Giá tri ? là kí tự đầu của Y+$ cho nên luôn luôn xác định. Như thế chúng ta tìm được X+?.