Hacker News Reader

Comment by microtonal | Hacker News Reader

It's nice to see suffix arrays being used in the real world. For anyone who is interested in suffix arrays, the following to papers are recommended:

* Sufﬁx arrays: A new method for on-line string searches, U Manber, G Myers, 1993

* Using Suffix Arrays to Compute Term Frequency and Document Frequency for All Substrings in a Corpus, M Yamamoto, KW Church, 2001

The second paper actually uses an 'inverted index' for matching sequences to documents.

View on HN

Suffix arrays are useful for approximate matches too-- they're used by the binary delta program BSDiff[1] to match similar code sequences. BSDiff is used in Google products (Including Chrome)[2] and Firefox's delta updates.

[1]: http://www.daemonology.net/papers/bsdiff.pdf [2]: It performs additional preprocessing to make updates smaller (Courgette).

Courgette isn't BSDiff, it is Google's replacement for/improvement upon BSDiff. They were using BSDiff for Chrome updates before they switched to Courgette.

Courgette is a preprocessing stage to reduce the number of differences (disassembly + offset fixup + reassembly) plus BSDiff to catch anything else (using lzma instead of bzip2).

URL of the paper: "Using Suffix Arrays to Compute Term Frequency and Document Frequency for All Substrings in a Corpus, M Yamamoto, KW Church, 2001"

http://acl.ldc.upenn.edu/J/J01/J01-1001.pdf

> It's nice to see suffix arrays being used in the real world.

You are apparently not working in Bioinformatics. Suffix arrays are used a LOT here, but rather the more advanced stuff like the BWT. Although, maybe Genomics and Next Generation Sequencing technology are not very "real worldy" to most... :)

Reply on news.ycombinator.com