def enhuffen(frequencies):
    """Produce huffman encoding for the given symbol:frequency map.

    This function constructs a huffman tree to encode the symbols.  It returns
    a dict mapping symbols to their corresponding code as a string of "0" and
    "1" characters, and a string encoding a tree lookup structure for decoding
    with the tree at runtime.

    All symbols are assumed to fit in 15 bytes, and the tree is encoded for
    lookup as follows.  Each node of the tree occupies four bytes in the
    lookup structure.  The first two bytes encoding the child for a "0" and
    the second two bytes encode the child for a "1".  If the high bit is set
    on those bytes then it's a leaf node, with the low 15 bits giving the
    symbol.  If not then it's the offset of the next node in the tree, whose
    data can be read at offset*2 bytes from the start of the string.
    """
    total = sum(f for f in frequencies.itervalues())
    in_queue = []
    for c in frequencies:
        in_queue.append((frequencies[c] / total, [c]))
    in_queue.sort()
    queue = []
    codes = defaultdict(lambda: "")

    def popmin():
        if not queue:
            return heapq.heappop(in_queue)
        if not in_queue:
            return heapq.heappop(queue)
        if queue[0][0] < in_queue[0][0]:
            return heapq.heappop(queue)
        return heapq.heappop(in_queue)

    while len(in_queue) > 0 or len(queue) > 1:
        (p1, s1) = popmin()
        (p2, s2) = popmin()
        for c in s1:
            codes[c] = "0" + codes[c]
        for c in s2:
            codes[c] = "1" + codes[c]
        heapq.heappush(queue, (p1 + p2, s1 + s2))

    def encode_symbol(n):
        assert n < 0x8000, "symbol too big: " + str(n)
        return chr(n & 0xFF) + chr(0x80 | (n >> 8))

    def encode_subtree(n):
        assert n < 0x8000, "subtree too big: " + str(n)
        return chr(n & 0xFF) + chr(n >> 8)

    NULL = encode_subtree(0)
    tree = [NULL, NULL]

    branch0 = []
    branch1 = []
    for symbol, code in codes.iteritems():
        if code[0] == "0":
            branch0.append((code[1:], symbol))
        else:
            branch1.append((code[1:], symbol))
    pending_subtrees = [(0, branch0), (1, branch1)]

    while pending_subtrees:
        (idx, subtree) = pending_subtrees.pop()
        assert tree[idx] == NULL
        if len(subtree) == 1:
            assert subtree[0][0] == ""
            tree[idx] = encode_symbol(subtree[0][1])
        else:
            branch0 = []
            branch1 = []
            for code_suffix, symbol in subtree:
                if code_suffix[0] == "0":
                    branch0.append((code_suffix[1:], symbol))
                else:
                    branch1.append((code_suffix[1:], symbol))
            tree[idx] = encode_subtree(len(tree))
            pending_subtrees.append((len(tree), branch0))
            tree.append(NULL)
            pending_subtrees.append((len(tree), branch1))
            tree.append(NULL)

    return codes, "".join(tree)
Produce huffman encoding for the given symbol:frequency map.

    This function constructs a huffman tree to encode the symbols.  It returns
    a dict mapping symbols to their corresponding code as a string of "0" and
    "1" characters, and a string encoding a tree lookup structure for decoding
    with the tree at runtime.

    All symbols are assumed to fit in 15 bytes, and the tree is encoded for
    lookup as follows.  Each node of the tree occupies four bytes in the
    lookup structure.  The first two bytes encoding the child for a "0" and
    the second two bytes encode the child for a "1".  If the high bit is set
    on those bytes then it's a leaf node, with the low 15 bits giving the
    symbol.  If not then it's the offset of the next node in the tree, whose
    data can be read at offset*2 bytes from the start of the string.
    
tools/compress_memory_initializer.py