IBM RD 50-1 | An approximation to the greedy algorithm for differential compression

http://www.research.ibm.com/journal/rd/501/agarwal.html

Differential compression arose as part of the string-to-string correction problem [2], finding the minimum cost of representing one string in terms of another.

問題：
差分圧縮：参照ファイルが与えられたときの、対象ファイルの符号化
文字列と文字列の距離計算とも類似

歴史：
2乗時間／線形領域で最適符号化をする greedy アルゴリズムが考案されている。

hsa: hash suffix array