Tutorial 11

Tuesday, July 30, 2013

12:30 PM

    Important L2W decoding

    • Given compressed string & initial dictionary, uncompress the string
    • Run compression algorithm with the role of the string swapped with the indices


    Try at home



    Important BWT aka Block - sorting compression

    • Does not compress
    • Reorder string so it is easier to compress
      • Ie patterns more obvious
    • Repeated substrings becomes runs of characters


    1. Sort all shifts lexicographically ($ is smallest)
    1. Output last column of character (last character of the shifts in sorted order.



    • Basic idea: follow indices
    • Follow indices


    Important Limits on compression

    • 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


    There are bounds for other cases

    • Lossless compression works by looking for patterns and writing it succinctly (using small # of bits)
    • Need dictionary or some set of rules for decoding


    Drawing KD tress



    • Most in MCs (1st 2 pages)


    Large emphasis on compression




Created with Microsoft OneNote 2010
One place for all your notes and information