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

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. 
Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML 
 42 
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. 
Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML 
 43 
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: 
Với M1
D
 và M
D
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 
danh sách hợp nhất M1
D
 và M1
D
 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 
ích của các node bị treo và giai đoạn xóa trƣớc: các entry trong M1
D
 và M2
D có tƣơng 
ứng 1-1 tức là node của mỗi entry trong M1
D
 là partner của đúng một node entry 
trong M2
D
 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 
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
D
, 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 
Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML 
 44 
 Trong ví dụ chúng ta thực hiện thủ tục makeMergePairList trên các danh sách 
hợp nhất M1
D
 và M2
D
 đƣợ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 
khóa trong M1
D
 và M2
D,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. 
Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML 
 45 
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 
Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML 
 46 
 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 
Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML 
 47 
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 
Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML 
 48 
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 
Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML 
 49 
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. 
Đồ án tốt nghiệp Phƣơng pháp hợp nhất các bản tin có cấu trúc XML 
 50 
Đề 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)