Chúng tôi có một yêu cầu trong dự án rằng chúng ta phải so sánh hai văn bản (update1, update2) và đưa ra một thuật toán để xác định có bao nhiêu từ và số câu đã thay đổi.Thuật toán so sánh văn bản
Có bất kỳ thuật toán nào mà tôi có thể sử dụng không? Tôi thậm chí không tìm kiếm mã. Nếu tôi biết thuật toán, tôi có thể mã nó trong java. Cảm ơn bạn.
Thông thường việc này được thực hiện bằng cách tìm số Longest Common Subsequence (thường được gọi là vấn đề LCS). Đây là cách các công cụ như công việc diff. Tất nhiên, diff là một công cụ định hướng dòng, và có vẻ như nhu cầu của bạn hơi khác. Tuy nhiên, tôi giả định rằng bạn đã xây dựng một số cách để so sánh các từ và câu.
Một số loại khác biến thể có thể hữu ích, ví dụ như wdiff
Nếu bạn quyết định để đưa ra thuật toán của riêng bạn, bạn sẽ phải giải quyết các tình huống mà một câu đã được chèn vào. Ví dụ trong hai giấy tờ sau:
The men are bad. I hate the men
và
The men are bad. John likes the men. I hate the men
công cụ của bạn sẽ có thể nhìn về phía trước để nhận ra rằng trong lần thứ hai, I hate the men chưa được thay thế bằng John likes the men nhưng thay vào đó là bị ảnh hưởng, và một câu mới được chèn vào trước nó. tức là nó phải báo cáo việc chèn câu, chứ không phải thay đổi bốn từ theo sau bởi một câu mới.
Thuật toán cụ thể được sử dụng bởi khác biệt và hầu hết các tiện ích so sánh khác là Eugene Myer's An O(ND) Difference Algorithm and Its Variations. Có một cài đặt Java của nó có sẵn trong gói java-diff-utils.
An O(NP) Sequence Comparison Algorithm được sử dụng bởi công cụ tìm khác biệt của subversion.
Để biết thông tin của bạn, bản thân bạn có nhiều bản cài đặt với nhiều ngôn ngữ lập trình khác nhau trong trang sau của github.
Khó khăn đến khi so sánh các file lớn một cách hiệu quả và với hiệu suất tốt. Vì vậy, tôi thực hiện một biến thể của Myers O (NĐ) thuật toán khác - mà thực hiện khá tốt và chính xác (và hỗ trợ lọc dựa trên biểu thức chính quy):
Thuật toán có thể được kiểm tra ra ở đây: becke.ch compare tool web application
Và một chút biết thêm thông tin trên trang chủ: becke.ch compare tool
Dưới đây là hai bài viết mô tả các thuật toán so sánh văn bản khác thường nên xuất 'tốt hơn' (ví dụ:nhỏ hơn, ý nghĩa hơn) khác biệt:
Các bài báo đầu tiên trích dẫn thứ hai và đề cập đến điều này về thuật toán của nó:
Heckel [3] chỉ ra tương tự các vấn đề với kỹ thuật LCS và đề xuất một thuật toán vôi tuyến tính để phát hiện các di chuyển khối. Thuật toán thực hiện đầy đủ nếu có vài ký tự trùng lặp trong chuỗi. Tuy nhiên, thuật toán cung cấp cho kết quả kém hơn . Ví dụ: với hai chuỗi aabb và bbaa, Thuật toán của Heckel không phát hiện ra bất kỳ chuỗi con chung nào.
Các bài báo đầu tiên được đề cập trong this answer và lần thứ hai trong this answer, cả hai cho câu hỏi tương tự như SO:
http://stackoverflow.com/questions/65199/ c-sharp-compare-algorithms –
http://neil.fraser.name/software/diff_match_patch/myers.pdf –