C#でDiffアルゴリズムを実装してみた
こちらで実装の詳細を書くと言ったので、書きたいと思います。
はじめに
C#実装のDiffライブラリはいくつかあったのですが、自分で実装したのは以下の理由からです。
- 差分抽出対象を文字列限定にしたくない
- IEqualityComparerを指定して比較方法を外部から指定したい
- 最短経路が複数存在する場合に、どの経路を採用するかを制御したい(後ほど詳しく解説します)
- 巨大データの差分を抽出するときに精度を落として高速化したい
- アルゴリズムの理解を深めたい
実装の解説
アルゴリズムについての詳細は、既に分かりやすく解説してくれているサイトがあるのでそちらを参考にして下さい。
Diff algorithm - 枕を欹てて聴く
1. EditGraph の作成
今回は good と dog の差分を例にして、差分結果が以下のようになることを目標とします。
g d o o g d - + = - + -
EditGraphを作成すると以下のようになります。
2. 編集距離(d) = 0
- 各k線に対する最遠点の配列farthestPointsと現在の先端ノードのリストheadsを初期化する
- 先端ノードのリストに原点のノードを追加する
- 追加したノードを斜めに進めるだけ進める
dog と good では(0, 0)から(1, 1)に進めないので以下のようになります。
3. 編集距離(d) = 1
- 右側に進める場合は進める
- 下側に進める場合は進める
進めるか進めないかの判定は以下の2点となります。
- 進めた先の点～最終点 の距離が、対応するk線における最遠点～最終点 の距離以下か (言い換えると最遠点を更新できるか、もしくは最遠点と同じか)
- EditGraphの範囲内か
d = 1のときはどちらも進めるので次のようになります。
4. 編集距離(d) = 2
同様に右、下に進めます
このとき(1,1)で複数のノードが存在してしまいます。
ここで指定された条件に最も合うものを採用します。
これが冒頭で述べた最短経路が複数存在する場合に、どの経路を採用するかを制御したいという処理になります。
この時点で ①を採用した場合は
g d - +
となり
②を採用した場合は
d g + -
となります。
今回は差分結果
g d o o g d - + = - + -
となることを目標にしているので、①を採用する必要があります。
そこで、各ノードにスコアを持たせてスコアで判定するようにします。
スコアは座標が更新されるごとにその座標を加算していくようにします。
①の場合は(0, 0) ⇒ (1, 0) ⇒ (1, 1) なので (2, 1)となり、ScoreX = 2, ScoreY = 1となります。
②の場合は(0, 0) ⇒ (0, 1) ⇒ (1, 1) なので (1, 2)となり、ScoreX = 1, ScoreY = 2となります。
g d o o g d - + = - + -
は削除優先なのでScoreXが大きいを①を採用すればいいことが分かります。
さらに、(1, 1)から(2, 2)は進めるので、最終的にこうなります。
5. 編集距離(d) = 3
編集距離が3の場合は次のようになり、今度は(3, 2)で複数のノードが存在します。
①の場合は(0, 0) ⇒ (1, 0) ⇒ (1, 1) ⇒ (2, 2) ⇒ (3, 2) なので (7, 5)となり、ScoreX = 7, ScoreY = 5となります。
②の場合は(0, 0) ⇒ (1, 0) ⇒ (2, 0) ⇒ (2, 1) ⇒ (3, 2) なので (8, 3)となり、ScoreX = 8, ScoreY = 3となります。
ここで削除優先なのでScoreXが大きいほう➂を採用してしまうと
g o d o - - + =
となり、目標と相違してしまいます。
そこで、ノードにスコアとは別に直進した回数StraightCountを持たせます。
①の場合は一回も直進してないので StraightCount = 0 となります
➁の場合は(0, 0) ⇒ (1, 0) ⇒ (2, 0) で直進しているので StraightCount = 1 となります
※斜めに直進した回数はカウントしません。
StraightCountが一番小さいものを採用します。
もし複数ある場合はその中でScoreXが大きいものを採用すればいいわけです。
結果は次のようになります。
5. 終了処理
以降は、先端ノードのいずれかが終点に達するまで同じことを繰り返すだけです。
終点に達したら親ノードをたどって経路を返してあげるだけです。
最終的にはこうなります。
