github.com/invertedtomato/integer-compression
InvertedTomato.Packing is all about encoding data in the smallest possible way quickly. This is super useful for both storage and transmission of data when size and speed are both important. Data isn't compressed, at least not in the traditional sense, rather stored in encoded in efficently manners.
Here's how to squash 24 bytes of data down to 2 using Fibonacci coding:
using InvertedTomato.Packing;
using InvertedTomato.Packing.Codecs.Integers;
// Encode some values...
using var stream = new MemoryStream(); // Could be a FileStream or a NetworkStream
using (var writer = new StreamBitWriter(stream))
{
// Pick a codec - you can use one or many - so long as you decode in the same order you encoded
var fib = new FibonacciIntegerEncoder(writer);
// Encode some values using the Fibonacci codec
fib.EncodeUInt64(1);
fib.EncodeUInt64(2);
fib.EncodeUInt64(3);
}
Console.WriteLine("Compressed data is " + stream.Length + " bytes"); // Output: Now data is 2 bytes
// Decode the values...
stream.Position = 0;
using (var reader = new StreamBitReader(stream))
{
var fib = new FibonacciIntegerDecoder(reader);
// Decode the Fibonacci values
Console.WriteLine(fib.DecodeUInt64()); // Output: 1
Console.WriteLine(fib.DecodeUInt64()); // Output: 2
Console.WriteLine(fib.DecodeUInt64()); // Output: 3
}
Modern PCs have stacks of RAM, so it's usually not a problem that integers take 4-8 bytes each to store in memory. There are times however when this is a problem. For exammple:
In almost all cases those numbers can be stored in a much lower number of bytes. Heck, its possible to store three integers in a single byte.
The example in the TLDR section used the Fibonacci codec. Whilst this codec is excellent for small numbers, it's not so great when numbers get larger. You really need to select a codec with your domain in mind. Following is a summary of the codecs available, their strengths and weaknesses.
Keep in mind that there is a physical minimum possible size for each number. That is displayed in blue.
This is a very interesting algorithm - it encodes the numbers against a Fibonacci sequence. It's the best algorithm in the pack for numbers up to 8,000, It degrades after that point - but not horrendously so. This is my personal favorite algo.
I couldn't find an algorithm which performed well for large integers (>8,000), so this is my own. In it's default configuration it has a flat 6-bits of overhead for each integer, no matter it's size. That makes it excellent if your numbers have a large distribution.
It seems VLQ was originally invented by the designers of MIDI (you know, the old-school MP3). The algorithm is really retro, there's stacks of variations of it's spec and it smells a little musty, but it's awesome! It produces pretty good results for all numbers with a very low CPU overhead.
Similar to VLQ, Inverted-VLQ is a slight variation which uses a final-byte flag, rather than a more-bit flag. Theoretically this has slightly better CPU performance for numbers that encode to more than three bytes.
Elias Omega is a sexy algorithm. It's well thought out and utterly brilliant. But I wouldn't use it. It does well for tiny integers (under 8), but just doesn't cut the mustard for larger values - all other algorithms do better. Sorry Omega :-/.
Like Elias-Omega, this is a very interesting algorithm. However it's only really useful for small integers (less than 8). For bigger numbers it performs terribly.
I have a lot of respect for this algorithm. It's an all-rounder, doing well on small numbers and large alike. If you knew you were mostly going to have small numbers, but you'd have a some larger ones as well, this would be my choice if it weren't for ThompsonAlpha. The algorithm is a little complex, so you might be cautious if you have extreme CPU limitations.
In order to make an accurate assessment of a codec for your purpose, some
algorithms have a method CalculateEncodedBits that allows you to know
how many bits a given value would consume when encoded. I recommend getting a set
of your data and running it through the CalculateEncodedBits methods of a few
algorithms to see which one is best.
If your numbers are unsigned (eg, no negatives), be sure to use unsigned calls to the Codec. That way you'll get the best size reduction. Obviously fall back to signed if you must. Hand-waving, it'll cost you an extra bit or so for each value if you used signed.
There are a few techniques you can use to further increase the reduction of your integers. Following is a summary of each
Smaller numbers use less space. So take a moment to consider what you can do to keep your numbers small. One common technique is to store the difference between numbers instead of the numbers themselves. Consider if you wanted to store the following sequence:
If you converted them to deltas you could instead store:
This sequence uses a stack less bytes!
Naturally this isn't suitable for all contexts. If the receiver has the potential to loose state (eg. UDP transport) you'll have to include a recovery mechanism (eg keyframes), otherwise those deltas become meaningless.
Sometimes it's okay to loose data when encoding. Let's say that you're compressing a list of distances in meters, however you only really care about the distance rounded to the nearest 100 meters. You can save a heap of data by dividing your value by 100 before compressing it, and multiplying it by 100 after.
Sometimes all of your values are always going to be above zero. Let's say that you're storing the number of cars going over a busy bridge each hour. If it's safe to assume there will never be 0 cars you could save some data by subtracting one from your value before encoding and adding one after decoding.
This may seem like a trivial optimization, however with most algorithms it will save you one or two bits per number. If you have several million numbers that really adds up.
So Fibonacci is best for small numbers, and ThompsonAlpha is better for large values - so why not use both? So long as I read it in the same order I wrote it. If you use this cleverly you can get some real size wins.
You thought we were compressing integers already? We'll it depends how you define your terms, but I'd say I was just encoding them more cleverly. But you can compress it as well. Check out BrotliStream. If you wrap your stream in this you can further compress your dataset. While the above encoding stores your data in the most efficent manner, Brotli will then look for patterns in your data to exploit to make it smaller again.
FAQs
Unknown package
Did you know?
Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.
Security News
In this segment of the Risky Business podcast, Feross Aboukhadijeh and Patrick Gray discuss the challenges of tracking malware discovered in open source softare.
Research
Security News
A threat actor's playbook for exploiting the npm ecosystem was exposed on the dark web, detailing how to build a blockchain-powered botnet.
Security News
NVD’s backlog surpasses 20,000 CVEs as analysis slows and NIST announces new system updates to address ongoing delays.