前回 2019/10/14 に投稿した「Javascript で diff (通信なし、ローカルで完結)」の内部仕様についての補足です。(2019/12/01 加筆)
基本アルゴリズム
基本アルゴリズムは、ほぼMyersのアルゴリズムのままです。
- ファイル１とファイル２から、内容が合致する行を探してペアを生成する。
- ペアが作れない行があったら、それは差分である。
diff_orzでは、各行に対してハッシュ値を生成しておき、ハッシュ値を比較するようにしています。
文字列からハッシュ値を生成する方法として、Murmur Hash が有名ですが、ここでは全体行数の短縮を優先で実装しています。
(ハッシュ値の生成のためだけに600行以上増えるのはうれしくないので)
- 半角空白、半角タブは除外してハッシュ値を生成する。
- ハッシュ値が異なる文字列は、異なる文字列である。
- ハッシュ値が同じ文字列どうしを発見した場合は、文字列の比較を行って本当に同じ文字列か確かめる。
const hash = (s_org, bIgnoreCase) => {
let s = s_org.trim().replace(this.BLANK_PATTERN, ""), len = s.length;
if (len == 0) { return 0; }
if (bIgnoreCase) { s = s.toLowerCase(); }
return [...s].reduce((v, c) => { return (c.codePointAt(0) ^ (v << 2)); }, len);
}
類似行の判別
変更行どうしで差分をとるにあたって、似ている行であれば差分を表示したいが、「どうみても別物の行」は行の削除＋行の追加として扱いたいわけです。
よく見かける実装では、
- 内容が一致する行どうしを検出する
- 内容が一致していない行のかたまり(hunk)どうしでword単位の差分を生成する
という手順ですが、これだと似ている行と似ていない行の処理が振り分けられません。
そこで、不一致な行どうしで文字列の類似度をはかっておき、似ていれば差分を表示、似ていなければ行の削除＋行の追加とします。
類似度の指標はいろいろな人がいろいろなものを考案されていますが、今回はレーベンシュタイン距離を文字列の長さ(2つの文字列のうち、長いほうの長さ)で割ったものを採用します。
半角スペースと半角タブを除いた状態で50%以上合致していれば、類似していると判定することにします。
DiffEngine.CalcScore() 関数のあたりが該当部分です。
左右の入れ替え
ファイル１とファイル２を入れ替えて差分をとる場合、「ファイル１のN1行目を削除」「ファイル２のN1行目に新しい内容の行を追加」をそのまま反転すると行の追加→行の削除の順に表示されてしまいます。
行の削除→行の追加 の順で表示しないと不自然なので、差分を検出し、さらに差分の境界位置を調整した後に並べ替えを行っています。
なので、[swap panes] ボタンで左右を入れ替えた場合、完全には左右対称になっていません。
diff_orzで採用しなかったアルゴリズムの話
行どうしの差分をとるにあたり、ペアを確定するにあたって
- 先頭から順にペアを確定していく (diff_orzで採用)
- LCS (Longest Common Subsequence) をベースにペアを決定する
の二つのやり方があります。
LCSベースでペアを生成するには、
- 行どうしのペアが最も長く連続で一致する部分 (= Longest Common Subsequence)を探す
- ファイル１とファイル２のそれぞれを「LCSの前」「LCS」「LCSの後ろ」に３分割する
- 「LCSの前」「LCSの後ろ」のそれぞれについて１、２を繰り返す
- それ以上分割ができなくなったら終了
解説サイトなどでは、LCSベースのほうが自然な差分がとれると説明されているようですが、個人的には「先頭から順にマッチングを行ってから差分の境界を調整する」のでもそんなに効果は変わらないように思います。（あくまで主観）
diff_orzでは不一致行どうしの類似度も判定しているので、LCSベースのアルゴリズムとうまく両立させる方法を思いつかなかったというのもあり、先頭から順にペアを確定することにしました。