Thuật toán để đo lường sự giống nhau giữa hai chuỗi chuỗi

Question

Làm cách nào để đo lường tỷ lệ phần trăm tương tự giữa hai chuỗi chuỗi?

Tôi có hai tập tin văn bản và In file có trình tự được viết như

Đầu tiên file:

AAA BBB DDD CCC GGG MMM AAA MMM

Thứ hai file:

BBB DDD CCC MMM AAA MMM

Làm cách nào để đo lường sự giống nhau giữa hai tệp này theo thứ tự chuỗi?

Ví dụ ở ví dụ trên, cả hai tệp đều giống nhau do thứ tự các chuỗi giống nhau tuy nhiên một số chuỗi bị thiếu trong tệp-2. Thuật toán nào là phù hợp nhất để giải quyết vấn đề này để tôi có thể đo lường mức độ giống nhau của chuỗi không phải là tần số của chuỗi trong hai?

Answer 1

Bạn có thể sử dụng thuật toán Levenstein Distance. Nó phân tích có bao nhiêu chỉnh sửa cần thiết để chuyển đổi một chuỗi thành chuỗi khác. This bài viết giải thích nó khá tốt, và một thực hiện mẫu được cung cấp.

Sao chép dán từ Codeproject:

1. Set n to be the length of s. ("GUMBO") 
    Set m to be the length of t. ("GAMBOL") 
    If n = 0, return m and exit. 
    If m = 0, return n and exit. 
    Construct two vectors, v0[m+1] and v1[m+1], containing 0..m elements. 
2. Initialize v0 to 0..m. 
3. Examine each character of s (i from 1 to n). 
4. Examine each character of t (j from 1 to m). 
5. If s[i] equals t[j], the cost is 0. 
    If s[i] is not equal to t[j], the cost is 1. 
6. Set cell v1[j] equal to the minimum of: 
    a. The cell immediately above plus 1: v1[j-1] + 1. 
    b. The cell immediately to the left plus 1: v0[j] + 1. 
    c. The cell diagonally above and to the left plus the cost: v0[j-1] + cost. 
7. After the iteration steps (3, 4, 5, 6) are complete, the distance is found in the cell v1[m]. 

Answer 2

Bạn có thể sử dụng chức năng python của SequenceMatcher.ratio mà các biện pháp chuỗi tương tự như một chiếc phao trong khoảng [0, 1]. Nếu T là tổng số phần tử trong cả hai chuỗi và M là số kết quả phù hợp, đây là số 2.0 * M/T. Mã chính là như sau:

from difflib import SequenceMatcher 
text1 = 'AAA BBB DDD CCC GGG MMM AAA MMM' 
text2 = 'BBB DDD CCC MMM AAA MMM' 
s = SequenceMatcher(None, text1, text2) 
similarity = s.ratio() * 100 

Tôi hy vọng điều này có thể giúp bạn!