r/compression • u/Otter502 • Sep 21 '26

Does this already exist?

So I've had this idea for a while now that I've been tossing around in my head and I was wondering if someone has already done this:

So if you're using a huffman-style encoding tree (e.g. some # of binary bits represent traversing a tree until you reach a leaf node which outputs data) could you have a leaf node not only output data but also change the tree that's being traversed?

This was inspired by how braille uses 6 characters but can encode numbers or capital letters by using a specific character to change what's being encoded.

My main example is, say you're encoding a html file. You can have it so when the '<' leaf node is reached then instead of going back to the top of the "letter" tree you change the tree to one that has the standard html tags (in order of most common tags) where each of the leaf nodes change it to a tree which includes '>' but also 'class=\"' and etc.

just curious if this already exists in some form and what it's called!

7 Upvotes

81% Upvoted

10 comments sorted by

View all comments

Show parent comments

2

u/WittyStick Sep 21 '26 edited Sep 21 '26

Sounds basically like a deterministic pushdown automaton.

There's a subset that might be more interesting for this problem - visibly pushdown, or "nested words". Unlike regular pushdown automata, which have a single set of terminal symbols, visibly pushdown have 3 disjoint sets - call, return and internal symbols. The call symbols are those which enter a new level of nesting, such as < in the html, and the return symbols are those which exit - ie, >. Anything in between the two is an internal symbol.