Disclaimer: I've never actually implemented Huffman compression, but I've read enough about it that I think I would be able to do so.

I was under the impression that, when compressing, the simplest way to store the huffman encoding information is in a table or map. This structure would have an entry for each source symbol, mapping the symbol to a bit length and pattern. To make storing the pattern easier, you usually enforce that patterns can't be longer than a certain length so your pattern entries can be contained in bitfields of the same size, but that's not strictly necessary.

Decompressing, though, probably does need a tree that you can navigate binary search style.

In either case, I'm unaware of any efficient encoding/decoding method that only references the canonical representation. So you definitely need some amount of RAM to allocate for an expanded structure, but it shouldn't be a colossal amount; it should be constant with respect to the number of source symbols.

The best decompression techniques all rely on building a table that you index with your current buffer, giving you the first symbol in the buffer and its size. That may be awkward on z80 though, that table can get pretty big (2 to the power however long you allow your longest symbol to be). There are more advanced techniques that use smaller buffers for that, but they tend to rely on other things that are awkward on z80 (such as bitscan). Or nested tables, but they are intrinsically a pain.

I don't even know where this tree search for encoding is coming from, doing it the normal way is much simpler. That table is only as long as your alphabet is big.

I believe that's the way to build the encoding. But once you've built the tree and saved it in some format to embed in the output, you can scrap it for a much more efficient table/map format, as I described earlier, for the encoding process.

And how to convert from tree to table/map/symbol lengths without searching? Will check up on package-merge later.

Isn't that DFS? I thought Axe didn't support recursion...

I agree, but I still think it'd be a lot cleaner and faster to store the tree backwards (as in edges go from children to parent) and then just parse the contiguous block of leaf nodes sequentially.

EDIT: Just read about package-merge on wikipedia, but unfortunately it looks like it would take up too much memory. 256 symbols * 16 bits max length=4096 coins. In addition i have to do manual memory management for all the merge operations.

I'm currently storing all the subtrees in L1, and keeping frequency data in L2 and pointer data in L6 during compression, then using the normal huffman tree-merge algorithm to pair them up until one is left. Keeping code lengths down to 15 bits would make things simpler, reduce storage overhead while having little to no effect on the compression ratio, but in a 24 kb file it's possible (although somewhat unlikely) to end up with optimal code lengths of more than 15 bits. My idea is to use a bit of package merge to reduce leaf variance and then the huffman algorithm for the rest. What do you think?

For decompression I'll just be building a tree or using sequential search through a 256 entry table.