This project recreates a compression method known as Huffman Encoding. Details about how it works are in the project and notes.
Huffman Encoding works by assigning characters bit strings (Example: 100110). The characters that are used more often are assigned shorter codes, while more sparsely used characters can afford to use longer codes. How does the computer know which codes mean what? It builds a tree. If you haven't already, compress something with the project and look at the tree graph it draws. Each one of the "leaf" nodes (nodes that have no descendants) represents a character in your data. Pick one of those leaf nodes and trace a path to it. You can describe the path you took with a series of left and rights. The computer describes the path you take as 0 for left, and 1 for right. Some nodes are closer to the root of the tree and take less steps to get there. These are your most commonly used characters. Being closer to the root of the tree means it takes a shorter code to describe. "But a bunch of 1s and 0s for one character seems like its expanding the data, what if B got mapped to 1110, that's 4 times larger!". It would be reasonable to say this, but character are actually represented as 8 1's and 0's to a computer in binary, so if B were mapped to 1110, it would actually be half the size.
