Fibonacci Coding | Hacker News Reader

Fibonacci Coding

en.wikipedia.org

61 pointscinquemb27 comments

I found the section above the linked one (Comparison with other universal codes) most interesting:

> Fibonacci coding has a useful property that sometimes makes it attractive in comparison to other universal codes: it is an example of a self-synchronizing code, making it easier to recover data from a damaged stream.

Cool. It’s like it has its own embedded clock pulses. Very nice.

A more familiar example of a self-synchronizing (but non-universal) code is UTF-8, which guarantees that if you start decoding a bytestream in the middle of a codepoint, it's trivial to find the next codepoint boundary because initial bytes always start with either 0 or 11, and continuation bytes always start with 10.

Just to make sure I understand, this assumes that you start decoding at the beginning of a byte, not halfway through a byte, correct?

Yes, the structure could still help resync if you have a bitstream and not a bytestream (you could identify the MSBs of bytes from their very different statistical behavior), but it isn't as trivial as skipping continuation bytes, those with '10' in the most significant position. You'd need to track all 8 shift positions until you find the one that looks like UTF-8.

Holy crap I did not know that and always thought it must be such a pain to decode variable-length text! How did I go so long without knowing this, that's such a neat feature.

A card trick based on this, and I also find the high level explanation more clear than Wikipedia's:

http://teachersofindia.org/en/article/fibonacci-coding-and-c...

Yes,! this was in my mind and I'm trying to apply the same technique.

Here is a backstory. I'm a UI developer and I code to build UI, question that came to me, why not build an UI that builds the UI?

It's an IDE or a design tool. I tried it, built it, https://github.com/imvetri/ui-editor. but I wasn't really not convinced. why? A problem is solved only when solved recursively.

I did solve it recursively - I built an UI to build an UI, however I wanted to take to next step.

I'm trying to reduce code and include more interactions. I'm really not sure how to build a true UI that can build UI, but Fibonacci series or other growing functions that is solved recursively is my inspiration.

How to apply that to building User interfaces ?

Everything is a rectangle. A rectangle can have children rectangles. A rectangle can have sibling rectangle. A parent rectangle can create children rectangle. A parent can delete child rectangle. A rectangle can edit itself. hahaha

A parent rectangle can edit itself to create more children.

So I need one rectangle hardcoded that can create more children, and can edit itself

And I have solved that too - https://vimeo.com/464104903.

TDLR: I work on a side project to bring all frameworks under one hood (by targeted code generation to different framework with single source of truth. It is tested well for reactJS). I still want to work on it on everyday basis, but couldn't find the time I had 3 years back. However I'll be glad to set some time to guide someone if they are interested to contribute.

I know mathematicians don't like this question, but: Why?

It's a binary comma code (https://en.wikipedia.org/wiki/Comma_code) for integers. If it didn't exist someone would invent it. The implication of Fibonacci numbers isn't arbitrary, it's because Zeckendorf representation is the neatest way to do the job.

I'm looking at different ways to compress a list of integers, came across [0] and this seems to work best [1] for small ints that I'm working with.

[0] https://github.com/invertedtomato/integer-compression

[1] https://raw.githubusercontent.com/invertedtomato/integer-com...

You can improve on this by quite a bit by not writing literal bits to the file, but instead feeding them through an arithmetic or range coder, with some reasonable statistical model. The statistical model can be very simple, even just an exponential moving average per digit will help.

Yeah, it seems like going with some of solutions listed here[0][1] work pretty well after passing the binary through (better when not passing through fib coding, but mapping most of the ints to characters and compressing them).

Still trying to explore though.

[0] https://en.wikipedia.org/wiki/Dynamic_Markov_compression

[1] http://mattmahoney.net/dc/text.html#1263

No, just keep the fibonacci coding, or whatever code, just feed to output bits from that coder through a simple statistical model and then into a range coder.

Here's how LZMA does it, for instance: https://en.wikipedia.org/wiki/Lempel–Ziv–Markov_chain_algori...

Ok I think I misunderstood you if passing it through something like DMC is not what you mean.

So I have some fibonacci encoded binary blob[0] (uint8_t for each byte), is there some kind of pseudocode example you could share of how I would pass each bit from the file through the a statistical model (like for exponential moving average, I'm not sure what to do with each bit I iterate over or how to store it after it would pass through from what you are trying to explain to me)?

[0] https://gist.github.com/cinquemb/94168c02da2a30b269cc5baef8c...

You should do it all in one go while processing the data, because you want to use the context you have during the encoding process to build your statistical model. The simplest version is, keep an array of exponential moving averages of the bit value for digits 1...N of each code, and use those as the probabilities for the range coder.

Ok, so as I iterate over the data and generate an fibonacci code, i:

- compute the ema for each code

- store the ema by mapping that code to a given ema value at the step during iteration

- encode that code to the file based on the algo here [0]

How much more efficient at compression would this be by actually getting the probabilities first rather than updating it on the fly (one full iteration over the non fibonacci codes to compute the exact probability, then again for actually passing it thru the range coder)? Or is this something that i'll just have to play around with?

[0] https://en.wikipedia.org/wiki/Range_encoding#Example

It is the EMA for each digit, rather than each code. So you have one EMA for all the first digits of all the codes, one for all the second digits, and so on.

You can then make it more intelligent by having even more different EMAs and picking between them in some more intelligent way than just by digit. By digit is just the easiest option.

Precalculating the probabilities may or may not be more efficient. You lose a tiny bit of efficiency because you have to include the probabilities at the start of the file rather than being able to re-calculate them when decompressing, but if they are very static you may gain a bit of efficiency. However, if the probabilities change throughout the file, the dynamic version again gains the upper hand since it can adapt to changing data. How quickly you let the EMA change also affects this.

> It is the EMA for each digit, rather than each code. So you have one EMA for all the first digits of all the codes, one for all the second digits, and so on.

> You can then make it more intelligent by having even more different EMAs and picking between them in some more intelligent way than just by digit. By digit is just the easiest option.

Ok cool, so if I'm using uint8_t, ill have an ema for each of the 8 bits. And yeah, I'll start with the easiet just so I can nail the implementation then try playing around with different emas if i'm not satisfied with it (right now I can turn 29kb to 5kb with paq8fthis2 compared to 12kb with snappy, so hopefully using something like this will make it go lower).

> However, if the probabilities change throughout the file, the dynamic version again gains the upper hand since it can adapt to changing data. How quickly you let the EMA change also affects this.

Yeah, I suspect this to likely be true. I'll need to probably play around with the ema weights to see how that will change things.

Thanks for helping me understand this all! I started out trying to compress the data by representing as a matrix with fewer # row operations to get back to the original, then ended up having to deal with it traditionally… lol

Universal codes are used in compression file formats to store integers efficiently when most values are small, but you still want to support arbitrarily large numbers.

These days, they would usually be combined with an arithmetic or range coder to store each binary digit more efficiently than just writing it directly to the file.

Is there a similar scheme using primes?

Similar but not totally analogous https://oeis.org/wiki/Primorial_numeral_system

This made me think of Gödel Numbering¹, which was used in the plot of "The Gold at the Starbow's End" by Frederick Pohl²

1) https://en.wikipedia.org/wiki/G%C3%B6del_numbering

2) https://en.wikipedia.org/wiki/The_Gold_at_the_Starbow's_End

If the Goldbach conjecture is true, such a scheme would be all zeros except in up two places, as long as the integer you want to encode is even. Even if the conjecture is true, the code must be ternary: to encode 6 you need to indicate 3 twice, as 6 = 3 + 3.

However, very many even integers are the total of more than one pair of primes. So, the encoding of a number using this scheme is not unique.

In contrast, because of the property F_n = F_{n-1} + F_{n-2} you never need more any Fibonacci number more than once in the code, so the code is binary (and the encoding unique).

I think past me would have thought this was cool. Now I'm just annoyed about having to think about this.

Good news! You don't have to think about this.

I know how you feel. Burnout is a real thing. I hope you heal and find the energy to enjoy things like this again.

Reply on news.ycombinator.com