Ở đây tại nơi làm việc, chúng ta thường cần phải tìm một chuỗi từ danh sách các chuỗi phù hợp nhất với một chuỗi đầu vào khác. Hiện tại, chúng tôi đang sử dụng thuật toán Needleman-Wunsch. Thuật toán thường trả về rất nhiều kết quả dương tính giả (nếu chúng tôi đặt số điểm tối thiểu quá thấp), đôi khi nó không tìm thấy kết quả phù hợp khi cần (khi điểm tối thiểu quá cao) và hầu hết các lần, chúng ta cần phải kiểm tra kết quả bằng tay. Chúng tôi nghĩ chúng ta nên thử các lựa chọn thay thế khác.Thuật toán đối sánh chuỗi gần đúng
Bạn có kinh nghiệm gì về thuật toán không? Bạn có biết cách các thuật toán so sánh với nhau không?
Tôi thực sự đánh giá cao một số lời khuyên.
PS: Chúng tôi đang viết mã bằng C#, nhưng bạn không nên quan tâm đến nó - tôi đang hỏi về các thuật toán nói chung.
Ồ, tôi xin lỗi tôi quên đề cập đến điều đó.
Không, chúng tôi không sử dụng nó để khớp với dữ liệu trùng lặp. Chúng tôi có một danh sách các chuỗi mà chúng tôi đang tìm kiếm - chúng tôi gọi đó là danh sách tìm kiếm. Và sau đó chúng tôi cần xử lý văn bản từ nhiều nguồn khác nhau (như nguồn cấp dữ liệu RSS, trang web, diễn đàn, v.v.) - chúng tôi trích xuất các phần của các văn bản đó (có toàn bộ quy tắc cho điều đó, nhưng điều đó không liên quan) và chúng tôi cần khớp những người chống lại danh sách tìm kiếm. Nếu chuỗi khớp với một trong các chuỗi trong danh sách tìm kiếm - chúng ta cần thực hiện thêm một số thao tác (điều này cũng không liên quan).
Chúng tôi không thể thực hiện việc so sánh bình thường, bởi vì các dây được chiết xuất từ các nguồn bên ngoài, hầu hết các lần, bao gồm một số lời thêm, vv
Dù sao, nó không phải là để phát hiện trùng lặp.
Bạn có khớp các chuỗi 'thực' (tức là tiếng Anh) hoặc tin sinh học không? Nếu chuỗi thực, bạn đang sử dụng ma trận thay thế của bạn? –
Các câu hỏi tương tự tại đây http://stackoverflow.com/questions/31494/how-to-detect-duplicate-data và tại đây http://stackoverflow.com/questions/42013/levenshtein-distance-based-methods-vs-soundex Những người khác có thể được tìm thấy thông qua các thẻ và cụm từ tìm kiếm có liên quan. Tuy nhiên, bạn không chỉ định chính xác * tại sao * bạn cần phải khớp các chuỗi theo cách này - bạn có đang kiểm tra dữ liệu trùng lặp không? –