分割diff

差分が大きく、メモリを大量に消費する場合に対処するため、O(NP)にHirshbergのアルゴリズムを適用しようとするが、うまくいかない。もうちょっと詳しく論文を読む必要性を感じつつ、なんだか疲れたので、気分転換に、記録された経路情報がある一定のサイズに達したら、その時点までのSESを一旦計算してしまって、経路情報を破棄する、といったことを繰り返すようにプログラムを変更してみた。結果は以下の通り。今回は差分が大きい(内容が全然違う)ファイル同士のみ対象。あと、編集距離はGNU diffutilsの計算結果を元に算出(なので最適解ではなく、近似解)。また、下記の計算時間は計算されたSESを元にUnified Formatで差分を出力する処理にかかった時間も含む(多分0.10〜0.15秒ぐらい)。

ファイルA	ファイルB	編集距離	計算時間(sec)
6351行	9107行	14674	0.917
6351行	35109行	41454	1.030

近似計算を行うようなdiffに比べると遅いが、それなりに速いし、差分の出力を見た感じ、精度もまあまあ。メモリを使い切ってしまうこともない。しかし、果たしてこれはリリースしていいものかちょっと悩む。