Đồ án Nghiên cứu phương pháp mã hóa Số học áp dụng nén số liệu

TÓM TẮT LUẬN VĂN TỐT NGHIỆP Nội dung của đồ án với đề tài Kỹ thuật nén số liệu mã hóa Số học được triển khai thành hai phần chính là phần thuyết minh và phần chương trình: * Phần thuyết minh gồm 6 chương được tổ chức như sau: Chương I: Giới thiệu thực trạng và sự cần thiết của nén số liệu. Chương II: Trình bày các kiến thức tổng quan, một số khái niệm và cấu trúc của quá trình nén số liệu. Chương III: Trình bày về các vấn đề liên quan của quá trình mã hóa. Triển khai các thuật toán với cấu trúc dữ liệu phù hợp để cài đặt trên ngôn ngữ lập trình bậc cao. Chương IV: Trình bày về cấu trúc dữ liệu và thuật toán của các mô hình từ và mô hình kí tự. Trình bày về mô hình bậc cao. Chương V: Trình bày về kết quả thực nghiệm đã tiến hành với các mô hình đã triển khai. So sánh kết quả với phương pháp nén khác. Chương VI: Kết luận, nêu những vấn đề đạt được, vấn đề chưa giải quyết và hướng phát triển của chương trình. * Phần chương trình gồm càc file nguồn và tệp thực thi. Các file nguồn viết trong môi trường C ở hệ điều hành Linux. Dựa theo thuật toán trình bày trong tài liệu [3].  MỤC LỤC TÓM TẮT LUẬN VĂN TỐT NGHIỆP..................................................................................1 MỤC LỤC 2 CHƯƠNG I CHƯƠNG I MỞ ĐẦU Ngày nay cùng với sự phát triển không ngừng của nền khoa học kỹ thuật thế giới là sự phát triển vượt bậc của ngành Công nghệ Thông tin nói chung và ngành Tin học nói riêng. Các hệ thống Tin học giúp ích rất nhiều trong công việc hàng ngày của các cơ quan, đơn vị tập thể hay mỗi cá nhân có liên quan. Các hệ thống Tin học còn giúp ta lưu trữ các thông tin cần thiết có liên quan đến công việc và đời sống hàng ngày. Mà ngày càng khối lượng thông tin cần lưu trữ tăng lên gấp bội chúng ta không còn không gian để lưu giữ chúng nữa. Một yêu cầu đặt ra là ta phải làm nhỏ lại không gian dành cho các thông tin đó. Với xu thế toàn cầu hóa, thì mạng Internet đã ra đời. Đây là một mạng của các mạng con trên thế giới. Qua mạng Internet ta có thể ngồi ở nhà liên lạc với các công ty, các đối tác làm ăn hay với bạn bè ở trên khắp thế giới. Qua mạng này ta có thể gửi đi và nhận về các thông tin cần thiết phục vụ cho cuộc sống hàng ngày. Khi gửi các thông tin đi mà ta để nguyên như vậy gửi đi thì tốn rất nhiều thời gian kèm theo đó là sự tốn kém về tiền bạc. Cùng với sự hoà nhập của Tin học vào các lĩnh vực đời sống thì việc xử lý các loại tập tin với các kiểu file khác nhau là điều tất yếu, và các tập tin này thường có kích thước lớn nên nhiều khi nó gây khó khăn cho công tác lưu trữ và truyền gửi. Vì vậy, khi lưu trữ hay truyền gửi người ta mong muốn giảm đến mức thấp nhất dung lượng bộ nhớ mà các tập tin này chiếm dụng để dễ tổ chức, quản lý và tiết kiệm về kinh phí. Để đáp ứng các yêu cầu nêu trên người ta đã nghĩ ra phương pháp làm cho các thông tin đó nhỏ lại nhằm chiếm dụng bộ nhớ ít hơn. Người ta gọi đó là kỹ thuật nén số liệu. Vậy nén số liệu là gì? Ở đây chúng ta có thể giới thiệu sơ qua về nén số liệu. Nén số liệu là quá trình giảm dung lượng nhớ cần thiết dành cho các tập tin mà vẫn biểu diễn cùng một lượng thông tin như trước. Có nhiều phương pháp nén khác nhau và chúng được thiết kế cho các loại dữ liệu khác nhau như hình ảnh, âm thanh, văn bản.v.v.. trong nội dung đồ án này chỉ bàn đến phương pháp dùng cho nén văn bản. Nén văn bản bao hàm thay đổi sự biểu diễn của tập tin so với không gian trống lấy được nhỏ hơn ở khối lượng dự trữ hoặc nhỏ hơn thời gian truyền tín hiệu, tuy nhiên nguyên bản chính của tập tin phải được khôi phục chính xác sau khi giải nén. Đã có rất nhiều phương pháp nén được phát minh và sử dụng trong nhiều năm qua. Khi thực hiện giải pháp nén số liệu chúng ta cần phải xem xét đến hai vấn đề trái ngược nhau: các thuật toán nén số liệu thực hiện trước hết phải đảm bảo giảm chi phí lưu trữ mà lại không sử dụng quá nhiều thời gian. Nguyên tắc chung của các phương pháp mã hoá đều dựa trên nhận xét loại bỏ việc lưu lại các thông tin trùng lặp. Các kỹ thuật nén không tổn hao thường được áp dụng cho các tập tin văn bản vì nó chứa các ký tự xuất hiện thường xuyên hơn các ký tự khác, và các thuật toán nén tổn hao thường áp dụng cho các tập tin ảnh vì nó có thể là các vùng đồng nhất, hay cho mô tả số của âm thanh và các ký hiệu tương tự khác. Đặc điểm của nén văn bản là dữ liệu của tệp tin gốc phải luôn luôn được khôi phục lại một cách chính xác sau khi giải nén. Một trong những phương pháp nén văn bản được biết sớm và đã thành công là nén Huffman, lần đầu tiên được phổ biến vào đầu những năm 1950. Phương pháp này tạo ra các từ mã khác nhau cho các kí hiệu đầu vào. Mã hóa Huffman được xem như một trong những phương pháp nén tốt trong nhiều thập kỷ, cho đến khi có bước đột phá về kỹ thuật nén vào cuối những năm bảy mươi là sự xuất hiện của phương pháp nén Mã hóa Số học. Mã hóa Số học ra đời vào thời gian này và được nghiên cứu phát triển bởi nhiều nhà nghiên cứu. Trong một thời gian dài từ những năm bảy mươi đến đầu những năm tám mươi, mã hóa Số học bị coi là phương pháp khó thực hiện bởi vì nó không tạo ra từng từ mã riêng lẻ cho từng ký hiệu mà chỉ tạo ra một từ mã duy nhất cho toàn bộ nguồn số liệu. Vì vậy nó không đòi hỏi số nguyên các bít để mã hóa ký hiệu. Ví dụ, ký tự s có xác suất xuất hiện là Pr[s] thì lượng thông tin chứa đựng trong nó là -logPr[s] bit (biểu thức này được định nghĩa là entropy của ký tự), giả sử xác suất xuất hiện của ký tự này là 99% thì Mã hóa Số học chỉ cần sử dụng 0,015 bit để mã hóa nhưng mã hóa Huffman phải sử dụng ít nhất là 1 bit để mã hóa ký tự này vì vậy người ta nói mã hóa Số học gần với entropy. Từ đây ta có thể nghĩ đến một tỉ số nén cao hơn cho nén văn bản khi áp dụng phương pháp mã hóa Số học. Sự công bố mã nguồn cho việc mã hóa nhiều kí hiệu được viết bởi Witten,Neal và Cleary trong tập Communication of ACM (CACM ). Với các vấn đề nêu trên và dựa vào tài liệu [3], trong đồ án này em đi sâu nghiên cứu về phương pháp mã hóa Số học. Đưa ra các mô hình khác nhau và kết quả thực tế của từng mô hình để người đọc lựa chọn. Chi tiết của các vấn đề sẽ được trình bày trong các chương tiếp theo của đồ án. CHƯƠNG II TỔNG QUAN VỀ NÉN SỐ LIỆU GIỚI THIỆU Nén số liệu là quá trình làm giảm số liệu cần thiết mà vẫn biểu diễn cùng một lượng thông tin như trước. Ở đây hai khái niệm số liệu và thông tin là khác nhau, ở đây số liệu là cái dùng để truyền tải thông tin. Dữ liệu sau khi nén phải được khôi phục lại giống hoàn toàn với lúc đầu. Cơ sở của nén số liệu là dựa vào các đặc trưng sau: Tính hữu hạn của tập ký hiệu. Tần số xuất hiện tương đối của các ký hiệu. Ngữ cảnh xuất hiện của các ký hiệu. Ví dụ 1: Để hiểu rõ tác dụng của nén ta xét ví dụ như sau: giả sử trong một đoạn văn có 50 chữ a, 30 chữ b, 20 chữ c, với mỗi kí tự là 1 bit thì ta tốn tổng cộng là 100 bit. Khi đó thay vì lưu 50 chữ a, 30 chữ b, 20 chữ c ta chỉ lưu 50a, 30b, 20c khi đó ta chỉ tốn 9 bit để lưu trữ tất cả chúng, như vậy ta tiết kiệm được 91 bit. PHÂN LOẠI CÁC KỸ THUẬT NÉN Dựa vào nguyên tắc nén ta có thể chia các kỹ thuật nén thành hai nhóm chính là nén tổn hao và nén không tổn hao. Nén tổn hao Nén tổn hao là kỹ thuật nén chấp nhận mất mát một lượng thông tin nhất định để đạt được hiệu quả nén cao, nén tổn hao thích hợp với các tập tin hình ảnh, âm thanh đã được số hoá. Theo bản chất việc biểu diễn thông tin tương tự dưới dạng số ngay từ đầu đã hàm chứa các sai số. Hầu hết các kỹ thuật nén tổn hao đều có thể được điều chỉnh để cân bằng giữa độ chính xác và hiệu quả nén. Đối với các thông tin bị mất mát không phải là vấn đề quan trọng bởi vì nó có thể được khôi phục lại. Do đó ở đây chúng ta chỉ quan tâm đến hiệu quả nén mà thôi. Nén tổn hao thường được thực hiện qua hai bước : Bước 1: Thực hiện xử lý số liệu trên toàn bộ nguồn số liệu, nó bao gồm việc biến đổi số liệu từ miền thời gian sang miền tần số. Sau đó nó tiến hành “làm trơn” số liệu bằng cách làm tròn, việc mất mát số liệu xảy ra ở giai đoạn làm tròn này. Bước 2: Tiến hành nén số liệu đã được biến đổi và làm trơn bằng các phương pháp nén không tổn hao quen thuộc. Ví dụ 2: Nếu ta dùng kỹ thuật nén tổn hao để nén câu văn “Trường Đại Học Kỹ Thuật Đà Nẵng” và nếu sau khi giải nén ta thu được “Trườn Đại Họ Kỹ Thuật Đà Nẵn” thì điều này là không thể chấp nhận được. Do đó ta không thể áp dụng kỹ thuật nén tổn hao để nén văn bản. Nén không tổn hao Nén không tổn hao là phương pháp nén đảm bảo không mất mát thông tin sau quá trình mã hoá và giải mã. Sau khi nén và giải nén thì nó phải tạo ra một bản sao chính xác so với lúc đầu. Kỹ thuật này sử dụng để lưu trữ và truyền các cơ sở dữ liệu, các bảng tính điện tử, các văn bản ....vì với các tập tin này thì việc mất mát dù chỉ một bit thông tin cũng là điều không thể chấp nhận được. Ví dụ, ta dùng kỹ thuật nén không tổn hao để nén câu văn “Trường Đại Học Kỹ Thuật Đà Nẵng” sau khi nén và giải nén ta phải thu được “Trường Đại Học Kỹ Thuật Đà Nẵng”. CÁC KHÁI NIỆM LIÊN QUAN ĐẾN NÉN SỐ LIỆU Sự phân bố của kí tự Trong chuỗi kí tự xuất hiện thì vài kí tự được xuất hiện nhiều lần còn vài kí tự thì xuật hiện ít hơn. Do đó khi mã hoá thì các kí tự xuất hiện nhiều ta sẽ mã hoá bằng từ mã ngắn còn kí tự xuất hiện ít ta sẽ mã hoá bằng các từ mã dài hơn. Sự lặp lại của những kí tự Khi xuất hiện thì có kí tự thường được lặp đi lặp lại nhiều lần. Có kí tự lại rất ít khi xuất hiện do vậy khi mã hoá ta có thể mã hoá cô động hơn bằng cách chỉ lưu các thuộc tính kí tự như: số lần lặp lại của kí tự, số kí tự đã xuất hiện. Độ dư thừa vị trí Nếu những kí tự nào đó xuất hiện ở một vị trí mà ta có thể đoán trước được thì khi mã hoá ta có thể sẽ giữ vị trí mà kí tự đó xuất hiện thay vì lưu trữ các kí tự đó. Đơn vị đo thông tin (Entropy) và độ dài trung bình của từ mã Đơn vị đo thông tin (Entropy): lý thuyết thông tin sử dụng thuật ngữ entropy là đơn vị đo thông tin được mã hoá trong một thông điệp. Entropy của một thông điệp càng cao thì thông tin nó chứa đựng càng nhiều. Giả sử rằng p là xác suất xuất hiện của kí hiệu thì entropy của nó sẽ là -log2p bit. Entropy của toàn bộ thông điệp là tổng entropy của các kí hiệu thành phần. Như vậy thì entropy sẽ phụ thuộc vào xác suất xuất hiện của kí hiệu. Một kí hiệu có xác suất xuất hiện cao thì thông tin chứa đựng trong nó thấp và cần ít bit hơn để mã hoá. Độ dài trung bình của từ mã: độ dài trung bình của từ mã là giá trị trung bình của tất cả các từ mã trong một bộ mã. Độ dài trung bình của từ mã không thể nào nhỏ hơn entropy của nguồn số liệu được mã hoá và do đó một bộ mã tối ưu là bộ mã có độ dài trung bình của từ mã gần với entropy của nguồn số liệu. Tỷ số nén Tỷ số nén là một đại lượng dùng để đánh giá hiệu quả của một phương pháp nén nào đó. Tỷ số nén là một đại lượng toán học ta có thể tính bằng công thức. Ngày nay tồn tại 2 quan niệm trái ngược nhau về cách tính tỷ số nén. Quan niệm thứ nhất tính tỷ số nén theo công thức: x 100 (%). Trong đó N1 kích thước file vào trước khi nén, N2 là kích thước của file ra sau khi nén. Đối với cách tính này: để đánh giá hiệu quả nén thì ta dựa vào CN : + Nếu CN càng nhỏ thì hiệu quả nén của phương pháp nén đó càng cao. + Nếu CN càng lớn thì hiệu quả nén của phương pháp nén đó càng thấp. Quan niệm thứ hai tính tỷ số nén theo công thức: x 100 (%). Đối với cách tính này thì CN càng lớn tức là phương pháp nén đó có hiệu quả nén cao và ngược lại tức là CN càng nhỏ thì hiệu quả nén càng thấp. Trong nội dung đồ án này em chọn cách tính theo quan niệm thứ nhất để tính tỷ số nén ở trong chương trình. cấu trúc của QUÁ TRÌNH NÉN SỐ LIỆU Quá trình nén số liệu bao gồm hai quá trình là mô hình hoá và mã hoá. Quá trình nén được minh hoạ bằng sơ đồ sau: Mô hình hoá Mã hóa Sự ước lượng xác suất Luồng kí hiệu đã được mã hoá Sự phân bố xác suất Luồng kí hiệu đầu vào Luồng kí hiệu đầu ra MÃ HÓA GIẢI MÃ Mô hình hoá Giải mã Sự ước lượng xác suất Sự phân bố xác suất Hình 1: Cấu trúc của quá trình nén số liệu (theo [5]) Mô hình hoá Khái niệm Mô hình là một tập hợp số liệu cùng các quy tắc được sử dụng để xử lý các ký hiệu đầu vào và đưa ra các từ mã tương ứng. Việc xác định một từ mã nhất định đối với một ký hiệu hoặc một tập hợp ký hiệu nhất định được thực hiện trên một mô hình (model). Một mô hình có nhiệm vụ xác định chính xác xác suất xuất hiện của từng ký hiệu và một bộ mã hoá sẽ tạo ra các từ mã cho các kí hiệu dựa trên các xác suất đó. Ở đây mô hình hoá và mã hoá là hai vấn đề hoàn toàn khác nhau, vì có rất nhiều cách để xây dựng mô hình cho một phương pháp mã hoá. Một phương pháp mã hóa có thể sử dụng nhiều mô hình khác nhau. Bậc của mô hình Công việc chính của mô hình hoá là tính xác suất xuất hiện của các kí hiệu ở đầu vào để cung cấp cho quá trình mã hoá. Do đó trong quá trình mô hình hoá đó ta phải tìm cách để nâng cao độ chính xác trong việc tính xác suất xuất hiện của các kí hiệu. Việc tính xác suất xuất hiện của các kí hiệu ta có thể dựa vào các kí hiệu đứng trước, ta gọi các kí hiệu đứng trước đó là ngữ cảnh, số lượng các kí hiệu đó có thể là khác nhau. Vậy bậc của mô hình chính là số kí hiệu đứng trước mà các kí hiệu này tạo thành ngữ cảnh. Việc tính xác suất xuất hiện dựa vào các kí hiệu đứng trước này sẽ mang lại độ chính xác cao và nhanh hơn. Do đó khi bậc của mô hình càng cao thì thì quả nén càng cao. Do vậy để nâng cao hiệu quả nén mà càng ngày người ta càng nâng cao hơn bậc của mô hình. Ngày nay thì bậc của mô hình có thể là 0, 1, 2, v.v... Phân loại mô hình Hiệu quả của quá trình nén phụ thuộc rất nhiều vào việc lựa chọn mô hình thích hợp. Hiện nay thì có hai loại mô hình phổ biến dùng cho nén số liệu là mô hình thống kê và mô hình từ điển. Sau đây ta xét đến từng loại mô hình đó: Mô hình từ điển: mô hình này làm việc theo cơ chế là đọc số liệu vào rồi tìm và so sánh với các kí hiệu đã có trong từ điển. Nếu tìm thấy nó sẽ trỏ đến kí hiệu đó. Ở đây hiệu quả nén sẽ phụ thuộc vào sự trùng lặp của các kí hiệu so với các kí hiệu đã có trong từ điển. Mô hình thống kê: mô hình này làm việc theo cơ chế mã hoá từng kí hiệu một dựa vào xác suất xuất hiện của từng kí hiệu đó. Sau mỗi lần xuất hiện thì xác suất xuất hiện của nó thay đổi. Với loại mô hình này ta lại có hai cách khác nhau là mô hình thống kê động và mô hình thống kê tĩnh. Mô hình thống kê tĩnh: làm việc theo cơ chế là xây dựng một bảng liệt kê các giá trị xác suất của nguồn kí hiệu. Do đó ta cần phải gửi thêm một lượng số liệu khác nữa cho bộ giải mã để giải mã thông điệp đó. Mô hình thống kê động: số liệu thống kê của nguồn số liệu không cần phải gửi đi trước mà nó sẽ liên tục được sữa đổi và tích luỹ dần trong quá trình tính toán sau đó của quá trình mã hoá. Nếu dựa vào kí hiệu đầu vào thì còn có các mô hình như mô hình từ và mô hình kí tự . Mô hình từ: ta xem đầu vào là các từ và các không từ xen kẽ nhau do đó mà nó trở thành các kí hiệu được nén. Với nén mô hình từ nó đặc biệt thích hợp cho dữ liệu là các văn bản lớn có vài chục nghìn từ. Bởi vì thông thường thì các từ thường được lưu trữ với mục đích để làm chỉ mục, do đó chỉ mục có thể được dùng như một phần của mô hình nén. Do đó nó mang lại hiệu suất nén cao hơn. Một văn bản thì có rất nhiều từ khác nhau và các từ đó được tạo thành từ một số kí hiệu nhất định. Mô hình kí tự: với mô hình này thì đầu vào là các kí tự do đó nó tốn thời gian hơn so với mô hình từ và hiệu quả nén sẽ thấp hơn so với mô hình từ nhưng bù lại nó dễ thực hiện hơn các mô hình khác. Bởi vì cái cơ bản nhất của một văn bản đó chính là các kí tự. Mã hoá Khái niệm Mã hoá là nhiệm vụ quyết định việc biểu diễn đầu ra của một kí hiệu dựa trên sự phân chia xác suất được cung cấp bởi mô hình. Hiện nay có nhiều phương pháp mã hoá khác nhau nhưng được sử dụng rộng rãi nhất vẫn là mã hoá Huffman và mã hoá Số học. Các phương pháp mã hoá: Mã hoá Huffman Phương pháp này dựa vào xác suất xuất hiện của kí hiệu được xây dựng bởi mô hình để mã hoá. Phương pháp này mã hoá một kí hiệu bằng một từ mã riêng biệt. Nếu kí hiệu có xác suất xuất hiện cao thì gán cho kí hiệu đó từ mã ngắn, và ngược lại tức là gán cho kí hiệu có xác suất xuất hiện thấp từ mã dài hơn. Ở đây từ mã là một số nguyên các bit. Với phương pháp này để xây dựng mã ta sử dụng cấu trúc cây nhị phân. Các nút lá của cây là các kí hiệu, các nút lá này có trọng lượng là tần số hoặc xác suất xuất hiện của các kí hiệu. Quá trình xây dựng cây tiến hành qua các bước như sau: Bước 1: xác định 2 nút lá có trọng lượng nhỏ nhất tức là các kí hiệu có xác suất xuất hiện nhỏ nhất. Bước 2: xây dựng nút cha của 2 nút con này với trọng lượng của nút cha là tổng trọng lượng của 2 nút con cộng lại. Bước 3: lúc này nút cha được xem như là một nút lá, và nó được bổ sung vào danh sách các nút lá, còn các nút con đã xét thì được đánh dấu là đã xét. Bước 4: đánh dấu một trong hai nút lá là “0” thì nút còn lại là “1”. Để thuận lợi cho việc đánh dấu “0” hay “1" ta qui ước rằng nút trái ta sẽ đánh dấu là “0” còn nút phải là “1”. Bước 5: lặp lại các bước trên cho đến khi chỉ còn một nút lá thì nút này chính là nút gốc của cây nhị phân ta vừa xây dựng. Ví dụ 3: Để hiểu rõ hơn quá trình làm việc của mã hóa Huffman ta xét ví dụ như sau. Giả sử ta có một thông điệp đầu vào gồm các kí tự và xác suất xuất hiện của mỗi kí hiệu cho như trong bảng dưới đây: Kí tự A B C D E G Xác suất xuất hiện 20 18 15 10 6 5 Bảng 1: Xác suất xuất hiện của các kí hiệu Ta tiến hành theo các bước trên để xây dựng cây nhị phân cho ví dụ này. Ban đầu thì cả sáu nút đều là các nút tự do tức là các nút lá. Đầu tiên ta tìm được hai nút lá có trọng lượng nhỏ nhất là E và G có trọng lượng lần lượt là 6 và 5. Hai nút này kết hợp với nhau tạo thành nút cha có trọng lượng là 11 lúc này nút cha được xem là nút lá và ta đánh dấu là đã xét các nút này rồi. Khi đó ta có nút E được đánh dấu là “0” còn nút G được đánh dấu là “1”. A 20 18 15 10 6 5 0 11 21 0 1 1 B C D E G Tiếp tục quá trình trên ta có các nút D và nút cha vừa tạo thành và các nút có trọng lượng nhỏ nhất lần lượt là 10 và 11. Khi đó ta có nút cha mới tạo thành từ hai nút này có trọng lượng là 21. Khi đó các nút đã xét qua ta đánh dấu là đã xét rồi. Tại thời điểm này ta có cây nhị phân như sau: Hình 2: Cây Huffman sau hai bước 1 1 1 0 1 0 0 0 0 41 74 11 21 18 15 20 10 6 5 1 33 Gốc 0 A B C D E G Ở các bước tiếp theo hai nút có trọng lượng nhỏ nhất là B và C được nối với nhau tạo thành nút cha có trọng lượng là 33. Sau bước này các nút có trọng lượng nhỏ nhất là nút A và nút cha được tạo thành sau bước thứ hai tức là nút có trọng lượng là 21và chúng kết hợp với nhau tạo thành nút cha mới có trọng lượng là 41. Cuối cùng là chỉ còn lại hai nút cha có trọng lượng lần lượt là 33 và 41 và chúng kết hợp với nhau tạo thành nút cha mới có trọng lượng là 74. Cuối cùng đây là nút cha duy nhất và ta đã hoàn thành việc xây dựng cây Huffman cho việc mã hóa. Kết quả cuối cùng của quá trình thực hiện được thể hiện bằng cây như hình vẽ dưới đây. Hình 3 Cây Huffman hoàn chỉnh Để đưa ra từ mã cho các kí hiệu chúng ta phải đi từ các nút lá đến gốc của cây Huffman. Tuy nhiên các bước trả về phải ngược lại với từ mã nên ta phải đặt chúng vào ngăn xếp để khi lấy ra thì theo thứ tự ngược lại và cho ta từ mã của các kí tự . Kết quả đưa ra các từ mã cho các kí hiệu trong thông điệp ở trên như sau: Kí tự A B C D E G Từ mã 10 00 01 110 1110 1111 Bảng 2: Bảng liệt kê các từ mã của các kí hiệu sau khi mã hóa Qua đây ta thấy rằng mã hóa Huffman sử dụng một số nguyên các bit cho một từ mã. Nhưng việc thực hiện mã hóa và giải mã của nó không quá phức tạp, không yêu cầu nhiều thời gian thực hiện cũng như bộ nhớ nên ngay từ lúc công bố nó đã được mọi người chấp nhận và yêu thích nó. Mã hóa Số học Ngay từ khi ra đời phương pháp này không mang tính khả thi vì nó phức tạp về mặt khái niệm lẫn việc thực hiện nó trong thực tế. Khi thực hiện phương pháp này nó yêu cầu bộ nhớ có dung lượng lớn, thới gian thực hiện lâu nên trong một thời gian dài nó vẫn chỉ mang tính thử nghiệm ở trong các cuộc thí nghiệm và nghiên cứu.