COMPSCI 61B Lecture Notes - Lecture 39: Compression Ratio, Complexity Class, Kolmogorov Complexity
1 Jun 2017
School
Department
Course
Professor
Document Summary
Labs 7 and 11 are free points for everybody. 2 points if you ll out the survey. You can also do it at home if you can"t make it to the physical lecture. Post- nal exam survey will be worth 4 extra credit points. Hu man coding can be used to compress any data, not just text. In bitmap format, the plant below is simply the stream of bits shown on the right. We will package the compressed data plus decoder into a single self-extracting . java. The goal is to nd short sequences of bits that generate desired longer sequences of bits. Given a sequence of bits b, nd a shorter sequence c(b) that produces b when fed into an interpreter. Compression ratio of 25% is certainly very impressive, but we can do much better. Of the 28389584 possible bitstreams of length 8389584, only one in 28360151 can be generated by our interpreter using an input of length 29,432 bits.
