# Huffman coding The first byte in a encoded stream indicates the number of key value pairs that follow in the translation table. Each pair starts with the key byte, has a second byte indicating the length of the code in bytes, and then the bytes that make up a code. In the table, if paths were stored as raw bytes, there would be no way to distinguish between 0001 and 01 due to the leading zeros. To fix this ambiguity, all codes are prepended with a 1 in the table. For those examples they would look like 00010001 and 00000101 respectively. After the table, there is one more byte which contains the number of padding bits at the end of the data region. The rest of the byte stream can be interpreted as data. ### Table representation possibilities: - Set (4 byte?) code lengths (requires preceding 1 to determine starting point) vs prefix byte giving length of code in bits - Sparse representation requiring each code to be prefixed with its corresponding byte vs all bytes being given in order [Huffman trees](https://www2.cs.duke.edu/csed/poop/huff/info/) [Docsite setup](https://github.com/rrbutani/mandelbrot/blob/master/.travis.yml) # Run length encoding There is no header, the stream consists of a number of symbol-count pairs. The symbol is the byte repeated, and the variable length field that follows is the number of times to repeat it. For each byte, if the value is not 0, take its value and end the field. Otherwise add 256 to the remainder of the field. # LZ78 compression # Burrows Wheeler # General - try rayon to speed stuff up - test benchmarks (ratios on audio/img/vid/english/binary/etc. fancy graphs?) - test benchmarks (speed) - test recompression dropoff curve and various combinations of methods - try chunking for huffman code improvement