Trong loạt bài này mình sẽ giới thiệu những kĩ thuật để cải tiến thuật toán quy hoạch động. Kĩ thuật trong bài này mình viết ở đây chủ yếu dựa trên notes của Jeff Erickson [1].

Tiết kiệm bộ nhớ bằng chia để trị

Trong bài viết trước, mình giới thiệu phương pháp quy hoạch động để tính khoảng cách Edit Distance (ED) giữa hai xâu $A[1,2,\ldots,n]$, $B[1,2,\ldots,m]$ với thời gian $O(mn)$. Gọi $ED[i,j]$ là khoảng cách giữa hai xâu con $A[1,2,\ldots,i]$ và $B[1,2,\ldots, j]$. Công thức đệ quy sau chính là ý tưởng chính của thuật toán quy hoạch động:

 
Trong bài viết trước, chúng ta đã thảo luận hai cách thực thi thuật toán quy hoạch động với bộ nhớ tương ứng là $O(mn)$ và $O(m)$. Nếu chúng ta chỉ quan tâm đến khoảng cách giữa hai xâu, thuật toán thứ hai hiển nhiên sẽ là lựa chọn tốt. Bây giờ nếu bài toán yêu cầu in ra một dãy với tổng số lượng các các thao tác "chèn", "xóa", "thay thế" nhỏ nhất để biến $A$ thành $B$, chúng ta sẽ làm thế nào?

Với thuật toán $O(mn)$, bằng cách truy ngược bảng $ED[1,2,\ldots, n][1,2,\ldots,m]$, chúng ta có thể dễ dàng thu được dãy tối ưu các thao tác. Tuy nhiên với cách thực thi với bộ nhớ $O(m)$, gần như không thể truy ngược lại vì chúng ta không lưu toàn bộ bảng $ED[1,2,\ldots, n][1,2,\ldots,m]$. Tuy nhiên, vào năm 1975, Dan Hirshberg đề xuất phương pháp chia để trị không những tính được khoảng cách giữa hai xâu với thời gian $O(mn)$ và bộ nhớ $O(m)$ mà còn tìm được một dãy tối ưu các thao tác để chuyển $A$ thành $B$ với cùng thời gian và bộ nhớ. Giải thuật của Dan Hirshberg sẽ là chủ đề chính của phần này.

 
Thuật toán của Hirshberg dựa trên quan sát rằng bài toán chuyển xâu $A[1,2,\ldots, n]$ thành xâu $B[1,2,\ldots,m]$ có thể được chia thành hai bài toán con: bài toán thứ nhất chuyển xâu $A[1,2,\ldots,n/2]$ thành $B[1,2,\ldots,h]$ và bài toán thứ hai chuyển xâu $A[n/2+1, \ldots, n]$ thành $B[h+1,2,\ldots,m]$. Vấn đề ở đây là làm sao để tìm điểm chia $h$. Hirshberg chứng minh bổ đề sau:

 
Ta sẽ chứng minh bổ đề này sau. Bây giờ giả sử chúng ta đã có thuật toán Hirshberg$(A[1,2,\ldots,n], B[1,2,\ldots,m])$ tìm điểm chia $h$ trong thời gian $O(mn)$ và bộ nhớ $O(m)$. Ta có thể gọi đệ quy trên các bài toán con để giải bài toán ban đầu. Chi tiết như trong giả mã sau:

 
Có thể dễ thấy là bộ nhớ cần thiết của thuật toán là $O(m)$ vì bộ nhớ cần thiết của thủ tục Hirshberg$(A[1,2,\ldots,n], B[1,2,\ldots,m])$ là $O(m)$. Thời gian tính của thuật toán được cho bởi công thức đệ quy sau:

 
Bằng phương pháp quy nạp, ta có thể chứng minh rằng $T(m,n) = O(mn)$.

Giải thuật Hirshberg tìm điểm chia

Giải thuật Hirshberg tìm điểm chia bằng phương pháp quy hoạch động. Gọi $H[i,j]$ là điểm chia khi biến xâu con $A[1,2,\ldots, i]$ thành $B[1,2,\ldots,j]$. Hay nói cách khác, bài toán chuyển xâu $A[1,2,\ldots, i]$ sang xâu con $B[1,2,\ldots,j]$ có thể được chia thành hai bài toán: bài toán chuyển xâu con $A[1,2,\ldots, n/2]$ sang xâu $B[1,2,\ldots,H[i,j]]$ và bài toán chuyển xâu con $A[n/2+1, \ldots, i]$ sang xâu con $B[H[i,j] + 2, \ldots, j]$. Dễ thấy:

1. Nếu $i < n/2$, $H[i,j]$ không tồn tại, ta sẽ khởi tạo là $\infty$.
2. Nếu $i = n/2$, $j$ chính là điểm chia mà ta cần tìm. Như vậy $H[i,j] = j$.
3. Nếu $i > n/2$ ta có 3 trường hợp con:
   1. Nếu $ED[i,j]$ thu được từ phép xóa $A[i]$, như vậy điểm chia của $A[1,2,\ldots,i]$ và $B[1,2,\ldots,j]$ chính là điểm chia của $A[1,2,\ldots,i-1]$ và $B[1,2,\ldots,j]$. Do đó, $H[i,j] = H[i-1,j]$
   2. Nếu $ED[i,j]$ thu được từ phép chèn $B[j]$ vào sau $A[i]$, như vậy điểm chia của $A[1,2,\ldots,i]$ và $B[1,2,\ldots,j]$ chính là điểm chia của $A[1,2,\ldots,i]$ và $B[1,2,\ldots,j-1]$. Do đó, $H[i,j] = H[i,j-1]$
   3. Nếu $ED[i,j]$ thu được từ phép thay thế $A[i]$ bằng $B[j]$, như vậy điểm chia của $A[1,2,\ldots,i]$ và $B[1,2,\ldots,j]$ chính là điểm chia của $A[1,2,\ldots,i-1]$ và $B[1,2,\ldots,j-1]$. Do đó, $H[i,j] = H[i-1,j-1]$

Tổng hợp lại, ta có công thức đệ quy sau của $H[i,j]$:

 
Như vậy, điểm chia Hirshberg$(A[1,2,\ldots,n], B[1,2,\ldots,m]) = H[n,m]$. Dựa vào công thức đệ quy ở trê, ta có thể tính được $H[n,m]$ với thời gian $O(mn)$ và bộ nhớ $O(m)$. Chi tiết coi như bài tập cho bạn đọc (tham khảo thêm tại đây).

Ví dụ bảng $ED[1,2,\ldots,n][1,2,\ldots,m]$ và bảng $H[1,2,\ldots, n][1,2,\ldots,m]$ với hai xâu $A[1,2,\ldots,n] = ALTRUISTIC$, $B[1,2,\ldots, m] = ALGORITHM$. Hình ảnh được lấy từ [1]

Chính vì kĩ thuật Hirshberg mà thông thường, với các bài toán quy hoạch động, nếu chúng ta có thể tìm được giá trị tối ưu trong thời gian $T$ và bộ nhớ $M$, chúng ta có thể tìm được ít nhất một phương án tối ưu với cùng thời gian và bộ nhớ.

Lợi dụng tính thưa của bảng QHD để tiết kiệm thời gian

Các bài toán quy hoạch động thông thường liên quan đến việc xây dựng bảng quy hoạch hai hoặc ba chiều. Mỗi ô của bảng được cập nhật dựa trên các ô liền kề của bảng. Một điểm chúng ta có thể nhận thấy là không phải tất cả các ô đều được sử dụng trong xây dựng phương án tối ưu. Do đó một cách để tiết kiệm thời gian và bộ nhớ là chúng ta chỉ lưu lại giá trị của những ô mà có thể được sử dụng trong xây dựng phương án. Nếu số lượng các ô đó nhỏ hơn nhiều kích thước cuả toàn bảng, chúng ta sẽ tiết kiệm thêm được thời gian và bộ nhớ. Trong bài này mình lấy bài toán dãy con chung dài nhất (Longest Common Subsequence - LCS) làm ví dụ:

 
Ví dụ: $A[1,\ldots, 11] = ALTRUISTIC?$ và $B[1,\ldots, 11] = ALGORITHMS?$ có xâu con chung dài nhất là $C[1,\ldots,5] = ALRIT?$ có chiều dài là 6 (ta thêm kí tự $?$ vào cuối hai xâu để việc lập trình đơn giản hơn).

Tương tự như bài toán Edit Distance, nếu ta gọi $LIS[i,j]$ là chiều dài dãy con chung dài nhất của hai xâu con $A[1,2,\ldots, i], B[1,2,\ldots, j]$. Ta có công thức đệ quy sau:

 
Dựa vào công thức trên, ta có thuật toán quy hoạch động giải bài toán trên với thời gian $O(mn)$. Thuật toán quy hoạc động cũng là thuật toán tối ưu để giải bài toán này theo nghĩa nếu $n=m$, không tồn tại thuật toán chạy với thời gian ít hơn $n^{2-\epsilon}$ với mọi $\epsilon > 0$ trừ khi Giả Thiết Thời Gian Lũy Thừa (Exponential Time Hypothesis) là sai [3].

 
Code của thuật toán bằng C. Trong code này, đầu vào $A,B$ là dãy các số nguyên từ 0-9 thay vì là kí tự.

int lcs(int A[], int B[], int n, int m){
int LCS[n+1][m+1];
int i = 0, j = 0;
for(i = 0; i < n+1; i++){
memset(LCS[i], 0, sizeof(LCS[i])); // set everything to 0
}
for(i = 1; i <= n; i++){
for(j = 1; j <= m; j++){
if(A[i-1] == B[j-1]){
LCS[i][j] = LCS[i-1][j-1]+1;
}else {
LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1]);
}
}
}
return LCS[n][m];
}

Tuy nhiên trong một số trường hợp đặc biệt, mà ở đây là trường hợp bảng QHD "thưa", ta có thể thiết kế thuật toán nhanh hơn $O(mn)$. Nếu để ý kĩ ta sẽ thấy các ô của bảng $LCS[1,2,\ldots,n][1,2,\ldots,m]$ được sử dụng để xây dựng phương án tối ưu là các ô $LCS[i,j]$ với $A[i] = B[j]$. Ta gọi các ô $LCS[i,j]$ với $A[i] = B[j]$ là các ô hữu ích.

Với ví dụ $A[1,\ldots, 10] = ALTRUISTIC$ và $B[1,\ldots, 10] = ALGORITHMS$, ta có tất cả 9 ô hữu ích. Hình sau được lấy từ [1].

Ta có thể thấy giá trị của các ô hữu ích phụ thuộc trực tiếp vào nhau theo công thức đệ quy sau:

 
Ở công thức trên, $LCS[i,j]$ là ô hữu ích ($A[i]= B[j]$). Gọi $K$ là số lượng các ô hữu ích. Ta có thể tính trước danh sách các ô hữu ích và lưu trong mảng $M$ trong thời gian $O(m\log m + n\log n + K)$ như sau:

 
Trong code bằng C của giả mã dưới đây, thay vì lưu giữ mảng chỉ số $I,J$ như trong giả mã, mình dùng cấu trúc dữ liệu pair để lưu chỉ số cùng với dữ liệu.

typedef struct{
int x;
int y;
}pair;

int find_useful_pairs(pair matches[], int A[], int B[], int n, int m){
int i = 0, j = 0;
pair Ap[n];
for(i = 0; i < n; i++){
Ap[i].x = A[i];
Ap[i].y = i; // keep track of indices of the sorted array
}
pair Bp[m];
for(i = 0; i < m; i++){
Bp[i].x = B[i];
Bp[i].y = i; // keep track of indices of the sorted array
}
qsort(Ap, n, sizeof(*Ap), compare);
qsort(Bp, m, sizeof(*Bp), compare);
int mp = 0;
int ii = 0, jj = 0;
i = 0;
while((i < n) && (j < m)){
if(Ap[i].x < Bp[j].x){
i++;
}
else if(Ap[i].x > Bp[j].x){
j++;
} else { // found an useful pair
ii = i;
while(Ap[ii].x == Ap[i].x){
jj = j;
while(Bp[jj].x == Bp[j].x){
matches[mp].x = Ap[ii].y; //the array M
matches[mp].y = Bp[jj].y;
mp++;
jj++;
}
ii++;
}
i = ii;
j = jj;
}
}
return mp; // the number of useful pairs
}
int compare(const void *a, const void *b){
pair *str_a = (pair *)a;
pair *str_b = (pair *)b;
return (str_a->x - str_b->x);
}

Sau khi đã tìm được chỉ số của các ô hữu ích, ta có thể tìm chiều dài của dãy con chung dài nhất bằng quy hoạch động dựa vào công thức đệ quy ở trên. Giả mã như sau:

 
Code của thuật toán bằng C. Code đầy đủ được cho ở cuối bài.

int sparse_lcs(int A[], int B[], int n, int m){
pair matches[m*n];
int k = find_useful_pairs(matches, A, B, n, m);
qsort(matches, k, sizeof(*matches), dic_compare);
pair sentinel;
sentinel.x = n + 1;
sentinel.y = m+1;
matches[k] = sentinel;// equivalent to add dummy characters at the end of A and B
int LCS[k+1];
memset(LCS, 0, sizeof(LCS));
int kk = 0, l = 0;
for (kk = 0; kk <=  k ; kk++){
pair i = matches[kk];
LCS[kk]  = 1;
for(l = 0; l < kk; l++){
pair j = matches[l];
if((j.x < i.x ) && (j.y < i.y)){
LCS[kk] = max(LCS[kk], LCS[l] + 1);
}
}
}
return LCS[k]-1;
}
int dic_compare(const void *a, const void *b){
pair *str_a = (pair *)a;
pair *str_b = (pair *)b;
if( str_a->x == str_b->x){
return (str_a->y - str_b->y);
} else {
return (str_a->x - str_b->x);
}
}

Phân tích thời gian Thuật toán tìm các ô hữu dụng có thời gian tính là $O(n\log n + m\log m + K)$. Sắp xếp mảng $M$ có thể thực hiện trong thời gian $K\log K$. Phần quy hoạch động cập nhật mảng $LCS[1,2,\ldots,K+1]$ có thời gian tính $O(K^2)$. Do đó, tổng thời gian tính toán của thuật toán SparseLCS là $O(m\log m + n\log n + K^2)$. Như vậy, nếu $K = o(\sqrt{mn})$ (bảng quy hoạch động "thưa") thì thuật toán trên sẽ nhanh hơn thuật toán quy hoạch động ban đầu.

Bằng kĩ thuật tương tự với kĩ thuật trong bài Edit Distance, chúng ta có thể giảm thời gian cập nhật mảng $LCS[1,2,\ldots,K+1]$ xuống còn $O(K\log K)$. Do đó thời gian tính có thể giảm xuống còn $O(m\log m + n\log n + K\log K)$. Chi tiết coi như bài tập cho bạn đọc.

Code: sparse-lcs.

Tham khảo
[1] Jeff Erickson, Advanced Dynamic Programming Lecture Notes, UIUC.
[2] D. S. Hirschberg. 1975. A linear space algorithm for computing maximal common subsequences. Commun. ACM 18, 6 (June 1975), 341-343.
[3] Abboud, Amir, Arturs Backurs, and Virginia Vassilevska Williams. Quadratic-Time Hardness of LCS and other Sequence Similarity Measures. arXiv preprint arXiv:1501.07053 (2015).