Longest Common Subsequence

Longest Common Subsequence(LCS)

「最長共同子序列」。出現於每一個序列、而且是最長的子序列。可能有許多個。

s1: 2 5 7 9 3 1 2
s2: 3 5 3 2 8

LCS(s1, s2) = 5 3 2
s1: a b c d b c e e a
s2: c a b d e f g a
s3: d c e a

LCS(s1, s2, s3) =  {c e a, d e a}

演算法

求出一群序列的LCS,是NP-hard問題,沒有快速的演算法。

簡單的方式是窮舉法:窮舉s1的所有子序列,檢查s2...sN是否都有該子序列。時間複雜度是O(s1! * (s2 + ... + sN))。

求出兩個序列的LCS,是P問題。接下來將介紹各種演算法。

Longest Common Subsequence: Dynamic Programming

分割問題

現在要找出s1和s2的LCS。寫成LCS(s1, s2)。

拆解s1和s2的最後一個元素,叫做e1和e2。

s1 = sub1 + e1
s2 = sub2 + e2

分成四種情況:一、LCS包含e1,不含e2;二、包含e2,不含e1;三、不含e1 e2;四、包含e1 e2。

第一種情況。e2毫無用處,想找LCS只需要找sub2。得到結論LCS(s1, s2) = LCS(s1, sub2)。

第二種情況。LCS(s1, s2) = LCS(sub1, s2)。

第三種情況。LCS(s1, s2) = LCS(sub1, sub2)。

第四種情況。LCS同時包含e1 e2,而且e1 e2位於尾端。因此LCS的最後一個元素一定是e1(也是e2),而且e1 e2相等!得到結論LCS(s1, s2) = LCS(sub1, sub2) + e1。

總合以上分析,可以得到遞迴公式:

LCS(s1, s2) =
 { LCS(sub1, s2) or LCS (s1, sub2) or LCS(sub1, sub2) , when e1 != e2
 { LCS(sub1, sub2) + e1                               , when e1 == e2

經過焠鍊簡化:

LCS(s1, s2) =
 { max( LCS(sub1, s2), LCS(s1, sub2) ) , when e1 != e2
 { LCS(sub1, sub2) + e1                , when e1 == e2

最後考慮初始值。當s1或s2是空集合,則LCS是空集合。

逐步削減尾端元素,將原問題縮小以求得解。

計算Longest Common Subsequence的長度

二維陣列array[i][j],代表「s1前i個元素」和「s2前j個元素」的LCS長度。

找出一個Longest Common Subsequence

使用一個二維陣列,記錄每一格的結果是從哪一格而來。

往回追溯,每當發現某一格array[i][j]是由array[i-1][j-1] + 1而來,就印出s1[i](也是s2[j])。

找出所有的Longest Common Subsequence

當某格的答案,可以由上方、左方、左上方同時求得,那麼就將這些情形全部記錄下來。往回追溯的時候,就將所有情形追溯一遍,便可求出所有可能的LCS。

就我所知,似乎無法在線性時間內找出所有的LCS。

節省記憶體空間

如果只想求出LCS的長度,而不需要求出LCS,那麼有個節省記憶體空間的方法。

填陣列,只需要上方、左方、左上方的格子。計算順序設定成由左到右、再由上到下,那麼陣列就可以精簡成一行,然後暫存左上方的格子的值。

UVa 111 531 10066 10192 10405 10723

© 2010 tkcn. All rights reserved.

Longest Common Subsequence: Hirschberg's Algorithm

演算法

http://en.wikipedia.org/wiki/Hirschberg's_algorithm

從中央分割,節省空間。空間複雜度為O(min(X,Y))。也有人省略了min函數,直接寫成O(N)。

Longest Common Subsequence: Hunt-Szymanski Algorithm

LCS問題轉換成二維LIS問題

從LCS問題的DP表格可以觀察到,LCS問題可以化作類似於LIS的問題:從兩序列中找出對應的相同元素,以位置數對表示;這些位置數對可以排出的最長嚴格遞增序列,即是兩序列的LCS。

【註:這個類似於LIS的問題,就像是二維版的LIS。不過「二維LIS」目前沒有正式定義。】

(1) A LCS problem:

  index: 0 1 2 3 4 5 6 7 8 9
  --------------------------
  s1:    a b a c d
  s2:    d b a a b c a

(2) All matched positions, with the matched character:

    a     a     a     a     a     a     b     b     c     d
  (0,2) (0,3) (0,6) (2,2) (2,3) (2,6) (1,1) (1,4) (3,5) (4,0)

(3) Here is the corresponding 2D table:

      d b a a b c a
    +---------------
  a |     * *     *
  b |   *     *
  a |     * *     *
  c |           *
  d | *

(4-1) { LCS == 2D LIS } example:

  LCS   :   a     b     a
  2D LIS: (0,2) (1,4) (2,6) 數對呈嚴格遞增,在表格中則是往右下走。

      d b a a b c a
    +---------------
  a |     x *     *
  b |   *     x
  a |     * *     x
  c |           *
  d | *

(4-2) Another { LCS == 2D LIS } example:

  LCS   :   b     a     c
  2D LIS: (1,1) (2,2) (3,5)  數對呈嚴格遞增,在表格中則是往右下走。

      d b a a b c a
    +---------------
  a |     * *     *
  b |   x     *
  a |     x *     *
  c |           x
  d | *

二維LIS問題轉換成一維LIS問題

首先將所有數對排序,規則是第一個維度由小到大排序,當第一個維度相等時,第二個維度由大到小排序。排序之後,第二個維度的1D LIS,就對應到原數對們的2D LIS。

(1) 先將所有數列排序。
    第一維由小到大,當第一維相等時,第二維由大到小。
  (排序規則亦可改成以第二個維度為主,最後則是找第一個維度的1D LIS。)

    a     a     a     b     b     a     a     a     c     d
  (0,6) (0,3) (0,2) (1,4) (1,1) (2,6) (2,3) (2,2) (3,5) (4,0)

(2) 依序取出第二個維度的數值。

  6 3 2 4 1 6 3 2 5 0

(3) 這個序列的1D LIS,對應到數對們的2D LIS。其實也就是一開始要求的LCS。

  6 3 2 4 1 6 3 2 5 0
      * *   *

  1D LIS:   2     4     6
  2D LIS: (0,2) (1,4) (2,6)   (註:第一個維度之前有排序)
  LCS   :   a     b     a
  
(4) 簡潔的表達方式是:

     a b a c d                                s1字串
  -> { a(6,3,2) b(1,4) a(6,3,2) c(5) d(0) }   s1在s2當中出現的位置(由後往前)
  -> { 6 3 2 1 4 6 3 2 5 0 }                  依序取出第二個維度的數值
  -> 2 4 6                                    LIS

演算法

先把LCS問題看成二維LIS問題,再把二維LIS問題轉成一維LIS問題,然後用Robinson-Schensted-Knuth Algorithm來算LIS。

這裡以s1 = cbaa、s2 = abcaa為例。大意為:依序看s1的每個元素,是不是能讓目前的common subsequece變得更長。

  | s2:   | 目前可生成的    | 截至目前最理想的
  | abcaa | 最長共同子序列  | 最長共同子序列
--+-------+-----------------+-------------
c | ..c.. |  ..c..          | 3
--+-------+-----------------+-------------
b | .b... |  .b...          | 2
--+-------+-----------------+-------------
a | ....a |  .b..a          | 2 5
  | ...a. |  .b.a.          | 2 4
  | a.... |  a.... & .b.a.  | 1 4	// 同時記錄到兩個
--+-------+-----------------+-------------
a | ....a |  a...a & .b.aa  | 1 4 5
  | ...a. |  a..a.          | 1 4 5
  | a.... |                 | 1 4 5	// 演算法結束

時間複雜度

先行判斷兩個序列的長度,將長度短的當作是s1,那麼時間複雜度就會是O(K * log(min(N,M))),其中K為位置數對的總數目,N和M分別是兩序列長度。也有人省略了min函數,直接寫成O(KlogN)。K最大可到N * M,遇到了極端的例子時,會跑得比用DP還慢。

實作的時候會利用counting sort的技巧,先掃描一遍s2,把s2每個字元的位置記下來,以符合時間複雜度。

計算Longest Common Subsequence的長度(兩序列自身皆無重複元素)

計算Longest Common Subsequence的長度

這裡再提供一個不使用binary search的程式碼,有時候會跑得比較快,各位可視情況採用之。

UVa 10635 10949

找出一個Longest Common Subsequence
找出所有的Longest Common Subsequence

可以參考LIS章節中的Robinson-Schensted-Knuth Algorithm。大家自己看著辦吧!

LIS問題與LCS問題可以互相轉換

LIS轉LCS:令原序列A排序後會變成B。A和B的LCS,就是A的LIS。

LCS轉LIS:將序列A和B當中的相同字母配對都找出來,呈現成索引值數對,再以特殊規則排序,最後找LIS,就是A和B的LCS。

Longest Common Subsequence: Four-Russians Speedup(Kronrod's Algorithm)

Four-Russians Speedup

http://par.cse.nsysu.edu.tw/paper/2004/041204/FourRussiansSpeedup.ppt

Longest Common Increasing Subsequence

Longest Common Increasing Subsequence(LCIS)

嚴格遞增的LCS。LIS的DP演算法稍作修改,即得LCIS,時間複雜度仍是O(N*M)。

UVa 12511 CF 10D

Cyclic Longest Common Subsequence

http://arxiv.org/pdf/1208.0396v3.pdf

ICPC 5890

Shortest Common Supersequence

找到一個最短的字串,其子序列包含了所有給定字串。

NP-hard。如果給定字串只有兩個,可以使用Dynamic Programming解決。

SCS長度,等於所有字串長度總和、再減去LCS長度。

UVa 10723