For Gauche 0.9.5


Next: , Previous: , Up: ライブラリモジュール - ユーティリティ   [Contents][Index]

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

Module: util.lcs

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

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

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

2つのリスト、seq-aseq-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つのリストabから引き出された“編集リスト”に対する 基本的なイテレータです。

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

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

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

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

(+|- position element)

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

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


Next: , Previous: , Up: ライブラリモジュール - ユーティリティ   [Contents][Index]