# Huffman
[Huffman](https://en.wikipedia.org/wiki/Huffman_coding) encoding and decoding.
Huffman coding is great for compressing binary data, especially with binaries
that contain a lot of repetition.
# Installation
Add the following to your mix.exs under deps:
`{:huffman, "~> 1.0"}`
# Usage
There are really just two functions to care about, `encode` and `decode`
```elixir
{encoded, keys} = Huffman.encode "Lil Wayne is the best rapper alive."
Huffman.decode encoded, keys
# returns "Lil Wayne is the best rapper alive."
```
The encode function takes a second optional argument in case the input is utf16
or utf32. Decode returns whatever encoding it was given.
```elixir
{encoded, keys} = Huffman.encode(<<"bananas"::utf32>>, :utf32)
Huffman.decode(encoded, keys)
# returns <<0, 0, 0, 98, 0, 0, 0, 97, 0, 0, 0, 110, 0, 0, 0, 97, 0, 0, 0, 110, 0, 0, 0, 97, 0, 0, 0, 115>>
```
## Internals
In case you care!
The basic formula is to calculate the frequencies of individual bytes, generate
a binary-tree structure, then walk that tree to determine each byte's encoded
value.
### Huffman.Tree
Huffman tree implementation. Can either take in a set of keys and weights to
build a corresponding tree (to calculated their encoded values) or take in a set
of codes and their corresponding codes to rebuild the tree.
Example:
Given the following codes (binary representation in comment) and keys, we can
reconstruct the huffman tree for decoding.
```elixir
codes_and_keys = %{
{<<4::size(3)>>, "n"}, # 100
{<<7::size(3)>>, " "}, # 111
{<<13::size(4)>>, "i"}, # 1101
{<<11::size(4)>>, "e"}, # 1011
{<<10::size(4)>>, "o"}, # 1010
{<<5::size(4)>>, "f"}, # 0101
{<<3::size(4)>>, "a"}, # 0111
{<<2::size(4)>>, "m"}, # 0011
{<<1::size(4)>>, "s"}, # 0001
{<<24::size(5)>>, "l"}, # 11000
{<<9::size(5)>>, "x"}, # 01001
{<<8::size(5)>>, "g"}, # 01000
{<<0::size(5)>>, "p"}, # 00000
{<<25::size(6)>>, "t"} # 011001
}
Huffman.Tree.from_codes(codes_and_keys)
```
Underneath, this is what the tree will look like:
![huffmantree](https://cloud.githubusercontent.com/assets/1015847/8145854/734aaf44-11ce-11e5-9d53-353cb53df5fb.png)