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?

  • $\begingroup$ Why don't you consider the article by Masek and Paterson as the first one that used repetitions? $\endgroup$ – Oleksandr Bondarenko Dec 10 '10 at 16:56
  • 1
    $\begingroup$ Please clarify: SLP = straight-line program? $\endgroup$ – Jeffε Dec 11 '10 at 8:29
  • $\begingroup$ I think I will consider it as the first though I am not sure it is. $\endgroup$ – stnr Dec 11 '10 at 16:15

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 .

| cite | improve this answer | |
  • 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$ – stnr Dec 21 '10 at 15:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.