I am doing a seminar on a paper titled "Unified Compression-Based Acceleration
of Edit-Distance Computation" that uses straight-line programs to improve edit distance computation. It is a common method to exploit repetitions for ED although I couldn't find the first article that used it and I thought it is important to mention it in the seminar.
Does anybody have a clue what it was?
Thanks!
$\begingroup$
$\endgroup$
3
-
$\begingroup$ Why don't you consider the article by Masek and Paterson as the first one that used repetitions? $\endgroup$– Oleksandr BondarenkoCommented Dec 10, 2010 at 16:56
-
1$\begingroup$ Please clarify: SLP = straight-line program? $\endgroup$– JeffεCommented Dec 11, 2010 at 8:29
-
$\begingroup$ I think I will consider it as the first though I am not sure it is. $\endgroup$– stnrCommented Dec 11, 2010 at 16:15
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
Crochemore, Landau and Ziv-Ukelson were, I believe, the first to consider (LZ) compression explicitly in this context. As mentioned in the comments above, the earlier technique of Masek and Paterson is also in effect a form of compression. Considering general grammar-compression (SLP) is, I believe, a relatively new idea. Using it for string comparison speedup is original to the paper you cite, although comparing grammar-compressed strings as such has been considered before. You will find references and discussion in the compression chapter of http://arxiv.org/abs/0707.3619 .
-
1$\begingroup$ Wow, what an honor, an answer by Alexander Tiskin :). Your answer is probably correct but eventually I didn't mention it since a week ago I wasn't 100% sure who it really was. The lecture went good anyway. Thank you for the detailed answer! $\endgroup$– stnrCommented Dec 21, 2010 at 15:06