Câu hỏi Các thuật toán khác nhau của tài liệu hoạt động như thế nào?

Nói chung, diff'ing thường được giải quyết bởi Vấn đề hậu quả phổ biến lâu nhất. Xem thêm "Thuật toán " của bài viết trên Wikipedia về Khác biệt:

Hoạt động của diff được dựa trên   giải quyết các subsequence phổ biến dài nhất   vấn đề.

Trong vấn đề này, bạn có hai   chuỗi các mục:

   a b c d f g h j q z

   a b c d e f g i j k r x y z

và bạn muốn tìm lâu nhất   chuỗi các mục hiện diện trong   cả hai chuỗi gốc trong cùng một   gọi món. Đó là, bạn muốn tìm một cái mới   trình tự có thể lấy từ   chuỗi đầu tiên bằng cách xóa một số   các mục và từ chuỗi thứ hai   xóa các mục khác. Bạn cũng muốn   trình tự này miễn là   khả thi. Trong trường hợp này, nó là

   a b c d f g j z

Từ chuỗi phổ biến dài nhất   nó chỉ là một bước nhỏ để có được   đầu ra tương tự:

   e   h i   q   k r x y 
   +   - +   -   + + + +

Điều đó nói rằng, tất cả điều này hoạt động tốt với các văn bản dựa trên văn bản. Vì Tài liệu Word có hiệu quả ở định dạng nhị phân và bao gồm nhiều thông tin định dạng và dữ liệu, điều này sẽ phức tạp hơn nhiều. Lý tưởng nhất, bạn có thể xem xét tự động hoá chính Word vì nó có khả năng "khác biệt" giữa các tài liệu, như được mô tả chi tiết ở đây:

Microsoft Word Mẹo: Làm thế nào để so sánh hai tài liệu cho sự khác biệt

Một khác biệt cơ bản là một giải pháp đến vấn đề thứ bậc phổ biến dài nhất.

Giải pháp tối ưu đòi hỏi kiến ​​thức về lập trình năng động vì vậy nó là một vấn đề khá phức tạp để giải quyết.

Tuy nhiên, nó cũng có thể được thực hiện bằng cách xây dựng một cây hậu tố. Cả hai thuật toán đều được vạch ra đây.

Xem Thuật toán chênh lệch O (ND) cho C #.

Như Ben S đã chỉ ra, vấn đề khác biệt có thể được giải quyết thông thường bằng cách giải quyết vấn đề thứ bậc phổ biến dài nhất. Cụ thể hơn, The Thuật toán Hunt-McIlroy là một trong những thuật toán cổ điển đã được áp dụng cho vấn đề (ví dụ: trong việc triển khai Unix ' khác biệt tiện ích).