›

Đồ án Phương pháp hợp nhất các bản tin có cấu trúc XML

pdf 50 trang huongle 2420
Download
Bạn đang xem 20 trang mẫu của tài liệu "Đồ án Phương pháp hợp nhất các bản tin có cấu trúc XML", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfdo_an_phuong_phap_hop_nhat_cac_ban_tin_co_cau_truc_xml.pdf

Nội dung text: Đồ án Phương pháp hợp nhất các bản tin có cấu trúc XML

  1. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML NHIỆM VỤ ĐỀ TÀI: Chƣơng 1: ĐẶT VẤN ĐỀ VÀ PHÁT BIỂU BÀI TOÁN + Đặt vấn đề + Phát biểu bài toán + Cách tiếp cận Chƣơng 2: CƠ SỞ LÝ THUYẾT +Tìm hiểu tổng quan XML + Nghiên cứu các phƣơng pháp hợp nhất các bản tin có cấu trúc XML Chƣơng 3: ĐÁNH GIÁ THỰC NGHIỆM + Thực nghiệm trên các bản tin mẫu và đánh giá kết quả Kết luận. Đề hƣớng phát triển trong tƣơng lai. Tài liệu tham khảo. 1
  2. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML LỜI CẢM ƠN Trong suốt khóa học 2005 – 2009 tại trƣờng Đại Học Dân Lập Hải Phòng với sự giúp đỡ của quý thầy cô và giáo viên hƣớng dẫn về mọi mặt, từ nhiều phía nhất là trong thời gian thực hiện đề tài, nên đề tài của em đã đƣợc hoàn thành đúng thời gian quy định. Em xin gửi lời cảm ơn chân thành nhất tới thầy giáo hƣớng dẫn Th.s Nguyễn Trịnh Đông đã tận tình hƣớng dẫn, giúp đỡ, tạo điều kiện để em hoàn thành khóa luận này. Em xin gửi lời cảm ơn chân thành tới Bộ môn Công Nghệ Thông Tin cùng toàn thể các thầy cô trong khoa cũng nhƣ toàn thể các thầy cô trong Trƣờng đã giảng dạy những kiến thức chuyên môn làm cơ sở để em thực hiện tốt cuốn luận văn tốt nghiệp này và đã tạo điều kiện thuận lợi để em hoàn thành khóa học. Em xin chân thành cảm ơn! Hải Phòng, ngày 1 tháng 7 năm 2009 Sinh Viên Vũ Thị Lệ 2
  3. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML 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 13 2.3 Cây và XML 18 2.3.1 Cây 18 2.3.2 Ánh xạ cây 19 2.3.3 Hợp nhất cây 20 2.3.4 Giải quyết bài toán hợp nhất cấu trúc để đồng bộ hóa 22 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 3
  4. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML BẢNG CÁC TỪ VIẾT TẮT STT Tên viết tắt Tên đầy đủ 1 CSDL Cơ sở dữ liệu 2 XML eXtensible Markup Language 3 DOM Document Object Model 4 HTTP Hypertext Transfer Protocoly 5 DTD Document Type Definition 6 XSLT eXtensible Stylesheet Language transformations 7 XSL XML- Schema XML Definitiom 8 SQL Structured Query Language - SQL 9 Tb Tập tin cơ sở 10 T1, T2 Tập tin nhánh 11 MBCS Mixed Byte Character Set 4
  5. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML CHƢƠNG 1: ĐẶT VẤN ĐỀ VÀ PHÁT BIỂU BÀI TOÁN 1.1 Đặt vấn đề 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 5
  6. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML 1.2 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. 6
  7. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML CHƢƠNG 2: NGHIÊN CỨU CÁC PHƢƠNG PHÁP HỢP NHẤT CÁC BẢN TIN XML 2.1 Tổng quan về XML. 2.1.1 Giới thiệu XML XML(Extensible Markup Language)ra đời vào tháng 2/1998, là ngôn ngữ có kiến trúc gần giống với HTML nhƣng XML nhanh chóng trở thành một chuẩn phổ biến trong việc chuyển đổi thông tin qua các trang web sử dụng giao thức HTTP. Trong khi HTML là ngôn ngữ chủ yếu về hiển thị dữ liệu thì XML lại đang phát triển mạnh về việc chuyển tải, trao đổi và thao tác dữ liệu bằng XML. XML đƣa ra một định dạng chuẩn cho cấu trúc của dữ liệu hoặc thông tin bằng việc tự định nghĩa định dạng của tài liệu. Bằng cách này, dữ liệu đƣợc lƣu trữ bằng XML sẽ độc lập với việc xử lý. Vì vậy XML ra đời sẽ đáp ứng đƣợc yêu cầu ngày càng cao của các nhà lập trình trong vấn đề trao đổi và xử lý thông tin. 2.1.2 Khái niệm XML XML là một chuẩn ngôn ngữ nhằm mục đích cung cấp việc chia sẻ dữ liệu giữa các hệ thống phần mềm theo hƣớng thân thiện ngƣời dùng. XML đang đƣợc đẩy mạnh để trở thành ngôn ngữ chung cho việc trao đổi dữ liệu trên internet. XML đƣợc hỗ trợ bởi tổ chức World wide web Consortium-W3C và các tập đoàn lớn. 2.1.3 Mục tiêu ra đời của XML Ngày nay, XML đang trở thành một chuẩn chung cho việc trao đổi dữ liệu cho những ứng dụng chạy trên môi trƣờng Internet. Vì XML cho phép ngƣời dùng có thể tự định nghĩa các thẻ (tag) - những thẻ này làm cho tài liệu XML đa dạng hơn những ngôn ngữ thông thƣờng nhƣ HTML. Nhƣ vậy mục tiêu đặt ra cho sự ra đời XML là gì? Đầu tiên nó sẽ tƣơng thích với SGML và dễ dàng viết những chƣơng trình để xử lý cho những tài liệu XML. Kế tiếp, những tài liệu XML rõ ràng, dễ đọc, dễ dàng tạo lập. Và điều quan trọng là nó đƣợc hỗ trợ trong nhiều ứng dụng. Tóm 7
  8. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML lại, XML dễ dàng chia sẻ thông tin qua những định dạng khác nhau thông qua môi trƣờng web. XML đƣợc thiết kế dành cho mọi ngƣời, đƣợc mọi ngƣời sử dụng. 2.1.4 Lợi ích ƣu điểm và hạn chế khi sử dụng XML Một số lợi ích khi sử dụng XML XML có thể tách rời dữ liệu. Sử dụng XML, dữ liệu đƣợc chứa trong các tập tin XML riêng biệt. XML có thể mô tả thông tin của những đối tƣợng phức tạp mà cơ sở dữ liệu quan hệ không thể giải quyết đƣợc. XML có thể dùng để chuyển đổi dữ liệu giữa các hệ thống không tƣơng thích. XML dùng để chia sẻ dữ liệu với những tập tin bản tin đơn giản dễ hiểu. XML cũng đƣợc dùng để lƣu trữ dữ liệu, có thể làm cho dữ liệu của chúng ta hữu ích hơn. Nhƣ vậy, chúng ta đã biết đƣợc lợi ích và vai trò của XML trong vấn đề lƣu trữ và trao đổi thông tin. Tuy nhiên hạn chế của XML cũng có : + Chuẩn hoá: Trong khi đã tồn tại các định nghĩa tên thẻ của ngành, bạn vẫn có thể định nghĩa các thẻ không phải là tiêu chuẩn. + Dung lƣợng lớn. 2.1.5 Cấu trúc chung Chúng ta có thể sử dụng trình soạn thảo bất kỳ để soạn thảo tài liệu XML, nhƣng phải tuân thủ theo nguyên tắc sau: . 8
  9. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML Theo định dạng trên, chúng ta thấy tuy tài liệu XML rất đơn giản nhƣng quy định cũng rất chặt chẽ, tức là các tài liệu XML đều xuất phát từ nút gốc (root), và mỗi phần tử phải có thẻ mở và thẻ đóng “ ” 2.1.6 Những thành phần của một tài liệu XML Khai báo: Mỗi một tài liệu XML có một chỉ thị khai báo xml version="1.0"?> Định nghĩa tài liệu XML tuân theo chuẩn của W3C và đây là phiên bản “1.0” Chú thích: đƣợc khai báo nhƣ sau: Phần tử (Elements): Một tài liệu XML đƣợc cấu thành từ những phần tử. Một phần tử có thẻ mở và thẻ đóng. Giữa thẻ mở và thẻ đóng là nội dung của phần tử đó. Phần tử có thể chứa dữ liệu hoặc có thể lồng vào một phần tử khác. Phần tử gốc (root): Trong tài liệu XML, chỉ có một phần tử gốc và phần tử này sẽ chứa tất cả những phần tử của tài liệu XML do chúng ta tạo ra . Thuộc tính (Attributes): Nhƣ đã trình bày ở trên, một phần tử có thể chứa dữ liệu hoặc chứa phần tử khác hoặc cả hai. Bên cạnh đó, phần tử có thể rỗng khi đó nó có thể chứa thuộc tính. Một thuộc tính chỉ là một sự lựa chọn để gắn dữ liệu đến phần tử. Một thuộc tính đặt trong thẻ mở của phần tử và chỉ ra giá trị của nó bằng cách sử dụng cặp name=value”. 2.1.7 Lƣợc đồ XML DTD(Document Type Definition)và Schema là hai cách khác nhau để quy định những luật về nội dung của một tài liệu XML.Tuy nhiên DTD có hạn chế là không sử dụng định dạng XML vì bản thân DTD không phải là một tài liệu XML và kiểu dữ liệu có sẵn dùng để định nghĩa nội dung của một thuộc tính hoặc một phần tử thì rất giới hạn trong DTD mặt khác DTD không có khả năng mở rộng và không hỗ trợ namespace. Do đó tài liệu không viết theo định dạng XML nên DTD khó viết 9
  10. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML và khó hiểu.Vì vậy việc sử dụng DTD để kiểm tra sự hợp lệ của một tài liệu XML là không khả thi. Chúng ta cần một sự lựa chọn khác khả thi hơn để kiểm tra sự hợp lệ của một tài liệu XML. Đó là chúng ta sử dụng lƣợc đồ XML-Schema XML Definition(XSD) Một lƣợc đồ đơn giản chỉ là một tập hợp những luật đƣợc định nghĩa lại mô tả nội dung dữ liệu của một tài liệu XML, nó tƣơng tự nhƣ một định nghĩa cấu trúc bảng trong cơ sở dữ liệu quan hệ. Trong lƣợc đồ XML, chúng ta định nghĩa một tài liệu XML, những phần tử của nó, những kiểu dữ liệu của phần tử và những thuộc tính liên quan và điều quan trọng nhất là mối quan hệ “cha con” giữa những phần tử. Chúng ta có thể tạo lƣợc đồ trong nhiều cách khác nhau. Cách đơn giản nhất là sử dụng Notepad. Các kiểu dữ liệu trong lƣợc đồ XML Có hai loại kiểu dữ liệu trong lƣợc đồ XML đó là kiểu dữ liệu cơ bản và kiểu dữ liệu mở rộng. Kiểu dữ liệu cơ bản là kiểu dữ liệu không bắt nguồn từ kiểu dữ liệu nào ví dụ nhƣ kiểu dữ liệu float. Kiểu dữ liệu mở rộng dựa trên những kiểu dữ liệu khác nhƣ kiểu integer dựa trên kiểu decimal. Kiểu dữ liệu cơ bản đƣợc định nghĩa cho mục đích của lƣợc đồ XML thì không nhất thiết phải giống với một số cơ sở dữ liệu khác. XPath Qua phần trình bày trên, chúng ta biết đƣợc cấu trúc và cú pháp của XML tƣơng đối đơn giản. Bƣớc tiếp theo là tìm hiểu cách nào để xử lý một tài liệu XML Nhƣ vậy để xử lý một tài liệu XML, chƣơng trình ứng dụng phải có cách di chuyển bên trong tài liệu để lấy ra giá trị của các phần tử hay thuộc tính. Do đó ngôn ngữ XML Path đƣợc ra đời mà chúng ta gọi tắt là XPath. XPath đóng vai trò quan trọng trong việc truy vấn dữ liệu cho các chƣơng trình ứng dụng vì nó cho phép ta lựa chọn hay sang lọc ra những phần tử nào mình muốn để trao đổi hay hiển thị. Xpath là một ngôn ngữ dùng để xử lý truy vấn trên tài liệu XML, cũng giống nhƣ SQL là một chuẩn để làm việc với cơ sở dữ liệu. Một biểu thức XPath có thể chỉ ra vị trí và mẫu nào để kết hợp. Chúng ta có thể áp dụng toán tử Boolean, hàm string 10
  11. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML và toán tử số học trong biểu thức XPath để xây dựng câu truy vấn phức tạp trên tài liệu XML. XPath cũng cung cấp một số hàm về số nhƣ tính tổng, hàm làm tròn (round),v.v 2.1.8 Đọc và phân tích tài liệu XML Sử dụng lớp XMLTextReader Lớp XMLTextReader cung cấp một cursor đƣợc sử dụng để lấy dữ liệu từ một tài liệu XML Cách khai báo: XmlTextReader myRdr = new XmlTextReader(Server.MapPath("catalog2.xml")); Khi một thể hiện đƣợc tạo ra, con trỏ cursor sẽ đƣợc đặt ở đầu tài liệu. Chúng ta có thể sử dụng phƣơng thức Read() để lấy những phần dữ liệu một cách tuần tự. Mỗi phần tử dữ liệu tƣơng tự nhƣ một nút trong cây XML. Thuộc tính NodeType sẽ lấy giá trị của nút. Vì thế, khi một phần dữ liệu đƣợc đọc, chúng ta có thể sử dụng câu lệnh sau để hiển thị tên, giá trị và kiểu của nút Response.Write(myRdr.NodeType.ToString() +" " + myRdr.Name + ":" + myRdr.Value); Nếu muốn kiểm tra nút đó có thuộc tính hay không, chúng ta có thể sử dụng phƣơng thức HasAttributes. Nếu giá trị trả về của phƣơng thức HasAttributes là true, chúng ta áp dụng phƣơng thức MoveToAttribute(i) để lặp qua các thuộc tính của nút. Sử dụng mô hình DOM(Document Object Module) Mô hình DOM để đọc và trình bày nội dung của một tệp tin XML. Việc sử dụng mô hình DOM sẽ thông qua một số đối tƣợng nhƣ XMLDocument, XMLDataDocument. Khi một XMLDocument đƣợc tạo ra, nó tổ chức nội dung của một tệp tin XML thành một cây. XMLDocument cung cấp việc truy xuất nhanh và trực tiếp đến 11
  12. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML một nút. Tuy nhiên việc sử dụng mô hình DOM rất tốn bộ nhớ để lƣu trữ thành một cây và thật sự sẽ khó khăn khi tài liệu XML có kích thƣớc lớn. 2.1.9 Định hƣớng qua tài liệu XML để rút trích dữ liệu Sử dụng lớp XMLTexeReader Trong phần trên, chúng ta đã biết cách để đọc vào một tài liệu XML, phần này chúng ta sẽ định hƣớng qua tài liệu XML và chỉ lấy những dữ liệu nào cần thiết cho ứng dụng của mình. Sử dụng mô hình DOM Bên cạnh XMLTextReader thì môi trƣờng Visual Studio.NET cũng hỗ trợ mô hình DOM để đọc và trình bày nội dung của một tập tin XML. Việc sử dụng mô hình DOM sẽ thông qua một số đối tƣợng nhƣ XMLDocment, XMLDataDocument. Khi một XMLDocment đƣợc tạo ra, nó tổ chức nội dung của một tập tin XML thành một cây. Trong khi đối tƣợng XMLTextReader cung cấp một cursor định vị trí theo một hƣớng thì XMLDocumemt cung cấp việc truy xuất nhanh và trực tiếp đến một nút. Tuy nhiên, việc sử dụng mô hình DOM rất tốn bộ nhớ để lƣu trữ thành một cây và thất sự sẽ khó khăn khi tài liệu XML có kích thƣớc lớn. Có nhiều cách khác nhau để tạo một đối tƣợng XMLDocument. Sau đây chúng ta sử dụng đối tƣợng XMLTextReader để tạo một XMLDocumnet. Một cây đƣợc tạo từ nhiều nút và một nút cũng là một cây chứa những nút khác. Nút lá thì không có nút con, vì thế nút này dùng để hiển thị dữ liệu bản tin. Lớp XMLDataDocument kế thừa từ lớp XMLDocument vì thế nó cũng có một số phƣơng thức nhƣ lớp XMLDocument. XMLDataDocument cung cấp hai cái nhìn trên cùng một dữ liệu đó là XML view và relational view. XMLDataDocument có một thuộc tính tên là DataSet, thông qua DataSet, XMLDataDocument trình bày dữ liệu nhƣ một hoặc nhiều bảng có quan hệ hoặc không có quan hệ. Khi chúng ta sử dụng phƣơng thức Load() để tải một đối tƣợng XMLDataDocument, chúng ta có thể xem nó nhƣ một cây hoặc nhƣ một bảng. Sau 12
  13. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML đây là minh họa cho hai cách nhìn về một tài liệu XML khi sử dụng XMLDataDocument 2.1.10 XSLT(eXtensible Stylesheet Language transformations) XSLT là một ngôn ngữ dựa trên XML dùng để biến đổi các tài liệu XML. Tài liệu gốc thì không bị thay đổi mà thay vào đó một tài liệu XML mới đƣợc tạo ra dựa trên nội dung của tài liệu cũ. Tài liệu mới có thể là có định dạng XML hay một định dạng nào đó khác, nhƣ HTML hay bản tin thuần. XSLT thƣờng dùng nhất trong việc chuyển đổi giữ liệu giữa các lƣợc đồ XML hay để chuyển đổi dữ liệu XML thành các trang web hay tài liệu dạng PDF. 2.2 Các bản tin có cấu trúc XML Bài toán đề nghị cách tiếp cận hợp nhất 3-way, lấy một tập tin làm cơ sở, với thông tin đầu vào là ba tập tin XML Tb, T1, T2 với Tb là tập tin cơ sở, T1 và T2 lần lƣợt là tập tin nhánh có thể chứa các thay đổi so với tập tin cơ sở Tb. Có hai bài toán riêng biệt nhƣng có liên quan đến nhau: Hợp nhất 2-way và hợp nhất 3-way. Sự khác nhau giữa chúng phụ thuộc vào vấn đề có hai tập tin hợp nhất hay có một tập tin “cơ sở”, mà từ đó các tập tin khác đƣợc dẫn suất ra. Hợp nhất 3-way có tiềm năng về một giải pháp chính xác hơn khi có tập tin cơ sở hiện hữu, nhƣng nó khá phức tạp. Trong bài toán chúng ta tập trung vào cách hợp nhất 3-way 13
  14. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML Với bài toán hợp nhất 2-way, các yêu cầu cơ bản có thể phát biểu một cách đơn giản theo cách không hình thức nhƣ sau: tài liệu đƣợc hợp nhất phải chứa mọi thứ từ cả hai tài liệu nguyên thủy, nhƣng không đƣợc trùng lặp nếu có những phần chung. Vấn đề ở đây là định nghĩa phần chung nhau là gì và việc đảm bảo điều này đƣợc điều quản một cách đúng đắn. Mặc dù mọi ngƣời dùng có cùng ý tƣởng rất rõ về các yêu cầu của mình nhƣng việc định nghĩa phần chung nhau có thể dẫn đến các kịch bản sử dụng khác nhau. Ta có thể tóm tắt các yêu cầu nhƣ sau: a. Các đặc tính của một phần tử bất kỳ trong tập tin kết quả phải là hợp nhất của các đặc tính trong hai tập tin với các phần tử tƣơng ứng với phần tử hợp nhất, nếu có đụng độ này phải đƣợc xử lí. b. Các phần tử con của một phần tử cho trƣớc bất kỳ(phần tử cha)phải đƣợc hợp nhất theo thứ tự của các phần tử con của các phần tử tƣơng ứng với phần tử cha đó trong hai tập tin. c. Thuật toán so sánh phải nhận biết đƣợc các phần tử tƣơng ứng trong hai tập tin tại mỗi mức trong cấu trúc cây. d. Quá trình hợp nhất phải xử lý đƣợc các phần tử có thứ tự. e. Khi các node PCDATA(text)thay đổi, phải có sự lựa chọn giữa việc thực hiện hợp nhất nội dung hoặc chọn một trong các hình thức trình bày text. 14
  15. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML f. Các đụng độ phải đƣợc nhận biết và xử lý ở các mức độ khác nhau. Bên cạnh các yêu cầu giống nhƣ trƣờng hợp hợp nhất 2-way, hợp nhất 3-way còn đòi hỏi: g. Mọi thay đổi của một phần tử thuộc một trong hai nhánh phải đƣợc thể hiện trong tập tin hợp nhất. h. Các phần tử bị xóa thuộc một trong hai nhánh không đƣợc xuất hiện trong tập tin hợp nhất. Xét hai cây có thứ tự, liên quan với nhau T1 và Tb, giả sử Tb thay đổi thành T2 và ta muốn truyền các thay đổi này đến các thành phần của Tb hiện hữu trong T1. Hiển nhiên T1 và T2 sẽ tham gia vào quá trình xử lý. Còn Tb tham gia vào để nhận biết các phần chung của T1 và T2. Tác vụ này đƣợc gọi là hợp nhất 3-way theo cấu trúc để nhấn mạnh rằng bản chất của việc hợp nhất là trên dữ liệu có cấu trúc (tức là trên các cây có thứ tự). Hợp nhất 3-way theo cấu trúc: Giả sử T1,T2 là các cây có thứ tự đƣợc dẫn ra từ cây Tb. Việc hợp nhất 3-way các cây T1,Tb và T2 hình thành cây có thứ tự Tm,với Tm chứa các thay đổi giữa Tb và T1 và các thay đổi giữa Tb và T2. Cây Tb gọi là cây cơ sở và các cây T1,T2 gọi là các nhánh. Nếu chúng ta phát sinh tập khác biệt Tb - T1 và áp dụng cho T2, chúng ta sẽ cần một phƣơng cách nào đó để nhận biết các node trong T2 mà các thao tác sửa đổi trong tập khác biệt sẽ đƣợc áp dụng. Điều này thật không dễ dàng, do cấu trúc của T2 có thể khác hoàn toàn Tb và chúng ta không giả thiết về sự tồn tại của bất kỳ node nào. Mặt khác chúng ta không có tên cố định cho các phần của T2, mà chúng ta muốn áp dụng các thay đổi đến các phần đó. Giải pháp cho vấn đề này là đƣa thêm một số dữ liệu vào trong phần khác nhau nhƣ là ngữ cảnh cho các thao tác sửa đổi và do đó chúng ta cần phải định nghĩa một loại “cây ngữ cảnh” nào đó. Các giải 15
  16. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML pháp hợp nhất khác nhau sẽ có những yêu cầu khác nhau nhƣng có hai yêu cầu chính ảnh hƣởng lên mọi giải pháp. Trƣớc tiên đó là các trƣờng hợp hợp nhất và các kết quả mong đợi. Ví dụ việc hợp nhất dữ liệu với cấu trúc phân cấp chặt chẽ dẫn tới quá trình xử lí đơn giản việc hợp nhất các tài liệu mà thông tin trong đó có thể di chuyển trong cấu trúc cây XML. Thứ hai là ảnh hƣởng của kết quả của bài toán ánh xạ đƣợc lựa chọn để đƣa ra tƣơng ứng giữa hai tập tin: đây là vấn đề mấu chốt Ví dụ về bài toán hợp nhất: Cây Tb là cây cơ sở, các cây T1, T2 lần lƣợt có các thay đổi nhƣ sau: T1 chèn node F vào vị trí node B, Tb cập nhật node B thành B1. Chúng ta muốn hợp nhất Tm phải thể hiện đƣợc các thay đổi trong các cây T1 và T2 so với Tb. Hình 1 : Ví dụ một trƣờng hợp hợp nhất cây Các yêu cầu chức năng trong việc hợp nhất các bản tin có cấu trúc XML Công cụ hợp nhất 3-way và tạo sự khác biệt –ráp cây để đồng bộ hóa phải thỏa mãn một số yêu cầu sau: 1 Thao tác hợp nhất phải dễ hiểu. 2 Mọi thay đổi trên các node trong các nhánh, nhƣ di chuyển, xóa, cập nhật, chèn, hay sao chép cần phải đƣợc xuất hiện trong cây hợp nhất. Các thao tác di chuyển và sao chép phải không bị hạn chế. 3 Các thao tác trên node phải đƣợc xem xét đến tính tƣơng đối thay cho việc xem xét tuyệt đối. Ví dụ, nếu node con của một node n đƣợc sắp thứ tự lại 16
  17. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML trong một nhánh và cây con gốc tại node n đƣợc di chuyển trong một nhánh khác, thì cả hai thao tác di chuyển của n và sắp thứ tự lại của các node con của node n phải đƣợc thể hiện trong cây hợp nhất. Nhƣ thế, các node con của node n đã đƣợc di chuyển một cách tƣơng đối đối với n, không phải là di chuyển một cách tuyệt đối. 4 Bằng cách di chuyển, sao chép hay chèn một node, chúng ta đặt node đó trong một ngữ cảnh có các node bao quanh nó. Chúng ta muốn giữ cảnh đó sẽ đƣợc giữ nguyên trong cây hợp nhất. 5 Nếu một cây con đƣợc sao chép trong một nhánh, và đƣợc chỉnh sửa trong một nhánh khác, các chỉnh sửa phải truyền đến tất cả các sao chép của cây con đó trong phiên bản hợp nhất. Tuy nhiên, cũng có một phản ví dụ. Nếu cây con đƣợc sao chép là nhỏ, hay các bản sao chép chỉ là ánh xạ một cách gần đúng với nguyên gốc, các chỉnh sửa không nhất thiết phải đƣợc truyền đi. 6 Giả sử một node n tồn tại trong cả hai nhánh và các node mới đƣợc nối vào nhau nhƣ các node con đối với node n (chẳng hạn Tb=(R,a).T1=(r;a b) và T2=(R;a c)) Trong một số trƣờng hợp chúng ta muốn danh sách con hợp nhất chứa các node đƣợc nối từ hai nhánh hoặc trong trƣờng hợp khác điều này là một tính huống đụng độ. 7 Việc hợp nhất phải có tính tƣơng đối. 8 Các đụng độ phải đƣợc phát hiện và xử lý a- Cập nhật/Cập nhật. Đụng độ xảy ra nếu cùng một node đƣợc cập nhật ở cả hai nhánh. b- Xóa/Di chuyển, Xóa/Cập nhật và Xóa/sao chép. Tình huống này xảy ra nếu một node bị xóa trong một nhánh và đƣợc “chỉnh sửa”, tức là di chuyển hay cập nhật trong một nhánh khác c- Di chuyển/Di chuyển. Node đƣợc di chuyển đến các vị trí khác nhau trong các nhánh. 17
  18. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML 9 Công cụ tạo khác biệt-ráp cây phải cho ra tập khác biệt cực tiểu để giảm băng thông khi truyền trên mạng 2.3 Cây và XML 2.3.1 Cây Giả sử tập các node V và tập E V×V các cạnh nối các node. Nếu (u, v) Є E ta nói rằng (u, v) là một cạnh và u là cha của v. T=(V,E) là cây gốc nếu tập các cạnh thỏa mãn các điều kiện sau: 1 Có đúng một node RЄ V không có cha. Node này gọi là gốc của cây T. 2 Mọi node, ngoại trừ node gốc, có đúng một node cha 3 Mỗi node trong V đều có thể đƣợc tham gia chiếu đến từ gốc. Ta nói rằng một cây là có thứ tự nếu các node con v1, vk của nột node đƣợc đánh số duy nhất từ 1 đến k. Danh sách con của node u, kí hiệu u, là danh sách các node con của u theo thứ tự v1,v2, vk. Ta kí hiệu u(i) là một thành phần trong vi. Đối với cây có thứ tự, ta định nghĩa khái niệm node kề trái và node kề phải. Một cây không có thứ tự gọi là cây không thứ tự. Các node của cây đều đƣợc gán nhãn Các cây đƣợc diễn tả thao các quy ƣớc sau: 1 - Các node đƣợc gán nhãn R, a, b, c , a1 an .Node gốc thƣờng đƣợc gán nhãn R. 2- Cây bao gồm một node đƣợc ký hiệu bởi hàm nhãn node đó một cây T có nhiều hơn một node đƣợc kí hiệu bởi(a,Ta1,Ta2 Tan)với Tan là các cây con có gốc tại node an sao cho an là con của a. Giả sử T1=(R; a b) và T2=(R; a c). Để phân biệt node a trong cây T1 với node a trong cây T2, ta kí hiệu T1(a), T2(a). 18
  19. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML 2.3.2 Ánh xạ cây Ánh xạ: Một ánh xạ giữa hai cây T và T‟ là một tập các cạnh(n, m)n T và m T‟. Tập ánh xạ đƣợc kí hiệu là M, với chỉ số tùy chọn nhằm nhận biết các cây liên quan. Trƣớc khi tiến hành hợp nhất chúng ta phải tìm đƣợc một ánh xạ giữa hai cây. Ta sử dụng ánh xạ để phát hiện các thay đổi làm biến đổi một cây thành một cây khác. Khi chúng ta nhận đƣợc các thay đổi giữa các cây chúng ta có thể thực hiện việc hợp nhất bằng cách tích hợp các thay đổi này vào trong một cây đơn. Khi hợp nhất hai nhánh, ta kiểm tra từng node khi nó truyền đến cây hợp nhất. Tuy nhiên, có một số trƣờng hợp ta không thể xác định các thay đổi đối với một node Các kiểu ánh xạ: Các node có kiểu ánh xạ nội dung: Hai node n Є T và m Є T‟ đƣợc gọi là có kiểu ánh xạ nội dung nếu cạnh (n, m) Є MTT‟, là kiểu ánh xạ nội dung Các node có kiểu ánh xạ cấu trúc: Hai node n Є T và m Є T‟ đƣợc gọi là có kiểu ánh xạ cấu trúc nếu cạnh (n, m) Є MTT‟, là kiểu ánh xạ cấu trúc Các node có kiểu ánh xạ đầy đủ: Hai node n Є T và m Є T‟ đƣợc gọi là có kiểu ánh xạ đầy đủ nếu và chỉ nếu chúng có kiểu ánh xạ cấu trúc và nội dung Khái niệm các kiểu ánh xạ khác nhau cho phép ta xử lí các sao chép node theo cả hai nghĩa truyền dẫn thay đổi và không truyền dẫn thay đổi. Các thay đổi đối với nội dung và cấu trúc truyền đi phải một cách tƣờng minh. Nghĩa là mọi kiểu ánh xạ nội dung của một node cơ sở phải phản ánh cùng thay đổi trong nội dung và tất cả các kiểu ánh xạ cấu trúc phải phản ánh cùng thay đổi trong nội dung danh sách con. 19
  20. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML Ánh xạ tự nhiên: Một tập ánh xạ M giữa hai cây Tb và T1 đƣợc gọi là tự nhiên nếu và chỉ nếu: 1) Mỗi node m Є T1 có 0 hay 1 node ánh xạ tƣơng ứng trong Tb 2) Nếu và chỉ nếu n Є Tb có các node ánh xạ tƣơng ứng trong T1, thì có ít nhất một node trong số đó có kiểu ánh xạ đầy đủ. 3) Nếu và chỉ nếu n Є Tb có các node ánh xạ trong T1 tất cả các node có kiểu ánh xạ cấu trúc có danh sách con đồng nhất. 4) Nếu và chỉ nếu n Є Tb có các node ánh xạ tƣơng ứng trong T1, tất cả các node có kiểu ánh xạ nội dung có nội dung đồng nhất. 5) Các cạnh (n, m)Є M đƣợc xác định kiểu. Các kiểu bao gồm kiểu ánh xạ nội dung, kiểu ánh xạ cấu trúc và kiểu ánh xạ đầy đủ. 2.3.3 Hợp nhất cây Trong tất cả các định nghĩa T1 và T2 có thể tráo đổi cho nhau. Chúng ta giả sử rằng các tập ánh xạ MB1 và MB2 tồn tại và chúng là các tập ánh xạ tự nhiên Node cộng sự: Hai node n Є T1 và m Є T2 là node cộng sự nếu và chỉ nếu tồn tại một node b Є TB sao cho n và b là các node đƣợc ánh xạ ,và b và n và m cũng là các node đƣợc ánh xạ Hai hình thức đặc biệt của node cộng sự là cộng sự nội dung và cộng sự cấu trúc. Nếu hai node là cộng sự nội dung, chúng thể hiện các thay thế về nội dung của node trong cây hợp nhất. Nếu các node là cộng sự cấu trúc, chúng thể hiện các thay thế về danh sách con của node đó trong cây hợp nhất. Node cộng sự nội dung: Hai node n Є T1 và m Є T2 là các node cộng sự cấu trúc nếu và chỉ nếu tồn tại một node b Є TB sao cho n và b là các node ánh xạ nội dung và b và m là các node ánh xạ nội dung. Node cộng sự cấu trúc: Hai node n Є T1 và m Є T2 là các node cộng sự cấu trúc nếu và chỉ nếu tồn tại một node b Є TB sao cho n và b là các node ánh xạ cấu trúc và b và m là các node ánh xạ cấu trúc. 20
  21. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML Chúng ta tiếp tục bằng cách hình thức hóa khái niệm cập nhật, chèn, xóa, di chuyển, sao chép node. Chèn node: Giả sử m Є T1. Node m đƣợc gọi là đƣợc chèn nếu và chỉ nếu nó không có node nào ánh xạ trong TB. Xóa node: Giả sử b Є TB. Node b gọi là bị xóa nếu và chỉ nếu nó không có node nào ánh xạ trong T1 Node cập nhật: Giả sử b Є TB và m Є T1. Nếu m và b ánh xạ nội dung nhƣng nội dung của chúng không giống nhau, hay m và b ánh xạ cấu trúc, m gọi là đƣợc cập nhật đối với TB Số sequence: Giả sử rằng n là node trong 1 cây bất kì. Mỗi node ni trong danh sách con n= n1 nk có một số sequence đƣợc kí hiệu là Sn(x). Số sequence đó đƣợc định nghĩa nhƣ sau: Sn (ni) = I và Sn(x) = -1, x ∉ n. Cộng sự danh sách: Giả sử b ε TB và m ε T1. Nếu và chỉ nếu m(i) có một hay một số node ánh xạ yi ε b, danh sách cộng sự của nó là các node ánh xạ với yi, với số sequence nhỏ nhất. Ngƣợc lại m(i) không có danh sách cộng sự. In sequence: Giả sử b ε TB và m ε T1. m(k),k>1 đƣợc gọi là in sequence đối với b nếu và chỉ nếu m(k-1) có một danh sách cộng sự x trong b và m(k) có một danh sách cộng sự y trong b và S(x)< S(y) và với mọi i, Sn (x)<i<Sn(y), thì b(i) bị xóa trong T1.m(0) là in sequence đối với b nếu có một danh sách cộng sự x trong b và với mọi i, i<S(x) thì b(i) bị xóa trong T1. Node sao chép: Giả sử m ε T1 và node ánh xạ của m trong TB là b. Node m bị sao chép đối với TB nếu nó bị di chuyển và b có nhiều hơn 1 node ánh xạ trong T1. Nếu m bị sao chép và một số node ánh xạ hiện hữu trong danh sách con mp, lúc đó node ánh xạ của m trong mp với số sequence nhỏ nhất là node sao chép chính trong mp và mọi node sao chép khác trong mp gọi là các node sao chép phụ trong mp. Nếu một node b ε TB có các node ánh xạ mà các node này bị sao chép, ta nói rằng b bị sao chép. 21
  22. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML Node hợp nhất: Các node trong TM là các node hợp nhất. Mỗi node hợp nhất là kết quả của việc hợp nhất một node đơn hay hai node, trong trƣờng hợp đó các node là cộng sự. Một node hợp nhất p là kết quả việc hợp nhất node n đƣợc gọi là node hợp nhất của n. Node ngữ cảnh trái(phải): Giả sử ni ε n và TB là cây cơ sở. Node ngữ cảnh trái (phải) của ni là nkni(nin1) với nk(n1) là node đầu tiên ở ngay trƣớc(ngay sau)ni trong n mà không bị xóa đối với TB. Nếu nk(ni) không tồn tại, node ni không có node ngữ cảnh trái (phải). Node ngữ cảnh: Node ngữ cảnh của ni là nknin1, với nkn1 là node ngữ cảnh trái và nin1 là node ngữ cảnh phải. Nếu một trong hai node ngữ cảnh trái hay phải của ni không tồn tại, node ni chỉ có ngữ cảnh phải hay trái. Trong các trƣờng hợp này chúng ta nói rằng ngữ cảnh là trái hay phải. 2.3.4 Giải quyết bài toán hợp nhất cấu trúc để đồng bộ hóa Giống nhau về nội dung- ngữ nghĩa: Xác định độ giống nhau nội dung bằng Q-GRAM Khoảng cách chuỗi q-gram giữa hai chuỗi đƣợc xác định nhƣ sau: Cho Σ là bộ kí tự hữu hạn, Σ* là tập tất cả các chuỗi sinh ra từ Σ và Σq là tất cả các chuỗi có chiều dài q sinh ra từ Σ. Một q-gram là một chuỗi v = a1a2 aq Є Σq Cho v là 1 q-gram và x = a1a2 an là một chuỗi trong Σ*. Nếu v = aiai+1 ai+q-1 ⊂ x với I nào đó, thì v xuất hiện trong x. Chúng ta kí hiệu số lần xuất hiện của v trong x là Gq(x)[v]. q-gram profile của x là vectơ Gq(x) = (G(x)[v]), v є Σq Khoảng cách q-gram giữa các chuỗi x và y là chuẩn L1 của Gq(x) – Gq(y): q|Gq(x)[v] – Gq(y)[v]|. Dq(x,y) = Σv ε Σ Để tránh ảnh hƣởng các q-gram profile giống nhau giữa các bản tin không liên quan nhƣng đủ dài, chúng ta tăng giá trị của q với chiều dài tổ hợp 1 của chỗi theo công thức: 22
  23. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML 1 l< 50 q = 2 50 ≤ l < 150 4 l ≥ 150 Các hằng 50 và 150 là các giá trị gần đúng. Chúng ta kí hiệu hàm khoảng cách này là qdist( ). Đo độ giống nhau về nội dung giữa các node đƣợc chuẩn hóa đến khoảng cách [0,1], với 1 nghĩa là khác nhau hoàn toàn. Chúng ta không sử dụng độ đo khoảng cách trực tiếp để đo độ giống nhau, do chúng ta không muốn các chuỗi ánh xạ ngắn đƣợc xem là các ánh xạ rất tốt. Điều này là do chúng ta sử dụng sự giống nhau nhƣ là độ đo chắc chắn mà một node thực sự ánh xạ với một node khác. Mặc dù khoảng cách là 0 giữa hai node mà nội dung của nó là cùng kí tự đơn thực ra không chuyển tải nhiều thông tin. Nếu nội dung của các node là hai câu dài đồng nhất, chúng ta hình thành công thức tính sự giống nhau của hai node từ trọng số trung bình của khoảng cách q- gram và một số hạng về mức độ vi phạm sao cho nội dung càng ngắn thì càng bị gán số hạng có trị số mức độ vi phạm cao Chúng ta định nghĩa khoảng cách nội dung giữa hai node là: Max(| text(n)| ct, 1 (i) infoSize(n) = ce + Σ attr(a,i) ca + max(| val(n,a)| - cv ,1)) (ii) chú ý: (i) : n là text node (ii): n là element node attrInfor(a) = min(val|n1,a|- ce,1)+ min(val(n2,a)-cv,1) 23
  24. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML Với ct, cv là các hằng nhằm giảm sự đóng góp đối với sự giống nhau của bản tin ngắn và các giá trị thuộc tính. Ca là nội dung thông tin trong tên thuộc tính Ce là nội dung thông tin trong tên phần tử C là tập các thuộc tính trong cả hai n1 và n2 D là số thuộc tính của n1 và n2 không hiện diện trong cả hai node Hàm sametag (.,.) trả về ce nếu các tên phần tử bằng nhau, ngƣợc lại trả về 0. Các hàm infoSize (.,.) và attrInfo(.,.) trả về chiều dài đã xén của các giá trị thuộc tính và nội dung của một node. Mục đích của các hàm này làm giảm đóng góp của các bản tin ngắn và các giá trị thuộc tính đối với độ đo sự tƣơng đồng. Khoảng cách tối đa giữa hai node bây giờ cho bởi công thức: 24
  25. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML 2.3.5 Giải thuật tìm kiếm ánh xạ giữa hai cây Giải thuật tìm kiếm ánh xạ cây con Chúng ta sẽ tìm kiếm các cây con lớn nhất có thể có của TB và T1 ánh xạ đƣợc với nhau bằng giải thuật heuristic greedy Ánh xạ giữa hai cây Ánh xạ giữa hai cây là tìm các cây con tƣơng ứng nhau trong 2 cây. Sự tƣơng ứng đƣợc định nghĩa nhƣ sau: Ánh xạ chính xác giữa 2 cây con: Nội dung của node gốc và các node con cũng nhƣ thứ tự các node con cũng phải giống nhau hoàn toàn. Nói chung có thể chồng khít 2 cây lên nhau đƣợc. Ánh xạ tƣơng đồng cấu trúc: Nội dung nút gốc có thể khác nhau nhƣng nội dung cũng tƣơng tự của các node con phải giống nhau hoàn toàn. Vậy các chiến lƣợc chấp nhận ánh xạ tƣơng đồng sẽ phụ thuộc cách chập nhận độ sai lệch giữa 2 nút gốc với nhau. Chính tại yếu tố này chúng ta sẽ can thiệp vào bằng 2 cách đo độ sai lệch đó là 2 phƣơng pháp sử dụng: - Từ điển đồng nghĩa - Q-gram 25
  26. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML Sau đây là minh họa của các phƣơng pháp trên * Từ điển đồng nghĩa * Q-gram Để thực hiện việc ánh xạ cây con ta sử dụng giải thuật greendy:lấy một node trong T1 và toàn bộ cây TB làm thông tin vào và trả về một node trong TB là gốc của cây con ánh xạ lớn nhất Toàn bộ các công đoạn của thuật toán đƣợc trình bày trong bảng Procedure buildMatching(TB,T1: cây) 1. matchSubtrees(TB,T1(R)) 2. removeSmallCopies(TB,T1) 3. matchSimilarUnmatched(TB,T1) 4. setMatchTypes(TB,T1) End Procedure 26
  27. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML Ánh xạ cây con: Trƣớc hết chúng ta định nghĩa khái niệm cây con bị xén. Một cây con bị xén của cây T là một cây con của T có tất cả các hậu duệ của một số node trong cây con đó bị xóa đi. Hình ảnh cây con bị xén Cây con bị xén: Cho T là một cây, và T‟ là một cây có tất cả các node n T‟: n T. Cho Ts là cây nhận đƣợc từ T‟ là một cây con bị xén của T nếu và chỉ nếu Ts là một cây con của T Thủ tục matchSubtrees duyệt đệ quy cây T1 và tìm các cây con bị xén trong TB. Thƣờng thì một loạt các cây con ánh xạ đƣợc tìm thấy và cây con có nhiều node nhất đƣợc sử dụng. Trong trƣờng hợp có nhiều ánh xạ với cùng số tối đa node, ta sử dụng giải thuật heuristic để quyết định ánh xạ tốt nhất Khi cây con ánh xạ tốt nhất đƣợc chọn, các node của cây con đó trong T1 và TB đƣợc ánh xạ với nhau. Các node của cây con trong T1 cũng đƣợc thẻ hóa với một thẻ của cây con, đồng nhất một cách duy nhất cây con đó. Điều này đƣợc thực hiện để theo vết các cây con ánh xạ cần cho giai đoạn tiếp theo. Cuối cùng thủ tục đệ quy đối với mỗi node con của các node lá của cây con ánh xạ, tức là các node chƣa đƣợc ánh xạ. 27
  28. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML Thuật toán đƣợc trình bày chi tiết 1. Tìm kiếm các ánh xạ Khi tìm kiếm các node ánh xạ đối với node n trong TB, các node mà nội dung của chúng ánh xạ một cách chính xác đƣợc xem xét trƣớc.Nếu không, chúng ta tiếp tục tìm các node đồng nghĩa, nếu vẫn không có node nào tìm thấy. Chúng ta trả về tất cả các node mi TB sao cho nodeDistance (n, mi) ≤ min (c1* minDist, c2), với minDist là khoảng cách node nhỏ nhất giữa một node trong TB và node n, c1 là một hằng dùng để chỉ độ sai lệch ánh xạ so với mong đợi và c2 là hằng cutoff(xén) để ngăn ngừa các ánh xạ không rõ ràng. Thông thƣờng c1 = 2 và c2 = 0.4 2. Tìm kiếm các cây con ánh xạ Các cây con đƣợc ánh xạ theo cách duyệt theo chiều sâu (DFS) bắt đầu tại node n và mi và đệ quy cho đến khi các node hiện tại của lần duyệt có chính xác cùng số node con và nội dung của các node con này ánh xạ một cách chính xác. Chúng ta gọi một cây bị xén nhƣ thế là cây con ánh xạ 3 Chọn cây con ánh xạ tốt nhất Giai đoạn này bao gồm hai bƣớc: Chọn cây con có số node tối đa nhận đƣợc kết quả của giải thuật greendy và nếu có nhiều cây con có cùng số node tối đa, chọn ra cây con ánh xạ tốt nhất trong số đó. Trong trƣờng hợp tất cả các ánh xạ đều xấu, không có cây con nào đƣợc chọn là tốt nhất 4 Ánh xạ và đệ quy Sau khi cây con bị xén ánh xạ tốt nhất đƣợc chọn ra, các node của cây con đó đƣợc ánh xạ với các node tƣơng ứng trong T1. Các node của cây con trong T1 cũng đƣợc gán giá trị thẻ. Cuối cùng, thủ tục tiếp tục đệ quy 28
  29. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML Procedure matchSubtrees(TB:cây,n: node trong cây T1) 1. (m1, ,mi):= các ánh xạ của n trong TB 2. : =các cây con có gốc tại mi thuộc ánh xạ với cây con bị xén có gốc tại n 3. : =các cây con có số node tối đa 4. T:= ánh xạ tốt nhất của 5. If ánh xạ tốt nhất T tồn tại then 6. ánh xạ các node trong T với các node tƣơng ứng trong T 1 7. gán cây con trong T1 thẻ cây con duy nhất 8. End if 9. for mỗi node lá 1 trong T do 10. for mỗi node con li của l do 11. matchSubtrees(TB,li) 12. end for 13. end for End Procedure Thuật toán ánh xạ cây con (chọn ra cây con ánh xạ tốt nhất trong số các cây con ứng viên có độ lớn bằng nhau) Độ đo khoảng cách ngữ cảnh n và mi là: ContextDistance (n, mi) = Min (nodeDistance (n1, nii), nodeDistance (n1, mri), nodeDistance (n.mi)) Nếu chúng ta tìm một ứng viên mi sao cho đối với ứng viên đó n1 và m1i ánh xạ với nhau, chúng ta sẽ chọn mi. Nếu không có một ứng viên nhƣ vậy thì node có khoảng cách ngữ cảnh nhỏ nhất đƣợc sử dụng miễn là nó là node ánh xạ đủ tốt. Nghĩa là nếu kích thƣớc của ứng viên tốt nhất chỉ là một node, khoảng cách ngữ cảnh cần phải nhỏ hơn một hằng số nào đó, ngƣợc lại sẽ không có một ánh xạ tốt nhất nào đƣợc chọn. 29
  30. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML 2.3.6 Xử lý đụng độ Đụng độ element node Trƣờng hợp này sẽ đƣợc xử lí bằng 3 option: - Tự động chọn theo T1 - Để ngƣời dùng tự chọn - Chọn bằng cách đo khoảng cách ngữ nghĩa của tag name bằng cách sử dụng WordNet Đụng độ text node Trƣờng hợp này sẽ đƣợc xử lí bằng 3 option - Tự động chọn theo T1 - Để ngƣời dùng tự chọn - Cho phép chỉnh sửa nội dung của Text node Để tăng tính hiệu quả cho công cụ, quá trình xử lí đụng độ cập nhật/cập nhật Text node sẽ đƣợc chia làm hai giai đoạn: - Tính khác biệt giữa Text node thuộc TB và T1 và giữa TB và T2 - Chọn lựa chỉnh sửa 2.4 Chọn lựa mô hình Để xử lí tài liệu XML ta có thể dùng 2 mô hình, nói chính xác hơn là 2 kĩ thuật đó là mô hình SAX và mô hình DOM DOM (data Object Model) là kĩ thuật cho ta khả năng thao tác tài liệu XML nhƣ thao tác trên một cấu trúc cây. Tuy nhiên thông tin ở mỗi node của cấu trúc cây đó đã đƣợc định nghĩa sẵn, chính điều này đã hạn chế việc sử dụng DOM trong việc xử lí các nút có nhiều thông tin. SAX (Simple API for XML) là kĩ thuật phức tạp hơn DOM. SAX dựa trên mô hình xử lý theo sự kiện. SAX sẽ đọc vào file XML và phát sinh ra những sự kiện khi gặp các loại phần tử của tài liệu XML. Dựa vào những sự kiện này chúng ta sẽ tái tạo mô hình cây của tài liệu XML với thông tin mỗi nút (node) là do chúng ta 30
  31. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML quyết định. Vậy SAX trao quyền định nghĩa mô hình cây của tài liệu cho ngƣời xử dụng và cũng chính vì điều này làm cho mô hình xử lí SAX linh động hơn DOM. Thực chất mô hình DOM cũng phải dùng mô hình xử lí SAX trƣớc ,nhƣng bƣớc này là “trong suốt” với ngƣời dùng. Và do đó chúng ta sẽ xử dụng mô hình SAX để thực hiện chƣơng trình hợp nhất cấu trúc 2.5 Các thuật toán ứng dụng trong hợp nhất bản tin Trong việc hợp nhất bản tin có cấu trúc việc xác định các từ, ngữ nghĩa của một tập tin đƣợc dựa vào các từ điển Tiếng Việt 2.5.1 Từ điển đồng nghĩa Tiếng Việt Cũng nhƣ Tiếng anh, Tiếng Việt có rất nhiều từ đồng nghĩa và trái nghĩa với nhau. Các từ đồng nghĩa và phản nghĩa có thể đƣợc tìm thấy rất nhiều trong các bản tin tiếng việt và trong ngôn ngữ giao tiếp hằng ngày. Việc xử lí đụng độ trong quá trình tổng hợp các nguồn thông tin bản tin Tiếng Việt yêu cầu phải nhận biết đƣợc các cặp từ đồng nghĩa và trái nghĩa với nhau. Do đó, việc xây dựng từ điển đồng nghĩa- trái nghĩa Tiếng Việt là rất cần thiết. 2.5.2 Nguồn dữ liệu Nguồn dữ liệu là một tập dạng Text gồm nhiều dòng tổ chức theo nhiều mục. Cấu trúc của một mục dữ liệu trong tập tin này đƣợc mô tả nhƣ sau: W + {Danh sách các từ đồng nghĩa của W cách nhau bởi dấu phẩy} (ký hiệu S) ++ {Danh sách các từ trái nghĩa của W cách nhau bởi dấu phẩy} (ký hiệu A) Nhận xét: Theo quy luật phát sinh quan hệ, các từ trong tập S đều là các từ đồng nghĩa với nhau. Tƣơng tự, các từ trong tập A đều là các từ đồng nghĩa với nhau. Tƣơng tự, các từ trong tập A đều là các từ đồng nghĩa với nhau. 31
  32. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML 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 Việc tra cứu thông tin trực tiếp vào nguồn dữ liệu ban đầu rất chậm vì cấu trúc dữ liệu của nguồn dữ liệu chỉ là dạng text đơn giản. Để tăng tốc độ truy vấn thông tin, chúng ta phải mã hóa các từ thành các con số. Các từ đồng nghĩa với nhau thì có mã số chênh lệch nhau 1 đơn vị. Mối quan hệ giữa 2 từ nhƣ sau: Synonym (W1, W2) (ID (W1) = ID (W2)) Synonym(W1, W2) ((ID(W1) lẽ ID(W2)= ID(W1)+ 1) (ID(W2) lẽ ID(W1) = ID(W2)+1++ Với ID (W1), ID (W2) lần lƣợt là mã số của từ W1 và W2. 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 In put: dữ liệu vào Output: +Bƣớc 1: ID =1 Cây hậu tố Ts rỗng + Bƣớc 2: Lặp Xét từng mục trong tập tin nguồn dữ liệu. Với mỗi mục: W + S ++ A - w S U {W} thực hiện: thêm cặp(w, ID)vào cây hậu tố. - w A thực hiện: thêm cặp (w,ID + 1) vào cây hậu tố. ID = ID +2 32
  33. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML 2.5.5 Thuật toán xác định quan hệ giữa 2 từ Tiếng Việt: Input: Cho 2 từ Tiếng Việt word1 và word2. Output: Mối quan hệ giữa chúng đƣợc xác định qua các bƣớc sau: + Bƣớc 1: Xác định mã số của word1, word2 thông qua cây hậu tố Ts . Ts Word 1 ID1 Ts word2 ID2 + Bƣớc 2: Nếu ID1 = ID2 thì word1 và word2 là hai từ đồng nghĩa với nhau và dừng thuật toán. Ngƣợc lại xuống bƣớc 3 . + Bƣớc 3: - Nếu ID1 lẽ và ID2 = ID1 + 1 thì word 1 và word2 là 2 từ trái nghĩa với nhau và dừng thuật toán - Nếu ID2 lẽ và ID1 = ID2+1 thì word1 và word2 là 2 từ trái nghĩa với nhau và dừng thuật toán. - Thông báo word1 và word2 không có quan hệ với nhau. Thuật toán kết thúc * Chú ý: Do sự phức tạp và đa dạng của các Font chữ Tiếng Việt nên trong quá trình xây dựng và truy vấn từ điển, các từ Tiếng Việt nguyên thủy ban đầu sẽ đƣợc chuyển sang dạng mã ngõ để việc lƣu trữ và truy vấn dữ liệu không bị sai sót. 33
  34. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML Cách chuyển mã căn cứ vào bảng sau: Sắc Huyền Hỏi Ngã Nặng â , ă đ 1 2 3 4 5 6 7 8 9 2.5.6 Ánh xạ cây Giải thuật tìm kiếm ánh xạ cây con Xóa các sao chép nhỏ: Giai đoạn tinh chỉnh đầu tiên là xác định một ngƣỡng trên số lƣợng dữ liệu nhân bản đƣợc xem xét là kết quả của các thao tác sao chép, chứ không phải là kết quả của thao tác chèn. Procedure builMatching (TB,T1: cây) 1. matchSubtrees(TB,T1(R)) 2. removeSmallCopies(TB,T1) 3. matchSimilarUnmatched(TB,T1) 4. setMatchType(TB,T1) End Procedure Các công đoạn ánh xạ giữa hai cây Thủ tục removeSmallCopies kiểm tra tất cả các nút trong T1 có nút ánh xạ cơ sở của nó có nhiều nút ánh xạ trong T1. Nếu cây con bản sao của TB có nội dung thông tin nhỏ hơn một ngƣỡng cho trƣớc, ánh xạ đó sẽ bị xóa và nhƣ thế nút đƣợc xem là nút đƣợc chèn vào. Nội dung thông tin của một cây con là độ đo lƣợng thông tin chứa đựng trong một cây con. Chúng ta đã xử dụng công thức heuristic sau đây để tính nội dung thông tin cho một cây con: Hằng số ced là nội dung thông tin trên một cạnh. Ở đây chúng ta đã xử dụng giá trị ced=4. 34
  35. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML Sau khi thực hiện thủ tục matchSubtrees tất cả các nút ánh xạ trong T1 đƣợc thẻ hóa với thẻ cây con để đồng nhất cây con ánh xạ mà chúng là một phần của cây con đó. Việc thẻ hóa này cho thấy rất thuận lợi khi thực hiện thủ tục removeSmallCopies . Đôi khi, các cây con của tất cả các ánh xạ đều nhỏ hơn ngƣỡng sao chép. Trong trƣờng hợp này chúng ta không muốn xóa tất cả các ánh xạ, giải pháp tốt hơn là cố gắng nhận biết ánh xạ tốt nhất. Chúng ta thực hiện điều này bằng cách xem xét các nút láng giềng của nút gốc của câu con ánh xạ: nếu các nút bên trái và bên phải ánh xạ với các nút ở bên trái và bên phải trong cây cơ sở, chúng ta thêm các nội dung thông tin của các cây ánh xạ vào các nút đó của ứng viên để xóa nút ánh xạ, ứng viên có nhiều byte nhất sẽ không đƣợc đánh dấu không ánh xạ 35
  36. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML Giá trị của hằng số ngƣỡng sao chép cthresold đƣợc xử dụng ngầm định là 128 byte 36
  37. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML 2.5.7 Thuật toán hợp nhất 3- way theo cấu trúc * Hợp nhất 3 – way theo cấu trúc Chúng ta sử dụng các ánh xạ MB1 và MB2 đƣợc sinh ra trong giai đoạn ánh xạ cây, để sinh ra cây hợp nhất.Do không phát sinh kịch bản chỉnh sửa, chúng ta sẽ không bị hạn chế trên các thao tác của kịch bản chỉnh sửa. Hạn chế duy nhất áp đặt là các ánh xạ tự nhiên và không cho phép các thao tác “uncopy”. Ý chính của thuật toán này là duyệt các cây T1 và T2 đồng thời để các node partner đƣợc thăm cùng một lúc. Mỗi bƣớc duyệt sẽ xuất ra một node đến TM. Node đƣợc xuất là sự hợp nhất các node trong T1 và T2 đang đƣợc thăm Tiến trình hợp nhất gồm 3 giai đoạn: - Giai đoạn tạo danh sách hợp nhất của mỗi cây con dựa vào cây TB. Giai đoạn này các thay đổi đặc trƣng của cây con so với cây TB sẽ đƣợc đánh dấu bằng 2 thao tác là treo những node đƣợc thêm mới và khóa những node bị di chuyển - Giai đoạn tạo thành các cặp hợp nhất. Input của giai đoạn này chính là 2 danh sách hợp nhất mà ta có đƣợc từ giai đoạn 1 của 2 cây con T1 và T2. Output là danh sách các cặp node sẽ đƣợc thực hiện hợp nhất ở giai đoạn sau. Mọi thay đổi đặc trƣng của 2 cây con mà ta xác định ở giai đoạn 1 sẽ đƣợc bảo lƣu trong giai đoạn này - Giai đoạn hợp nhất các cặp lấy từ danh sách có đƣợc ở giai đoạn 2, ta sẽ thực hiện hợp nhất từng cặp trong danh sách này, kết quả sẽ là một node mới trong cây hợp nhất Để hỗ trợ việc trình bày thuật toán chúng ta giới thiệu khái niệm con trỏ cây (tree cursos). Con trỏ cây chỉ ra vị trí hiện tại trong cây theo cách tƣơng tự nhƣ con trỏ trong trình xử lí bản tin chỉ thị vị trí hiện tại của bản tin. Con trỏ cây cũng có thể đƣợc định vị tại một vị trí đặc biệt là NULL, khi con trỏ không hoạt động. Chúng ta sẽ kí hiệu các con trỏ là Cn với n là tên con trỏ và kí hiệu tham chiếu đến node mà con trỏ đang trỏ đến là node(Cn). Nút NULL đƣợc kí hiệu là 0. Quy ƣớc 37
  38. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML việc con trỏ đang trỏ tại một node m là Cn = m. Cho C1 và C2 và CM lần lƣợt là con trỏ của các cây T1 và T2, TM. Procedure treemerge 1. phát sinh danh sách cặp hợp nhất của các node con của node(C1) và node(C2) 2. p:= node(CM) 3. for với mỗi cặp := {ui,vj} trong danh sách cặp hợp nhất do 4. hợp nhất các nội dung của ui và vj thành một node mới w 5. thêm w nhƣ một node con của p và định vị lại CM tại w 6. định vị lại C1 đến u và C2 đến v 7. call treemerge 8. end for End Procedure Thuật toán hợp nhất Các node partner đƣợc sắp thành cặp để hợp nhất bởi thuật toán sẽ đƣợc tham chiếu nhƣ cặp hợp nhất. Các cặp hợp nhất đƣợc kí hiệu bởi {n, m}, với n m là các node trong cặp. Các cặp hợp nhất cũng có thể chỉ chứa một node, trong trƣờng hợp đó ta kí hiệu là {n, .}. Danh sách cặp hợp nhất là danh sách các cặp hợp nhất đƣợc phát sinh bằng cách tổ hợp các danh sách con của các node đƣợc trỏ tới bởi C1 và C2. Ví dụ hợp nhất cây đơn giản. 38
  39. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML Chúng ta giả sử T1 và T2,TB là các cây trong hình trên,chúng đƣợc ánh xạ theo hình vẽ, và tất cả các con trỏ đƣợc định vị tại gốc của mỗi cây. 1 Phát sinh danh sách cặp hợp nhất Trong bƣớc này chúng ta sắp cặp các con của node (C1) và node (C2) theo các ánh xạ đó, sau đó chúng ta xác định dãy các cặp này, theo các di chuyển bất kì đƣợc hình thành trong các cây. Các node bị xóa sẽ đƣợc loại bỏ khỏi danh sách. Trong trƣờng hợp này chúng ta sắp cặp các danh sách con b a c i d ( của T1(R)) và a b‟ c ( của T2(R)). Danh sách cặp kết quả là: b a c i b‟ a c • Dòng trên chứa các node từ T1 và dòng dƣới chứa các node từ T2. Chú ý rằng thứ tự của các cặp tuân theo các di chuyển đƣợc tạo thành trong T1 đối với TB, và d bị xóa trong T2 nên sẽ không xuất hiện và node i đƣợc chèn vào không có cặp 2. Việc hợp nhất các nội dung Bây giờ chúng ta xác định việc hợp nhất nội dung của cặp {ui,vi}phải thực hiện nhƣ thế nào. Nói chung, chúng ta luôn lấy nội dung mà thể hiện sự thay đổi đối với TB. Trong trƣờng hợp này việc hợp nhất nội dung sẽ là b‟ a c i. 3. Thêm w Chúng ta đã hợp nhất thành công các node ui và vj thành node w. Node hợp nhất đƣợc thêm vào cây hợp nhất và vị trí con trỏ đƣợc cập nhật để nối các node con đến node mới bằng cách thêm b‟ a c i cây hợp nhất của chúng ta bây giờ là: TM = (R; b‟ a c i) 4. Định vị lại C1 và C2 Các con trỏ của T1 và T2 đƣợc cập nhật để trỏ đến các node trong cặp hợp nhất mà nội dung hợp nhất của chúng đã đƣợc thêm vào TM. Thông thƣờng các con trỏ đƣợc trỏ trực tiếp đến ui và vj không phải là các partner cấu trúc. Con trỏ cập nhật đối với các cặp hợp nhất trong cùng trƣờng hợp là: 39
  40. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML {b,b‟} => C1 = T1(b) ^C2 = T2(b‟) {a ,a} => C1 = T1(a) ^ C2 = T2( a) {c ,c } => C1 = T1(c) ^ C2 = T2( c) {i , •} => C1 = T1(i) ^ C2 = 0 5 Gọi thực hiện treemerge Đây là bƣớc đệ quy của thuật toán. Chú ý rằng chúng ta đã thêm một node hợp nhất của các node con của các node đƣợc trỏ đến bởi các giá trị nguyên thủy của C1 và C2 đén TM. Các con trỏ C1, C2 đã đƣợc reset để trỏ đến một tập các partner mới và Cm đƣợc cập nhật đến vị trí “chèn ” mới trong TM. 40
  41. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML 2.5.8 Kiểm tra các node bị xoá và di chuyển xa: Cho các danh sách hợp nhất đƣợc phát sinh từ các node con của u và v là M1 và M2. Node cơ sở chung của u và v là node b. Chúng ta bắt đầu tổ hợp các danh sách hợp nhất bằng cách kiểm tra các node xuất hiện trong b nhƣng không có trong M1 hoặc M2 ,tức là các node mà đã bị xóa hoặc di chuyển xa khỏi b trong cả hai nhánh. Nói tóm lại, một node bất kì bi b không xuất hiện nhƣ là một node của một entry trong M1 mà node đó có một entry ánh xạ đƣợc trong M2 có một entry của nó bị loại bỏ khỏi M2 và ngƣợc lại. Tuy nhiên, chúng ta không thể chỉ đơn giản loại bỏ các entry từ cả hai danh sách hợp nhất mà không cân nhắc. Chúng ta cần kiểm tra rằng không có các chỉnh xửa trong một cây của các node bị xóa có gốc tại entry bị xóa, trong trƣờng hợp đó các chỉnh xửa này sẽ đƣợc bỏ qua. Thêm nữa, một entry có thể không bị xóa nếu nó đƣợc cập nhật, di chuyển hoặc là bản sao chép chính khi các bản sao chép thứ cấp tồn tại sẽ vi phạm các yêu cầu 1, 4, 5. Nếu một entry với các node bị treo đƣợc loại bỏ, các node bị treo phải đƣợc di chuyển đến entry ở trƣớc . Việc cây delete TD của node bị xóa n chứa n và tất cả các hậu duệ bị xóa của n, mà không có bất kì node nào không bị xóa ở giữa. Chúng ta định nghĩa cây delete của n là cây con Tn mà từ đó các cây con Tn1 Tnk bị loại bỏ, với các node ni Tn đƣợc ánh xạ đầy đủ với node cơ sở và có một partner, tức là các node mà đƣợc đảm bảo sẽ đƣợc viếng tại một giai đoạn khác của thuật toán. 41
  42. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML Bây giờ TD là tập các node sẽ không xuất hiện trong cây hợp nhất, do việc loại bỏ node n khỏi danh sách hợp nhất. Chúng ta cần kiểm tra rằng không có node nào trong các node này thể hiện một thao tác chỉnh xửa và nếu một node này là thể hiện một thao tác chỉnh xửa, chúng ta có thể hoặc bỏ qua hoặc đƣa ra một cảnh báo về việc cập nhật có khả năng mất. Việc kiểm tra các node chỉnh xửa đƣợc thực hiện theo các định nghĩa thao tác chỉnh xửa trong cây hợp nhất. 42
  43. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML Ví dụ trên kết quả của việc thực hiện thủ tục removeDeletedOrMoved trên các danh sách nhƣ sau: D D Với M1 và M 2 là các danh sách hợp nhất M1 và M2 sau khi thủ tục removeDeleteOrMoved đƣợc thực hiện Nhƣ ta có thể thấy node d đã bị loại bỏ khỏi M1, do nó đã bị xóa trong T2 và node a đã bị loại bỏ khỏi M2,do di chuyển xa trong T1. Chú ý rằng kết quả này có đúng các node cùng entry trong cả hai danh sách : b ,c,e,h,f,và g 2.5.9 Tổ hợp các danh sách hợp nhất thành danh sách hợp nhất Trong bƣớc phát sinh danh sách hợp nhất cuối cùng, chúng ta tổ hợp các D D danh sách hợp nhất M1 và M1 thành một danh sách cặp hợp nhất tuân theo việc sắp thành dãy các node bị treo và các entry bị khóa. Bây giờ chúng ta có thể thấy lợi D D ích của các node bị treo và giai đoạn xóa trƣớc: các entry trong M1 và M2 có tƣơng D ứng 1-1 tức là node của mỗi entry trong M1 là partner của đúng một node entry D trong M2 và ngƣợc lại. Sự tƣơng ứng 1-1 này làm đơn giản hóa đáng kể việc hợp nhất các danh sách. Chúng ta xử dụng việc duyệt đồng thời các danh sách hợp nhất, tƣơng ứng D việc duyệt node đồng thời đƣợc mô tả ở trên. Cho p1 và p2 là vị trí hiện tại trong M1 D và M2 , cả hai đƣợc khởi đầu tại vị trí đầu tiên của danh sách. Chúng ta xuất ra các node p1 và p2 trỏ đến các node bị treo cũng nhƣ các cặp hợp nhất. Vị trí của p1 và p2 lúc đó đƣợc cập nhật để chúng ta luôn đi theo sau một khóa phải nếu tồn tại. Điều này đƣợc lập lại cho đến khi đạt đến cuối danh sách hợp nhất 43
  44. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML Trong ví dụ chúng ta thực hiện thủ tục makeMergePairList trên các danh sách D D hợp nhất M1 và M2 đƣợc phát sinh trong giai đoạn trƣớc. Kết quả danh sách cặp hợp nhất là: Với các node trong hàng trên từ T1 và các node trong hàng dƣới từ T2( đây cũng là vấn đề định dạng danh sách,thuật toán thêm các cặp {n,m} sao cho n T1 và m T2 hoặc n T2 và m T1. Chúng ta chú ý rằng thứ tự của các cặp trong danh sách hợp nhất thỏa các D D khóa trong M1 và M2 ,cũng nhƣ treo các node không khóa trong thứ tự nguyên thủy của nó. Thêm nữa, node i đƣợc chèn trong T1 không có cặp hợp nhất và cả hai bản sao chép của node b trong T1 đƣợc sắp với phiên bản cập nhất của node trong T2 Mặc dù rõ ràng thứ tự của các cặp tuân theo thứ tự ngầm định bởi các entry bị khóa trong các danh sách hợp nhất, một số thuộc tính, chẳng hạn tính dừng của vòng lặp là không rõ ràng. 44
  45. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML CHƢƠNG 3: ĐÁNH GIÁ THỰC NGHIỆM VÀ KẾT LUẬN 3.1 Giới thiệu về phần mềm Tree Way Merge Merge là các tập tin hình ảnh, kết hợp ứng dụng và thƣ mục đồng bộ hóa từ Araxis. Xử dụng nó để so sánh và hợp nhất các mã nguồn, các trang web, XML và các tập tin dạng bản tin với các ứng dụng hiệu quả. Trực tiếp mở và so sánh các bản tin từ Microsoft Ofice, OpenDocument, PDF và các tập tin RTF. Hierarchies làm việc với các thƣ mục chứa hàng ngàn tập tin. Merge tích hợp nhiều SCM và các hệ thống khác Ƣu điểm: - Đối với các chuyên gia pháp lí và xuất bản: Xác định ngay tất cả các thay đổi khác nhau giữa các hợp đồng hoặc bản thảo. Trực tiếp mở và so sánh các bản tin từ Microsoft Office, OpenDocument, PDF . Sao chép bản tin từ các ứng dụng khác và dán nó trực tiếp vào một cửa sổ so sánh bản tin. - Đối với kỹ sƣ phần mềm và các nhà phát triển web: So sánh và hiểu kết hợp các tập tin mã nguồn phiên bản khác nhau. Làm việc một cách nhanh chóng và chính xác, cho dù bạn đang so sánh các tập tin cá nhân hoặc chi nhánh của reconciling toàn bộ mã nguồn. - Những ngƣời dùng khác: Cần phải giữ nhiều thƣ mục trong đồng bộ. Hợp nhất giúp tiết kiệm và giảm các lỗi bằng cách giúp bạn làm việc một cách nhanh chóng và chính xác. Merge cho phép bạn có thể so sánh và làm việc với các phiên bản khác nhau của tập tin bản tin, chẳng hạn nhƣ chƣơng trình mã nguồn, html, xml và các tập tin. Merge có thể trích xuất và so sánh các bản tin từ Microsoft Office, OpenDocument, PDF và các tập tin rtf. Tệp tin XML có thể đƣợc hiển thị với các định dạng đặc biệt, giúp bạn xem các thay đổi một cách rõ ràng hơn. Nó hỗ trợ các tệp tin với mã ascii, mbcs (Mixed Byte Character Set) và ký tự Unicode Encodings. Liên kết giữa các dòng đƣợc trích ra các tài liệu đƣợc hiển thị rõ ràng nhƣ thế nào khi có liên quan 45
  46. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML Merge cho thấy chi tiết nổi bật những thay đổi trong dòng. Nó có thể đƣợc cấu hình để bỏ qua sự khác biệt trong dòng và các hậu tố, cũng nhƣ các thay đổi trong dòng phù hợp với quy định. Nhƣợc điểm: Trong quá trình hợp nhất các bản tin có cấu trúc vẫn còn một số nhƣợc điểm chƣa khắc phục đƣợc và chƣa thân thiện với ngƣời dùng, đòi hỏi cần phải có một chƣơng trình dễ hơn để hợp nhất các bản tin Tiếng Việt. 3.2 Mô hình thử nghiệm và đánh giá Cấu trúc của tài liệu XML 46
  47. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML Mô hình của phần mềm Tree Way Merge Demostration Một số các mô hình ví dụ hợp nhất 3-way 47
  48. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML Ví dụ về hợp nhất 2-way Tập dữ liệu để đánh giá: STT Loại tài liệu Số lƣợng Nội dung 1 Quyết định 20 Thông báo quyết định của trƣờng ĐHDLHP 2 Bản kiểm điểm 30 Công tác nâng lƣơng 3 Biên bản 30 Quản lý bộ môn Kết quả đánh giá: Các kết qủa thử nghiệm trên các tập tin XML thực tế cho thấy chƣơng trình chạy khá chính xác. Đặc biệt các trƣờng hợp có liên quan đến ngữ nghĩa trên Tag Name cũng nhƣ các đụng độ trên Text Node đã đƣợc giải quyết theo hƣớng thân thiện ngƣời dùng và tỏ ra có ý nghĩa thực sự - Chƣơng trình giúp tiết kiệm thời gian và giảm các lỗi làm việc một cách nhanh chóng và chính xác - Dễ dàng xử dụng đối với mọi ngƣời - Thích hợp mở với các loại file 48
  49. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML Kết luận Hợp nhất thông tin có cấu trúc là bài toán rất cần thiết, đặc biệt là trong môi trƣờng cộng tác nhiều ngƣời cùng chia sẻ một số thông tin hoặc trong môi trƣờng một ngƣời dùng chia sẻ thông tin trên nhiều thiết bị. Nếu hệ thống của chúng ta là hệ thống mạng mạnh, bài toán đồng bộ hóa đã đƣợc giải quyết khá tốt, mục đích của đề tài này là nghiên cứu và phát triển công cụ hợp nhất để đồng bộ hóa trong môi trƣờng mạng yếu với các tập tin có cấu trúc, đƣợc hỗ trợ tối thiểu của hệ thống. Các điểm mới của luận văn bao gồm: 1 Về phƣơng pháp tiếp cận: Điểm khác biệt căn bản của đồ án so với các tiếp cận hiện đó là chọn lựa cách hợp nhất 3-way nhƣng mã hóa tập khác biệt dƣới dạng một kịch bản chỉnh xửa để đồng bộ hóa dữ liệu có dạng XML. Cách tiếp cận này cho phép hợp nhất các bản tin có cấu trúc khác nhau và sinh tập khác biệt có kích thƣớc cực tiểu. 2 Về kĩ thuật ánh xạ: Tận dụng tính gợi ý của các thẻ XML để tăng tính chính xác của thuật toán ánh xạ. 3 Về xử lí đụng độ: Đụng độ Tag Name đƣợc tinh tế hóa thông qua chọn lựa tự động-Đụng độ Text Node đƣợc xử lí linh động hơn thông qua thuật toán LCS, cho phép ngƣời dùng nhận biết các thay đổi trong Text Node 4 Hiện thực công cụ xử lí quá trình hợp nhất và đồng bộ hóa có tính ứng dụng cao, ngoài ra còn chứng minh khả năng hỗ trợ đa ngôn ngữ, cũng cho phép mở rộng ứng dụng hệ thống không chỉ trên các bản tin XML mà trên các dữ liệu có cấu trúc bất kì của công cụ. Tuy nhiên vẫn còn nhiều vấn đề chƣa đƣợc đề cập và giải quyết về vấn đề hợp nhất thông tin, chẳng hạn việc xem xét DTD của tập tin XML xử lí tự động việc hợp nhất không chỉ cấu trúc XML mà còn hợp nhất nội dung của Text Node. Tuy nhiên các nỗ lực của đồ án cho thấy có thể xây dựng một phần mềm thƣơng mại dựa trên các vấn đề đã đƣợc phát triển trong đồ án. 49
  50. Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML Đề hƣớng phát triển trong tƣơng lai Đồ án đã giải quyết việc hợp nhất để đồng bộ hoá các bản tin có cấu trúc dạng XML và thử nghiệm cho thấy công cụ có khả năng đồng bộ hoá một cách hiệu quả trong môi trƣờng mạng yếu Tuy nhiên đây là những ý tƣởng cải tiến bƣớc đầu còn phải hoàn thiện nhiều hơn nữa mới có thể trở thành sản phẩm thƣơng mại Các vấn đề cần đƣợc giải quyết tiếp theo để hoàn thiện công cụ bao gồm: ->Nghiên cứu cải tiến thuật toán hợp nhất 3-way, nhất là các trƣờng hợp đụng độ cấu trúc. -> Nghiên cứu ứng dụng các thuật toán tạo khác bịêt mới để có tập khác biệt càng nhỏ càng tốt. -> Thể hiện kịch bản chỉnh xửa cũng nhƣ các bản tin XML dƣới dạng thân thiện ngƣời dùng. -> Xử lí DTD: hai tập tin có cấu trúc giồng nhau nhƣng DTD khác nhau cần phải đƣợc nhận biết. Tài liệu tham khảo [1] Asklund U. – Identifying Conflicts During Structural Merge – Proceeding of the Nordic Workshop on Programming Environment Research „ 94 . Lund Universit y, 1994. [2] Cederqvist P. Et al. – Version Management with CVS – Signum Support AB, Linkoping, Swenden, 1993. [3] Eric Amstrong - Working with XML – 1.1/docs/tutorial/index.html [4] IBM Alphaworks. – XML diff and merge tôl home page http:// www.alphaworks.ibm.com/tech/xmldiffmerge [5] http:// www.W3c.org – World wide web consortium (W3C) 50