Around 2001, I found an interesting algorithm that could be useful for several applications. I called it "Recursive Range Reduction" ("3R" for short) and it is described in some depth at http://f-cpu.seul.org/whygee/ddj-3r/ddj-3r_compact.html (EN). It is an encoder, not a transform, which means that it requires correctly pre-processed input data to be efficient (so it is expected that 3R expands "random" data, like most encoders).
This page is a Javascript port of the 3R algorithm that was developed in C in 2003. The first version ("3R") shows the original idea. "3Rpi" is an enhanced version, thanks to Steven Pigeon's suggestion to use "Phase-In" codes : a modest increase in computation complexity gains several bits per block in average. Later (february 2008), I modified the "Phase-In" coder to take into account the "Big Numbers Law" : there are more large numbers than small numbers, so I concluded that the large numbers should use less bits :-) The new encoder is called "3Rpo" (for "Phase-Out", the reverse of "Phase-In" :-D) and a single substration was added to the source, resulting in an average gain of 1 bit (and more with "interesting" data sets).
Sometimes, 3Rpi is shorter than 3Rpo so this page implements a combined version called "3Rpio". The results of 3Rpi and 3Rpo are compared, the shortest result is kept and a bit is added (to signal the decoder which encoder is chosen). You can keep on hitting the "random" button tens or hundreds of times : 3Rpo wins anyway !
Output data (normal) :
Output with phasing-in :
Output with phasing-out :
Legend : Size prefix, Total sum without MSB, Partial sum, Some of the terminal values
Accumulated length
Retour à la page d'accueil de ygdes.com