Tài liệu Tìm hiểu và so sánh vài kỹ thuật nén XML

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ ĐẶNG THỊ HOÀNG ANH TÌM HIỂU VÀ SO SÁNH MỘT SỐ KỸ THUẬT NÉN XML Ngành : Công nghệ thông tin Chuyên ngành : Kỹ thuật phần mềm Mã số : 60480103 LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. VÕ ĐÌNH HIẾU Hà nội - 2014 Lời cam đoan Tôi xin cam đoan kết quả đạt được trong luận văn là sản phẩm của riêng cá nhân tôi. Trong toàn bộ nội dung của luận văn, những điều được trình bày hoặc là của cá nhân hoặc là được tổng hợp từ nhiều nguồn tài liệu. Tất cả các tài liệu tham khảo đều có xuất xứ rõ ràng và được trích dẫn hợp pháp. Tôi xin hoàn toàn chịu trách nhiệm và chịu mọi hình thức kỷ luật theo quy định cho lời cam đoan của mình. Hà nội, ngày 30 tháng 9 năm 2014 Người cam đoan Đặng Thị Hoàng Anh Lời cảm ơn Trong quá trình học tập và hoàn thành luận văn tốt nghiệp, tôi đã nhận được rẩt nhiều sự giúp đỡ, động viên từ thầy cô, gia đình và bạn bè. Tôi muốn bày tỏ sự cảm ơn sâu sắc của mình tới tất cả mọi người. Tôi xin bày tỏ sự cám ơn đặc biệt tới TS. Võ Đình Hiếu, người đã định hướng cho tôi trong lựa chọn đề tài, đưa ra những nhận xét quý giá và trực tiếp hướng dẫn tôi trong suốt quá trình nghiên cứu và hoàn thành luận văn tốt nghiệp. Tôi xin cảm ơn các thầy cô trong khoa CNTT - Trường Đại học Công nghệ - ĐHQG Hà Nội đã dạy bảo tận tình cho tôi trong suốt khoảng thời gian học tập tại trường. Tôi xin cảm ơn toàn thể bạn bè đồng nghiệp tại Công ty IFI Solution, đơn vị mà tôi đang công tác, đã chia sẻ, giúp đỡ tạo điều kiện cho tôi tham gia khoá học và hoàn thành khoá luận này. Xin cảm ơn tất cả những bạn bè đã giúp đỡ tôi trong suốt quá trình học tập và công tác. Cuối cùng, tôi xin gửi lời cảm ơn sâu sắc nhất tới gia đình của mình, nguồn động viên và cổ vũ lớn lao và là động lực giúp tôi thành công trong công việc và trong cuộc sống. Hà Nội, ngày 30 tháng 9 năm 2014 Đặng Thị Hoàng Anh Mục lục Lời cam đoan Lời cảm ơn Mục lục Danh mục các ký hiệu và chữ viết tắt Danh mục các bảng Danh mục các hình vẽ Danh mục các biểu đồ Mở đầu......................................................................................................................................1 Chương 1: TỔNG QUAN XML .........................................................................................2 1.1. Tổng quan XML ........................................................................................................2 1.2. Ưu điểm của XML.....................................................................................................2 1.3. So sánh XML và HTML ...........................................................................................2 1.3.1. Sự giống nhau giữa XML và HTML ...................................................................2 1.3.2. Sự khác nhau giữa XML và HTML .....................................................................2 1.4. Cấu trúc tài liệu XML ...............................................................................................3 1.5. Cú pháp ......................................................................................................................4 1.5.1. Khai báo XML .....................................................................................................4 1.5.2. Thể hiện tài liệu (Document Instance) .................................................................4 1.5.3. Thuộc tính (Attribute) ..........................................................................................4 1.5.4. Khai báo kiểu tài liệu ...........................................................................................4 1.6. Định nghĩa kiểu tài liệu .............................................................................................5 1.7. Ngôn ngữ định nghĩa lược đồ XML ..........................................................................5 1.8. XSLT .........................................................................................................................6 Chương 2. TỔNG QUAN NÉN DỮ LIỆU ........................................................................9 2.1. Nén dữ liệu ................................................................................................................9 2.1.1. Định nghĩa ............................................................................................................9 2.1.2. Phân loại ...............................................................................................................9 2.1.2.1. Nén tổn hao (lossy compression) ..................................................................9 2.1.2.2. Nén không tổn hao (lossess compression) ....................................................9 2.1.3. Một số khái niệm ...............................................................................................10 2.1.3.1. Tỷ lệ nén (compression ratio) .....................................................................10 2.1.3.2. Hiệu suất nén ...............................................................................................10 2.1.3.3. Độ dư thừa dữ liệu.......................................................................................10 2.2. Các kỹ thuật nén XML ............................................................................................11 2.2.1. Tính năng và phân loại .......................................................................................11 2.2.1.1. Các kỹ thuật nén văn bản tổng quát ............................................................13 2.2.1.2. Các kỹ thuật nén XML không truy vấn.......................................................14 2.2.1.3. Các kỹ thuật nén XML truy vấn ..................................................................15 Chương 3. MỘT SỐ KỸ THUẬT NÉN XML .................................................................17 3.1. XMill .......................................................................................................................17 3.1.1. Tổng quan về XMill ...........................................................................................17 3.1.2. Kiến trúc của XMill ...........................................................................................18 3.1.2.1. Phân chia cấu trúc từ nội dung ....................................................................18 3.1.2.2. Nhóm các giá trị dữ liệu dựa trên ngữ nghĩa...............................................19 3.1.2.3. Các bộ nén ngữ nghĩa ..................................................................................22 3.2. XGrind .....................................................................................................................24 3.2.1. Tổng quan về XGrind ........................................................................................24 3.2.2. Các kỹ thuật nén được sử dụng trong XGrind ...................................................24 3.2.2.1. Quá trình nén siêu dữ liệu ...........................................................................24 3.2.2.2. Quá trình nén giá trị của thuộc tính kiểu liệt kê ..........................................25 3.2.2.3. Quá trình nén giá trị của phần tử hoặc thuộc tính tổng quát .......................25 3.2.3. Nén đồng cấu (Homomorphic Compression) ....................................................25 3.2.4. Kiến trúc của XGrind .........................................................................................26 3.3. XAUST ....................................................................................................................28 3.3.1. Tổng quan về XAUST .......................................................................................28 3.3.2. Mã hóa số học và mô hình ngữ cảnh hữu hạn ...................................................29 3.3.2.1. Mã hóa số học (Arithmetic Coding) ...........................................................29 3.3.2.2. Mô hình ngữ cảnh hữu hạn (Finite Context Modeling) ..............................29 3.3.3. Máy tự động hữu hạn xác định ..........................................................................29 3.3.4. Quá trình nén và giải nén sử dụng XAUST .......................................................31 3.4. XSAQCT .................................................................................................................33 3.4.1. Tổng quan về XSAQCT.....................................................................................33 3.4.2. Kiến trúc của XSAQCT .....................................................................................34 3.4.3. Quá trình xử lý thuộc tính và nội dung tài liệu được trộn .................................36 3.4.4. Quá trình cài đặt XSAQCT ................................................................................37 3.4.4.1. Quá trình xây dựng cây chú thích TA,D .....................................................37 3.4.4.1.1. Đặc điểm của cây chú thích TA,D ........................................................37 3.4.4.1.2. Cài đặt cây chú thích TA,D...................................................................37 3.4.4.2. Quá trình giải nén của XSAQCT ................................................................44 3.4.4.2.1. Bộ chú thích lại (Reannotator) ..............................................................44 3.4.4.2.2. Bộ phục hồi (Restorer) ..........................................................................45 3.5. EXI ..........................................................................................................................46 3.5.1. Tổng quan về EXI ..............................................................................................46 3.5.2. EXI Header ........................................................................................................47 3.5.2.1. EXI Cookie ..................................................................................................47 3.5.2.2. Các bit phân biệt..........................................................................................47 3.5.2.3. Bit hiện diện cho tùy chọn EXI ...................................................................47 3.5.2.4. Phiên bản định dạng EXI ............................................................................47 3.5.2.5. EXI Options ................................................................................................48 3.5.2.6. Padding bits .................................................................................................49 3.5.3. EXI Body ...........................................................................................................49 3.5.3.1. Event Code ..................................................................................................51 3.5.3.2. Event Content ..............................................................................................53 3.5.4. String Table ........................................................................................................54 3.5.5. EXI Grammar .....................................................................................................57 3.5.5.1. Built-In Grammar ........................................................................................58 3.5.5.2. Schema-informed Grammar ........................................................................58 3.5.6. Quá trình nén EXI ..............................................................................................58 3.5.6.1. Block ...........................................................................................................59 3.5.6.2. Channel........................................................................................................59 3.5.6.2.1. Kênh cấu trúc (Structure Channel) .......................................................60 3.5.6.2.2. Kênh giá trị (Value Channel) ................................................................60 3.5.6.3. Dòng nén (Compressed Stream) .................................................................61 Chương 4. CÀI ĐẶT THỰC NGHIỆM VÀ SO SÁNH MỘT SỐ KỸ THUẬT NÉN ..63 4.1. Dữ liệu thử nghiệm ..................................................................................................63 4.2. Môi trường cài đặt ...................................................................................................64 4.3. Đo hiệu năng thực hiện............................................................................................64 4.3.1. Tỷ lệ nén Compression ratio ...........................................................................64 4.3.2. Hiệu suất nén (Compression Performance) .......................................................64 4.3.3. Thời gian nén (Compression Time) ...................................................................64 4.3.4. Thời gian giải nén Decompression Time ........................................................64 4.4. Kết quả thực nghiệm ...............................................................................................64 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN .............................................................................70 TÀI LIỆU THAM KHẢO ......................................................................................................71 Danh mục các ký hiệu và chữ viết tắt DFA DTD GPS HTML SGML XML XSD XSLT Máy tự động hữu hạn xác định. Document Type Definition Định nghĩa kiểu tài liệu. Global Positioning System Hệ thống định vị toàn cầu. Ngôn ngữ đánh dấu siêu văn HyperText Markup Language bản. Standard Generalized Markup Ngôn ngữ đánh dấu tổng quát Language hóa tiêu chuẩn. Extensible Markup Language Ngôn ngữ đánh dấu mở rộng. XML Schema Definition Language Ngôn ngữ định nghĩa lược đồ. Extensible Stylesheet Language Ngôn ngữ định dạng chuyển Transformations đổi mở rộng. Deterministic Finite Automata Danh mục các bảng Bảng 1.1: So sánh XML và HTML ..........................................................................................2 Bảng 1.2: Các thành phần cơ bản của một tài liệu XML .........................................................3 Bảng 2.1: Danh sách các bộ nén không truy vấn [16] ...........................................................14 Bảng 2.2: Danh sách các bộ nén có khả năng truy vấn [16] ..................................................15 Bảng 3.1: Định nghĩa hàm Match c, p [11] ..........................................................................21 Bảng 3.2: Các bộ xử lý ngữ nghĩa nguyên tử (Atomic Semantic Compressors) [11] ...........22 Bảng 3.3: Mô tả các bước thực hiện thuật toán 3.1 khi tạo mới cây chú thích của tài liệu D trong hình 3.13 [20] ................................................................................................................41 Bảng 3.4: Một số phiên bản định dạng EXI ...........................................................................48 Bảng 3.5: Các tuỳ chọn EXI [6] .............................................................................................48 Bảng 3.6: EXI Events [7] .......................................................................................................50 Bảng 3.7: Quá trình mã hóa mã sự kiện khi EXI compression không được thiết lập và tùy chọn bit-packed aligment được sử dụng [6] ...........................................................................52 Bảng 3.8: Quá trình mã hóa mã sự kiện khi EXI compression được thiết lập bằng true và giá trị pre-compression của tùy chọn byte-aligment được sử dụng [6] .......................................52 Bảng 3.9: Các kiểu dữ liệu đã được xây dựng sẵn trong EXI [6] ..........................................53 Bảng 3.10: Quá trình thiết lập phân vùng của String Table [7] .............................................54 Bảng 4.1: Tập dữ liệu thử nghiệm..........................................................................................63 Bảng 4.2: Môi trường cài đặt thực nghiệm. ...........................................................................64 Bảng 4.3: Trình bày kết quả thực nghiệm khi sử dụng bộ nén gzip ......................................65 Bảng 4.4: Trình bày kết quả thực nghiệm khi sử dụng bộ nén XMill ...................................65 Bảng 4.5: Trình bày kết quả thực nghiệm khi sử dụng bộ nén XGrind .................................65 Bảng 4.6: Trình bày kết quả thực nghiệm khi sử dụng bộ nén XAUST ................................66 Bảng 4.7: Trình bày kết quả thực nghiệm khi sử dụng bộ nén EXI (Exificient) ...................66 Danh mục các hình vẽ Hình 1.1: XSLT style sheets được sử dụng để chuyển đổi giữa các tài liệu XML [18] ..........6 Hình 1.2: XSLT style sheets được sử dụng để chuyển đổi một tài liệu XML sang các cách biểu diễn khác nhau [18] ..........................................................................................................7 Hình 2.1: Quá trình nén/giải nén dữ liệu ..................................................................................9 Hình 2.2: Quá trình truyền dữ liệu XML mà không có quá trình nén XML [17] ..................11 Hình 2.3: Quá trình truyền dữ liệu XML có sử dụng quá trình nén XML [17] .....................11 Hình 2.4: Phân loại các bộ nén XML dựa vào sự nhận biết cấu trúc của các tài liệu XML [17] .........................................................................................................................................12 Hình 2.5: Phân loại bộ nén XML dựa vào sự hỗ trợ khả năng truy vấn [17] ........................13 Hình 3.1: Kiến trúc của XMill [11] ........................................................................................18 Hình 3.2: Mô tả quá trình XMill phân tách cấu trúc và dữ liệu .............................................19 Hình 3.3: Kiến trúc của bộ nén XGrind [15] .........................................................................27 Hình 3.4: DFA của phần tử card trong ví dụ 3.14 ..................................................................30 Hình 3.5: Kiến trúc của XSAQCT [20]..................................................................................34 Hình 3.6: Minh họa một tài liệu D đơn giản [20] ..................................................................35 Hình 3.7: Cây chú thích TA,D của tài liệu D trong hình 3.6 [20] ............................................35 Hình 3.8: Quá trình xử lý nội dung tài liệu được trộn [20] ....................................................36 Hình 3.9: Cây chú thích TA,D và các bộ chứa văn bản [20] ....................................................36 Hình 3.10: Biểu diễn một tài liệu D có chứa chu trình đơn giản [20]....................................38 Hình 3.11: Biểu diễn cây chú thích của tài liệu D có thêm các node giả “$” [20] ................39 Hình 3.12: Khôi phục lại cây tài liệu D với các node giả “$” [20] ........................................39 Hình 3.13: Biểu diễn một tài liệu D sẽ được áp dụng thuật toán 3.1 [20] .............................40 Hình 3.14: Biểu diễn cây chú thích của tài liệu D trong hình 3.13 [20] ................................42 Hình 3.15: Biểu diễn cây chú thích hoàn chỉnh của tài liệu D trong hình 3.13 [20] .............43 Hình 3.16: Khôi phục lại cây tài liệu D từ cây chú thích TA,D trong hình 3.15 [20] ..............44 Hình 3.17: Cấu trúc cơ bản của EXI Stream [7] ....................................................................46 Hình 3.18: Định dạng EXI Header [6] ...................................................................................47 Hình 3.19: EXI Cookie [6] ....................................................................................................47 Hình 3.20: Các bit phân biệt (Distinguishing Bits) [6] ..........................................................47 Hình 3.21: Minh họa EXI Stream Body của tài liệu Notebook trong ví dụ 3.23 [7] .............51 Hình 3.22: Các đầu vào khởi tạo trong phân vùng URI [7] ...................................................56 Hình 3.23: Các đầu vào khởi tạo trong phân vùng Prefix [7] ................................................56 Hình 3.24: Các đầu vào khởi tạo trong phân vùng LocalName [7] .......................................56 Hình 3.25: Các đầu vào được khởi tạo trong phân vùng Value [7] .......................................57 Hình 3.26: Tổng quan quá trình nén EXI [6] .........................................................................59 Hình 3.27: Quá trình dồn kênh các sự kiện EXI [6] ..............................................................60 Hình 3.28: Minh họa quá trình nén của EXI Body Stream trong hình 3.21 [7].....................61 Danh mục các biểu đ Biểu đồ 4.1: So sánh tỷ lệ nén của các bộ nén gzip, XMill, XGrind, XAUST và EXI .........66 Biểu đồ 4.2: So sánh hiệu suất nén của các bộ nén gzip, XMill, XGrind, XAUST và EXI ..67 Biểu đồ 4.3: So sánh thời gian nén của các bộ nén gzip, XMill, XGrind, XAUST và EXI ..67 Biểu đồ 4.4: So sánh thời gian giải nén của các bộ nén gzip, XMill, XGrind, XAUST và EXI .........................................................................................................................................68 1 Mở đầu XML (Extensible Markup Language) đã được công nhận là một chuẩn phổ biến cho việc biểu diễn và trao đổi dữ liệu qua Internet. XML được sử dụng để giải quyết nhiều vấn đề như cung cấp dữ liệu trung gian giữa các kiến trúc không đồng bộ và lưu trữ dữ liệu bán cấu trúc. Sức mạnh của XML là khả năng tự mô tả. Ưu điểm này làm cho XML trở nên mềm dẻo, linh hoạt nhưng nó cũng là nguyên nhân làm cho XML trở nên rườm rà, dài dòng mà kết quả là kích thước tập tin rất lớn. Kích thước lớn dẫn đến lượng thông tin được truyền tải, xử lý, lưu trữ, truy vấn thường lớn hơn các định dạng dữ liệu khác. Để giải quyết vấn đề này, một số kỹ thuật nén đã được giới thiệu như: XMill, XGrind, XAUST, EXI, XSAQCT. Việc sử dụng các công cụ nén XML có nhiều lợi thế như làm giảm băng thông mạng, giảm không gian lưu trữ đĩa cũng như giảm bộ nhớ trong việc xử lý và truy vấn các tài liệu XML. Luận văn sẽ tập trung nghiên cứu bốn nội dung chính: tìm hiểu chung về XML, tìm hiểu về nén dữ liệu và nén dữ liệu XML, trong đó tìm hiểu chi tiết năm kỹ thuật nén XML bao gồm: XMill [11,23], XGrind [15,22], XAUST [10,21], XSAQCT [19-20], EXI [6-8,13]. Luận văn tiến hành thực nghiệm, so sánh các kỹ thuật nén với nhau, đưa ra một số hướng dẫn, khuyến nghị hữu ích giúp cho người sử dụng có thể đưa ra các quyết định hiệu quả, đúng đắn khi lựa chọn các công cụ nén XML phù hợp nhất với yêu cầu của họ. Lý do luận văn lựa chọn, tìm hiểu năm bộ nén XML trên bởi vì đây là các bộ nén mới, phổ biến, một số bộ nén chưa được so sánh, đánh giá bằng thực nghiệm. Nội dung chính của luận văn được tổng hợp, trình bày trong 4 chương. Chương 1: Giới thiệu về XML, so sánh XML với HTML, cấu trúc và cú pháp khai báo một tài liệu XML. Chương này cũng trình bày các khái niệm và đưa ra ví dụ về định nghĩa kiểu tài liệu Document Type Definition - DTD , ngôn ngữ định nghĩa lược đồ XML Schema Definition Language - XSD và ngôn ngữ định dạng chuyển đổi mở rộng (Extensible Stylesheet Language Transformations - XSLT). Chương 2: Tập trung vào tìm hiểu và phân loại các kỹ thuật nén dữ liệu nói chung bao gồm nén tổn hao, nén không tổn hao và nén XML nói riêng bao gồm các kỹ thuật nén văn bản tổng quát, kỹ thuật nén XML không truy vấn, kỹ thuật nén XML hỗ trợ truy vấn. Chương 3: Giới thiệu chi tiết năm kỹ thuật nén XML bao gồm XMill, XGrind, XAUST, XSAQCT và EXI. Kiến trúc cũng như chi tiết quá trình cài đặt bộ nén, bộ giải nén của từng công cụ được trình bày chi tiết trong chương này. Chương 4: Cài đặt thực nghiệm và so sánh các kỹ thuật nén XMill, XGrind, XAUST, EXI trên các tập dữ liệu XML chuẩn. Từ các kết quả thu được luận văn sẽ đưa ra một số hướng dẫn, khuyến nghị hữu ích giúp người dùng lựa chọn các công cụ nén phù hợp nhất với yêu cầu sử dụng. 2 Chương 1: TỔNG QUAN XML Chương này giới thiệu về XML, so sánh XML với HTML, cấu trúc và cú pháp khai báo một tài liệu XML. Chương này cũng trình bày khái quát các khái niệm định nghĩa kiểu tài liệu, ngôn ngữ định nghĩa lược đồ và ngôn ngữ định dạng chuyển đổi mở rộng XSLT. 1.1. Tổng quan XML XML Extensible Markup Language là một ngôn ngữ đánh dấu được dùng để lưu trữ và định nghĩa cấu trúc của dữ liệu thông qua các thẻ có nghĩa. XML được chuẩn hoá bởi liên minh mạng toàn cầu World Wide Web Consortium với mục đích đơn giản hoá quá trình trao đổi dữ liệu giữa các hệ thống khác nhau khác nhau, đặc biệt là các hệ thống được kết nối qua Internet. Giống như HTML, XML cũng là một tập con của SGML Standard Generalized Markup Language) - ngôn ngữ đánh dấu tổng quát hóa tiêu chuẩn. 1.2. Ưu điểm của XML Dữ liệu độc lập được mô tả dưới dạng text thông qua các thẻ với cấu trúc và sự phân cấp rõ ràng rõ ràng giúp XML dễ dàng đọc và phân tích bởi con người hay chương trình máy tính. XML cho phép dễ dàng xử lý, chuyển tải, trao đổi dữ liệu giữa nhiều ứng dụng và tài liệu với các định dạng khác nhau. XML c n cung cấp nhiều cách để kiểm tra chất lượng của một tài liệu với các quy tắc cú pháp, kiểm tra liên kết bên trong, so sánh các mô hình tài liệu và các kiểu dữ liệu với nhau. Với Unicode là bộ ký tự chuẩn, XML hỗ trợ hầu hết các hệ thống văn bản, biểu tượng, ký tự của hầu hết quốc gia trên thế giới. Ngoài ra, XML c n được lưu trữ làm cấu hình cho website hay sử dụng cho phương thức Remote Procedure Calls RPC phục vụ web service. Vì là một chuẩn mở nên XML không gắn liền với bất kỳ công ty hay phần mềm cụ thể nào. 1.3. So sánh XML và HTML 1.3.1. Sự giống nhau giữa XML và HTML XML và HTML đều dựa trên SGML Standard Generalized Markup Language . 1.3.2. Sự khác nhau giữa XML và HTML ảng 1.1: So sánh XML và HTML XML XML được thiết kế cho mục đích lưu trữ và chuyển đổi dữ liệu giữa các hệ thống khác nhau. XML dùng để mô tả dữ liệu và chú trọng vào nội dung dữ liệu. HTML HTML được thiết kế cho mục đích trình bày dữ liệu. HTML được dùng để hiển thị dữ liệu và chú trọng vào việc dữ liệu được hiển thị 3 như thế nào. Cho phép người dùng định nghĩa các Các phần tử đã được định nghĩa trước phần tử Kiểm tra tính hợp lệ Hầu như không bắt lỗi Được định nghĩa một cách chặt chẽ Không bắt buộc Các phần từ phải được đóng Các phần tử rỗng không cần phải đóng 1.4. Cấu trúc tài liệu XML Một tài liệu XML gồm có hai phần: phần thứ nhất là prolog của tài liệu prolog document . Phần này là tùy chọn, lưu trữ thông tin của tài liệu XML bao gồm khai báo XML, định nghĩa kiểu tài liệu DTD, chú thích, các chỉ dẫn xử lý. Phần thứ hai là phần tử gốc root element hay c n gọi là phần tử tài liệu document element). Phần này chứa tất cả các phần tử con và nội dung của nó, đây là phần bắt buộc phải có trong một tài liệu XML. ảng 1.2: Các thành phần cơ bản của một tài liệu XML Prolog (tùy chọn) Khai báo XML Định nghĩa kiểu tài liệu Chú thích Các chỉ dẫn xử lý (Processing Instructions) Khoảng trắng Phần tử gốc bắt buộc Thẻ mở của phần tử gốc Các phần tử con và nội dung XML Tutorial http://www.quackit.com/xml HTML Tutorial http://www.quackit.com/html Thẻ đóng của phần tử gốc Ví dụ 1.1: Biểu diễn một tài liệu XML đơn giản [25] 4 XML Tutorial http://www.quackit.com/xml HTML Tutorial http://www.quackit.com/html 1.5. Cú pháp 1.5.1. Khai báo XML D ng đầu tiên của một tài liệu XML là khai báo XML. Nó khai báo phiên bản của một đặc tả XML đang được sử dụng. Ví dụ 1.2: Khai báo XML 1.5.2. Thể hiện tài liệu (Document Instance) Phần của một tài liệu mà bên trong đó dữ liệu được biểu diễn được gọi là một thể hiện tài liệu document instance . Mỗi document instance sắp xếp thứ tự các thông tin của nó theo cấu trúc phân cấp, được định nghĩa bởi các mối quan hệ giữa các phần tử cha-con. Thông thường các phần từ cha thiết lập một ngữ cảnh và nó được kế thừa bởi các phần tử con. Ví dụ 1.3: Mối quan hệ cha con đơn giản giữa các phần tử trong XML Joe Smith 1.5.3. Thuộc tính (Attribute) Mỗi phần tử cũng có các thuộc tính gọi là attribute. Mỗi phần tử cha có thể có rất nhiều lớp phần tử con lồng nhau, nhưng nó chỉ có quan hệ 1-1 với một thuộc tính. Ví dụ 1.4: Ví dụ thuộc tính category của phần tử … 1.5.4. Khai báo kiểu tài liệu Để kết hợp một tài liệu với một lược đồ, một câu lệnh khai báo riêng được yêu cầu. Ví dụ khai báo liên kết đến một DTD trong tài liệu XML. Ví dụ 1.5: Khai báo kiểu tài liệu 5 1.6. Định nghĩa kiểu tài liệu Trong XML, DTD Document Type Definition được sử dụng để định nghĩa cấu trúc tài liệu XML các loại phần tử và mối quan hệ cha-con và tất cả các quy tắc điều khiển, thao tác nội dung tài liệu. Tuy nhiên, không như HTML sử dụng một DTD đã được định nghĩa trước với một tập hợp các loại phần tử cố định, DTD trong XML có thể được tùy chỉnh. Ví dụ 1.6: Mô tả quá trình khai báo một DTD hoàn chỉnh ]> 1.7. Ngôn ngữ định nghĩa lược đ XML XSD XML Schema Definition Language là một ngôn ngữ mô hình dữ liệu toàn diện cho các tài liệu XML. Không như DTD, XSD là một cài đặt thực sự của ngôn ngữ XML, các lược đồ bản thân nó chính là tài liệu XML. Một trong những tính năng quan trọng nhất của XSD là hỗ trợ nhiều kiểu dữ liệu. Nó cải thiện chất lượng biểu diễn dữ liệu XML và đóng vai tr như là một chuẩn vận chuyển dữ liệu doanh nghiệp. Các lược đồ XSD hỗ trợ không gian tên (namespace). Điều này cho phép thiết lập các miền logic, trong đó một số hay toàn bộ các phần của lược đồ được áp dụng. XSD cung cấp một số tính năng nâng cao bao gồm hỗ trợ nhiều kiểu dữ liệu, nâng cao cú pháp kiểm tra tính hợp lệ, mô phỏng các mô hình lược đồ quan hệ thông qua việc sử dụng khóa (key và ràng buộc constraint , có khả năng mở rộng qua phần tử any và module hóa bằng cách sử dụng phần tử include, import. Ví dụ 1.7: Mô tả quá trình định nghĩa một lược đồ XSD hoàn chỉnh Leo Tolstoy John Doe Ví dụ 1.9: Mô tả quá trình định nghĩa XSLT hoàn chỉnh [18] 8 Kết quả template trên sẽ cho kết quả đầu ra được định dạng theo HTML được hiển thị như sau: Kết luận Trong chương này, chúng ta đã tìm hiểu về XML là một ngôn ngữ đánh dấu được dùng để lưu trữ và định nghĩa cấu trúc của dữ liệu thông qua các thẻ có nghĩa. Một tài liệu XML gồm có hai phần: prolog của tài liệu và phần tử tài liệu. Prolog của tài liệu là phần tùy chọn, chứa thông tin của tài liệu XML như khai báo XML, định nghĩa DTD, chú thích và các chỉ dẫn xử lý. Phần tử tài liệu hay phần tử gốc là phần bắt buộc, chứa tất cả các phần tử con. Trong XML, DTD được dùng để định nghĩa cấu trúc tài liệu XML và các quy tắc điều khiển thao tác nội dung tài liệu. Bên cạnh đó, XSD được dùng để hỗ trợ kiểu dữ liệu, không gian tên và cung cấp một số tính năng nâng cao cú pháp kiểm tra tính hợp lệ, khả năng mở rộng và module hóa. Dữ liệu XML có thể được chuyển đổi từ dạng này sang dạng khác một cách tự dộng dựa trên chuẩn XSLT. Chương tiếp theo sẽ giới thiệu tổng quan về nén dữ liệu và các kỹ thuật nén XML. 9 Chương 2. TỔNG QUAN NÉN DỮ LIỆU Chương này tập trung vào tìm hiểu và phân loại nén dữ liệu bao gồm nén tổn hao, nén không tổn hao và nén XML bao gồm các kỹ thuật nén văn bản tổng quát, kỹ thuật nén XML không truy vấn, kỹ thuật nén XML hỗ trợ truy vấn. Bên cạnh đó, chương này cũng trình bày một số khái niệm liên quan đến nén dữ liệu như tỷ lệ nén, hiệu suất nén và độ dư thừa dữ liệu. 2.1. Nén dữ liệu 2.1.1. Định nghĩa Nén dữ liệu data compression là quá trình chuyển đổi luồng dữ liệu đầu vào thành một luồng dữ liệu đầu ra khác có kích thước nhỏ hơn. Hình 2.1: Quá trình nén/giải nén dữ liệu 2.1.2. Phân loại Phân loại dựa vào nguyên lý nén có hai họ chính là nén tổn hao lossy compression và nén không tổn hao lossess compression . 2.1.2.1. Nén tổn hao (lossy compression) Nén tổn hao c n gọi là nén có mất mát thông tin. Kỹ thuật nén này chấp nhận mất mát một lượng thông tin nhất định để thu được hiệu suất nén cao hơn, do vậy, sau khi giải nén, ta sẽ không thu được dữ liệu gốc. Nén tổn hao thường được áp dụng cho các tập tin hình ảnh hay âm thanh được số hóa bởi vì đối với các tập tin thuộc loại này thì việc mất mát một ít thông tin là điều có thể chấp nhận được. Một số thuật toán nén tổn hao điển hình là JPEG [4], MPEG-4 [4]. 2.1.2.2. Nén không tổn hao (lossess compression) Nén không tổn hao c n gọi là nén chính xác hay nén không mất thông tin. Trong phương pháp nén không tổn hao, dữ liệu được nén sau khi giải nén sẽ giống y như dữ liệu gốc ban đầu. Các thuật toán nén không tổn hao được dùng để nén các file như exe, word, excel. Một số thuật toán nén không tổn hao là: Shannon-Fano [4], LZW [4]. 10 2.1.3. Một số khái niệm 2.1.3.1. Tỷ lệ nén (compression ratio) Tỷ lệ nén là một trong các đặc trưng quan trọng nhất của mọi phương pháp nén. Tỷ lệ nén được tính theo công thức sau: ỷ ệ é 2.1.3.2. í ướ ữ ệ é í ướ ữ ệ ố Hiệu suất nén Hiệu suất nén được tính theo công thức sau: ( 2.1.3.3. ) Độ dư thừa dữ liệu Nguyên tắc chung của các phương pháp nén dữ liệu là loại bỏ thông tin trùng lặp, dữ liệu dư thừa đến mức tối thiểu có thể được. Việc xác định bản chất kiểu dư thừa dữ liệu rất có ích trong việc xây dựng các phương pháp nén phù hợp. Nhìn chung, có bốn kiểu dư thừa chính trong dữ liệu.  Sự phân bố ký tự Trong một chuỗi ký tự, có một số ký tự có tần suất xuất hiện nhiều hơn những ký tự khác. Do vậy, có thể giảm bớt lượng dữ liệu bằng cách mã hóa các dãy ký tự có tần xuất cao được thay thế bởi một từ mã nhị phân với số bít nhỏ. Ngược lại, các dãy ký tự có tần xuất thấp sẽ được mã hoá bởi từ mã có số bít nhiều hơn. Kiểu dư thừa này đặc biệt phù hợp với phương pháp mã hóa Huffman [3].  Sự lặp lại của các ký tự Trong các tập tin ảnh, thường có những kí tự và chuỗi kí tự lặp lại nhiều lần liên tiếp nhau. Khi đó, dữ liệu có thể được giảm bớt bằng cách thay thế những dãy kí tự đó bằng mã của chúng và số kí tự lặp lại. Phương pháp nén với mô hình từ điển khai thác rất hiệu quả loại dư thừa này.  Những m u sử dụng tần suất cao Thông thường, trong các văn bản dạng text, sự tuần tự của những kí tự nào đó sẽ tái xuất hiện với tần suất tương đối cao, vì vậy, có thể biểu diễn bằng dãy bit ngắn hơn. Đây là cơ sở của phương pháp mã hoá kiểu từ điển như LZW Lempel - Ziv - Welch).  Độ dư thừa vị trí Có nhiều trường hợp, dữ liệu trong một nguồn số liệu có sự phụ thuộc lẫn nhau, do đó nếu biết được kí hiệu xuất hiện tại một vị trí nào đó, ta có thể phỏng đoán trước một cách hợp lý sự xuất hiện của các kí hiệu khác ở những vị trí khác nhau. Ví dụ, ảnh biểu diễn trong một lưới hai chiều, một số điểm ở hàng dọc lại xuất hiện trong cùng vị trí ở các hàng