Javascript で diff (内部仕様についての補足５)

10/14 に投稿したJavascript で diff (通信なし、ローカルで完結)の内部仕様についての補足、その５です。
Javascript で diff (内部仕様についての補足)
Javascript で diff (内部仕様についての補足２)
Javascript で diff (内部仕様についての補足３)
Javascript で diff (内部仕様についての補足４)

※10/14 投稿のソースは Microsoft Edge で文字コードをUTF-8として認識していなかったので、文字コードの指定を追加しました。
Edge が Chrome 準拠になったら、また微修正するかもしれません。

文字列の類似度をはかる (検討しようとして撃沈された)

補足その１ Javascript で diff (内部仕様についての補足) で、レーベンシュタイン距離の用語を出したまま説明を端折っていたので、今回はレーベンシュタイン距離の話題です。

行単位の差分をとるにあたって、似ている行は差分を表示、似ていない行は削除＋追加として表示するため、文字列の類似度を測ることにします。
文字列の類似度を測る指標はいろいろありますが、まずはどの指標でどのような数値が算出されるのか試してみようとして、下記の方法でスコアを算出してみることにしました。

• レーベンシュタイン距離(Levenshtein distance)
• ダメラウ・レーベンシュタイン距離(Damerau-Levenshtein distance)
• ジャロ・ウィンクラー距離 (Jaro-Winkler distance)
• N-Gram

「abcdef」「defabc」の距離をはかると、レーベンシュタイン距離は類似度0.5となりましたが、残り３つはすべて類似度0となり、検討する前に終了してしまいました………… orz
なので、diff_orz では、レーベンシュタイン距離を類似度の指標として採用しています。

レーベンシュタイン距離

Wikipediaの該当ページ － レーベンシュタイン距離

レーベンシュタイン距離の解説そのものは、Wikipedia のものをはじめネット上の各所にあるので、詳細な説明はここでは省略します。
簡単に言うと、ある文字列を別の文字列に変形するのに必要な操作回数を調べれば、「削除・追加・置換の操作回数が多い」＝「似ていない文字列」といえます。
削除・追加・置換の回数を調べた段階では、操作回数の絶対値が算出されるだけですので、何%くらい似ているかを調べるには、

　　1 - (操作回数 / 文字列の長さ)

と換算する必要があります。
上述の換算には、

• 置換を操作コスト1としてカウントするか、操作コスト2としてカウントするか
• 二つの文字列のうち、長いほうの長さを基準にするか、両方の長さを考慮するか

など、バリエーションがあります。diff_orz では、

• 削除・追加・置換の操作のコストはすべて1
• 二つの文字列のうち、長いほうの長さを基準にする

としています。

最初に試作したときは、動的計画法で実装していたのですが、効率がO(MN)で大変遅かった (2019/11/16 時点の Wikipedia では何故か「効率がよい」となっている) ため、あれこれ試行錯誤した後、Wu のアルゴリズムによる O(NP) の実装に落ち着きました。

An O(NP) sequence comparison algorithm

文字列どうしが似ていると判定する閾値は threshold で指定しています。
既定値の0.5のままでも大抵うまくいくと思いますが、判定をゆるくしたい場合は0に近い数値、判定をきつくしたい場合は1.0に近い数値を指定してください。
下記実装では、閾値を超えた場合に計算を打ち切って「似ていない」と判定しています。

var DiffEngine = {
	//中略
	threshold: 0.5,	//0(loose) < threshold < 1(strict) 文字列どうしが似ていると判定する閾値

	//中略

	//レーベンシュタイン距離のスコアを計算
	CalcScore(s1, s2, len1, len2) {
		const pmax = len1 + 1 - this.threshold * len2, _max = Math.max;
		if (pmax < 1) { return 0; }		//optimize
		let y, p = 0, fp = (new Int32Array(len1 + len2 + 3)).fill(-1);
		for (; (p < pmax) && (fp[len2 + 1] != len2); p++) {
			for (let k = len1 - p; k < len2; k++) {
				for (y = _max(fp[k] + 1, fp[k + 2]);
					(y < k) && (s1.charCodeAt(y - k + len1) == s2.charCodeAt(y));
					y++) {}
				fp[k + 1] = y;
			}
			for (let k = len2 + p; k >= len2; k--) {
				for (y = _max(fp[k] + 1, fp[k + 2]);
					(y < len2) && (s1.charCodeAt(y - k + len1) == s2.charCodeAt(y));
					y++) {}
				fp[k + 1] = y;
			}
		}
		return (1 - (len2 - len1 + p - 1) / len2);	//distance score
	},
	//後略
}