<p>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 <a href="http://arxiv.org/abs/0707.3619" rel="nofollow">http://arxiv.org/abs/0707.3619</a> .</p>

CC BY-SA 2.5
2010-12-21T15:06:59.547Z
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!
stnr
CC BY-SA 2.5
2010-12-21T09:59:03.433Z
2010-12-21T09:59:03.433Z
Alexander Tiskin
<p>I am doing a seminar on a paper titled <a href="http://www.wisdom.weizmann.ac.il/~oweimann/Publications/SLP2.pdf" rel="nofollow">"Unified Compression-Based Acceleration
of Edit-Distance Computation"</a> 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.
<br>
Does anybody have a clue what it was?
<br>Thanks!</p>

CC BY-SA 2.5
2010-12-10T16:56:19.873Z
Why don't you consider the article by Masek and Paterson as the first one that used repetitions?
Oleksandr Bondarenko
CC BY-SA 2.5
2010-12-11T08:29:20.410Z
Please clarify: SLP = straight-line program?
Jeffε
CC BY-SA 2.5
2010-12-11T16:15:48.053Z
I think I will consider it as the first though I am not sure it is.
stnr
<reference-request><ho.history-overview><string-matching><edit-distance>
Using compression to improve edit distance computation
stnr
# Using compression to improve edit distance computation

(Asked by: username_0 on 2010-12-10)

I am doing a seminar on a paper titled ["Unified Compression-Based Acceleration
of Edit-Distance Computation"](http://www.wisdom.weizmann.ac.il/~oweimann/Publications/SLP2.pdf) 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!

**Tags:** reference-request, ho.history-overview, string-matching, edit-distance
> **Comments:**
> **username_1**: Why don't you consider the article by Masek and Paterson as the first one that used repetitions?  
> **username_2**: Please clarify: SLP = straight-line program?  
> **username_0**: I think I will consider it as the first though I am not sure it is.  

---

## 1 answers

### Answer by username_3 on 2010-12-21. Score: 2 | Accepted answer

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> .

> **Comments:**
> **username_0**: 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!  

---

