Thuật toán liên kết ký tự Java

Question

Tôi có hai mảng 100 ký tự (tối đa, có thể ít hơn hoặc không cùng kích thước) mà tôi muốn căn chỉnh. Tôi muốn thêm "-" khi có một ký tự khác với ký tự còn lại. Tôi đã tìm thấy thuật toán Needleman–Wunsch, dựa trên lập trình động và thuật toán Smith–Waterman là phương pháp căn chỉnh chung cục bộ cũng dựa trên lập trình động nhưng có vẻ quá phức tạp đối với những gì tôi muốn làm. Tôi chỉ cần một thuật toán đơn giản trong Java có lẽ khoảng ít hơn 50 dòng, mã này sẽ được dịch sang ngôn ngữ lắp ráp sau, vì vậy mà tại sao tôi cần một thuật toán đơn giản.

Có cách nào thực hiện loại căn chỉnh này với thuật toán khác không? Nếu có ai đó có thể chỉ cho tôi cách làm điều này? Tôi tìm kiếm trên phần biostar, nhưng có vẻ như tôi cần sử dụng hai thuật toán mà tôi đã đề cập.

Tiếng Anh không phải là ngôn ngữ mẹ đẻ của tôi, vì vậy, có lẽ tôi đã tìm kiếm từ khóa sai.

Chương trình của tôi đã hoạt động với thuật toán Needleman và khoảng 200 dòng mã (ish) của nó.

Ví dụ về mong muốn đầu vào/đầu ra:

Input 
Array 1 : MKNLASREVNIYVNGKLV 
Array 2 : QMASREVNIYVNGKL 


Output 
Array 1 (or a simple print) : -MKNLASREVNIYVNGKLV 
Array 2 (or a simple print) : QM---ASREVNIYVNGKL- 

Cảm ơn

Answer 1

Sử dụng một biến thể của khoảng cách levenshtein thực hiện chính xác những gì bạn muốn:

Output

-MKNLASREVNIYVNGKLV 
QM---ASREVNIYVNGKL- 

Code:

public class Main { 
    public static void main(String[] args) { 
     String[] aligned = align("MKNLASREVNIYVNGKLV", "QMASREVNIYVNGKL"); 
     System.out.println(aligned[0]); 
     System.out.println(aligned[1]); 
    } 

    public static String[] align(String a, String b) { 
     int[][] T = new int[a.length() + 1][b.length() + 1]; 

     for (int i = 0; i <= a.length(); i++) 
      T[i][0] = i; 

     for (int i = 0; i <= b.length(); i++) 
      T[0][i] = i; 

     for (int i = 1; i <= a.length(); i++) { 
      for (int j = 1; j <= b.length(); j++) { 
       if (a.charAt(i - 1) == b.charAt(j - 1)) 
        T[i][j] = T[i - 1][j - 1]; 
       else 
        T[i][j] = Math.min(T[i - 1][j], T[i][j - 1]) + 1; 
      } 
     } 

     StringBuilder aa = new StringBuilder(), bb = new StringBuilder(); 

     for (int i = a.length(), j = b.length(); i > 0 || j > 0;) { 
      if (i > 0 && T[i][j] == T[i - 1][j] + 1) { 
       aa.append(a.charAt(--i)); 
       bb.append("-"); 
      } else if (j > 0 && T[i][j] == T[i][j - 1] + 1) { 
       bb.append(b.charAt(--j)); 
       aa.append("-"); 
      } else if (i > 0 && j > 0 && T[i][j] == T[i - 1][j - 1]) { 
       aa.append(a.charAt(--i)); 
       bb.append(b.charAt(--j)); 
      } 
     } 

     return new String[]{aa.reverse().toString(), bb.reverse().toString()}; 
    } 
} 

Answer 2

Các mô tả về vấn đề của bạn ngay lập tức làm cho tôi nghĩ về Levenshtein distance và thuật toán liên quan của nó, đó là đơn giản (chắc chắn ít hơn 50 dòng) nhưng cũng dựa trên lập trình động.

Thuật toán gốc chỉ tính số lượng thay đổi cần thiết, nhưng nó có thể dễ dàng sửa đổi để tìm chèn, xóa và thay thế được yêu cầu. Trên thực tế tôi không chắc chắn nếu bạn thậm chí muốn xử lý thay thế, làm thế nào bạn sẽ align cho ví dụ ABC và ADC?