最長共同子序列 (Longest Common Subsequence; LCS) - Part 1

1.1 - Longest Common Subsequence (LCS)

• 在多個序列中，出現在每一個序列 (亦即：每個序列都有的值) 且長度最為最長，該共同序列稱為「最常共同子序列 (Longest Common Subsequence; LCS)」。以下為例：

  • $S_1$ 和 $S_2$ 為以下二個序列，試求最長共同子序列。

    $$\begin{align*} & S_1 = [ 2, 5, 7, 9, 4, 1, 3 ]\\ & S_2 = [ 3, 5, 4, 5, 7 ]\\ & \mathrm{LCS}(S_1, S_2) = [ 5, 4, 3 ] \end{align*}$$

  • $S_1$、$S_2$ 和 $S_3$ 為以下三個序列，試求最長共同子序列。

    $$\begin{align*} & S_1 = [ a, b, c, d, b, c, e, e, a ]\\ & S_2 = [ c, a, b, d, e, f, g, a ]\\ & S_3 = [ d, c, e, a ]\\ & \mathrm{LCS}(S_1, S_2, S_3) = { [ c, e, a ], [ d, e, a ] } \end{align*}$$
• 求解一群數列的「最長共同子序列 (Longest Common Subsequce; LCS)」為 NP-hard 問題，沒有快速的演算法。最簡單的方式是「窮舉法」：窮舉 $S_1$ 的所有子序列，檢查 $S_2$，…，$S_n$ 是否都有該子序列。
  • 時間複雜度 (Time complexity)：$O(s_1! \cdot (s_2 + ... + s_n))$。
  • 求解二個序列的「最長共同子序列」為 P 問題。

1.2 - LCS: Dynamic Programming

1.2.1 - 分割問題 (Partition)

• 假設有二個序列為 $S_1$ 和 $S_2$，其「最長共同子序列 (LCS)」表示為：$\mathrm{LCS}(S_1, S_2)$。

• 序列 $S_1$ 和 $S_2$ 的最後一個元素分別以 $e_1$ 與 $e_2$ 表示，剩餘部分以 $\mathrm{sub}_1$ 與 $\mathrm{sub}_2$ 表示，故可以將序列 $S_1$ 與 $S_2$ 表示如下：

  $$\begin{align*} & S_1 = \mathrm{sub}_1 + e_1\\ & S_2 = \mathrm{sub}_2 + e_2 \end{align*}$$
• 由以上的二個式子，可以將 $S_1$ 與 $S_2$ 的「最長共同子序列 (LCS)」分為以下四種情形討論：

  1. LCS 包含 $e_1$ 但不含 $e_2$。 此種情形對於 $e_2$ 沒有用處，若要找到 LCS 只需找 $\mathrm{sub}_2$ 即可。

     $$\begin{equation} \mathrm{LCS}(S_1, S_2) = \mathrm{LCS}(S_1, \mathrm{sub}_2) \end{equation}$$

  2. LCS 包含 $e_2$ 但不含 $e_1$。 此種情形對於 $e_1$ 沒有用處，若要找到 LCS 只需找 $\mathrm{sub}_1$ 即可。

     $$\begin{equation} \mathrm{LCS}(S_1, S_2) = \mathrm{LCS}(\mathrm{sub}_1, S_2) \end{equation}$$

  3. LCS 不含 $e_1$ 且不含 $e_2$。 此種情形對於 $e_1$ 與 $e_2$ 沒有用處，若要找到 LCS 需找到 $\mathrm{sub}_1$ 與 $\mathrm{sub}_2$。

     $$\begin{equation} \mathrm{LCS}(S_1, S_2) = \mathrm{LCS}(\mathrm{sub}_1, \mathrm{sub}_2) \end{equation}$$

  4. LCS 包含 $e_1$ 且包含 $e_2$。 此種情形同時包含 $e_1$ 與 $e_2$ 且 $e_1$ 與 $e_2$ 都是二個序列的最後一個元素，故 LCS 的最後一個元素必定為 $e_1$ (也是 $e_2$)。

     $$\begin{equation} \mathrm{LCS}(S_1, S_2) = \mathrm{LCS}(\mathrm{sub}_1, \mathrm{sub}_2) + 1 \end{equation}$$

• 上述四種情形可以簡化為以下遞迴式：

  $$\begin{equation} \mathrm{LCS}(S_1, S_2) = \begin{cases} \mathrm{max}( \mathrm{LCS}( \mathrm{sub}_1, S_2), \mathrm{LCS}(S_1, \mathrm{sub}_2) ) & \quad \text{if } n \text{ is even}\\ \mathrm{LCS}(\mathrm{sub}_1, \mathrm{sub}_2) + e_1 & \quad \text{if } n \text{ is odd} \end{cases} \end{equation}$$
  • 當 $s_1$ 或 $s_2$ 為空集合，則 LCS 亦為空集合。

1.2.2 - 計算 Longest Common Subsequence (LCS) 的長度

• length[i][j]：「 $s_1$ 前 $i$ 個元素」和「 $s_2$ 前 $j$ 個元素」的 LCS 長度。

int s1[7] = {2, 5, 7, 9, 3, 1, 2};
int s2[5] = {3, 5, 3, 2, 8};
int length[8][6];

void findLCS() {
    // 初始化：當 s1 或 s2 為空集合，則 LCS 為空集合。
    for (int i = 0; i <= 7; ++i)
        length[i][0] = 0;
    for (int j = 0; j <= 5; ++j)
        length[0][j] = 0;

    // 依照遞迴公式填表格
    for (int i = 1; i <= 7; ++i) {
        for (int j = 1; j <= 7; ++j) {
            if (s1[i - 1] == s2[j - 1])
                // 因為 e1 的長度為 1，故要 +1
                length[i][j] = length[i - 1][j - 1] + 1;
            else
                length[i][j] = max(length[i - 1][j], length[i][j - 1]);
        }
    }

    // Print the result
    printf("LCS length: %d\n", length[7][5]);
}

1.2.3 - 找出一個 Longest Common Subsequence (LCS)

• LCS[i][j]：記錄每一格的結果是從哪一格而來。
• 當某一格 length[i][j] 是由 length[i-1][j-1] + 1 而來，就印出 s1[i] (也是 s2[j])。

int s1[7] = {2, 5, 7, 9, 3, 1, 2};
int s2[5] = {3, 5, 3, 2, 8};
int length[8][6];
int LCS[8][6];  // 記錄每一格的的結果是從哪一格而來
int seq[5]

void findLCS() {
    // Initialize
    for (int i = 0; i <= 7; ++i)
        length[i][0] = 0;
    for (int j = 0; j <= 5; ++j)
        length[0][j] = 0;
    
    // Start
    for (int i = 1; i <= 7; ++i) {
        for (int j = 1; j <= 7; ++j) {
            if (s1[i - 1] == s2[j - 1]) {
                length[i][j] = length[i - 1][j - 1] + 1;
                // LCS from the left-top
                LCS[i][j] = 0
            }
            else {
                length[i][j] = max(length[i - 1][j], length[i][j - 1]);
                if (length[i - 1][j] < length[i][j - 1]) {
                    length[i][j] = length[i][j - 1];
                    // LCS from the left
                    LCS[i][j] = 1;
                }
                else {
                    length[i][j] = length[i - 1][j];
                    // LCS from the top
                    LCS[i][j] = 2;
                }
            }
        }
    }

    // Print the result
    printf("LCS length: %d\n", length[7][5]);
    printf("LCS (Loop): ");
    printLCS_loop(7, 5);
    printf("LCS (Recursive): ");
    printLCS_recursive(7, 5);
}

/* Loop version */
void printLCS_loop(int i, int j) {
    int len = length[i][j];

    while (len > 0) {
        if (LCS[i][j] == 0) {
            --len;
            seq[len] = s1[i];
        }
        else if (LCS[i][j] == 1)
            --j
        else
            --i;
    }

    len = length[i][j];
    for (int l = 0; l < len; ++l)
        printf("%d ", seq[l]);
}

/* Recursive version */
void printLCS_recursive(int i, int j) {
    // End of null set
    if (i == 0 || j == 0)
        return;
    
    if (LCS[i][j] == 0) {
        printLCS_recursive(i - 1, j - 1);
        printf("%d ", s1[i]);
    }
    else if (LCS[i][j] == 1)
        printLCS_recursive(i, j - 1);
    else
        printLCS_recursive(i - 1, j);
}

1.2.4 - 如何「找出所有的 LCS」？

• 某一格的答案可以由上方、左方、左上方同時求得，因此可以將這些情形全部記錄下來。
• 往回追溯的時候，可將所有情形追溯一遍，便可求出所有可能的 LCS。
• 目前似乎無法在「線性時間內」找出所有的 LCS。

1.2.5 - 節省記憶體空間

• 如果只想求出 LCS 的長度，而不需要求出 LCS：填陣列時，只需要填上方、左方、左上方的格子。
• 計算順序：由左到右、由上到下，陣列可以精簡成一行，然後暫存左上方的格子的值。

Practice

• Online Judge UVa
  • UVa-111 - History Sorting
  • UVa-531 - Compromise
  • UVa-10066 - The Twin Towers
  • UVa-10192 - Vacation
  • UVa-10405 - Longest Common Subsequence
  • UVa-10723 - Cyborg Genes

References

• 演算法筆記 - Longest Common Subsequence