Tutorial 11

Tuesday, July 30, 2013

12:30 PM

- Given compressed string & initial dictionary, uncompress the string
- Run compression algorithm with the role of the string swapped with the indices
- Does not compress
- Reorder string so it is easier to compress
- Ie patterns more obvious
- Repeated substrings becomes runs of characters
- Sort all shifts lexicographically ($ is smallest)
- Output last column of character (last character of the shifts in sorted order.
- Basic idea: follow indices
- Follow indices
- Why can't we compress until 1 bit?
- Entropy limit from information theory
- There is a lower bound on the # of bits needed to represent a string
- Need to distinguish all possible strings
- For codes encoding 1 character per code word limit is
- Huffman codes obtain this if we ignore floors & ceilings
- Lossless compression works by looking for patterns and writing it succinctly (using small # of bits)
- Need dictionary or some set of rules for decoding
- Most in MCs (1st 2 pages)

L2W decoding

Try at home

referees_ref_refs

BWT aka Block - sorting compression

Decoding

Limits on compression

There are bounds for other cases

Drawing KD tress

Cumulative

Large emphasis on compression

Created with Microsoft OneNote 2010

One place for all your notes and information