Erlang 實作最長共同子序 (Longest Common Subsequence)

看到這一篇 http://using-c.blogspot.com/2010/07/problem-10405-longest-common.html ,稍微翻閱他們的程式碼,是建立一張二字串索引對照表,做個動態規劃。

我用 Erlang 想法來做,比較簡單,首先如果我有二個字串 Str 和 Str1 ,會先取二個字串索引的交集,把文字相同的兩兩對應數字全部拿出來。

    S = lists:zip(Str, lists:seq(1,length(Str))),
    S1 = lists:zip(Str1, lists:seq(1,length(Str1))),
    Cs = [ {N, N1} || {C, N} <- S, {C1, N1} <- S1, C == C1, N =< N1 ],

以 “hello" 和 “hello, world" 來說,全部有 5 x 12 種字母位置配對,我只取出其中 9 對: [{1,1}, {2,2}, {3,3}, {3,4}, {3,11}, {4,4}, {4,11}, {5,5}, {5,9}] 。接下來,我要從二個字串的索引 1, 1 找共同序列 (不連續) ,找出來的序列要和從索引 2, 2 找出來的共同序列比長度,然後和從 3, 3 找出來的共同序列比長度。所以,接下來的問題分成二段:一段是先收到任何一串共同項位置列表,像這一串,我只要從頭開始找共同序列。這個答案有只有一筆。第二段問題是,收到這一串共同項位置列表,我要判斷從哪一項開始抓共同序列會最長。

以下程式是處理第一個問題:拿到一串共同項的位置列表,就找出共同序列。找序列的原則是,在前面看到 {M, N} ,就要把後面的 {M, *} 和 {*, N} 全都忽略掉,而去找之後其他項做後繼者。

common_seq_index([]) ->
    [];
common_seq_index([{M,N}]) ->
    [{M,N}];
common_seq_index([{M,N},{M,_}|Seq]) ->
    common_seq_index([{M,N}|Seq]);
common_seq_index([{M,N},{_,N}|Seq]) ->
    common_seq_index([{M,N}|Seq]);
common_seq_index([{M,N}|Seq]) ->
    [{M,N}|common_seq_index(Seq)].

接著,以下程式處理第二段問題:對一串共同項的位置列表,要將目前這一段,與它重疊著尾段的其他段互相比較,找出最長的共同子序列。找法很單純,先找尾段的最長共同子序列,然後找本段的共同子序列跟它比較。

lcs_index([]) ->
    [];
lcs_index([Seq|Ss]) ->
    Cseq = lcs_index(Ss),
    Cseq1 = common_seq_index([Seq|Ss]),
    N = length(Cseq),
    M = length(Cseq1),
    if
	M > N ->
	    Cseq1;
	true ->
	    Cseq
    end.

主程式 find/2 如下,把最長共同子序列抽出來,列成新字串:

find(Str, Str1) ->
    S = lists:zip(Str, lists:seq(1,length(Str))),
    S1 = lists:zip(Str1, lists:seq(1,length(Str1))),
    Cs = [ {N, N1} || {C, N} <- S, {C1, N1} <- S1, C == C1, N =< N1 ],
    {Rs, _} = lists:unzip(lcs_index(Cs)),
    lists:map(fun(N) -> lists:nth(N, Str) end, Rs).

計算一筆測試資料:

2> lcseq:find("abcdefghijklmnopqrstuvwxyz","a0b0c0d0e0f0g0h0i0j0k0l0m0n0o0p0q0r0s0t0u0v0w0x0y0z0").
"abcdefghijklmnopqrstuvwxyz"

以下,簡單的測試程式可以測量計算時間:

test(Str, Str1) ->
    S = now(),
    find(Str, Str1),
    E = now(),
    timer:now_diff(E, S).

測量時間的情況:

3> lcseq:test("abcdefghijklmnopqrstuvwxyz","a0b0c0d0e0f0g0h0i0j0k0l0m0n0o0p0q0r0s0t0u0v0w0x0y0z0").
6126

我這個程式的資料與計算模式,如果把 Erlang 平台底層的部份也算進去,好像也叫做動態規劃。不過,我沒有準備一大片表格,這一點是贏面。

廣告

About 黃耀賢 (Yau-Hsien Huang)

熱愛 Erlang ,並且有相關工作經驗。喜歡程式語言。喜歡邏輯。目前用 Python 工作。
本篇發表於 Arena, Erlang。將永久鏈結加入書籤。

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s