Compressing a list of records so it can be uncompressed elementwise [closed]

Question

I have a bunch of lists of generic items (byte sequences) and I would like to store them compressed. There are several tools out there that run on modern computers to compress data into as-small-as-possible representation with a quick(-ish) Z80 uncompressor. However, I don't have enough space on my target machine to uncompress the whole list; instead, I am looking for a compression scheme that can uncompress just a single given element of a list.

So basically, imagine I have the following byte data:

1. 00 01 02 03 04 05
2. 06 07 08
3. 09 0a 0b 0c 0d

And I would like to store it compressed so that I can uncompress just 06 07 08 for index #2, without using memory for the other 11 bytes.

Are there any existing compression implementations that can support this use case?

A couple more information that might be relevant:

1. I have several lists, but there's not going to be much redundancy between the lists so compressing each whole list separately is OK.
2. There's huge amount of redundancy between elements of the same list, so compressing each item separately would make no sense.
3. Each item is about 10-100 bytes. Each list is "jagged", i.e. the items are different length.
4. The lists are 100-200 items long.
5. The largest list's total size is 8K

Using ZX0, for example, my largest list, stored flattened with a special separator byte between items, takes 8779 bytes uncompressed and 3479 bytes compressed. But of course with ZX0, I can't then uncompress only a single list item, and I don't have an extra 8779 bytes of RAM.

Answer 1

Compression isn't really retrocomputing-related, but I'll give it a crack anyway as there are a few tricks which work on small systems.

Essentially, you want to compress a large-ish (100–200) list of small strings (10–100B) with a total size of ~8kB (never mind that 200x100B is ~2kB) and be able to decompress each string independently, but still take advantage of the fact that there is redundancy between the strings.

I think the best solution is probably Huffman coding: build the frequency table for the entire list, and then compress each string with that table. You will also need to have a table mapping indices to each compressed string and its length, but you already needed to do that because of your jagged array. Actually, since Huffman-compressed data is in the same order as the input and each byte is compressed independently into a variable-length bit sequence, it is possible to take a substring of the compressed data and decompress it into a substring of the output, but your pointers into the compressed data must contain the bit offset. Since this adds 3 bits to your pointers and only saves an average of 4 bits per string, the marginal savings might not be worth it.

Although the Huffman table itself is accessed randomly and will need to be entirely in RAM, the (de)compression is a streaming operation so only a very small window (a byte or two) of the compressed and decompressed data needs to be in RAM. On the other hand, you probably are just decompressing into a buffer in RAM, and probably also have the luxury of having hundreds of bytes of RAM for temporary workspace, so there are a couple of extra tricks which should improve the compression ratio and are still fairly cheap on a Z80:

• The Burrows–Wheeler transform. This is the main secret sauce of the bzip2 compressor. It is actually quite a memory hog for large bits of data and used to bring my old 486 to its knees, but for strings shorter than 256 bytes the transformation table is the same size as the input and that's actually reasonable even on a Z80. The BWT will tend to increase the number of repeated bytes in the output.
• Move-to-front transformation which tends to turn a compressible string into small integers in a somewhat logarithmic distribution; repeated bytes such as the output of BWT turn into runs of zeroes. This is simple and fun to write on an 8-bit. You'll need 256 bytes for the transformation table. (I did a 6502 version in about 50 bytes.)

Further, a run-length encoding step is worth trying, because the output of BWT and/or MTF will tend to contain a lot of repeated bytes, particularly zeroes. Indeed, you might at this point find that the compression ratio is already good enough for your purposes that adding a Huffman table doesn't really win anything overall.

As a final tip, if you're combining RLE and Huffman, you should use the (length, byte)-tuples from the RLE as the input symbols to the Huffman coder rather than flattening those tuples into bytes and compressing those. Since you're on Z80, you'll probably just arrange for that tuple to be a 16-bit value which, when loaded into BC, can fall into a DJNZ loop which writes B copies of C to (HL).

Note that BWT and MTF do not actually compress data themselves but merely make it easier to compress with a "proper" compressor such as RLE or Huffman.

Answer 2

[I'm not really sure that this is a RC.SE related question at all, as it asks for a basic strategy independent of technology. Will vote for getting it moved.]

There are only two basic strategies to solve this:

a) Compress List as One Blob - Decompress Partitially Virtual

The whole data structure (all data/list elements) gets compressed including list management (pointers/length delimiters/stop words/etc.) as one item.

To access a data item decoding starts with the whole blob, but the decoder does not write resulting data to memory, but hands every byte to the list interpreter (*1) which will interpret list management information until the right sub block comes along. Only after that all data will be written to memory (*2. That function will return with some condition code telling the decompressor to continue or quit - the later as soon as the end of that list element is reached.

Going this way so splits decompressing into three phased

• Virtual decompressing all data before the desired entry
• Real decompression of the entry
• Virtual decompression afterwards (aka doing noting :))

There are a few advantages and some quite important disadvantages:

Pro:

• Possibly highest compression ration (depending on method and data)
• Use of rather standard tools for creation of the blog

Contra:

• List structure must support streaming access (no back or forward referenced access)
• Decoding Software must be (re-)written to support a callback instead of memory write
• High variation of access time
• Later items will have considerable higher access time
• High over all processing time

b) Compress/Decompress Each Item On Its Own

Here each list item is compressed on it's own and then put into the list structure. For decompression each item will be decompressed directly on it's own.

Pro:

• Standard tools (functions) can be used to decode each element
• Finding an item is is a basic memory access
• Access time is (almost) independent of position
• Only the data item requested needs to be decoded.
• Decoding is as fast as possible
• High flexibility for item handling

Con:

• Creation of the data structure may need additional tools/code
• Compression may be less effective
• Worst case compressed ata may be longer than uncompressed

The later is quite depended on compression method and data structure. A directory based compression will yield dismal results, while algorithmic compression may not show any difference. Likewise limited value range data (like Text) may show better results than binary data. While both are common place knowledge for compression, they do have more influence on smaller data chunks.

The item based approach does offer a high degree of flexibility as each entry can be handled different. A flag may note for example if an entry is compressed at all - like for short entries or such where compression isn't effective at all due their random nature. It could also note the use of specific compression methods depending on data type.

In fact, content specific compression may produce a way more desirable result than a generic method, especially with limited resources of memory and CPU. Just think of the good old ZSCII compression. Similar can easy be done for certain value fields and may result in shorter forms than generic compression (*3).

---

*1 - Like calling a list input function (callback) with that byte in A.

*2 - Or forwarded it using a callback to whoever needs that data - doing so might a lot faster if that data needs to be interpreted only once.

*3 - In some way this can be seen as turning a data based dictionary into a code based one. A gain is made if the resulting code is shorter than the dictionary otherwise added.

Answer 3

Using a specific method that works only for the exact data you posted.

The short example given:

• Looks to be contiguous sequences which can be generated from a start # and value count
• values 0 to 65535 (two bytes)
• number of values to generate is <255 (one byte)

Can be done with 3 bytes per 'sequence': 2 bytes start value and 1 byte of how many values to generate. Easily indexed off sequence number.

0 6  ; starting at 0 output 6 values
6 3  ; starting at 6 output 3 values
9 5  ; starting at 9 output 5 values    
...

Guessing your actual data isn't this uniform. Still similar or related techniques to store/generate your actual data probably exist that can beat generic algorithms.