ファイルのバージョン管理アプローチについて

ソース管理バージョン管理システム（SVN、Mercurial、Gitなど）を使用する人は、ファイルバージョンを比較してユーザーが行った変更を表示する機能を利用する可能性が高いでしょう。 多くの独立したバージョン比較プログラムがあります（ WinMerge 、 BeyondCompareなど）。 バージョンを比較する場合、原則として、ファイルの2つのバージョンが隣り合わせに表示されるため、ドキュメントの同じ（変更されていない）部分が互いに反対側に配置され、変更（追加および削除）が対応する色で強調表示されます。

多くの人が、このような比較を実装するためにどのアルゴリズムを使用できるかを知りたいと思うでしょう。



単純なケースとして、プレーンテキストファイルの比較を検討してください。

テキストファイルは、テキストの行（または段落）のコレクションです。 段落とは、行末文字と復帰文字（Windowsの場合）または1つの行末文字（Unix / Linuxの場合）で終わる文字の行です。 文字が異なるエンコーディングで表現できるという事実に気を取られず、シングルバイトASCIIを扱っていると仮定します。 このようなファイルのバージョンを比較するタスクは、どの段落が変更されていないか、どの段落が変更、削除、または追加されたかを判断することです。



ほとんどのファイル比較アルゴリズムは、Longest Common Subsequence（LCS）検索アルゴリズムに基づいています。 実際、2つのファイルの文字の最長共通サブシーケンスは変更されていない部分と見なすことができ、他のすべてのセクション（バージョンの1つに属しているかどうかに応じて）は削除（古いバージョンに属している場合）または追加（新しいバージョンに属している場合）されます。 LCSアルゴリズムにはいくつかの実装があり、その計算の複雑さは、多項式（比較されるサブシーケンスの長さに直接比例する）から対数まで変化します。 また、これらのアルゴリズムは非常にメモリ集約型です。 このような条件で文書を文字ごとに表示することは非現実的であることが明らかになります。 比較の単位として段落を使用する方が便利です。 それらは「現状のまま」で比較できます。 文字列として直接、しかしそれを最適化するために、それらをキャッシュし、ハッシュを比較し、ハッシュが一致する場合にのみ文字列自体を参照する方が便利です（ハッシュ中に誰も衝突から安全ではないため）。



したがって、比較アルゴリズムの最初のステップは、ドキュメントの段落のリストをメモリにロードし（はい、両方のドキュメントをメモリに完全にロードする必要があります）、それらをハッシュし、検索アルゴリズムのハッシュに最大共通一致サブシーケンス（LCS）を適用します。 この段階の出力では、ドキュメントの保証された変更されていない（つまり一致する）セクションに関する情報を受け取ります。 他のすべてのサイトが変更されます。 古いバージョンから変更されたセクションが新しいバージョンの空のセクションに対応する場合、このセクションは削除されています。 新しいバージョンの変更されたセクションが古いバージョンの空のセクションに対応する場合、このセクションが追加されています。



古いバージョンと新しいバージョンの両方に変更されたセクションが存在するため、状況はより複雑です。 たとえば、2つの一致するセクションの間に、変更されたセクションを配置できます。これは、古いバージョンでは2つの段落で、新しいバージョンでは3つでした。 これらの5つのパラグラフの中に等しい（一致する）パラグラフはありません。 このステップで停止すると、変更された段落グループ全体をユーザーに表示し、詳細な変更を分析するタスクをユーザーにシフトできます。 しかし、あなたはもっと巧妙なことができます。 どのセクションが一致するかを正確に知るために、変更されたセクションの段落の最適な一致を計算できます。 段落の各ペアの「類似性」を評価するために、いわゆる「編集距離」（またはレーベンシュタイン距離）を計算するアルゴリズムを適用できます。 編集距離は、ある行を別の行に変換するために必要な、ある文字を別の文字に挿入、削除、および置換する最小数です。 変更されたセクションの段落の各ペア間の編集距離を計算したら、動的プログラミング法を適用して、変更されたセクションの段落間の最適な対応を計算できます。 この場合の最も非最適な配置オプションは、古いバージョンの変更されたセクションのすべての段落が削除されたと見なされ、新しいバージョンのすべての段落が追加されたときです（つまり、だれも一致しません）。 他のすべての宿泊施設オプションがより最適です。 動的計画法を適用すると（この場合どのように正確に適用できるか、別の投稿に書きます）、最適な対応のバリアントを見つけることができます。 これで、変更されたセクションのどの段落がどの段落に対応するかが確実にわかったので、比較アルゴリズム（今回は記号）を適用して、段落内の正確な変更を計算できます。



親愛なる読者が、最大共通サブシーケンスを見つけるアルゴリズムの実装の詳細と機能に興味がある場合、距離を編集し、動的プログラミング手法を適用して、変更された段落のグループに最適なフィットを計算します（後者のアルゴリズムを私のノウハウと考えています）、これについてコメントに書いてくださいこれについてさらに詳細な記事を書きます（これらのアルゴリズム自体は非常に興味深いものであり、別の記事に値します）。