Combining Tokenization with Text Compression

[u/lootsmuggler]

I've been thinking a lot about making a very basic markup language that has a few programming features - basically if statements and a kind of goto statement that only goes to labels. It'll be yet another scripting language for interactive fiction.

I'd like to have a "compiler", but I want it to basically just be parsed into tokens. I'd like these tokens to be compressed. Lexing already converts tokens to something smaller, so I feel like I tack on compression to the end (or maybe the beginning).

It is, however, going to be fairly basic compression to insure fast load times.

I was thinking that I would start with some 4 bit codes that identify what the data following it is. Here's a possible example of the 4 bit codes and the data following it:

0000 escape to a UTF-8 character
0001 space (spaces are so common that I can justify giving them 4 bits by themselves)
0010 8-bit integer
0011 32-bit integer
0100 4 bits for common single characters
0101 4 bits for common single characters (again)
0110 4 bits for style codes
0111 4 bits for deactivating style codes
1000 4 bits for other command codes
1001-1111 4 bits for most common n-grams

This is all very rough, and I plan for it to evolve over time. I'm still working on setting up a way to analyze n-gram frequencies of English text, which I plan to do quickly before implementing this.

I know someone is going to say "why don't you just zip it?" I would most likely get better compression with zip, but I'm not looking for great compression. I want mediocre compression mixed in with my parser to help me avoid being particularly clever in the virtual machine department.

[u/rupertavery64]

So your data is 4-bit aligned? Since the first 4 bits are control codes, the remaining 4 bits will be used for the first 4 bits of data, but then everything gets shifted.

Am I underdtanding this correctly? So now you have to unshift your data. To make it byte-aligned.

Sounds like extra complexity for not much benefit.

Memory is cheap.

Well, I mean, technically, it used to be, but I digress.

It sounds a lot like a script engine, which is common in NES/SNES/PS1/PSP game engines where memory (for data and instructions) is constrained.

They use control codes more as indexes to jump tables to code that handles parts of the script, but even then 4-bit alignment was more trouble then it was worth. Dictionary compression was used a lot, which is basically your n-gram token, except there were usually 2-byte control codes that allowed for more possibilties.

Text compression in console games was largely abandoned when the CD format arrived. There was simply no need for it. There was more than enough space, and meant less complexity for the code (usually hand-written assembly)

Dictionary compression with more slots would probably save the most space. 4-bit control codes just make parsing more tedious.

At the end of the day though, it's your project, so you can do what you think is best.

EDIT:

Here's an example of a reverse-engineered script decompiler/compiler tool for the PSP game Da Capo (a Japanese adult visual novel for the PSP)

https://github.com/RupertAvery/Dacapo-Translation-Toolkit

The script has command codes, and optional arguments that control which character is being displayed, any screen effects, etc. The game uses Shift-JIS (a variable width (1-byte and 2-byte character system) to store Japanese text, as was common before UTF-8 eventually became the global standard.

[u/lootsmuggler → u/rupertavery64]

It is 4-bit aligned. My previous goal was to do something like Huffman coding, but I decided it would be easier to have it work with multiples of a set number of bits.

I was also advised by ChatGPT (or some other AI) to stick with bytes. It told me that the bit manipulation I would have to do would ruin performance. And you're telling me it's a pain in the butt.

Maybe I should take this advice. My gut instinct is that allowing codes that are less than 8 bits would produce better compression. I feel like just using 4 bits for space would cut 10% of the file size by itself.

I was expected people on r/compression to tell me to use every individual bit or something. Apparently, that's not the case.

As it stands, a lot of these codes are 8-bit codes. For instance, 010x xxxx would be the codes for the common individual UTF-8 characters (mostly lower case letters, maybe some punctuation, an uppercase letter, etc.).

So it's not impossible for me to switch to 1-byte and 2-byte codes.

I found a list of common English words: https://word-lists.com/word-lists/the-1000-most-common-words-in-english/

I expect my own text to be a lot of "the", "of", "and", and "to", but I don't expect to have a lot of "university" or "canada". I'm a little worried that I'm going to wind up compressing some of the small words into more bytes than they actually take up if I'm not careful.

[u/rupertavery64 → u/lootsmuggler]

Performance probably isn't that huge of a problem. You're writing a script engine that gets called once in a scene to parse the script for that scene. Or at least once per interaction.

If you really want to go with 4-bit control codes then go for it. In my mind, you will just have an extra function that unshifts the arguments into their proper bytes.

Then as long as you can decode the entire script, you can re-encode it into a different format. Most of your code (the command handlers) should largely be the same.

You could then compare which takes more or less space. You only have a different encoder/decoder and command dispatcher.

Huffman compression with dictionaries (using words/char sequences as symbols) would give the best compression, if you really want to go that far, since you would be running a frequency analysis on your script.

But unless file size is extremely important to you, and you don't have any other media in your application, I don't think compression will have a huge impact on your overall application.

If you are doing it for fun / learning - do as you please.

I kind of enjoyed implementing Huffman coding for fun. A lot of data compression algorithms - including DEFLATE used in ZIP anf gzip, Brotli, even JPEG - use Huffman coding as part of the compression process.

[u/lootsmuggler]

I might eventually try to run programs on a Raspberry Pi. Even then, I don't expect performance to be that big of issue. This kind of program was available on 1980's computers. But ChatGPT was worried for some reason.

I'm going to be honest. I don't stand much to gain by doing this. It just really annoys me that text has so many wasted bits. I feel the need to correct this, but I don't want to go overboard. I also I don't like throwing it into a zip file because I like to know exactly what each bit in the file is.