fixedpoint.jp - An R6RS library for Longest Common Subsequence (LCS)




An R6RS library for Longest Common Subsequence (LCS)

Errata では、訂正前と訂正後のテキストの差分を表示するために最長共通部分列(LCS)を抽出しています。LCS を計算するためのアルゴリズムはいくつか知られており、これまでは Gauche の util.lcs モジュールで実装されている O(ND) のものを移植して使っていました。

今回 S. Wu, U. Manber, G. Myers, and W. Miller, "An O(NP) Sequence Comparison Algorithm" (1989) に書かれているアルゴリズムを検討してみました。それによると、O(ND) よりも O(NP) の方が最悪のケースで2倍程度、差分が大きい場合にはさらにより効率がよいということです。再利用出来るように R6RS のライブラリとしてプログラムを作成しました: http://github.com/tabe/lcs

実際どれくらい性能が出ているかを計測するのは今後の課題です。

後日行なった計測の結果を 2009/10/19 にまとめています。

© 2006-2010 Takeshi Abe