A new lightweight lossless compression scheme

xiasongh — Sat, 19 Aug 2023 04:22:42 +0000

Hi, everyone!

Recently, I’ve been researching lightweight compression and approximate computing in data streams. During this time, I’ve found a simple lightweight compression algorithm. To my knowledge, it hasn’t been proposed before.

Compression is used heavily in databases to improve performance. Lightweight compression algorithms are usually very simple and hardware-friendly. For lightweight compression schemes, there’s a great comprehensive survey by the researchers at TU Dresden.

In short, there aren’t many lightweight compression schemes:

Frame of reference
Delta encoding
Dictionary compression
Run-length encoding
Null suppression

They are all very simple, lightweight, and fast compared to more generic compression algorithms like LZW. Lightweight schemes can even get better compression ratios in some scenarios.

Frame of reference is quite interesting. It was originally proposed to compress database indexes. The claim is that there are cases when the dynamic range of data is quite small. For example, in stocks, we don’t expect to see big changes in a short period of time. We may get something like:

[100, 101, 102, 102, 101, 104, 105]

Using frame of reference compression, we take the minimum value in some block, which will be our “reference”, and then we represent the rest of the numbers as the difference to that reference value. The data will now look like:

[100, 1, 2, 2, 1, 4, 5]

The hope is that the differences to the reference value requires less space to store than the original values (e.g. int64_t to int8_t).

In signal processing and IoT, data volumes are large while IoT devices are small and low-power. To address these issues, approximations can be used.

One class of techniques is piecewise approximation, which segments the data stream and approximates each segment.

Some techniques here include:

Adaptive piecewise constant approximation
Piecewise linear approximation
Discrete wavelet transform

The one I took particular interest in was PLA (piecewise linear approximation). There are fast O(N) algorithms to segment a stream and find an approximation such that the approximation differs no more than a given maximum error threshold. And while the algorithm cannot be vectorized, it is embarrassingly parallel.

Here is an animation that may give some intuition on how it works.

With this info in mind, I came up with a new lightweight compression scheme. It’s so simple that it’s certainly not new.

The algorithm is simple and very straightforward:

Run piecewise linear approximation and set the maximum error to something that will fit in, say, int8_t
Record the differences between the approximation and the actual value, which is guaranteed to fit in int8_t

That’s it! It’s really that simple. There is a little bit of tweaking that needs to be done so that the PLA algorithm can support integers, but that is also quite straightforward. Both compression and decompression is embarrassingly parallel. While compression is not vectorizable, decompression is. It can also be combined with other techniques such as run-length encoding or delta encoding to compress even further.

Thanks for reading!

References

A way to (actually) run Python code in ChatGPT

xiasongh — Sat, 19 Aug 2023 04:14:26 +0000

Hi, everyone!

TL;DR: I made a chrome extension that lets you run Python code and see text and plot outputs in ChatGPT

I’ve never really worked on any personal projects before. Maybe one. I enjoy coding and I think it’s fun, I just don’t do it in my free time. But I wanted to change that, and so I set out to create something. They say the best projects are the ones you will use yourself, so I just went about my regular day, but paying attention to any project ideas that might pop up into my head.

When ChatGPT first came out, I was super amazed by it. One thing I did a lot was tell it to code for me. It’s just much faster than searching through google and stackoverflow.

One thing I noticed was that the way I was using ChatGPT was similar to how I would use Jupyter notebooks. I would have some text describing something, then have a code example. That’s similar to what I do in ChatGPT, have a prompt that describes what I want, then have ChatGPT give a code example. The only thing missing was that I couldn’t run the code. Instead, I would have to copy the code out to something that could.

I wanted to have the full Jupyter notebook experience in ChatGPT. I already had a name in mind, too: JPT. I wanted to combine Jupyter and ChatGPT somehow and that’s what I came up with.

The project isn’t polished at all, but I wanted to quickly release and iterate. And of course, if it isn’t really used, there’s not much point in continuing.

I have most of the core functionality I wanted to include:

Run/edit/copy Python code
See output, plots, and errors
Use a bunch of packages, including your own
Upload and download files

It works quite well. There’s a piece of software called Pyodide that does all the heavy lifting. It’s the CPython interpreter compiled to webassembly, so it can run on the browser. That’s what I meant by actually running Python. The extension doesn’t trick ChatGPT into becoming a Python interpreter or send your code to some code execution server. It runs the code right there in your browser. It’s also what makes it fast.

Again, this is one of my first projects, so I was quite obsessed over it and constantly looking at downloads and just thinking about ideas on how to improve it or get more reach.

It has been a really good learning experience. You get to see the whole product development pipeline after the coding is done. Once I finished coding, I released it out onto the chrome webstore, but obviously I wasn’t going to stop there. I wanted to figure out how to get more people to use it, so I shamelessly tried to make posts about it on reddit and hackernews. It didn’t really gain traction on either platform. It is getting downloads, though, and it has a little over 900 users now. I’ve been trying to figure out how to get the featured badge and how to make the store listing more professional in hopes that it boosts the visibility of the extension.

There’s definitely a lot to learn on this side of the product development world, as I’ve usually just been on the coding side. I’d love to learn more about sales, marketing, product, and design.

I’ve also had a couple of ideas on how to improve the extension:

Make better UI/UX for handling files

Right now the way I handle uploading and download files is atrocious. I’m planning on making a proper UI using the extension popup. When I first released the extension, it wasn’t able to handle files. A few weeks after I released it on the webstore, ChatGPT came out with their code interpreter plugin. I wanted to use that publicity to get some more users, so I felt like I had to be able to handle files since ChatGPT’s plugin could. I coded it in a super hacky way to get it out as soon as possible.
Supporting Claude, Bard, and other ChatGPT competitors

A little bit boring and tedious, but it’s definitely a nice-to-have. It would be great if I could figure out a nice design so that I can hook onto different UIs easily.
Infinite loops will freeze the chrome extension

This is basically a Pyodide and chrome extension thing. Pyodide requires webworkers to be able to interrupt execution and getting webworkers to work on chrome extensions is just annoying. I don’t think this is a deal breaker, but it’s just not great.
Optimizing the MutationObservers to make UI and event handling more robust

Let me explain this last one. I thought it was quite an interesting problem that would be cool to research a bit more. When I intially wrote this extension, I needed to think about how I could inject the UI into ChatGPT’s UI. ChatGPT’s app is dynamic, so I needed to dynamically add the UI onto each of the Python code blocks. The main way to do this is using a MutationObserver. The thing is, I thought the performance of trying to observe the entire application was going to be too poor, so I tried to come up with a more optimized solution, which includes some weird observer directed acyclic graph structure.

This solution sucked for so many reasons:

Premature optimization is the root of all evil

I didn’t even bother to check whether the unoptimized solution was actually bad or I just thought it was bad
The code is hard to read, modify, and reason about
The code is really frail and depends a ton on the exact details of the ChatGPT UI

For example, when ChatGPT changed the regenerate response button from “Regenerate response” to “Regenerate”, my extension broke. Yes, I know. Terrible code.

It’s been really fun working on this project. I’m so much more interested and motivated than in the projects I work on at work or school. I really do feel like I learned a ton and I’m learning more from this project even now. One thing is for sure, I want to keep creating. I’ll continue to work on this or try tackling a new project.

Thanks for reading!

DEV Community: xiasongh

A new lightweight lossless compression scheme

A way to (actually) run Python code in ChatGPT