59

Git はデルタ圧縮を使用して、互いに類似したオブジェクトを格納します。

このアルゴリズムは標準化されており、他のツールでも使用されていますか? フォーマットを説明するドキュメントはありますか? xdelta/VCDIFF/RFC 3284 と互換性がありますか?

4

3 に答える 3

70

パック ファイルに使用される diff アルゴは、そこにあるデルタ エンコーディングの 1 つにリンクされていたと思います:最初 (2005) xdelta、次にlibXDiff。
しかしその後、以下に詳述するように、カスタム実装に移行しました。

とにかく、ここで述べたように：

Git はパックファイルでのみ差分化を行います。
しかし、SSH経由でプッシュすると、gitは反対側にないコミットを含むパックファイルを生成し、それらのパックはシンパックであるため、デルタもあります...しかし、リモート側はそれらのシンパックにベースを追加してそれらを作成しますスタンドアロン。

(注: 多くのパックファイルを作成したり、巨大なパックファイルから情報を取得したりするのはコストがかかります。git が巨大なファイルや巨大なリポジトリをうまく処理できない理由を説明してください。
詳細については、「git with large files」を参照してください) 。

このスレッドは、次のことも思い出させてくれます。

実際、packfiles と deltification ( xdelta ではなく LibXDiff ) は、もともとネットワーク帯域幅(ディスク容量よりもはるかにコストがかかる) と、非常に多数のファイルではなく単一の mmaped ファイルを使用することによるI/O パフォーマンスが原因でした。緩いオブジェクトの。

LibXDiff は、この2008 スレッドで言及されています。

ただし、それ以来、この2011 スレッドが示すように、および のヘッダーがdiff-delta.c指摘するように、アルゴリズムはおそらくカスタムのもので進化しました。

したがって、厳密に言えば、現在の Git のコードは libxdiff のコードとはまったく似ていません。
ただし、両方の実装の背後にある基本的なアルゴリズムは同じです。
これがどのように機能するかを理解するには、libxdiff バージョンを調べる方がおそらく簡単です。

/*
 * diff-delta.c: generate a delta between two buffers
 *
 * This code was greatly inspired by parts of LibXDiff from Davide Libenzi
 * http://www.xmailserver.org/xdiff-lib.html
 *
 * Rewritten for GIT by Nicolas Pitre <nico@fluxnic.net>, (C) 2005-2007
 */

Git Bookのパックファイルの詳細:

パックファイル形式

Git 2.18 は、この新しいドキュメント セクションのデルタの説明に追加され、現在 (2018 年第 2 四半期) は次のように述べています。

オブジェクトの種類

有効なオブジェクト タイプは次のとおりです。

  • OBJ_COMMIT(1)
  • OBJ_TREE(2)
  • OBJ_BLOB(3)
  • OBJ_TAG(4)
  • OBJ_OFS_DELTA(6)
  • OBJ_REF_DELTA（7）

タイプ 5 は、将来の拡張用に予約されています。タイプ 0 は無効です。

微分表現

概念的には、コミット、ツリー、タグ、ブロブの 4 つのオブジェクト タイプしかありません。
ただし、スペースを節約するために、オブジェクトを別の「ベース」オブジェクトの「デルタ」として格納できます。
これらの表現には、パック ファイルでのみ有効な新しいタイプの s-delta および ref-delta が割り当てられます。

オブジェクトを再構築するために、別のオブジェクト (「ベース オブジェクト」と呼ばれる) に適用される「デルタ」を格納しますofs-delta。 それらの違いは、ref-delta

  • ref-delta は、20 バイトのベース オブジェクト名を直接エンコードします。
    • ベース オブジェクトが同じパックにある場合、ofs-delta は代わりにパック内のベース オブジェクトのオフセットをエンコードします。

同じパックにある場合、基本オブジェクトも差分化できます。
Ref-delta は、パックの外側のオブジェクトを参照することもできます (つまり、いわゆる「シン パック」)。ただし、ディスクに保存する場合は、循環依存を避けるためにパックを自己完結型にする必要があります。

差分データは、ベース オブジェクトからオブジェクトを再構築するための一連の命令です。
ベース オブジェクトが差分化されている場合は、最初に標準形式に変換する必要があります。各命令は、ターゲット オブジェクトが完了するまで、さらに多くのデータをターゲット オブジェクトに追加します。
これまでのところ、次の 2 つの命令がサポートされています。

  • 1 つはソース オブジェクトからバイト範囲をコピーするためのもので、
  • 1 つは、命令自体に埋め込まれた新しいデータを挿入するためのものです。

各命令は可変長です。命令タイプは、最初のオクテットの 7 番目のビットによって決まります。次の図は、RFC 1951 (Deflate 圧縮データ形式) の規則に従っています。

于 2012-02-28T08:25:49.870 に答える
25

Git デルタ エンコーディングは、コピー/挿入ベースです。

これは、派生ファイルが一連のオペコードとしてエンコードされ、コピー命令 (例: ベース ファイルからオフセット x から始まる y バイトをターゲット バッファーにコピーする) または挿入命令 (例: 次の x バイトをターゲット バッファーに挿入する) を表すことができることを意味します。ターゲット バッファー)。

非常に単純な例 (論文「ファイル システム サポート デルタ圧縮」から引用) として、テキスト「プロキシ キャッシュ」を「キャッシュ プロキシ」に変換するデルタ バッファを作成するとします。結果の命令は次のようになります。

  1. オフセット 7 から 5 バイトをコピー (ベース バッファから「キャッシュ」をコピー)
  2. 2 つのスペースを挿入する
  3. オフセット 0 から 5 バイトをコピー (ベース バッファから「プロキシ」をコピー)

git のエンコーディングに変換すると、次のようになります。

(バイト 1 ～ 3 は最初の命令を表します)

  • 0x91 (10010001) に分割されます。
    • 0x80 (10000000) (最上位ビットを設定すると、これは「ベースから出力へのコピー」命令になります)
    • 0x01 (00000001) (「1 バイト進めてベースオフセットとして使用する」という意味)
    • 0x10 (00010000) (1バイト進めて長さとして使用)
  • 0x07 (オフセット)
  • 0x05 (長さ)

(バイト 4 ～ 6 は 2 番目の命令を表します)

  • 0x02 (MSB が設定されていないため、これは「次の 2 バイトを出力に挿入する」ことを意味します)
  • 0x20 (スペース)
  • 0x20 (スペース)

(バイト 7 ～ 8 は最後の命令を表します)

  • 0x90 (10010000) に分割されます。
    • 0x80 (10000000) (「コピー」を意味します)
    • 0x10 (00010000) (1バイト進めて長さとして使用)
  • 0x05 (長さ)

最後のコピー命令では、オフセット 0 を意味するオフセットが指定されていないことに注意してください。より大きなオフセット/長さが必要な場合は、コピー オペコードの他のビットも設定できます。

この例のデルタ バッファの結果は 8 バイトで、ターゲット バッファが 12 バイトであるため、あまり圧縮されていませんが、このエンコーディングを大きなテキスト ファイルに適用すると、大きな違いが生じる可能性があります。

私は最近、git delta エンコーディングを使用して diff/patch 関数の両方を実装する github にnode.js ライブラリをプッシュしました。コードは、 大幅に最適化された git ソースのものよりも読みやすく、コメントが付けられている必要があります。

上記と同様の形式で、各例で使用される出力オペコードを説明するいくつかの テストも作成しました。

于 2013-01-13T13:30:54.543 に答える