( Đừng hỏi đất nước có thể làm gì cho bạn mà hãy hỏi bạn có thể làm được gì cho đất nước của bạn .)
· “ask “ xuất hiện hai lần
· “what” xuất hiện hai lần
· “your” xuất hiện hai lần
· “country” xuất hiện hai lần
· “can” xuất hiện hai lần
· “do” xuất hiện hai lần
· “for” xuất hiện hai lần
· “you” xuất hiện hai lần
LZ được viết tắt từ “ Lempel and Ziv“ những người tạo nên thuật toán và “từ điển” là phương pháp tạo đoạn danh mục của dữ liệu .
1. ask 2. what 3. your 4. country 5. can 6. do 7. for 8. you |
Câu của chúng ta sẽ được ghi như sau :
"1 not 2 3 4 5 6 7 8 -- 1 2 8 5 6 7 3 4" |
Nếu trong hệ thống mới bạn có thể dễ dàng tạo lại câu ban đầu từ từ điển của nó . Đó chính là nguyên nhân tại sao những file sau khi nén muốn sử dụng thì phải được giải nén trước đó . Bao nhiêu khoảng trống bạn đã tiết kiệm "1 not 2 3 4 5 6 7 8 -- 1 2 8 5 6 7 3 4" rõ ràng là ngắn hơn so với "Ask not what your country can do for you; ask what you can do for your country;" , nhưng nên nhớ rằng chúng ta cần lưu từ điển này cùng với file nén .
Với ví dụ kiểu quy định trên , mọi lí tự thì chứa một đơn vị nhớ thì câu đầu chưa nén dùng 79 đơn vị . Câu nén và cả khoảng trống là 37 đơn vị , kèm theo từ điển cũng dùng 37 đơn vị . Như thế sau khi nén sẽ dùng 74 đơn vị , như thế kích thước file sau khi nén không giảm nhiều .
Nhưng điều đó chỉ có một câu , bạn có thể xem một hình ảnh nén file có nhiều câu , trong đó chúng có nhiều phần được lặp đi lặp lại .
Nếu chương trình nén quét cụm từ của Kenedy , đầu tiên nó sẽ đi qua những cặp từ . Trong “ask not what your," có mẫu được lặp lại của chữ cái “t” với dấu trống trong từ “not” và “what” . Nếu chương trình nén viết từ này vào trong từ điển , nó có thể ghi “1” là “t” kèm theo dấu trống . Nhưng trong cụm từ ngắn , mẫu này xảy ra không thường xuyên đủ để ghi nó thành một từ trong từ điển do vậy chương trình sẽ ghi đè lên mẫu này.
Tiếp theo chương trình có thể lưu ý tới từ “ou” mà nó xảy ra trong từ “your" và “country” . Nếu từ này có trong tài liệu dài hơn , nó ghi mẫu này tới từ điển để tiết kiệm nhiều chỗ trống – “ou” cũng khá hay xảy ra đối với sự kết hợp từ trong tiếng Anh . Nhưng chúng ta đang xét tới chương trình nén trong câu trên , nó nhanh chóng phát hiện ra lựa chọn tốt nhất cho ghi vào từ điển : Không chỉ có :”ou” được lặp lại , nhưng những từ “your” và “country” cũng được lặp lại . Trong trường hợp đó chương trình sẽ ghi đè vào từ điển từ”ou” bằng "your country."
Cụm từ "can do for" cũng được lặp lại , một lần đi theo với”your” và một lần khác theo với “you” cho chúng ta mẫu lặp lại "can do for you." . Điều này cho phép chúng ta ghi 15 kí tự bao gồm cả khoảng trống bằng một giá trị số , trong khi "your country" chỉ dùng 13 kí tự bao gồm cả khoảng trống cũng bằng một giá trị số . Do đó chương trình sẽ ghi đè lên mẫu "your country" bằng mẫu của “r country” và sau đó viết tách với “ "can do for you." . Chương trình chấp nhận cách như vậy , lấy tất cả những Bit thông tin được lặp lại và sau đó tính toán những mẫu này và ghi chúng vào trong từ điển . Khả năng ghi lại và ghi đè lên những mẫu trong từ điển gọi là “thích nghi” ( Adaptive ) là một phần trong “Thuật toán dựa trên từ điển thích nghi LZ” .
Không có vấn đề đối với những phương pháp mà bạn dùng cụ thể , hệ thống tìm kiếm những mẫu ghi trong từ điển càng sâu thì hiệu suất nén file của bạn càng hiệu quả . Đối với vi dụ trên chúng ta có những mẫu sau kèm theo cả khoảng trống
1. ask__ 2. what__ 3. you 4. r__country 5. __can__do__for__you |
Và chúng ta được câu nén như sau :
"1not__2345__--__12354" |
Câu trên dùng 18 đơn vị nhớ , và từ điển của chúng ta dùng 41 đơn vị nhớ . Do đó chúng ta nén tổng dung lượng file từ 79 đơn vị xuống còn 59 đơn vị . Đó là một phương pháp để nén cụm từ .
Hệ thống nén file như thế nào thì được cho là tốt ? Tỉ lệ nén file phụ thuộc vào một số nhân tố như : kiểu file , kích thước file và kế hoạch nén .
Hầu hết những ngôn ngữ trên thế giới , những chữ cái và những từ thường xuất hiện trong cùng một mẫu . Bởi vì tỉ lệ nén file cao đối với những file dạng văn bản . Những file văn bản kích thước giản 50% thì được gọi là tốt .Đa số ngôn ngữ lập trình cũng có tỉ lệ nén file cao là vì chúng có tập hợp những lệnh lặp đi lặp lại . Những file bao gồm chứa nhiều thông tin riêng biệt như đồ hoạ hoặc MP3 nên không thể có tỉ lệ nén nhiều với những file này bởi vì chúng không có nhiều mẫu được lặp đi lặp lại .
Nếu file có nhiều mẫu được lặp lại thì tỉ lệ nén sẽ tăng lên cùng với kích thước của file .
Hiệu quả của tỉ lệ nén file phụ thuộc nhiều vào thuật toán sử dụng trong chương trình nén . Một vài chương trình có những từ ghép đặc biệt để lấy những mẫu này trong những kiểu file nào đó và do vậy chúng có thể nén được file có tỉ lệ nén cao hơn . Một vài chương trình khác lại có từ điển bên trong từ điển để tăng hiệu suất với file có kích thước ban đầu lớn mà không phù hợp với file có kích thước ban đầu nhỏ ... Những người lập trình đang cố gắng tạo ra những thuật toán , những chương trình nén với hiệu suất cao hơn .
Kiểu nén suy hao làm việc hoàn toàn khác . Những chương trình như vậy đơn giản là loại bỏ những Bit thông tin không cần thiết để file có kích thước nhỏ hơn . Kiểu nén này dùng để giảm kích thước file hình ảnh Bitmap có dung lượng lớn .
Chương trình nén file bảo toàn không thể nén nhiều đối với kiểu file hình ảnh . Trong khi phần lớn của hình ảnh nhìn trông có thể tương tự nhau như : tất cả bầu trời là Xanh da trời hầu hết những Pixel riêng biệt chỉ khác nhau một chút . Để cho bức tranh có kích thước nhỏ hơn mà không ảnh hưởng nhiều tới độ phân giải , bạn phải thay đổi giá trị màu của những Pixel . Nếu bức ảnh có nhiều vùng bầu trời xanh , chương trình sẽ dùng một màu xanh cho mọi Pixel để hiển thị vùng bầu trời . Sau đó chương trình sẽ ghi lại file đó . Nếu thuật toán nén được gọi là tốt nếu như chúng ta không nhận biết được sự thay đổi mà kích thước của file cũng giảm đi đáng kể .