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

Module: util.lcs

このモジュールは、与えられた2つのシーケンスの最長共通サブシーケンスを見つける アルゴリズムを実装しています。アルゴリズムは、Eugene Myersの O(ND)アルゴリズムに基づいています(Myers86)。

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

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

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

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

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

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手続きが返すものと同じ構造だということが分かるでしょう。

This document was generated by Shiro Kawai on November, 22 2009 using texi2html 1.78.