Tài liệu Tìm hiểu và phát triển kỹ thuật truyền tin theo hướng biến đổi dữ liệu

i ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG HOÀNG PHƯƠNG THẢO TÌM HIỂU VÀ PHÁT TRIỂN KỸ THUẬT TRUYỀN TIN THEO HƯỚNG BIẾN ĐỔI DỮ LIỆU LUẬN VĂN THẠC SỸ KHOA HỌC MÁY TÍNH THÁI NGUYÊN - 2016 ii ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG HOÀNG PHƯƠNG THẢO TÌM HIỂU VÀ PHÁT TRIỂN KỸ THUẬT TRUYỀN TIN THEO HƯỚNG BIẾN ĐỔI DỮ LIỆU CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH MÃ SỐ CHUYÊN NGÀNH: 60 48 01 01 LUẬN VĂN THẠC SỸ: KHOA HỌC MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC PGS TSKH NGUYỄN XUÂN HUY THÁI NGUYÊN - 2016 i LỜI CAM ĐOAN Tôi xin cam đoan rằng các kết quả nghiên cứu được trình bày trong luận văn này là hoàn toàn mới, do bản thân tôi tự làm, dưới sự hướng dẫn của PGS.TSKH Nguyễn Xuân Huy. Các số liệu và kết quả nêu trong luận văn là trung thực, có nguồn trích dẫn và chưa từng được tác giả nào khác công bố trong bất kì công trình nào khác. Thái Nguyên, ngày 12 tháng 5 năm 2016 HỌC VIÊN Hoàng Phương Thảo ii LỜI CẢM ƠN “ Người thầy vẫn lặng lẽ đi về sớm trưa. Từng ngày giọt mồ hôi rơi đầy trang giấy … Thầy vẫn đứng bên sân trường năm ấy. Dõi theo bước em trong cuộc đời. Dẫu đếm hết sao trời đêm nay. Dẫu đếm hết lá mùa thu rơi. Nhưng ngàn năm, làm sao em đếm hết công ơn người thầy”. Trích ca khúc “Người thầy” sáng tác Nguyễn Nhất Huy Em xin được gửi lời cảm ơn sâu sắc tới thầy PGS.TSKH Nguyễn Xuân Huy Viện Công nghệ thông tin người đã dẫn dắt và định hướng cho em tìm hiểu và phát triển về lĩnh vực biến đổi thông tin trong kỹ thuật truyền tin. Thầy đã luôn tận tình giúp đỡ, giảng giải cho em trong mỗi bài học để em có thể nghiên cứu và hoàn thành luận văn này. Em trân trọng gửi lời cảm ơn đến các thầy cô trong và ngoài nhà trường đã cung cấp kiến thức, tài liệu học tập, tài liệu tham khảo và luôn tạo điều kiện thuận lợi cho quá trình học tập, rèn luyện của bản thân em. Em xin cảm ơn các Phòng, Ban, Khoa, đặc biệt là Khoa sau đại học trường Đại học Công nghệ thông tin và truyền thông Thái Nguyên đã hỗ trợ, hướng dẫn em trong suốt quá trình học tập, kể từ ngày đầu nhập học cho đến hôm nay. Sau cùng, em xin gửi lời cảm ơn sâu sắc tới gia đình, Ban lãnh đạo trường Cao đẳng nghề Hòa Bình, các bạn học cùng lớp, các bạn đồng nghiệp đã giúp đỡ về vật chất, động viên về tinh thần, dành thời gian cho em tham gia khóa học cùng lo lắng, chia sẻ vui buồn với em trong quãng thời gian em đi học. Thái Nguyên, ngày 12 tháng 5 năm 2016 HỌC VIÊN Hoàng Phương Thảo iii MỤC LỤC LỜI CAM ĐOAN .....................................................................................................i LỜI CẢM ƠN .........................................................................................................ii MỤC LỤC ............................................................................................................ iii DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT ............................................ v DANH SÁCH CÁC BẢNG BIỂU .......................................................................... vi DANH SÁCH CÁC HÌNH ẢNH..........................................................................viii MỞ ĐẦU ................................................................................................................ 1 1. Lý do chọn đề tài ............................................................................................. 1 2. Nhiệm vụ nghiên cứu ....................................................................................... 2 4. Hướng nghiên cứu của đề tài ........................................................................... 2 5. Những nội dung nghiên cứu chính ................................................................... 2 6. Phương pháp nghiên cứu ................................................................................. 3 7. Ý nghĩa khoa học của đề tài ............................................................................. 4 CHƯƠNG 1: THÔNG TIN VÀ QUÁ TRÌNH TRUYỀN TIN ................................. 5 1.1 Tổng quan về thông tin ...................................................................................... 5 1.1.1 Một số khái niệm về thông tin ..................................................................... 5 1.1.2 Lượng tin - đơn vị đo lượng tin ................................................................... 5 1.1.3 Sơ đồ tổng quát của một quá trình xử lý thông tin ....................................... 6 1.1.4 Sự trùng lặp thông tin ................................................................................. 7 1.2 Tìm hiểu một số kỹ thuật biến đổi dữ liệu .......................................................... 9 1.2.1 Kỹ thuật biến đổi Burrows-Wheeler ............................................................ 9 1.2.1.1 Tư tưởng .............................................................................................. 9 1.2.1.2 Thuật toán Burrows-Wheeler ............................................................... 9 1.2.2 Kỹ thuật biến đổi Move-To-Front.............................................................. 15 1.2.2.1 Tư tưởng ............................................................................................ 15 1.2.2.2 Thuật toán Move-To-Front ................................................................. 16 1.3 Mã hóa Entropy ............................................................................................... 18 1.3.1 Mã hóa Huffman ....................................................................................... 18 1.3.2 Mã hóa số học........................................................................................... 20 iv 1.4 Mã hóa độ dài (RLE) ....................................................................................... 21 1.5 Khảo sát đặc thù truyền tin .............................................................................. 22 1.5.1 Quá trình truyền tin .................................................................................. 23 1.5.2 Truyền tin số ............................................................................................. 25 1.6 Kết luận .......................................................................................................... 26 CHƯƠNG 2: TRUYỀN TIN KẾT HỢP VỚI KỸ THUẬT .................................... 27 BIẾN ĐỔI DỮ LIỆU............................................................................................. 27 2.1 Các phương pháp biến đổi dữ liệu.................................................................... 27 2.1.1 Phương pháp Entropy ............................................................................... 27 2.1.2 Phương pháp biến đổi dữ liệu Burrow-Wheeler ........................................ 30 2.2 Mô hình truyền tin kết hợp với biến đổi dữ liệu ............................................... 37 2.3 Lợi ích của kỹ thuật biến đổi dữ liệu khi truyền tin .......................................... 48 2.4 Một số phát triển với kỹ thuật biến đổi BWT và MTF ..................................... 49 2.4.1 Sự đảo ngược tần số.................................................................................. 52 2.4.2 Phương pháp đếm trọng số (WFC)............................................................ 53 2.4.3 Giai đoạn EC ............................................................................................ 54 2.4.4 Lược đồ biến đổi dữ liệu ........................................................................... 55 2.4.5 So sánh tỷ lệ và thời gian thực hiện ........................................................... 57 2.5 Kết luận ........................................................................................................... 59 CHƯƠNG 3 : CÀI ĐẶT VÀ THỬ NGHIỆM ........................................................ 60 3.1 Dữ liệu mẫu ..................................................................................................... 60 3.2 Cài đặt thử nghiệm .......................................................................................... 61 3.3 Nhận xét và đánh giá kết quả thử nghiệm ........................................................ 61 3.4 Kết luận và hướng phát triển ............................................................................ 68 3.4.1 Kết luận .................................................................................................... 68 3.4.2 Hướng phát triển của đề tài ...................................................................... 68 TÀI LIỆU THAM KHẢO ..................................................................................... 69 Tài liệu tiếng việt ............................................................................................... 69 Tài liệu tiếng anh ............................................................................................... 69 Các trang web ................................................................................................... 70 v DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT Chữ viết tắt Diễn giải Ý nghĩa BWT Burrows - Wheeler Transform Biến đổi Burrows - Wheeler MTF Move - To - Front Biến đổi đưa lên trước SA Suffix Array Mảng hậu tố EC Entropy Coding Mã hóa Entropy DC Distance Coding Mã hóa khoảng cách WFC Weighted Frequency Count Đếm trọng số tần số LUA List Update Algorithm Thuật toán cập nhập danh sách GST Global Structure Transformation Chuyển đổi cấu trúc tổng thể RLE Run Length Encoding Mã hóa độ dài vi DANH SÁCH CÁC BẢNG BIỂU Số bảng Bảng 1.1 Tên bảng Thể hiện các thông tin dự báo thời tiết diễn ra trong các Trang 8 ngày của một tuần Bảng 1.2 Quá trình quay chuỗi “ABBAANDPANAMA” 10 Bảng 1.3 Kết quả sắp xếp theo thứ tự từ điển dãy cho 13 “ABBAANDPANAMA” Bảng 1.4 Sắp xếp L và F cùng với các chỉ số 13 Bảng 1.5 Giải mã khóa K 14 Bảng 1.6 Mô tả quá trình biến đổi MTF thuận 18 Bảng 1.7 Mô tả quá trình biến đổi MTF nghịch 19 Bảng 1.8 Mô tả các thông tin với mã Huffman 20 Bảng 1.9 Mô tả các trường hợp xuất hiện các ký hiệu khi nén 23 Bảng 2.1 Bảng tần xuất số lần xuất hiện của dãy số 27 Bảng 2.2 Bảng tần xuất số lần xuất hiện tăng dần của dãy số 27 Bảng 2.3 Mô tả thông tin cây Huffman 29 Bảng 2.4 Quá trình quay chuỗi BWT thuận 30-31 Bảng 2.5 Kết quả sắp xếp theo thứ tự tăng dần trong bảng mã ASCII 31-32 Bảng 2.6 Gán chỉ số cho giá trị L và giá trị F Bảng 2.7 Kết quả thực nghiệm MTF thuận 34-35 Bảng 2.8 Kết quả thực nghiệm MTF nghịch 35-36 Bảng 2.9 Kết quả thực nghiệm quy trình nén và truyền 38 Bảng 2.10 Kết quả thực nghiệm quy trình biến đổi và truyền 44 Bảng 2.11 Kết quả thực nghiệm quy trình kết hợp Nén-Biến đổi-Truyền Bảng 2.12 Những giá trị trung bình rx và thời gian thực hiện theo giây 32 45-46 49 cho những giai đoạn MTF và WFC Bảng 2.13 Sự đảo ngược tần số 51 Bảng 2.14 Những giá trị trung bình rx và thời giang thực hiện theo giây 52 vii cho những giai đoạn MTF và WFC Bảng 2.15 Thể hiện các bước nén khối dữ liệu 55 "abracadabraabracadabra" Bảng 2.16 Tỉ lệ nén kết hợp biến đổi với Calgary Corpus 56 Bảng 2.17 Thời gian thực hiện với Calgary Corpus theo giây 57 Bảng 3.1 Dữ liệu mẫu thực hiện với mọi file 58 Bảng 3.2 Kết quả cài đặt thử nghiệm nén Huffman và phép biến đổi 65 BWT với Huffman viii DANH SÁCH CÁC HÌNH ẢNH Số hình ảnh Tên hình ảnh Trang Hình 1.1 Mô hình quá trình xử lý thông tin tổng quát 6 Hình 1.2 Minh họa phương pháp biến đổi BWT nghịch 12 Hình 1.3 Mô tả quá trình biến đổi BWT nghịch 16 Hình 1.4a Mã hóa Huffman 20 Hình 1.4b Mã hóa Huffman ngược 21 Hình 1.5 Xác suất và khoảng con khởi tạo của biểu 21 Hình 1.6 Mã hóa số học 22 Hình 1.7 Phương pháp nén RLE (1) 23 Hình 1.8 Phương pháp nén RLE (2) 23 Hình 1.9 Các bộ phận của một hệ truyền tin 24 Hình 2.1 Minh họa nén theo phương pháp Huffman 28 Hình 2.2 Cây Huffman 28 Hình 2.3 Kết quả thực nghiệm biến đổi BWT nghịch 33 Hình 2.4 Quy trình truyền dữ liệu kết hợp với các phép biến đổi. 37 Hình 2.5 Quá trình phát triển kỹ thuật nén BWT 48 Hình 2.6 BWT với giai đoạn GST hỗn hợp 50 Hình 2.7 Lược đồ nén dữ liệu của Burrows-Wheeler 53 Hình 3.1a Kết quả cài đặt thử nghiệm thuật toán kỹ thuật biến đổi 60 BWT khi nạp trực tiếp dữ liệu Hình 3.1b Kết quả cài đặt thử nghiệm thuật toán kỹ thuật biến đổi 60 BWT khi nạp một file dữ liệu Hình 3.2a Kết quả cài đặt thử nghiệm thuật toán kỹ thuật biến đổi 61 MTF khi nạp trực tiếp dữ liệu Hình 3.2b Kết quả cài đặt thử nghiệm thuật toán kỹ thuật biến đổi 61 MTF khi nạp một file dữ liệu Hình 3.3a Kết quả cài đặt thử nghiệm với thuật toán nén 62 ix Huffman khi nạp file dữ liệu mẫu “Mylib.h” Hình 3.3b Kết quả cài đặt thử nghiệm kết hợp BWT và Huffman 62 từ file dữ liệu mẫu “Mylib.h” Hình 3.4a Kết quả cài đặt thử nghiệm với thuật toán nén 63 Huffman khi nạp file dữ liệu mẫu “index.html” Hình 3.4b Kết quả cài đặt thử nghiệm kết hợp BWT và Huffman 63 từ file dữ liệu mẫu “index.html”. Hình 3.5a Kết quả cài đặt thử nghiệm với thuật toán nén 63 Huffman khi nạp file dữ liệu mẫu“Point.xls” Hình 3.5b Kết quả cài đặt thử nghiệm kết hợp BWT và Huffman 64 từ file dữ liệu mẫu “Point.xls” Hình 3.5a Kết quả cài đặt thử nghiệm với thuật toán nén Huffman 64 khi nạp file dữ liệu mẫu “NhietDo092015.dat” Hình 3.5b Kết quả cài đặt thử nghiệm kết hợp BWT và Huffman từ file dữ liệu mẫu “NhietDo092015.dat” 65 1 MỞ ĐẦU 1. Lý do chọn đề tài Trong thời đại hiện nay, sự bùng nổ của cuộc cách mạng khoa học kỹ thuật công nghệ, đặc biệt với những thành tựu trong các lĩnh vực điện tử, tin học, truyền thông,... con người đã xây dựng và thực hiện được bước tiến đáng kể trong sự nghiệp công nghiệp hóa, hiện đại hóa. Việc áp dụng nhanh chóng các thành tựu của khoa học công nghệ đã góp phần nâng cao chất lượng các sản phẩm và hiệu quả của các lĩnh vực ngày càng trở nên cấp thiết. Thông tin tiềm tàng khắp mọi nơi trong xã hội, đó là các nguồn thông tin về giá vàng, thị trường chứng khoán, dự báo thời tiết, thông tin về các tổ chức, các hoạt động kinh tế xã hội, thông tin về khoa học công nghệ,... nhưng đó chỉ là thông tin ở dạng tiềm năng. Thông tin chỉ có giá trị và ý nghĩa khi nó được truyền đi, phổ biến và được sử dụng. Có thể nói bản chất của thông tin nằm trong sự giao lưu của nó. Do đó thông tin luôn phát triển gắn liền với truyền tin. Nhịp độ cuộc sống hiện đại, tính phức tạp của công việc và tốc độ trong giao dịch đòi hỏi sự giao lưu nhanh chóng của các dịch vụ thuộc lĩnh vực công nghệ thông tin, truyền tin đã làm tăng nhu cầu của các loại hình thông tin, truyền tin trong các tổ chức quốc gia cũng như các tổ chức quốc tế. Việc tổ chức các dịch vụ hiện đại dựa vào các hệ thống điều khiển nhằm thu thập và xử lý thông tin qua các phương tiện truyền tin, các kỹ thuật truyền tin. Các hình thức truyền tin thông dụng như video, âm thanh, hình ảnh, văn bản,... đã trở nên khá phổ biến trong xã hội. Truyền tin là một phương tiện và cũng là nhịp cầu liên kết giữa con người, các lĩnh vực trong xã hội với nhau. Nhưng hiện tại việc trao đổi thông tin vẫn còn nhiều giới hạn bởi chất lượng thông tin, kích thước gói tin, tốc độ truyền tin, và khả năng bảo mật của thông tin chưa hoàn toàn đáp ứng người dùng. Vì vậy kỹ thuật truyền tin theo hướng biến đổi dữ liệu ra đời với mong muốn là thu nhỏ dung lượng các gói tin, chuyển tin chuẩn xác với nội dung ban đầu, giúp cho quá trình truyền thông tin nhanh hơn, không gian lưu trữ trên đĩa ít hơn. 2 Với mong muốn thực hiện việc biến đổi tin và truyền tin trong khoảng thời gian ngắn, kích thước gói tin nhỏ, chất lượng tin tốt. Học viên lựa chọn đề tài luận văn “Tìm hiểu và phát triển kỹ thuật truyền tin theo hướng biến đổi dữ liệu”. Với đề tài này, học viên nghiên cứu hai kỹ thuật biến đổi cơ bản là: Kỹ thuật biến đổi dữ liệu Burrows-Wheeler, Move-To-Front kết hợp với thuật toán nén Huffman. 2. Nhiệm vụ nghiên cứu - Tìm hiểu tổng quan về thông tin, truyền tin, kỹ thuật biến đổi dữ liệu Burrows-Wheeler, kỹ thuật biến đổi dữ liệu Move-To-Front - Cài đặt thử nghiệm kỹ thuật biến đổi Burrows-Wheeler và kỹ thuật biến đổi Move-To-Front kết hợp với thuật toán nén Huffman. Đưa ra kết quả đối sánh quá trình truyền tin và biến đổi thông tin khi kết hợp kỹ thuật biến đổi dữ liệu Burrows-Wheeler và kỹ thuật biến đổi MoveTo-Front với thuật toán nén Huffman. 3. Đối tượng và phạm vi nghiên cứu Tập trung vào nghiên cứu: - Tư tưởng của kỹ thuật biến đổi Burrows-Wheeler và Move-To-Front. - Thuật toán biến đổi Burrows-Wheeler và Move-To-Front. - Các ví dụ cụ thể áp dụng thuật toán biến đổi Burrows-Wheeler và MoveTo-Front và thuật toán nén Huffman. - Những lợi ích riêng của từng kỹ thuật biến đổi Burrows-Wheeler và kỹ thuật biến đổi Move-To-Front. 4. Hướng nghiên cứu của đề tài - Tìm hiểu về thông tin và quá trình truyền tin. - Nghiên cứu về mã hóa dữ liệu. - Tìm hiểu truyền tin theo các kỹ thuật biến đổi dữ liệu. - Cài đặt thử nghiệm 5. Những nội dung nghiên cứu chính Luận văn được trình bày trong 3 chương, có phần mở đầu, phần kết luận, phần mục lục, phần tài liệu tham khảo. 3 Nội dung cơ bản của luận văn được trình bày như sau: Chương 1: Thông tin và quá trình truyền tin Trong chương này học viên trình bày những khái niệm cơ sở, ý tưởng, thuật toán liên quan thông tin, truyền tin. Ngoài ra, học viên có nêu thêm một số khái niệm liên quan đến thông tin, nén dữ liệu và đưa ra một số ví dụ, dẫn chứng cụ thể để dẫn dắt vấn đề cho luận văn. Chương 2: Truyền tin kết hợp với kỹ thuật biến đổi dữ liệu Trong chương 2 học viên chứng minh một số kỹ thuật biến đổi dữ liệu cơ bản bằng cách áp dụng thuật toán đã trình bày tại chương 1 để thực hiện các ví dụ cụ thể. Kết hợp các kỹ thuật biến đổi dữ liệu, nén dữ liệu để thực hiện mô hình theo 4 quy trình chính để áp dụng kỹ thuật biến đổi dữ liệu BWT, MTF và phương pháp nén dữ liệu Entropy để chứng minh kết quả đạt được của luận văn. Chương 3: Cài đặt và thử nghiệm Chương trình cài đặt và thử nghiệm sử dụng các chương trình chính sau: * Kỹ thuật biến đổi: Burrows - Wheeler và Move - To - Front * Thuật toán nén: Huffman. Áp dụng mô hình biến đổi dữ liệu kết hợp thành các quy trình thực hiện dựa trên cơ sở lý thuyết, đã cài đặt chuyển đổi thử nghiệm dữ liệu thực. 6. Phương pháp nghiên cứu  Về lý thuyết: - Tìm hiểu thông tin và quá trình truyền tin - Tìm hiểu nén dữ liệu, thuật toán nén Huffman. - Nghiên cứu truyền tin theo các kỹ thuật biến đổi dữ liệu BurrowsWheeler và Move-To-Front.  Về thử nghiệm: - Sử dụng ngôn ngữ lập trình Dev C++ xây dựng và cài đặt thử nghiệm chương trình nén dữ liệu theo kỹ thuật biến đổi Burrows-Wheeler, kỹ thuật Move-To-Front kết hợp với thuật toán nén Huffman. 4 - Nhận xét, đánh giá kết quả thử nghiệm. 7. Ý nghĩa khoa học của đề tài Theo các nghiên cứu về biến đổi dữ liệu, học viên phân tích các đặc tính của dữ liệu đã được biến đổi khi truyền tin và hy vọng đưa ra một số mô hình để đạt được sự biểu diễn ngắn gọn hơn, chuẩn xác hơn. Điều này làm gia tăng sự đa dạng của mô hình dữ liệu và những kỹ thuật biến đổi dữ liệu. Luận văn tập trung vào xây dựng cơ sở khoa học cho việc truyền tin theo kỹ thuật biến đổi dữ liệu Burrows-Wheeler với kỹ thuật Move-To-Front kết hợp thuật toán nén Huffman xây dựng ứng dụng, thử nghiệm để tìm ra phương pháp truyền tin hiệu quả nhất. 5 CHƯƠNG 1: THÔNG TIN VÀ QUÁ TRÌNH TRUYỀN TIN 1.1 Tổng quan về thông tin 1.1.1 Một số khái niệm về thông tin Thông tin được tổ chức tuân theo một số quan hệ logic nhất định, trở thành một bộ phận của tri thức, đòi hỏi phải được khai thác và nghiên cứu một cách hệ thống. Trong hoạt động của con người thông tin được thể hiện qua nhiều hình thức đa dạng và phong phú như: Con số, chữ viết, âm thanh, hình ảnh v.v... Từ Latin “Information”, gốc của từ hiện đại “information” (thông tin) có hai nghĩa. Một, nó chỉ một hành động rất cụ thể là tạo ra một hình dạng (forme). Hai, tuỳ theo tình huống, nó có nghĩa là sự truyền đạt một ý tưởng, một khái niệm hay một biểu tượng. Tuy nhiên cùng với sự phát triển của xã hội, khái niệm thông tin cũng phát triển theo. Thông tin tồn tại khách quan, có thể ghi lại và truyền đi. Những điều mà ta gặp hàng ngày như thông tin dự báo thời tiết, tin điện sắp sửa tăng giá, lịch tập huấn của đội tuyển bóng đá Việt Nam, thị trường chứng khoán, giá vàng,...chính là thông tin. Việc chúng ta ghi lại những điều này ra giấy, đó là chúng ta ghi lại thông tin. Còn việc chúng ta nói với mọi người những điều này hoặc đưa cho mọi người xem những điều này, đó là truyền tin. 1.1.2 Lượng tin - đơn vị đo lượng tin Khi nào thì lượng tin bằng không, hay nói cách khác, khi nào thì các thông tin được coi là không có nghĩa? Đó chính là những điều hiển nhiên, chắc chắn, ai cũng biết. (Điều này tương đương với việc hệ thống chỉ có một trạng thái). Ví dụ về lượng tin bằng không: Ai đó thông báo rằng, “ngày mai mặt trời lại mọc ở hướng Đông đấy”. Thông báo đó hầu như không đem lại thông tin gì mới cả, ai cũng biết điều này vậy kết quả là không. Tuy nhiên, điều càng bất ngờ, khó xảy ra thì lượng tin càng cao. Ví dụ, tin về thiên tai sóng thần tại châu Á, tin về toà tháp đôi của Mỹ bị đổ thu hút sự quan 6 tâm của rất nhiều người bởi đây đều là những điều hoàn toàn bất ngờ, rất khó xảy ra. Như vậy, có thể nói rằng: Lượng tin tỷ lệ nghịch với xác suất của sự kiện[4]. Vậy trong máy tính, các thông tin được biểu diễn bằng hệ đếm nhị phân. Tuy chỉ dùng 2 ký hiệu số là ‘0’ và ‘1’ mà ta gọi là bit nhưng hệ nhị phân đã giúp máy tính biểu diễn - xử lý được trên hầu hết các loại thông tin mà con người hiện đang sử dụng như văn bản, hình ảnh, âm thanh, video, ... 1.1.3 Sơ đồ tổng quát của một quá trình xử lý thông tin Mọi quá trình xử lý thông tin bằng máy tính hay bằng con người đều được thực hiện theo một qui trình sau : Dữ liệu (data) được nhập ở đầu vào (input). Máy tính hay con người sẽ thực hiện quá trình xử lý nào đó để nhận được thông tin ở đầu ra (output). Quá trình nhập dữ liệu, xử lý và xuất thông tin đều có thể được lưu trữ (Hình 1.1). Hình 1.1 Mô hình quá trình xử lý thông tin tổng quát Việc xử lý thông tin bao gồm 3 quy trình sau: - Quy trình thu nhận thông tin: Nạp, ghi nhớ thông tin vào vùng nhớ trong não hoặc các vật lữu trữ trung gian ( giấy, đĩa từ,…). - Quy trình tìm kiếm thông tin: Nhớ lại thông tin trong vùng nhớ đã lưu, hoặc thu thập, truy tìm thông tin trong các vật lưu trữ thông tin. - Quy trình biến đổi thông tin: Các hoạt động xử lý, biến đổi thông tin dẫn đến việc thay đổi thông tin, tao ra thông tin mới. Từ mô hình trên ta nhận thấy rằng mỗi hệ thống truyền tin đều có đặc trưng riêng nhưng có một số đặc tính chung cho tất cả các hệ thống. Đặc trưng chung có tính nguyên lý là tất cả các hệ thống truyền tin đều nhằm mục đích truyền tải thông 7 tin từ điểm này đến điểm khác. Trong các hệ thống truyền tin, thường gọi thông tin là dữ liệu hay thông điệp. Để truyền tin hiệu quả thì giữa bên phát và bên thu phải hiểu thông điệp muốn truyền và phải có khả năng biến đổi thông điệp, dịch thông điệp chính xác. Đặc trưng toàn quá trình truyền tin của một hệ thống được xác định và bị giới hạn riêng của nguồn tin, của môi trường truyền và đích thu. Nhìn chung, dạng thông tin cần truyền quyết định kiểu nguồn tin, môi trường và đích thu. Ví dụ 1.1: Giả sử ta có một văn bản gốc với nội dung “abbaandpanama”, ta cần chuyển văn bản này đến một vị trí khác. Ta thực hiện như sau: Dữ liệu vào Input S = “abbaandpanama”, sau quá trình biến đổi và truyền ta thu được bản mã dữ liệu đích Output L = “mbanpabanaaad”, với khóa D = 2. Từ khóa D = 2 sau khi giải mã ta thu được dữ liệu đích Output S’ = “abbaandpanama” - Quy trình truyền thông tin: Truyền hoặc dẫn thông tin từ nơi này sang nơi khác, từ đối tượng này sang đối tượng khác. - Quy trình lý giải, suy luận thông tin: Các hoạt động mang tính trí tuệ và sáng tạo như phân tích, so sánh, lý giải, suy luận, đối chiếu, đánh giá vai trò, ý nghĩa của thông tin[4]. 1.1.4 Sự trùng lặp thông tin Thông tin trùng lặp có thể là một số thông tin được che dấu, một số cơ sơ dữ liệu chung, một số các ký tự giống nhau, một số cấu trúc tương đương trong tự nhiên… . Xét một số ví dụ đơn giản sau đây: Ví dụ 1.2: Xét chuỗi ký tự S = “panama” Để biểu diễn chuỗi ký tự S = “panama” theo cách thông thường cần 48 bits. Như vậy, với chuỗi ký tự S ta có thể lưu ở bảng ký hiệu mới với mã tương ứng cho từng ký hiệu là p = 100, n = 101, m = 11, a = 0. Vậy để biểu diễn chuỗi ký tự S lúc này ta chỉ cần 11 bits. Tuy nhiên còn có nhiều cách khác để có thể giảm bớt số bit của các ký tự bằng cách thay đổi độ dài từ mã vẫn luôn đảm bảo dữ liệu chính xác. Ví dụ 1.3: Xâu “ bananaaaaaa” có 8 biểu tượng ‘a’ và hai biểu tượng ‘n’ 8 được lặp lại liên tục. Ví dụ 1.4: Xem xét một văn bản với các từ được lặp lại như sau: "nguoi oi nguoi o dung ve nguoi ve em chang cho ve em nam vat ao em de lam tho tho nay nguoi o nguoi ve nguoi di di mai chang ve nguoi oi" Ở đây có các từ được lặp lại đó là : Từ "nguoi" 7 lần, từ "ve" 5 lần, từ "em" 3 lần, từ "oi" 2 lần, từ "o" 2 lần, từ "tho" 2 lần, từ "chang" 2 lần. Ví dụ 1.5: Xét thông tin dự báo thời tiết của tỉnh Hòa Bình trong tuần một của tháng 9 năm 2015. Tính trung bình một ngày thông tin dự báo thời tiết báo nhiệt độ 3 lần (sáng, chiều và đêm). Trong đó một tuần bằng 7 ngày. Vậy số lượt báo nhiệt độ trong 7 ngày x 3 = 21 lần báo nhiệt độ. Giả sử tính trung bình và làm tròn nhiệt độ mỗi ngày sẽ cho ta một dãy thông tin. Những thông tin về nhiệt độ biến động trong ngày được cập nhật, và cần phải được truyền tin ngay khi xuất hiện thông tin dự báo nhiệt độ mới chứ không để có đủ lượng thông tin về bảng đo nhiệt độ của một tuần ta mới nén để gửi đi. Với bảng thông số nhiệt độ như sau: Bảng 1.1 Thể hiện các thông tin dự báo thời tiết diễn ra trong các ngày của một tuần Ngày Chủ nhật Thứ 2 Thứ 3 Thứ 4 Thứ 5 Thứ 6 Thứ 7 Sáng 25 24 25 25 23 24 24 Chiều 27 26 27 28 25 25 26 Tối 24 24 25 25 22 23 24 Dựa vào bảng nhiệt độ trên, ta thấy các thông số về nhiệt độ dự báo 23, 24, 25, 26, 27 được lặp lại rất nhiều lần. Vì vậy để thuận tiện cho quá trình truyền thông tin, chúng ta cần áp dụng một số kỹ thuật biến đổi thông tin kết hợp với nén thông tin 9 trước khi truyền tin. Mục đích chính nhằm rút ngắn thời gian truyền tin và chiếm không gian lưu trữ ít hơn. 1.2 Tìm hiểu một số kỹ thuật biến đổi dữ liệu Với phương hướng của đề tài, học viên áp dụng hai kỹ thuật biến đổi chính đó là: Kỹ thuật biến đổi Burrows-Wheeler, kỹ thuật biến đổi Move-To- Front và kết hợp phương pháp Entropy trong quá trình thực hiện. 1.2.1 Kỹ thuật biến đổi Burrows-Wheeler 1.2.1.1 Tư tưởng Xác định đối tượng truyền tin là một tập hợp hữu hạn các thành phần và gọi chúng là biểu tượng, các biểu tượng được xác định là một chuỗi. Kỹ thuật biến đổi Burrow-Wheeler làm thay đổi cấu trúc dữ liệu, tạo dữ liệu đầu vào cho các thuật toán nén dữ liệu khác như RLE, hoặc có thể kết hợp với phương pháp MTF để đạt được hiệu quả nén cao hơn với các thuật toán nén Entropy. Các BWT dựa vào thứ tự từ điển phân loại các biểu tượng theo thứ tự quay vòng của một chuỗi. Các hoạt động của BWT tốt nhất có thể được giải thích thông qua một số ví dụ cụ thể bằng kỹ thuật biến đổi BWT thuận và BWT ngược[11]. 1.2.1.2 Thuật toán Burrows-Wheeler  Burrows-Wheeler thuận Input: BWT(S)// Dữ liệu vào: Chuỗi văn bản, âm thanh, hình ảnh,… Output: L, D // L = Dữ liệu ra; D = Chỉ số xác định lưu trữ vị trí ký tự đầu tiên của S. Phương pháp: BWT tạo ra các khối dữ liệu bằng cách hoán vị vòng tròn ký tự ký tự đầu tiên của khối xuống cuối khối và thu được ma trận X[n×n], mỗi hàng của ma trận là một hoán vị của S: Thuật toán: Bước 1: Quay xâu S mỗi lần 1 ký tự dịch chuyển thành vòng tròn ký tự đầu tiên của khối xuống cuối khối. Ta thu được ma trận X[n×n], mỗi hàng của ma trận là một hoán vị của S.