Luận Văn Phương pháp hợp nhất các bản tin có cấu trúc XML

Trong tương lai gần đây, khi máy tính trở nên phổ biến đến mức nó chuyển từ khuynh hướng sử dụng ý thức sang tiềm thức. Con người chỉ sử dụng máy tính theo nghĩa thông thường là dùng một máy tính PC, hay Laptop để thực hiện công việc của mình mà có một khái niệm mới sẽ nảy sinh trong tương lai, đó là thông tin di động. Hệ thống thông tin di động đang bước đầu hình thành với sự xuất hiện đa dạng của các hình thức Smart phone, PDA
Một trong những cách thức trao đổi thông tin trong tương lai là sẽ truyền thông tin dưới dạng các bản tin có cấu trúc, chẳng hạn các bản tin XML. Bản tin có cấu trúc là một khái niệm tổng quát ẩn chứa trong cách tiếp cận khác nhau nhằm quản lí thông tin. Về mặt cú pháp một thành phần của bản tin bao gồm một cụm từ và một nhãn ngữ nghĩa. Các thành phần của bản tin có thể lồng vào nhau trong các thành phần lớn hơn. Hầu hết các thông tin được thể hiện ở dạng bản tin, chẳng hạn thẻ trong XML, kiểu text trong các cơ sở dữ liệu quan hệ và hướng đối tượng và các kết quả từ các hệ thống xử lí thông tin.
Việc gia tăng số người dùng muốn áp dụng công nghệ tính toán song song dựa trên nền tảng trao đổi dữ liệu thông qua XML, nghĩa là công nghệ cho phép nhiều người dùng thêm vào cùng một tập dữ liệu đơn đồng thời, dẫn đến phát sinh nhu cầu phải có công cụ hợp nhất dữ liệu XML đủ mạnh để điều quản quá trình cộng tác này. Việc đưa ra một giải pháp nhất quán, linh động và tương thích cho cơ chế tự động hợp nhất là vấn đề được đặt ra trước tiên.
Em đã chọn đề tài làm đồ án tốt nghiệp là: “Phương pháp hợp nhất các bản tin có cấu trúc XML”. Với mục đích nghiên cứu các phương pháp hợp nhất các bản tin có cùng cấu trúc một cách nhanh nhất
1.1 Phát biểu bài toán

Trên thực tế ngày nay có nhiều loại nhiều công văn và bản tin sử dụng các định dạng riêng của nó. Chúng ta có nhiều phương pháp hợp nhất khác nhau nhưng việc hợp nhất các bản tin này thành 1 loại bản tin có cấu trúc chung là phương pháp tối ưu nhất. Phương pháp giúp chúng ta xác định ngay tất cả các thay đổi giữa các bản tin, giúp so sánh, hiểu và kết hợp các tập tin mã nguồn khác nhau một cách dễ dàng, nhanh chóng chính xác. Vì vậy việc hợp nhất các bản tin trở nên cần thiết và quan trọng.
Hiện nay phương pháp hợp nhất các bản tin có cấu trúc XML để lưu trữ và trao đổi thông tin là giải pháp được đánh giá cao. XML là một chuẩn định dạng dữ liệu cho nhiều ứng dụng, do bản chất đơn giản và tự giải thích của mình và nó độc lập giữa dữ liệu với ứng dụng.
1.3 Cách tiếp cận

Bản tin có cấu trúc XML đã có cùng cấu trúc hoặc có cấu trúc tương tự nhau, nghĩa là cùng các từ khóa và nội dung. Để giải quyết bài toán hợp nhất ta có hai phương án là hợp nhất 3-way và hợp nhất 2 – way. Nhưng bài toán hợp nhất 3 – way được nghiên cứu chính trong đồ án này.
Bài toán hợp nhất 3-way được phát biểu cụ thể như sau:
Giả sử T1 và T2 là hai cây có thứ tự được dẫn xuất từ cây Tb. Chúng ta sẽ phân tích và thiết kế một công cụ có thể:
1 Thực hiện việc hợp nhất 3-way theo cấu trúc các cây T1 ,T2 và Tb và phát hiện diễn tả mọi đụng độ xảy ra trong khi hợp nhất. Gọi là bài toán hợp nhất cây.
2 Sinh ra tập khác biệt giữa hai cây T1 và T2 dưới dạng một kịch bản chỉnh sửa. Sử dụng tập khác biệt và thông tin của cây T1 nhận lại được cây T2. Gọi là bài toán khác biệt và ráp cây.











MỤC LỤC​ BẢNG CÁC TỪ VIẾT TẮT. 4
CHƯƠNG 1: ĐẶT VẤN ĐỀ VÀ PHÁT BIỂU BÀI TOÁN 5
1.1 Đặt vấn đề. 5
1.2 Phát biểu bài toán. 6
1.3 Cách tiếp cận. 6
CHƯƠNG 2: NGHIÊN CỨU CÁC PHƯƠNG PHÁP HỢP NHẤT CÁC BẢN TIN XML 7
2.1 Tổng quan về XML. 7
2.1.1 Giới thiệu XML 7
2.1.2 Khái niệm XML 7
2.1.3 Mục tiêu ra đời của XML 7
2.1.4 Lợi ích ưu điểm và hạn chế khi sử dụng XML 8
2.1.5 Cấu trúc chung. 8
2.1.6 Những thành phần của một tài liệu XML 9
2.1.7 Lược đồ XML 9
2.1.8 Đọc và phân tích tài liệu XML 11
2.1.9 Định hướng qua tài liệu XML để rút trích dữ liệu. 12
2.1.10 XSLT(eXtensible Stylesheet Language transformations) 13
2.2 Các bản tin có cấu trúc XML 14
2.3 Cây và XML 19
2.3.1 Cây. 19
2.3.2 Ánh xạ cây. 19
2.3.3 Hợp nhất cây. 21
2.3.4 Giải quyết bài toán hợp nhất cấu trúc để đồng bộ hóa. 23
2.3.5 Giải thuật tìm kiếm ánh xạ giữa hai cây. 25
2.3.6 Xử lý đụng độ. 30
2.4 Chọn lựa mô hình. 30
2.5 Các thuật toán ứng dụng trong hợp nhất bản tin. 31
2.5.1 Từ điển đồng nghĩa Tiếng Việt 31
2.5.2 Nguồn dữ liệu. 31
2.5.3 Chuyển đổi từ điển đồng nghĩa – trái nghĩa Tiếng Việt sang dạng thích hợp. 32
2.5.4 Thuật toán xây dựng từ điển đồng nghĩa – trái nghĩa Tiếng Việt 32
2.5.5 Thuật toán xác định quan hệ giữa 2 từ Tiếng Việt: 33
2.5.6 Ánh xạ cây. 34
2.5.7 Thuật toán hợp nhất 3- way theo cấu trúc. 37
2.5.8 Kiểm tra các node bị xoá và di chuyển xa: 41
2.5.9 Tổ hợp các danh sách hợp nhất thành danh sách hợp nhất 43
CHƯƠNG 3: ĐÁNH GIÁ THỰC NGHIỆM VÀ KẾT LUẬN 45
3.1 Giới thiệu về phần mềm Tree Way Merge. 45
3.2 Mô hình thử nghiệm và đánh giá. 46
Kết luận. 49
Đề hướng phát triển trong tương lai 50
Tài liệu tham khảo. 50