be_fed_up_with_u
New Member
Download miễn phí Đề tà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
Một điều cần chú ý khi nén bằng LZW: nó thêm phrase vào từ điển trước khi toàn bộ phrase này được nén, cụ thể là ký tự cuối của phrase chỉ được xử lý ở lần lặp sau. Nếu vì một lý do nào đó mà trình nén sử dụng ngay lập tức phrase này thì khi giải nén sẽ có vấn đề là gặp phải code của một phrase mà phrase này lại chưa xuất hiện trong từ điển (phrase này còn thiếu một ký tự cuối là ký tự đầu của xâu được giải mã tiếp theo. Rất tiếc là điều này có thể xảy ra. Điều này chỉ xảy ra khi trong dữ liệu vào có đoạn CHARACTER.STRING.CHARACTER.STRING.CHARACTER. Trong ví dụ sau CHARACTER=I, STRING=WOMBAT. Giả sử xâu IWOMBAT đã có trong từ điển (mã là 300) còn IWOMBATI thì chưa có. Như vậy khi gặp đoạn dữ liệuIWOMBATIWOMBATI trình nén sẽ cho ra mã 300 và thêm IWOMBATI vào từ điển(với mã 400 chẳng hạn). Và sau đó nó sử dụng ngay mã 400 cho đoạn tiếp theo, tức là cả đoạn dữ liệu trên sẽ cho ra mã <300><400>. Bây giờ chúng ta hãy theo dõi quá trình giải nén. Sau khi thay <300> bằng IWOMBAT thì trình giải nén gặp mã 400. Nhưng khi đó trong từ điển của trình giải nén còn chưa có phrase IWOMBATI vì còn thiếu chữI ở cuối. Cho nên trong đoạn pseudocode trên, lệnh string1=dictionary_lookup(code) không phải lúc nào cũng thành công. Nhưng nó cũng chỉ không thành công trong trường hợp gặp phải dữ liệu có dạng như vừa mô tả, vì để tạo thành pharase mới trong từ điển chúng ta cũng chỉ thiếu có 1ký tự cuối và ký tự này xuất hiện ở ngay đầu của đoạn dữ liệu tiếp theo. Cho nên chúng ta cần sửa lại như sau:
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
Lời nói đầuNgà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” . tui đư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 tui 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 Thank 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+?.
Ví dụ. Nén theo LZW
0 a
1 b
Bước 1 aabababaaababb
thay ađ0
được 0abababaaababb từ điển
đoạn copy mới aabababaaababb
0 a
1 b
2 aa 0+a
Bước 2 aabababaaababb
thay ađ0
được 00bababaaababb
từ điển
0 a
1 b
2 aa 0+a
3 ab 0+b
đoạn copy mới aabababaaababb
Bước 3 00bababaaababb
thay bđ1
được 001ababaaababb
từ điển
0 a
1 b
2 aa 0+a
3 ab 0+b
4 ba 1+a
5 aba 3+a
đoạn copy mới aabababaaababb
Bước 4 001ababaaababb
thay abđ3
được 0013abaaababb
từ điển
đoạn copy mới aabababaaababb
aabababaaababb
0 a
1 b
2 aa 0+a
3 ab 0+b
4 ba 1+a
5 aba 3+a
6 abaa 5+a
Bước 5 0013abaaababb
thay abađ5
được 00135aababb
từ điển
đoạn copy mới aabababaaababb
0 a
1 b
2 aa 0+a
3 ab 0+b
4 ba 1+a
5 aba 3+a
6 abaa 5+a
7 aab 2+b
Bước 6 00135aababb
thay aađ2
được 001352babb
từ điển
đoạn copy mới aabababaaababb
0 a
1 b
2 aa 0+a
3 ab 0+b
4 ba 1+a
5 aba 3+a
6 abaa 5+a
7 aab 2+b
8 bab 4+b
Bước 7 001352babb
thay bađ4
được 0013524bb
từ điển
đoạn copy mới aabababaaababb
Thuật toán LZW
Trong LZW thì token chỉ có index. Để làm việc này, từ điển khi được khởi tạo đã gồm tất cả các ký tự đơn lẻ cho nên nó luôn được tìm thấy trong từ điển mặc dù có thể trước đó chưa xuất hiện trong văn bản.
Thuật toán nén cho LZW:
Khi mới bắt đầu, từ điển đã gồm tất cả các ký tự đơn lẻ.
Xâu hiện tại bắt đầu có độ dài 1. Mỗi khi đọc thêm 1 ký tự thì nó được thêm vào xâu hiện tại. Nếu xâu hiện tại còn trùng với một trong các phrase đã có thì quá trình cứ tiếp tục.
Khi không có phrase trong từ điển trùng với xâu hiện tại nữa thì :
chúng ta cho ra index là chỉ số xâu trước đó (không kể ký tự vừa đọc vào) trong từ điển.
thêm xâu hiện tại (bao gồm cả ký tự vừa đọc vào) vào trong từ điển.
string1[0]=getc(input);
string1[1]=’\0’;
while (!feof(input)) {
character=getc(input);
if in_dictionary(string1+character)
{string1=string1+character;}
else {
code=look_up_dictionary(string1);
output_code(code);
add_to_dictionary(string1+character);
string1[0]=character;
string1[1]=’\0’;
}
code=look_up_dictionary(string1);
output_code(code);
bắt đầu một xâu mới bằng ký tự vừa đọc vào.
Pseudocode nén của LZW:
Hai lệnh cuối cùng là để xử lý khi hết file, lúc đó chưa có phrase mới nên không có lệnh add_to_dictionary(). Cột đầu tiên là string1 (biến của lệnh add_to_dictionary) bỏ bớt đi ký tự đầu (ký tự này có do các lệnh string1[0]=character; string1[1]=’\0’; ở phần else {} của bước trước), đây thực chất là các ký tự đã được đọc bởi lệnh character=getc(input) . Cột thứ hai là index của phrase trong từ điển (ở đây khi phrase chỉ có 1 ký tự thì chúng ta sử dụng chính ký tự này thay cho index, đúng ra là phải dùng hàm ascii (ký tự)). Cột thứ 3 là biến (string1 + character) trong lệnh add_to_dictionary (string1 + character) kèm theo index của nó trong từ điển.
Ví dụ: Mỗi dòng của bảng sẽ ứng với một lần thực hiện vòng lặp
while (!feof(input)) (trừ dòng đầu tiên).
Input String: “ WED WE WEE WEB WET”
Từ thuật toán nén ta thấy rằng:
index của string1 ở bước hiện tại được đưa vào tệp nén.
phrase được thêm vào từ điển là string1 ở bước hiện tại + character, trong đó character là ký tự đầu của string1 ở bước sau
Thuật toán giải nén như sau:
Đầu tiên, đọc một index vào và tìm phrase tương ứng với nó trong từ điển. Đưa phrase này ra tệp (string1 ở bước trước).
Vòng lặp:
đọc index tiếp theo, tra từ điển để tìm string1 ở bước hiện tại, đưa nó vào tệp giải nén
thêm (string1 ở bước trước + ký tự đầu của string1 ở bước hiện tại) vào từ điển
Trong đoạn pseudocode sau thì string2 chính là ‘string1 ở bước trước’:
string2[0]=input_bits();
string2[1]=’\0’;
putc(string2[0], output);
while ((code=input_bits() )!=EOF) {
string1=dictionary_lookup(code);
fputs(string1, output);
add_to_dictionary(string2+string1[0]);
strcpy(string2, string1);}
Ví dụ của việc giải nén:
Trong bảng sau đây, mỗi dòng sẽ tương ứng với một lần thực hiện vòng lặp while{}, riêng dòng đầu tiên là do các lệnh
string2[0]=input_bits();
string2[1]=’\0’;
putc(string2[0], output);
Cột thứ nhất (I) là kết quả của lệnh code =input_bits();
Cột thứ hai (II) là kết quả của các lệnh
string1=dictionary_lookup(code);
fputs(string1, output);
Cột thứ ba (III) là biến string2 trong lệnh add_to_dictionary(string2+ string1[0]). Nó bằng với cột thứ hai (string1) ở bước trước do lệnh strcpy(string2, string1).
Cột thứ tư (IV) là ký tự đầu của cột thứ II (string1[0]).
Cột thứ năm (V) là biến (string2+string1[0]) trong lệnh add_to_dictionary(string2+ string1[0]).
Input Codes: “ WEDEBT”
Một điều cần chú ý khi nén bằng LZW: nó ...