Ko-fi

Showing posts with label data. Show all posts
Showing posts with label data. Show all posts

Wednesday, 20 February 2019

Data folding... yet another compression method

Recently, I wrote about a compression technique I've called "Iteratively Sequenced Data Compression" making magnificent claims about the level of compression it could attain.

I have another compression technique using [spoiler alert!] folded data structures. I'll explain what I mean by that shortly.

For this technique I won't bore you with a back-history of how I got involved in data compression, nor will I make claim to impressive compression ratios because this, currently, is a little more theoretical.

It's important to remember that when it comes to data compression, we don't really care about the data itself. The data itself can go in the trashcan because it's probably too big - after all, that's why we're looking to compress it right?! All we need is to remember is how to reconstruct the data once we're done forgetting about it. That bit is really important. So important in fact, it deserves a line of its own.

Forget the data; just remember how to reconstruct it.

So, with that in mind, what do I mean by folded data structures?



Imagine you have your data in one nice long strip. Easy enough.

Now imagine you start wrapping that data into rows, essentially like word-wrap on your fave text editor. Also easy.

Okay, so now imagine you had that data printed out on a piece of paper. Also not difficult to imagine.

Hold tight folks, here's where it starts to get a little more tricky.

Now look for a way of folding that piece of paper such that you align common values and drive a skewer through the paper to hold all those matched values in one place.

Let's further imagine you tried folding that piece of paper many different ways until you landed on the optimal folds to get the maximum continuous strip of values on your skewer.

Remember the value you skewered and the folding pattern. That's your first folded data item.

You can forget about that chunk of data now, so go ahead and erase all the data you just skewered from your piece of paper.

Go ahead and repeat this process of finding the optimal fold; remember the value and the folding pattern. That's your second folded data item. Forget the data you just skewered from the page.

Do it again. That's your third. Keep repeating this until you have skewered all your data.

You will find that as you reduce the data by skewering it off the page, your folding patterns become easier to spot, and less complex, so the process becomes faster the more you work through the page.

Once you've got all your folded data items, simply concatenate them and pop them in a small file.

Easy!

All you've had to remember is the skewered value and the folding pattern; which can then be unfolded back out all the way back out to that continuous stream of data that you started with.

So what this technique effectively does is allow you to do run-length-encoding across a landscape of data that, as a continuous strip, could not make the best use of high run lengths; which is therefore sub-optimal. By folding (or crinkling) the data in the right way, you can maximise your run-lengths to get highly effective compression.

Hypothesis:

  • Compression will be intensive and slow, whereas decompression will be fast.
  • Splicing byte values to enable layering of data prior to folding would improve compression and performance.
  • The compression method could be iterative to produce progressively smaller content.
Concept (c) 2019 letsbuildathing.com

Friday, 15 February 2019

Iteratively Sequenced Data Compression

I first came across data compression back in the 1980s, some 5 or 6 years after first being awestruck by this thing called a computer.

At the time I was very young, and these computer things were new - and, by all accounts, a pretty big deal. I was fortunate enough to have one at home that I shared with my brother. It was a BBC Micro Model-B from Acorn Computers. Go Acorn!

It was awesome.

This thing was competing with a trusty BMX, He-Man, haunted house exploring, and lots of shenanigans. So it really did have to be awesome to get a look in.

It had 8K of memory. Eight freaking K. An unimaginably large number of transistors that you couldn't dream of filling! Right? Well, no. It turns out that you run out of 8K memory pretty fast... even back in the day.

Back then I was writing 6502 assembly language, dabbling in the 8-bit games industry, designing graphics on graph paper with a pencil (until I wrote a frickin' nifty sprite editor), and maps, because dammit, I was a games programmer! High school and night classes at college were just a necessary pastime. Game programming. That was going to be my life.

And then in 1988 Superior Software brought out an amazing new game called Exile. It was literally a game changer - no pun intended. It was a great game, with many hours and fond memories with buddies spent trying to get to the end of it. I believe it was the first, or one of the first games, that sported an early physics engine... gravity and inertia at least. It was amazing. The graphics were, by 8-bit 8-colour standards, intricate and plentiful. The map was huge. It broke so many rules of what was possible.

All of that was, of course, fascinating and made for a great game.

Only I like to learn and tinker. So tinker and learn I did.

One of the claims that this game made was around the size of the graphics, the size of the sound, and the map. The numbers were staggering - significantly more than 8K!

Whoa!?

How does that work, I thought. It won't fit.


I pondered.

I reached out to friends.

We pondered together.

It did not make sense.

Back then, there was no Internet. There was not an endless amount of resources, or of people doing this stuff to reach out to, especially not outside of universities.

So I took to doing what I would always do in these scenarios. Take it apart. Take a look. Figure out what the hell was going on.

I was pretty resourceful when it came to getting into computers and code, and by this time I was a dab hand at reading machine code; not just assembly language, I mean actual hexadecimal compiled code and understanding exactly what it was up to - often printed out on reams of dot matrix printer paper that I would read travelling about in the back of my parents awesome Rover 2600. Pretty geeky. To be fair, 6502 machine code was a hell of a lot more simple compared to today's machine code, and you had to know it back then to figure out clock cycles and see where you could save the odd millisecond.

Anyway, the point is, Superior Software got all of this content that was bigger than the thing it was going in to by using compression. I genuinely agonized for some time how a bit would get smaller than a one or a zero, came to the conclusion it couldn't, so went to the byte level, and I was still stuck. So then I did some tinkering. You may choose to call it hacking. Whatevs. That, along with talking it through with a buddy, came up with the realisation of what is now known as RLE; run-length encoding.

It's a very basic compression technique whereby you don't store the data itself, rather, you store the pattern of data.

Mindblown.

You don't store the data.

Mind. Blown.

These days it's unbelievably obvious of course and a very basic algo.

Data is quite often a series of the same value, particularly in graphics, maps, and sound. So for example, instead of storing 28 zero's for a strip of black in your image, you store the number 28, followed by the number 0. Then your code decompresses it by reading the 28, 0, and expands it back out to 28 occurrences of 0. The thing is, you only stored two bytes (the 28 and the 0) instead of 28 bytes (28 consecutive 0's). So if you do that across your entire set of graphics, sound, and map data, you get something big into a smaller space.

Easy.

Or rather, easy when you know how.

So... that's a very long intro to a possible new compression technique that, I hasten to add, would make a pretty neat TED talk intro. The important part to take away is this...

You don't store the data.

So I've concluded that if we don't care about the data, and we're never truly going to store the data, and we want lossless compression, well then, let's not even go down that path. Let's not figure out clever algorithms to look at data in different ways - for example looking in cubic data not strips of data; losing quality by deciding on a loss factor and figuring out if the value is "close enough" for the loss, or breaking graphical data into meaningful slices, e.g. filter the red component of the RGB values, compress, then do green, and so on and so forth... there are many techniques.

Here's the thing...

All we need is an established public library of bit sequences.

I've long held the belief that every image, and indeed every sound, can be generated through tedious incremental change; therefore all the patterns of data already exist.

To that point; all data that will exist already exists.

Don't dwell on that, just run with it and maybe I will write about that some other time.

To record massive data sets as single sequences would be borderline silly because of the indexing time required. So we break the full data set into sensible, optimised, chunks. Then we simply index them against our established public sequence library. We do not store the sequence library itself because they are established public sequences, and remember; we do not store the data.

Then you repeat the process on your newly generated sequence because there will be a public library sequence for that too. You continue to repeat the process until you have an incredibly tiny amount of metadata where all you need to store is the iteration depth and the sequence numbers starting with the seed sequence. Decompression would be the reverse process.

The resulting compressed data only ever consists of metadata to describe what the data was when it did exist.

The public sequence library would contain multiple sequence lengths, so you would check your data size, compare it to the library length that best fits, and as you iterate and compress you step back to the next smallest size until you run out of practical compression.

So depending upon the chunk size for the sequences, a multi-gigabyte file could easily be compressed to a few kilobytes at most, possibly even bytes.

Imagine being able to download an entire UHD film in mere seconds over the crappiest of narrow bandwidth, and saving a decade's worth of images on a tiny drive.

That would be awesome.




Concept (c) 2019 letsbuildathing.com