Làm thế nào để xác định một chuỗi dna cho giống với một số khác

Question

Tôi hy vọng tôi đang diễn đạt điều này một cách chính xác để vượt qua những gì tôi đang tìm kiếm.

Tôi cần so sánh hai phần văn bản. Nếu hai dây giống nhau, tôi muốn có điểm số rất giống nhau nếu các dây rất khác nhau, tôi cần điểm số rất khác nhau.

Nếu tôi lấy hàm băm md5 của một email và thay đổi một ký tự, giá trị băm thay đổi đáng kể Tôi muốn một cái gì đó không thay đổi quá nhiều. Tôi cần so sánh hai phần nội dung giống nhau như thế nào mà không lưu trữ chuỗi.

Cập nhật: Tôi đang xem xét kết hợp một số ý tưởng từ các liên kết khác nhau mà mọi người đã cung cấp. Lý tưởng nhất là tôi sẽ thích một hàm đầu vào đơn lẻ để tạo ra điểm số của mình vì vậy tôi đang xem xét việc sử dụng một chuỗi tham chiếu để luôn so sánh đầu vào của mình. Tôi cũng đang xem xét các ký tự asci và tổng hợp các ký tự này. Vẫn đọc tất cả các liên kết được cung cấp.

Answer 1

Điều bạn đang tìm kiếm là một thuật toán LCS (xem thêm Levenshtein distance). Bạn cũng có thể thử Soundex hoặc một số khác phonetic algorithm.

Answer 2

Kiểm tra của họ Levenshtein Distance

Trong PHP bạn thậm chí có levenshtein() function mà làm chính xác điều đó.

Answer 3

Tôi cần so sánh hai phần văn bản. Nếu hai dây giống nhau, tôi muốn có điểm số rất giống nhau nếu các dây rất khác nhau, tôi cần điểm số rất khác nhau.

Nó thực sự phụ thuộc vào ý bạn là "giống" hoặc "khác". Ví dụ: nếu ai đó thay thế "Hoa Kỳ" bằng "Hoa Kỳ" trong chuỗi của bạn, hầu hết là cùng một chuỗi (vì Hoa Kỳ chỉ là viết tắt cho một cái gì đó dài hơn) hoặc nó rất khác (vì nhiều ký tự thay đổi))?

Về cơ bản, bạn cần đưa ra một hàm mô tả cách tính toán "mẫu" hoặc sử dụng định nghĩa đã có từ trước. Ví dụ: số Levenshtein distance nói trên đo lường sự khác biệt tổng số dựa trên số lượng thay đổi bạn phải thực hiện để truy cập chuỗi gốc.

Answer 4

Vì khoảng cách Levenshtein cần cả hai chuỗi đầu vào để tạo ra một giá trị, bạn sẽ phải lưu trữ tất cả các chuỗi.

Tuy nhiên, bạn có thể sử dụng một số chuỗi nhỏ làm điểm đánh dấu và chỉ lưu trữ các chuỗi này dưới dạng chuỗi.

Sau đó, bạn sẽ tính khoảng cách Levenshtein từ một chuỗi mới đến từng chuỗi đánh dấu này và lưu trữ các giá trị này. Sau đó bạn có thể đoán rằng hai chuỗi có khoảng cách Levenshtein tương tự với tất cả các điểm đánh dấu cũng tương tự nhau. Nó có khả năng là hợp lý để "kỹ sư" các điểm đánh dấu theo cách như vậy mà của họ khoảng cách Levenshtein lẫn nhau là càng lớn càng tốt. Tôi không biết liệu có một số nghiên cứu theo hướng này không.

Answer 5

Nhiều người đã đề xuất xem xét khoảng cách/chỉ số như phương pháp tiếp cận và tôi nghĩ từ ngữ của câu hỏi dẫn đến cách đó. (Nhân tiện, một băm như md5 đang cố gắng làm khá nhiều điều ngược lại mà một số liệu thực hiện, vì vậy không có gì ngạc nhiên khi điều này không hiệu quả với bạn.Có những ý tưởng tương tự không thay đổi nhiều trong khu vực đồng bằng nhỏ, nhưng tôi nghi ngờ họ không mã hóa đủ thông tin cho những gì bạn muốn làm)

Đặc biệt, hãy đưa ra các cập nhật trong nhận xét, tôi nghĩ kiểu tiếp cận này không phải là rất hữu ích.

Điều bạn đang tìm kiếm là nhiều vấn đề về cụm, nơi bạn muốn tạo chữ ký (tức là vector đặc trưng) từ mỗi email và sau đó so sánh nó với các mục nhập mới. Vì vậy, về cơ bản những gì bạn có là một vấn đề học máy. Quyết định "gần" có nghĩa là một chút thách thức. Tuy nhiên, để bắt đầu, giả sử nó thực sự là email bạn đang xem bạn có thể làm tốt để xem các loại tính năng tạo bởi nhiều bộ lọc spam, điều này sẽ cung cấp cho bạn (có thể là Euclide, ít nhất là bắt đầu) đo khoảng cách dựa trên chữ ký (vector đặc trưng).

Nếu không biết rõ hơn về sự cố của bạn thì khó có thể cụ thể hơn.

Answer 6

Đọc nhận xét của bạn, có vẻ như bạn đang thực sự cố so sánh toàn bộ tài liệu, mỗi tài liệu chứa nhiều từ.

Điều này được thực hiện thành công trong hệ thống truy xuất thông tin theo số treating documents as N-dimensional points in space. Mỗi từ trong ngôn ngữ là một trục. Khoảng cách dọc theo trục được xác định bằng số lần từ đó xuất hiện trong tài liệu. Các tài liệu tương tự sau đó "gần" nhau trong không gian.

Bằng cách này, toàn bộ tài liệu không cần phải được lưu trữ, chỉ cần đếm từ. Và thông thường những từ phổ biến nhất trong ngôn ngữ không được tính.