12.88 util.lcs - 最長共通サブシーケンス ¶

Module: util.lcs ¶

このモジュールは、与えられた2つのシーケンスの最長共通サブシーケンスを見つける アルゴリズムを実装しています。アルゴリズムは、Eugene Myersの O(ND)アルゴリズムに基づいています (Eugene Myers, An O(ND) Difference Algorithm and Its Variations, Algorithmica Vol. 1 No. 2, pp. 251-266, 1986.)。

このアルゴリズムを使うアプリケーションの1つは、2つのテキストストリームの 相違点を計算するtest.diffモジュールです (text.diff - テキストストリームの相違点を計算する参照)。

Function: lcs seq-a seq-b :optional eq-fn ¶

{util.lcs} 2つのリスト、seq-aとseq-bの最長共通シーケンスを計算して 返します。オプションのeq-fnでは、比較を行う述語を指定します。 省略されると、equal?が使われます。

(lcs '(x a b y) '(p a q b))
 ⇒ (a b)

Function: lcs-with-positions seq-a seq-b :optional eq-fn ¶

{util.lcs} lcsの詳細バージョンです。引数は同じです。

以下の構造のリストを返します。

(length ((elt a-pos b-pos) ...))

lengthは、見つかったLCS(最長共通サブシーケンス)の長さを表す整数です。 それに続くのは、LCSの要素のリストで、その要素を構成するそれぞれのサブリスト、 seq-aの中での要素の位置(整数)、seq-bの中での要素の位置(整数) となります。

(lcs-with-positions '(a) '(a))
 ⇒ (1 ((a 0 0)))

(lcs-with-positions '(x a b y) '(p q a b))
 ⇒ (2 ((a 1 2) (b 2 3)))

(lcs-with-positions '(x a b y) '(p a q b))
 ⇒ (2 ((a 1 1) (b 2 3)))

(lcs-with-positions '(x y) '(p q))
 ⇒ (0 ())

Function: lcs-fold a-proc b-proc both-proc seed a b :optional eq-fn ¶

{util.lcs} 2つのリストaとbから引き出された“編集リスト”に対する 基本的なイテレータです。

a-proc、b-proc、both-procは全て2引数を取る手続きです。 2番目の引数は、計算の中間の値です。最初の値は、a-procではaにしかない要素、 b-procではbにしかない要素、both-procではaとbの両方に ある要素となります。それぞれの手続きが返す値は、次に呼び出される手続きのうちの1つの 状態を表す値として使われます。seedは、状態を表す値の初期値として使われます。 lcs-foldが返す値は、最後の状態を表す値です。

これらの3つの手続きは、以下の順番で呼ばれます。ここでは、シーケンスaは a’ca”、bはb’cb”となっているとすると、 ここではa’、b’、a”、b”はサブシーケンスで、 cはaとbのLCSの先頭になります。そして、a-procはまず a’のそれぞれの要素に対して呼ばれ、b-procがb’のそれぞれの 要素に対して呼ばれ、both-procがcに対して呼ばれます。 その後、このプロセスはa”とb”を使って繰り返されます。

Function: lcs-edit-list a b :optional eq-fn ¶

{util.lcs} 2つのリストaとbから“編集リスト”を計算します。それは、 aをbに変更するためのコマンド(追加と削除)の最小セットです。 この手続きは、上のlcs-foldの上に構築されています。

(+|- position element)

例を挙げます。aとbがそれぞれ以下のようなリストだとします。

a ≡ ("A" "B" "C" "E" "H" "J" "L" "M" "N" "P")
b ≡ ("B" "C" "D" "E" "F" "J" "K" "L" "M" "R" "S" "T")

すると、(lcs-edit-list a b equal?)は以下のリストを返します。

(((- 0 "A"))
 ((+ 2 "D"))
 ((- 4 "H") (+ 4 "F"))
 ((+ 6 "K"))
 ((- 8 "N") (- 9 "P") (+ 9 "R") (+ 10 "S") (+ 11 "T"))
)

結果は5つの片からなります。最初のものは1つのディレクティブ、(- 0 ``A'')から なり、これはリストaの位置0にある要素``A''が削除されることを意味します。 2番目のものはまた1つのディレクティブ、(+ 2 ``D'')からなり、これは リストbの位置2にある要素``D''が追加されることを意味します。 3番目のものは、リストaの位置4にある``H''は削除され、リストbの 位置4にある``F''が追加される、などとなります。

もしあなたがPerlのAlgorithm::Diffモジュールを良く知っていれば、 そのdiff手続きが返すものと同じ構造だということが分かるでしょう。

Function: lcs-edit-list/context a b :optional eq-fn :key context-size ¶

Function: lcs-edit-list/unified a b :optional eq-fn :key context-size ¶

{util.lcs} 二つのシーケンスaとbから、変更の文脈を含めた編集リストを計算します。 diff -cおよびdiff -uコマンドの出力と似たようなものです。 text.diffモジュールではこの手続きの上に、コンテクストdiff出力を得る ユーティリティを提供しています (text.diff - テキストストリームの相違点を計算する参照)。

eq-fn引数はシーケンスの各要素を比較する述語で、デフォルトはequal?です。 context-size引数は、文脈を示すために変更点の前後に付加される変更のない 要素の最大数で、正の正確な整数でなければなりません。デフォルトは3です。

戻り値はhunkのリストです。各hunkがaとbの相違点を示します。 hunkのフォーマットはlcs-edit-list/contextとlcs-edit-list/unifiedで 異なります。

lcs-edit-list/contextのhunkは次のとおりです。

<hunk> : #(<a-edits> <b-edits>)

<a-edits> : <edits>
<b-edits> : <edits>

<edits> : (<start-pos> <end-pos> <edit> ...)

<edit> : (= <element>)     ; same in both a and b
       | (- <element>)     ; deleted: only in a
       | (+ <element>)     ; inserted: only in b
       | (! <element>)     ; changed

<start-pos>と<end-pos>は正確な整数のインデックスで、 シーケンス中でhunkがカバーする範囲を示します (<start-pos>は含まれ、 <end-pos>は含まれません)。

各<edit>はその範囲の要素と、それが両シーケンスで同じなのか、 削除された(aだけに存在)か、挿入された(bだけに存在)か、 あるいは置き換えられたかを示します。

これが例です:

(lcs-edit-list/context '(a b c) '(a B c d))
 ⇒
   (#((0 3 (= a) (! b) (= c))
     ((0 4 (= a) (! B) (= c) (+ d)))))

結果には1つのhunkが含まれ、それはbをBに置き換えてdを追加することを 指示しています。

lcs-edit-list/unifiedのhunkは次のとおりです:

<hunk> : #(<a-start> <a-size> <b-start> <b-size> (<edit> ...))

<edit> : (= <element>)     ; unchanged
       | (- <element>)     ; deleted
       | (+ <element>)     ; inserted

各startとsizeはそれぞれのシーケンス中での、 hunkの開始位置(0起点)とその長さを示します。

(lcs-edit-list/unified '(a b c) '(a B c d))
  ⇒
  (#(0 3 0 4 ((= a) (- b) (+ B) (= c) (+ d))))

コンテキストの大きさ: 各hunkの前後には、文脈を示すために、 最大でcontext-sizeの、変更のない要素が付加されています。 もし変更のあった二ヶ所の間の要素が(+ 1 (* conext-size 2))より少なければ、 二つの変更箇所は一つのhunkにまとめられます。 次の例では、bからB、eからEへの変更は 十分に離れていないのでひとつのhunkになり、一方iからIへの変更は 別のhunkになっています:

(lcs-edit-list/context '(a b c d e f g h i j)
                       '(a B c d E f g h I j)
                       equal? :context-size 1)
 ⇒
   (#((0 6 (= a) (! b) (= c) (= d) (! e) (= f))
      (0 6 (= a) (! B) (= c) (= d) (! E) (= f)))
    #((7 10 (= h) (! i) (= j))
      (7 10 (= h) (! I) (= j))))

(lcs-edit-list/unified '(a b c d e f g h i j)
                       '(a B c d E f g h I j)
                       equal? :context-size 1)
 ⇒
   (#(0 6 0 6 ((= a) (- b) (+ B) (= c) (= d) (- e) (+ E) (= f)))
    #(7 3 7 3 ((= h) (- i) (+ I) (= j))))