How CpcSketch's CompressionData gets generated?

[tisonkun]

In code comment, I saw:

~/ocaml-4.03.0/bin/ocamlopt -o generateHuffmanCodes columnProbabilities.ml generateHuffmanCodes.ml
./generateHuffmanCodes > raw-encoding-tables.c

But I can't find the source of (columnProbabilities.ml generateHuffmanCodes.ml) anywhere.

[leerho]

Kevin did most of his math simulations and modeling in Ocaml. And his code was on his computer, which no longer exists. And his personal code died with him. Those references were his references to that code. I could try to see if Yahoo has it in their archives. But even if they have a copy of his old computer it might be trying to find a needle in a haystack.

[tisonkun]

Got it. Kudos to Kevin for his brilliant CpcSketch.

We have three encoding tables here. The decoding tables are derived from encoding tables and the deriving logics are available.

• LENGTH_LIMITED_UNARY_ENCODING_TABLE65 - having some comments, but doesn't tell how it is computed
• COLUMN_PERMUTATIONS_FOR_ENCODING - having some comments, generated by "generatePermutationsForSLIDING.ml". We may reverse engineer from the comments to the original program
• ENCODING_TABLES_FOR_HIGH_ENTROPY_BYTE - having some comments, generated by "columnProbabilities.ml" and "generateHuffmanCodes.ml". It is "23 length-limited Huffman codes".

Not sure how much details are included in the "Back to the Future" paper.

[leerho]

You should definitely read the paper. But it won't tell you any details on the Huffman codings. As I recall, in his paper he used a more standard compression scheme. He finished his work on the code after he had finished his paper -- and in the process came up with the modified Huffman coding idea, which is quite a bit more efficient than what he discussed in the paper.