Thuật toán phiên bản XML

Question

Tôi đang tìm một cách hiệu quả để so sánh và nhận được sự khác biệt giữa hai cây phân tích dựa trên XML.

Bạn sẽ đề xuất cách nào tốt nhất để lưu trữ những khác biệt đó? Tôi đã có thể làm điều này:

XML A:

<w:p> 
    <w:pPr> 
    <w:spacing w:after="1"/> 
    </w:pPr> 
    <w:r> 
    <w:t>World</w:t> 
    </w:r> 
</w:p> 

XML B:

<w:p> 
    <w:pPr> 
    <w:spacing w:after="1"/> 
    </w:pPr> 
    <w:r> 
    <w:t>ASDF</w:t> 
    </w:r> 
</w:p> 

Thuật toán xác định rằng "Thế giới" đã được đổi thành "asdf" và sau đó cửa hàng:

div: <w:p><w:r><w:t>World</w:t> -> <w:p><w:r><w:t>ASDF</w:t> 

Điều này có đủ để trang trải tất cả các trường hợp có thể xảy ra không?

Có ai biết cách tốt để làm điều đó không? Bất kỳ trợ giúp sẽ thực sự được đánh giá cao!

Answer 1

Nó có thể khó hơn. Nhìn vào ví dụ này:

<w:p> 
    <w:pPr> 
    <w:spacing w:after="1"/> 
    </w:pPr> 
    <w:r> 
    <w:t>World</w:t> <-- Case 1: this changes to <w:t>ASDF</w:t> 
    <w:t>World</w:t> <-- Case 2: this changes to <w:t>ASDF</w:t> 
    </w:r> 
</w:p> 

Để có thể nhận ra cả hai trường hợp, bạn sẽ phải lưu trữ một như

div: <w:p><w:r><w:t>World</w:t> -> <w:p><w:r><w:t>ASDF</w:t> 

và người kia như

div: <w:p><w:r><w:t>World</w:t><w:t>World</w:t> -> <w:p><w:r><w:t>World</w:t><w:t>ASDF</w:t> 

hoặc một cái gì đó tương tự (bạn cũng có thể muốn thêm các thẻ đóng "w: p" vào cả hai thẻ để biến chúng thành các cây con XML hợp lệ). Nói chung, các chương trình như vậy có thể trở nên rất phức tạp, vì vậy tôi sẽ không khuyên bạn tạo một cái gì đó hoàn toàn mới nhưng sử dụng một số thuật toán khác hiện có (hầu hết sẽ đủ tốt ngay cả khi không phân tích cú pháp cấu trúc XML) hoặc sửa đổi một trong số họ cho phù hợp với nhu cầu của bạn.

Answer 2

XMLDiff:

Giải thích làm thế nào để sử dụng XML Diff và công cụ Patch, mà so sánh hai XML tập tin và tạo ra một đầu ra XML của sự khác biệt, bằng cách sử dụng một kịch bản điển hình mà độc giả có thể áp dụng cho các ứng dụng của riêng họ.

Answer 3

Làm thế nào để tìm kiếm theo chiều sâu đơn giản trên phần chung? Đó là, thực hiện tìm kiếm theo chiều sâu và ngay khi bạn gặp phải sự khác biệt, hãy lưu trữ nó và bắt đầu quay lại. Thông tin bổ sung cần thiết để xây dựng phần ngữ cảnh của đầu ra có thể được lưu trữ dễ dàng trên "ngăn xếp ngược".

Answer 4

khi bạn muốn so sánh sự khác biệt giữa hai cây và bằng cách nào đó tạo ra "sự khác biệt" so với so sánh đó, về cơ bản bạn đang tìm kiếm một biến thể của khoảng cách chỉnh sửa cây. Để bắt đầu, hãy xem this paper.

Một vấn đề "khoảng cách chỉnh sửa" phổ biến hơn là vấn đề chỉnh sửa khoảng cách cho chuỗi. Phần mềm điều khiển phiên bản như CVS hoặc SVN sử dụng "mã hóa delta" để lưu trữ các thay đổi được thực hiện cho các tệp sử dụng các biến thể của thuật toán khoảng cách chỉnh sửa chuỗi để tính toán các vùng đồng bằng.Trường hợp của cây ít phổ biến hơn nhưng chắc chắn thú vị.