3 ms·
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: * Suffix ar
by danieldk 13y ago
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:
* Suffix 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.
- ramayac 13y agoURL 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 http://acl.ldc.upenn.edu/J/J01/J01-1001.pdf
- Scaevolus 13y agoSuffix 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 http://www.daemonology.net/papers/bsdiff.pdf [2]: It performs additional preprocessing to make updates smaller (Courgette).
- LukeShu 13y agoCourgette isn't BSDiff, it is Google's replacement for/improvement upon BSDiff. They were using BSDiff for Chrome updates before they switched to Courgette.
- Scaevolus 13y agoCourgette 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).
- fnl 13y ago> 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... :)