Most of the papers I run across that deal with compressed representations of sets/sequences just talk about rank and select out of context. I'm looking for something that explains directly how these are used to implement set operations, but would be happy with something that goes through using them for pattern matching.
This is a good question.
A good place to start looking for an answer is in
P. Prochazka, Natural language compression using byte codes Ph.D. thesis, Czech Technical University in Prague, 2014:
http://www.fit.cvut.cz/sites/default/files/PhDThesis.pdf
See Section 2.2, starting on page 10, on Liguistic basics. This is an especially good introduction to character-based compression. The basic idea is to replace repeating substrings in a text by a link to a dictionary or to a previous occurrence of the substring.
- Badges
- Science topic
- Similar topics
- Engineering
- Electrical Engineering
- Signal Processing
- Image Processing