Sự cố: Cần Độ dài của LCS giữa hai chuỗi. Kích thước của chuỗi tối đa là 100 ký tự. Bảng chữ cái là một ADN thông thường, 4 ký tự "ACGT". Cách tiếp cận năng động không đủ nhanh.Thuật toán Nhanh (er) cho Độ dài của Hậu quả Chung Dài nhất (LCS)
Vấn đề của tôi là tôi đang đối phó với rất nhiều và rất nhiều cặp (của hàng trăm triệu như xa như tôi có thể nhìn thấy). Tôi tin rằng tôi đã giảm việc gọi hàm LCS_length xuống mức tối thiểu có thể vì vậy cách duy nhất để làm cho chương trình của tôi chạy nhanh hơn là có chức năng LCS_Length hiệu quả hơn.
Tôi đã bắt đầu bằng cách thực hiện theo phương pháp lập trình động thông thường. Điều đó mang lại câu trả lời đúng và hy vọng được triển khai đúng cách.
#define arrayLengthMacro(a) strlen(a) + 1
#define MAX_STRING 101
static int MaxLength(int lengthA, int lengthB);
/*
* Then the two strings are compared following a dynamic computing
* LCS table algorithm. Since we only require the length of the LCS
* we can get this rather easily.
*/
int LCS_Length(char *a, char *b)
{
int lengthA = arrayLengthMacro(a),lengthB = arrayLengthMacro(b),
LCS = 0, i, j, maxLength, board[MAX_STRING][MAX_STRING];
maxLength = MaxLength(lengthA, lengthB);
//printf("%d %d\n", lengthA, lengthB);
for (i = 0; i < maxLength - 1; i++)
{
board[i][0] = 0;
board[0][i] = 0;
}
for (i = 1; i < lengthA; i++)
{
for (j = 1; j < lengthB; j++)
{
/* If a match is found we allocate the number in (i-1, j-1) incremented
* by 1 to the (i, j) position
*/
if (a[i - 1] == b[j - 1])
{
board[i][j] = board[i-1][j-1] + 1;
if(LCS < board[i][j])
{
LCS++;
}
}
else
{
if (board[i-1][j] > board[i][j-1])
{
board[i][j] = board[i-1][j];
}
else
{
board[i][j] = board[i][j-1];
}
}
}
}
return LCS;
}
Đó phải là O (mn) (hy vọng).
Sau đó, để tìm tốc độ, tôi tìm thấy bài đăng này Longest Common Subsequence Đã cho phép O(ND) paper bởi Myers. Tôi đã thử điều này liên quan đến LCS với kịch bản chỉnh sửa ngắn nhất (SES). Quan hệ họ đưa ra là D = M + N - 2L, trong đó D là chiều dài của SES, M và N là độ dài của hai chuỗi và L là độ dài LCS. Nhưng điều này không phải lúc nào cũng đúng trong quá trình triển khai của tôi. Tôi thực hiện việc triển khai (mà tôi nghĩ là chính xác):
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define arrayLengthMacro(a) strlen(a)
int LCS_Length (char *a, char *b);
int MinLength (int A, int B);
int Max (int A, int B);
int snake(int k, int max, char *a, char *b, int lengthA, int lengthB);
int main(void)
{
int L;
char a[] = "tomato", b[] = "potato"; //must give LCS = 4
L = LCS_Length(a, b);
printf("LCS: %d\n", L);
char c[] = "GTCGTTCGGAATGCCGTTGCTCTGTAAA", d[] = "ACCGGTCGAGTGCGCGGAAGCCGGCCGAA"; // must give LCS = 20
L = LCS_Length(c, d);
printf("LCS: %d\n", L);
char e[] = "human", f[] = "chimpanzee"; // must give LCS = 4
L = LCS_Length(e, f);
printf("LCS: %d\n", L);
char g[] = "howareyou", h[] = "whoareyou"; // LCS =8
L = LCS_Length(g, h);
printf("LCS: %d\n", L);
char i[] = "TTCTTTCGGTAACGCCTACTTTATGAAGAGGTTACATTGCAATCGGGTAAATTAACCAACAAGTAATGGTAGTTCCTAGTAGAGAAACCCTCCCGCTCAC",
j[] = "GCACGCGCCTGTTGCTACGCTCTGTCCATCCTTTGTGTGCCGGGTACTCAGACCGGTAACTCGAGTTGCTATCGCGGTTATCAGGATCATTTACGGACTC"; // 61
L = LCS_Length(i, j);
printf("LCS: %d\n", L);
return 0;
}
int LCS_Length(char *a, char *b)
{
int D, lengthA = arrayLengthMacro(a), lengthB = arrayLengthMacro(b),
max, *V_, *V, i, k, x, y;
max = lengthA + lengthB;
V_ = malloc(sizeof(int) * (max+1));
if(V_ == NULL)
{
fprintf(stderr, "Failed to allocate memory for LCS");
exit(1);
}
V = V_ + lengthA;
V[1] = 0;
for (D = 0; D < max; D++)
{
for (k = -D; k <= D; k = k + 2)
{
if ((k == -D && V[k-1] < V[k+1]) || (k != D && V[k-1] < V[k+1]))
{
x = V[k+1];
}
else
{
x = V[k-1] + 1;
}
y = x - k;
while ((x < lengthB) && (y < lengthA) && (a[x+1] == b[y+1]))
{
x++;
y++;
}
V[k] = x;
if ((x >= lengthB) && (y >= lengthA))
{
return (lengthA + lengthB - D)/2;
}
}
}
return (lengthA + lengthB - D)/2;
}
Có các ví dụ trong chính. Ví dụ: "cà chua" và "khoai tây" (không bình luận), có chiều dài LCS là 4. Việc thực hiện thấy rằng nó là 5 sice SES (D trong mã) đi ra như 2 thay vì 4 mà tôi mong đợi (xóa "t", chèn "p", xóa "m", chèn "t"). Tôi có khuynh hướng nghĩ rằng có lẽ thuật toán O (ND) cũng thay thế được, nhưng tôi không chắc chắn về điều này.
Bất kỳ phương pháp nào có thể triển khai được (tôi không có kỹ năng lập trình bao la) đều được hoan nghênh. (Nếu ai đó biết cách tận dụng lợi thế của bảng chữ cái nhỏ chẳng hạn).
EDIT: Tôi nghĩ sẽ hữu ích khi nói lên mọi thứ khác, rằng tôi sử dụng hàm LCS giữa BẤT K two hai chuỗi bất kỳ lúc nào. Vì vậy, nó không chỉ là chuỗi nói s1, so với vài triệu người khác. Nó có thể là s200 với s1000, sau đó s0 với s10000, và sau đó 250 với s100000. Không có khả năng theo dõi hầu hết các chuỗi được sử dụng. Tôi yêu cầu độ dài LCS KHÔNG phải là xấp xỉ, vì tôi đang triển khai thuật toán xấp xỉ và tôi không muốn thêm lỗi bổ sung.
CHỈNH SỬA: Chỉ cần chạy callgrind. Đối với một đầu vào của 10000 dây Tôi dường như gọi hàm lcs khoảng 50.000.000 lần, cho các cặp dây khác nhau. (10000 dây là thấp nhất tôi muốn chạy và tối đa là 1 triệu (nếu điều đó là khả thi)).
Trong phiên bản thứ hai, bạn sẽ không xóa 'V_', điều này chắc chắn sẽ gây ra sự cố nếu bạn gọi hàm này hàng trăm triệu lần. Bạn nên trong mọi trường hợp tránh phân bổ bộ nhớ mỗi khi chức năng được gọi, vì nó sẽ làm chậm bạn xuống. Trong trường hợp của bạn, tôi sẽ khai báo một mảng có độ dài cố định 'int V_ [2 * MAX_STRING + 2]' trên stack. – TonyK
Không gian được LCS sử dụng là O (mn). Bạn có thể đưa nó xuống O (n), nó có thể làm cho chương trình của bạn nhanh hơn nhiều, bởi vì tỷ lệ hit cho bộ nhớ cache sẽ tăng lên. Tuy nhiên, tôi thường sử dụng này nếu n, m ~ 10^3. Bạn có thể thử [this] (http://www.ideone.com/4rG7k) mã mà tôi đã viết đôi khi trước đây và thấy sự khác biệt, nếu có, trong thời gian. –
@logic_max: đó là một sửa đổi tốt đẹp của thuật toán, nhưng bản sao trên dòng 19 sẽ hoàn tác bất kỳ lợi thế hiệu suất nào của việc tránh truy cập bộ nhớ cache (mà tôi tưởng tượng không quá khủng khiếp đối với mảng ~ 40kb). Bạn có thể tránh bản sao đó bằng cách giữ hai con trỏ int, L và L_old mà bạn trao đổi ở mỗi lần lặp. –