RFC 3284 の VCDIFF では、エンコーディングのためのアルゴリズムを自由に選択できるように設計されています。その選択についての情報がデータに含まれているため、追加の情報なしでデコーディングできます。実際、仕様にはエンコーディングのアルゴリズムについては述べられておらず、エンコーダーを実装するにはそこを用意しなければなりません。
オープンソースの VCDIFF の実装 open-vcdiff は "Data Compression Using Long Common Strings" を元にしたエンコーディングを行うそうです。この論文の著者の1人は 「珠玉のプログラミング」などの Jon Bentley です。その内容は簡潔にまとめられており分かりやすいです。ただし、そこで提案されているアルゴリズムでは Rabin-Karp string search algorithm の fingerprint を計算しているので、そちらも参照しなければなりません。
Diagonal でのエンコーダーの参考になりそうです。