Tài liệu Khai thác mẫu tuần tự nén

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC CÔNG NGHỆ TP. HCM --------------------------- TRỊNH MINH SỸ KHAI THÁC MẪU TUẦN TỰ NÉN LUẬN VĂN THẠC SĨ Chuyên ngành : Công Nghệ Thông Tin Mã số ngành: 60480201 TP. HỒ CHÍ MINH, tháng 10 năm 2015 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC CÔNG NGHỆ TP. HCM ----------oOo---------- TRỊNH MINH SỸ KHAI THÁC MẪU TUẦN TỰ NÉN LUẬN VĂN THẠC SĨ Chuyên ngành : Công Nghệ Thông Tin Mã số ngành: 60480201 CÁN BỘ HƯỚNG DẪN KHOA HỌC: PGS.TS. LÊ HOÀI BẮC TP. HỒ CHÍ MINH, tháng 10 năm 2015 CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ TP. HCM Cán bộ hướng dẫn khoa học : PGS.TS. LÊ HOÀI BẮC Luận văn Thạc sĩ được bảo vệ tại Trường Đại học Công nghệ TP. HCM ngày 17 tháng 10 năm 2015 Thành phần Hội đồng đánh giá Luận văn Thạc sĩ gồm: TT Họ và tên Chức danh Hội đồng 1 PGS.TS. Nguyễn Xuân Huy Chủ tịch 2 PGS.TS. Quản Thành Thơ Phản biện 1 3 TS. Nguyễn Thị Thúy Loan Phản biện 2 4 TS. Võ Đình Bảy 5 TS. Cao Tùng Anh Ủy viên Ủy viên, Thư ký Xác nhận của Chủ tịch Hội đồng đánh giá Luận Văn sau khi Luận Văn đã được sửa chữa (nếu có). Chủ tịch Hội đồng đánh giá LV TRƯỜNG ĐH CÔNG NGHỆ TP. HCM CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM PHÒNG QLKH – ĐTSĐH Độc lập – Tự do – Hạnh phúc TP. HCM, ngày 03 tháng 04 năm 2015 NHIỆM VỤ LUẬN VĂN THẠC SĨ Họ tên học viên:TRỊNH MINH SỸ. Giới tính: Nam Ngày, tháng, năm sinh: 07/10/1960 Nơi sinh: Bình Định Chuyên ngành:Công Nghệ Thông Tin MSHV: 1341860052 I- Tên đề tài: KHAI THÁC MẪU TUẦN TỰ NÉN II- Nhiệm vụ và nội dung: Mã hóa dữ liệu tuần tự bằng cách gán các codeword đối với các khoảng cách nhỏ, rồi từ đó tiến hành xử lý trên mẫu với khoảng cách lớn hơn. Tính toán độ phức tạp của quá trình khai phá mẫu nén trên cơ sở dữ liệu tuần tự. Nghiên cứu thuật toán GoKrimp để khai phá trực tiếp trên mẫu đã được nén dựa trên thuật toán tham lam. Tiến hành thực nghiệm trên các bộ dữ liệu khác nhau và đánh giá kết quả, đề xuất cải tiến. III- Ngày giao nhiệm vụ: 03/04/2015 IV - Ngày hoàn thành nhiệm vụ: 07/09/2015 V - Cán bộ hướng dẫn: Phó Giáo Sư. Tiến Sĩ. Lê Hoài Bắc CÁN BỘ HƯỚNG DẪN KHOA QUẢN LÝ CHUYÊN NGÀNH i LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các số liệu, kết quả nêu trong Luận văn là trung thực và chưa từng được ai công bố trong bất kỳ công trình nào khác. Tôi xin cam đoan rằng mọi sự giúp đỡ cho việc thực hiện Luận văn này cũng như các trích dẫn hay tài liệu học thuật tham khảo đã được cảm ơn đến tác giả và các thông tin trích dẫn trong Luận văn đã được chỉ rõ nguồn gốc. Học viên thực hiện Luận văn Trịnh minh Sỹ ii của Thầy PGS.TS. Lê Hoài Bắc. ớng dẫn và giúp đỡ tận tình ầy/Cô Khoa Công Nghệ Thông Tin Đại Học Công Nghệ TP. HCM, các bạn học cùng lớp LỜI CÁM ƠN iii TÓM TẮT Khai thác mẫu tuần tự đóng đối với dữ liệu dạng văn bản đã được áp dụng thành công trong nhiều bài toán khác nhau của khai thác dữ liệu. Tuy nhiên, kết quả khai thác vẫn còn một số mặt hạn chế như: - Vấn đề dư thừa của mẫu đã trích ra. - Mẫu trích ra bị trùng lắp. - Một số mẫu tối nghĩa. Để khắc phục những mặt hạn chế trên, ý tưởng dựa trên nguyên lý mô tả chiều dài tối thiểu (MDL minimum description length) được đề xuất nhằm khai thác mẫu tuần tự nén đối với cơ sở dữ liệu tuần tự. Với dữ liệu là itemset, thuật toán Krimp [7] dựa trên mô tả chiều dài tối thiểu đã tỏ ra khá hiệu quả trong việc giải quyết vấn đề dư thừa của mẫu, trích ra những mẫu ít trùng lắp và dễ hiểu hơn. Với dữ liệu tuần tự, đề tài đề xuất hai thuật toán SeqKrimp và GoKrimp. Trong đó, thuật toán chính của đề tài là GoKrimp. • SeqKrimp là thuật toán khai thác mẫu nén gồm hai pha: -Pha thứ nhất: lấy những mẫu tuần tự đóng bởi hàm GetCandidate() đã có. -Pha thứ nhì: từ những mẫu tuần tự đóng đã lấy ở trên chọn lại chỉ còn những mẫu nén dữ liệu tốt nhất. Vậy mẫu nén dữ liệu như thế nào là tốt nhất? Đề tài nghiên cứu hai phần: -Cách thức nén dữ liệu: chọn nén dữ liệu theo phương pháp mã hóa Huffman[3], xây dựng cây nhị phân để mã hóa, cây nhị phân như vậy sẽ thỏa tính chất mã tiền tố nghĩa là không có từ mã nào là phần đầu của từ mã khác. -Hiệu quả nén: là hiệu số giữa số bit trước khi nén và sau khi nén dữ liệu. iv • GoKrimp là thuật toán khai thác trực tiếp mẫu nén, khác với SeqKrimp ở pha thứ nhất, nghĩa là, thuật toán không lấy mẫu tuần tự đóng đã có sẵn mà khai thác trực tiếp mẫu từ tập các từ phổ biến ban đầu. Từ đó dùng thuật toán tham lam nới rộng mẫu nhưng tránh không duyệt hết mọi trường hợp để nới rộng nhờ một kỹ thuật kiểm tra sự kiện liên quan đến mẫu. Sau cùng nghiên cứu thực nghiệm trên tám tập dữ liệu để chỉ ra rằng GoKrimp tỏ ra hiệu quả nhất. So sánh GoKrimp với các thuật toán như SeqKrimp, BIDE, SQS để thấy ưu điểm ở các tính chất: dễ hiểu, thời gian thực thi, tỉ lệ nén và độ chính xác sự phân lớp. v ABSTRACT Mining closed sequential pattern in text data has been successfully applied in many different problems of data mining. However, the mining result still has some drawbacks, include: - The problem of redundancy extracted patterns. - The duplication of extracting patterns. - The existing of ambiguous patterns. To overcome the above drawbacks, the approach that is based on the principles of the minimum description length (MDL) to exploit sequential pattern compression in sequence databases. For the itemset, Krimp [7] was based on the minimum description length that has proved quite effective in solving the problem of redundant patterns. Thus, it extracts less duplicate patterns and easier to understand. For the sequence data, the thesis proposed two algorithms, include SeqKrimp and GoKrimp. In which, GoKrimp is the main contribution. • SeqKrimp mine the compressed pattern that consists of two phases: The first phase: get the closed sequential pattern by using the exist GetCandidate() function. The second phase: reselect the best compressed patterns from the closed sequential patterns. Our work concentrates on how is the best compressed pattern which includes two parts: - The data compression method: apply the data compression Huffman encoding method[3], built a binary tree for encoding which satisfies the prefixed code vi property. That means there is no word code is the beginning part of others word codes. -Effective compression: The difference between the number bits of data before and after the compression. • GoKrimp allows to mine the compressed patterns directly. It differs from the first phase of SeqKrimp, i.e., The algorithm mines the patterns directly from the set of initial frequent patterns. The greedy algorithm then is used to extend the patterns. The algorithm avoids to scan all of cases by applying a related events checking technique. Finally, the experimental studies are conducted on eight datasets to show the efficiency of GoKrimp. The comparisons with SeqKrimp, Bide, SQS to demonstrate the advantages of GoKrimp in the following characteristics: easy to understand, real-time enforcement, compression ratio, and accuracy classification. vii MỤC LỤC CHƯƠNG 1 GIỚI THIỆU ĐỀ TÀI ............................................................................ 1 1.1. ĐẶT VẤN ĐỀ.................................................................................................. 1 1.2. MỤC TIÊU, NỘI DUNG VÀ PHƯƠNG PHÁP NGHIÊN CỨU ................... 3 1.2.1. Mục tiêu của đề tài .................................................................................... 3 1.2.2. Nội dung nghiên cứu ................................................................................. 3 1.2.3. Phương pháp luận và phương pháp nghiên cứu ........................................ 4 1.3. Ý TƯỞNG NÉN DỮ LIỆU ............................................................................. 4 CHƯƠNG 2 CƠ SỞ LÝ THUYẾT ............................................................................ 6 2.1. MÃ HUFFMAN ............................................................................................... 6 2.1.1. Mã tiền tố .................................................................................................. 6 2.1.2. Cây nhị phân biểu diễn từ mã ................................................................... 6 2.2. KHAI THÁC MẪU TUẦN TỰ NÉN.............................................................. 8 2.2.1. Khai thác mẫu tuần tự đóng ...................................................................... 8 2.2.2. Nguyên lý nén dữ liệu ............................................................................... 8 2.3. PHƯƠNG PHÁP MÃ HÓA DỮ LIỆU ........................................................... 9 2.3.1. Mã hóa và giải mã số tự nhiên .................................................................. 9 2.3.2. Phương pháp nén và hiệu quả nén .......................................................... 10 2.4. MÃ HÓA VÀ GIẢI MÃ MỘT DÃY CÁC TỪ............................................. 11 2.5. BÀI TOÁN TÌM MẪU NÉN ......................................................................... 14 2.5.1. Định nghĩa (Bài toán nén dãy) [4] .......................................................... 14 2.5.2. Kết luận ................................................................................................... 15 CHƯƠNG 3 THUẬT TOÁN KHAI THÁC MẪU NÉN ......................................... 16 3.1. THUẬT TOÁN SEQKRIMP ......................................................................... 16 3.1.1. Thuật toán lấy mẫu tuần tự đóng GetCandidate() ................................... 16 3.1.2. Thuật toán so khớp với chi phí tối thiểu MinGapMatch [4] ................... 17 3.1.3. Thuật toán tính hiệu quả nén Compress [4] ............................................ 19 3.1.4. Thuật toán khai thác mẫu nén SeqKrimp [4] .......................................... 21 viii 3.2. THUẬT TOÁN GOKRIMP ........................................................................... 23 3.2.1. Kiểm tra sự kiện có liên quan ................................................................. 23 3.2.2. Thuật toán nới rộng mẫu GetNextPattern [4] ......................................... 25 3.2.3. Thuật toán khai thác trực tiếp mẫu nén GoKrimp [4] ............................. 26 CHƯƠNG 4 THỰC NGHIỆM VÀ KẾT LUẬN...................................................... 30 4.1. BỘ DỮ LIỆU THỬ NGHIỆM ....................................................................... 32 4.1.1. Bộ dữ liệu JMLR ..................................................................................... 32 4.1.2. Bộ dữ liệu Parallel ................................................................................... 33 4.2. THỜI GIAN THỰC THI ............................................................................... 34 4.3. ĐỘ CHÍNH XÁC PHÂN LỚP ...................................................................... 35 4.4. TÍNH NÉN ..................................................................................................... 38 4.5. HIỆU LỰC CỦA SỰ KIỆN LIÊN QUAN .................................................... 41 4.6. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ..................................................... 42 ix DANH MỤC BẢNG Bảng 1.1 Mẫu tuần tự đóng [4] ................................................................................ 2 Bảng 2.1 Mã Alias [4] ................................................................................................ 9 Bảng 2.2 Cách mã hóa và hiệu quả nén ................................................................ 10 Bảng 4.1 Mẫu tuần tự đóng[4] ............................................................................... 30 Bảng 4.2 Bộ dữ liệu[4] ............................................................................................. 31 Bảng 4.3 Thời gian thực thi và số mẫu trích[4] .................................................... 34 Bảng 4.4 Phân lớp[4] ............................................................................................... 36 Bảng 4.5 So sánh tỉ lệ nén[4] .................................................................................. 41 Bảng 4.6 Tỉ lệ nén với kiểm tra dấu[4] .................................................................. 42 x DANH MỤC HÌNH Hình 2.1 Cây nhị phân mã Huffman ........................................................................... 7 Hình 3.1 So khớp khoảng cách tối thiểu[4] .............................................................. 18 Hình 3.2 Kiểm tra sự kiện liên quan ......................................................................... 24 Hình 4.1 Kết quả phân lớp[4] ................................................................................... 37 Hình 4.2 Hiệu quả nén[4] ......................................................................................... 39 1 CHƯƠNG 1 GIỚI THIỆU ĐỀ TÀI 1.1. ĐẶT VẤN ĐỀ Vấn đề khai thác mẫu tuần tự phổ biến từ cơ sở dữ liệu tuần tự đã được ứng dụng thành công trong lĩnh vực khai thác dữ liệu. Trong những năm gần đây nhiều công trình khai thác mẫu tuần tự đóng đã đóng góp nhiều ứng dụng cụ thể cho lĩnh vực khai thác dữ liệu. Tuy vậy khi quan sát Bảng 1.1[4] chỉ ra 20 mẫu tuần tự phổ biến đóng được trích ra từ tập dữ liệu Journal of Machine Learning Research (JMLR), bộ dữ liệu này chứa cơ sở dữ liệu của 787 cụm từ, mỗi cụm từ tương ứng với tóm tắt của một bài báo trong JMLR có nhận xét rằng: - Mẫu trùng lắp mặc dù có độ hỗ trợ cao ví như mẫu algorithm algorithm - Mẫu tối nghĩa ví như hai mẫu learn algorithm và algorithm learn nếu mẫu này có nghĩa thì mẫu kia tối nghĩa - Mẫu dư thừa, rườm rà ví như mẫu algorithm algorithm algorithm Qua quan sát trên rút ra nhận xét rằng có những mẫu có độ hỗ trợ cao nhưng lại xãy ra tình trạng mẫu trùng lắp, tối nghĩa, dư thừa không đáng quan tâm. Để khắc phục tình trạng trên, đưa ra một ý tưởng mới là khai thác những mẫu dùng để nén bộ dữ liệu và ý tưởng này cơ sở dựa trên thuật toán Krimp[7], thuật toán khai thác mẫu nén đối với bộ dữ liệu là các tập mục (itemset). Cơ sở của thuật toán Krimp là tính hiệu quả nén đó là số bit lợi được trước và sau khi nén, nguyên lý này gọi là nguyên lý mô tả chiều dài tối thiểu MDL (minimum description length). 2 Bảng 1.1 Mẫu tuần tự đóng [4] Pattern algorithm algorithm learn learn learn algorithm algorithm learn data data learn data model model problem problem learn result problem algorithm Support 0.376 0.362 0.356 0.288 0.244 0.263 0.260 0.258 0.255 0.251 Pattern method method algorithm result data set learn learn learn learn prolem learn method algorithm data learn set problem learn algorithm algorithm algorithm Support 0.250 0.247 0.244 0.241 0.239 0.229 0.229 0.228 0.227 0.222 20 mẫu tuần tự phổ biến đóng không đơn từ bộ dữ liệu tóm tắt JMLR. Đối với dữ liệu tuần tự, khác với dữ liệu là các tập mục và đặc biệt dữ liệu tuần tự dạng văn bản thì thứ tự các từ khác nhau mang nghĩa khác nhau cho nên việc khai thác mẫu tuần tự phải càng tránh trùng lắp, tối nghĩa hay ngược nghĩa, dư thừa. Tiếp theo ý tưởng khai thác mẫu nén, đối với mẫu tuần tự dưa ra hai thuật toán: Thuật toán SeqKrimp: gồm hai giai đoạn - Giai đoạn một lấy những mẫu tuần tự đóng đã có. - Chọn những mẫu nén tốt nhất trích ra. Thuật toán GoKrimp: cũng gồm hai giai đoạn - Giai đoạn một tự nới rộng mẫu để tìm mẫu. - Giai đoạn hai chọn những mẫu nén tốt nhất trích ra. Với hai thuật toán trên thì GoKrimp tỏ ra hiệu quả hơn và là thuật toán chính của đề tài. 3 1.2. MỤC TIÊU, NỘI DUNG VÀ PHƯƠNG PHÁP NGHIÊN CỨU 1.2.1. Mục tiêu của đề tài Mục tiêu đề tài là đi tiếp theo của ý tưởng MDL (mô tả chiều dài tối thiểu) để đưa ra đặc tả ngữ cảnh của dữ liệu tuần tự. Và đặc biệt trọng tâm là việc lấy ý tưởng MDL để khám phá mẫu tuần tự nén đáng quan tâm, có nghĩa và khả dụng. 1.2.2. Nội dung nghiên cứu Trong phạm vi này nghiên cứu giải thuật dựa trên nguyên lý MDL để giải quyết vấn đề dư thừa và tìm ra các mẫu có nghĩa, đáng quan tâm và khả dụng. Có thể tóm tắt công việc trong bốn chương như sau: Chương 1: Giới thiệu đề tài Giới thiệu đề tài, nghiên cứu các vấn đề liên quan trong vài năm gần đây, những kết quả đạt được và những mặt hạn chế như là việc trích ra những mẫu dư thừa và tối nghĩa. Đồng thời đưa ra cách hạn chế những khắc phục trên, nghiên cứu mô hình nén dữ liệu đối với cơ sở dữ liệu tuần tự để làm cho mẫu được trích ra sáng tỏ hơn, đáng quan tâm hơn. Chương 2: Cơ sở lý thuyết Nghiên cứu mô hình mã hóa dữ liệu tuần tự, mã Huffman, mã Elias từ đó tính hiệu quả nén dữ liệu với phương thức chọn mẫu nén, cách giải mã. Tính toán độ phức tạp của quá trình khai phá mẫu nén trên cơ sở dữ liệu tuần tự. Kết quả chỉ ra rằng đây là bài toán có độ phức tạp cấp NP-khó và thuộc lớp bài toán không thể xấp xỉ, không thể duyệt hết mọi trường hợp. Chương 3: Thuật toán khai thác mẫu nén Nghiên cứu thuật toán SeqKrimp, là thuật toán lấy ứng viên của mẫu tuần tự đóng rồi chọn các mẫu nén có hiệu quả nén cao, thuật toán gồm hai pha, pha thứ nhất lấy những mẫu tuần tự đóng bằng các thuật toán trước đó sau đó từ những mẫu đóng chọn những mẫu nén tốt trích ra,thuật toán này lấy ý tưởng từ thuật toán Krimp. 4 Nghiên cứu thuật toán GoKrimp để khai phá trực tiếp trên mẫu nén dựa trên thuật toán tham lam, nới rộng mẫu bởi các sự kiện có liên quan bằng phương thức kiểm tra phụ thuộc, thử dấu rồi chọn mẫu có hiệu quả nén dương cao nhất đưa vào từ điển, trích ra mẫu nén. Trong mỗi thuật toán, giải thích ý nghĩa của thuật toán và có ví dụ minh họa từng bước giải quyết của thuật toán đi kèm. Chương 4: Thực nghiệm và kết luận. Tiến hành thực nghiệm trên các 8 bộ dữ liệu khác nhau và đánh giá kết quả, trong đó xem xét đến bốn tính chất là tính dễ hiểu, tính phân lớp, tính nén và thời gian thực thi. Tóm tắt công việc đã nghiên cứu, những việc đã đạt được, đề xuất cho những việc sắp tới. 1.2.3. Phương pháp luận và phương pháp nghiên cứu 1.2.3.1. Phương pháp luận Nghiên cứu về lý thuyết các thuật toán có liên quan đến đề tài cùng với các khái niệm đi kèm, trong mỗi thuật toán giải thích ý nghĩa, cho ví dụ minh họa từng bước giải quyết của thuật toán. 1.2.3.2. Phương pháp nghiên cứu Đọc hiểu về lý thuyết cách mã hóa dữ liệu, tìm chọn mô hình mã hóa tối ưu dữ liệu, từ đó sẽ cho hiệu quả nén tốt để kết quả đưa ra những mẫu dễ hiểu hơn, giảm dư thừa và khả dụng. 1.3. Ý TƯỞNG NÉN DỮ LIỆU Đối với dữ liệu tuần tự dạng văn bản, để trích ra những mẫu hay những cụm từ với mong muốn cụm từ đó là đại diện cho một đoạn văn, là đặc trưng cho cho một dãy các từ thì một cách trực quan ta nhận thấy rằng những cụm từ nào xuất hiện nhiều lần trong đoạn văn bản đó thì có thể là một mẫu tuần tự đáng quan tâm. 5 Xuất hiện nhiều lần nhưng cách xuất hiện liên tục hay rời rạc thì mỗi cách xuất hiện mang ý nghĩa khác nhau, xuất hiện liên tục ví như mẫu abcd nằm liền nhau trong dãy thì mẫu đó có thể là đại diện cho dãy còn ngược lại mẫu abcd nằm rời rạc nhau mỗi từ cách nhau khá nhiều khoảng trống (gap) như nằm trong dãy S=ca__b___c____d_____. thì mẫu đó thường là mẫu tối nghĩa, khó hiểu không đáng quan tâm. Vậy ý tưởng nén dữ liệu là gom các mẫu xuất hiện nhiều lần trong dãy lại thành một từ ta gọi là từ không đơn, đưa vào trong từ điển và mã hóa thành một từ mã dùng nó nén dãy hay nén dữ liệu. Những mẫu có các từ nằm rời rạc nhau thì phạt khoảng trống, với khoảng trống nhỏ tương ứng với từ mã có chiều dài ngắn và khỏang trống lớn thì tăng đột biến chiều dài từ mã VÍ DỤ: Khoảng cách 1 nghĩa là nằm liền nhau thì mã hóa là 1 vậy E(1)=1. Khoảng cách 8 nghĩa là nằm cách nhau 8 khoảng trống thì mã hóa là 0001000 vậy E(8)=7. Tóm lại nén dữ liệu là tìm ra những mẫu nén tốt nhất. Nén tốt nhất căn cứ theo hiệu quả nén đó là hiệu số tính theo bit của mô tả chiều dài dữ liệu trước và sau khi nén. 6 CHƯƠNG 2 CƠ SỞ LÝ THUYẾT 2.1. MÃ HUFFMAN Đối với bài toán tìm mẫu nén tốt cho cơ sở dữ liệu tuần tự đặc biệt đối với dữ liệu dạng văn bản tốt nhất là dùng phương pháp mã hóa Huffman để nén dữ liệu. Mã hóa Huffman là một thuật toán mã hóa dùng để nén dữ liệu. Nó dựa trên bảng tần suất xuất hiện các kí tự cần mã hóa để xây dựng một bộ mã nhị phân cho các kí tự đó sao cho dung lượng (số bít) sau khi mã hóa là nhỏ nhất. Để mã hóa dữ liệu văn bản ta dùng các chuỗi nhị phân để mã hóa các từ. Trong một đoạn văn bản hay còn gọi là dãy các từ ta tính xem trong dãy đó có bao nhiêu từ khác nhau và tính tần suất của các từ đi kèm. Phương pháp mã Huffman là phương pháp có các tính chất cơ bản sau: 2.1.1. Mã tiền tố Là bộ các từ mã của một tập hợp các kí hiệu sao cho từ mã của mỗi ký hiệu không là tiền tố (phần đầu) của từ mã một ký hiệu khác trong bộ mã. VD -Hai từ mã 101 và 1011 thì từ mã trước nằm ở phần đầu của từ mã sau do đó không có tính chất của mã tiền tố. -Hai từ mã sau 10 và 110 là hai từ mã thỏa tính chất mã tiền tố vì không có từ mã nào là tiền tố của từ mã còn lại. 2.1.2. Cây nhị phân biểu diễn từ mã Giả sử có n từ, ta ký hiệu w1, w2,…, wn có các tần suất tương ứng t1, t2,…, tn. Phương pháp mã hóa Huffman là phương pháp mã hóa sao cho chiều dài từ mã tỉ lệ nghịch với tần suất. Với phương pháp nầy xây dựng cây nhị phân n lá và tạo một bộ