Lz77 Hash Tables: Alternative?

Hi! I successfully debugged one of my compression techniques several times recently, but each time, the compression ratio was poor. I believe it's because I was using MTF without anything else and hash tables for LZ77. I got another technique to do very well, but when I applied hash tables to its LZ77, I lost big points with its compressibility. Worse yet, it cost well over 8k for its table, and I'm coding for 8-bit systems, where memory is at a premium. I'm looking for a better way that requires much less RAM and produces much better results. It can be slightly slower. Any suggestions?

BTW, I want to implement BWT and a better form of BPE. I'm currently using a method of BPE that acts like LZ77 and compresses very recent occurrences better. I really think I should use a form of tokenization there and compress the most often-occurring words better but need a more efficient method to do so. Any ideas?

 

I'm creating my own compression technique, but it's very slow. I'm asking for help to make it faster. LZ77 is one of the compression techniques I'm using, and you can find more information on it on wikipedia. Hash tables are a technique suggested to me a long time ago to optimize LZ77 but produce bad results. Does this help?

 

Ask Google AI -
For 8-bit environments where memory is at a premium, you can drastically reduce RAM usage and improve compression by moving to offline compression (compressing on a PC and decompressing on the 8-bit system), or by replacing large hash tables with a chained rolling hash or a fixed-size sliding window with a small look-back buffer. If you need to compress directly on the 8-bit hardware, limiting your history window to 256 bytes allows you to use single-byte pointers, shrinking your table overhead to a fraction of your current 8KB. [1]

1. Ultra-Low RAM LZ77 Strategies

• Offline Compression (The 8-Bit Gold Standard): If your target system only needs to decompress data, use an offline tool on a PC like ZX7 by Einar Saukas or Salvador. The PC handles the heavy, slow math, while the 8-bit system runs a tiny assembly decompressor (often under 100 bytes) requiring zero extra RAM besides your input/output buffers. [1]
• Chained Index with a 256-Byte Window: If you must compress on-device, reduce your window to 256 bytes. Because the window is small, your offsets fit into a single byte. A hash table with 64 or 128 buckets pointing to 1-byte heads, paired with a 1-byte "next" chain table, will drop your RAM footprint to under 256 bytes total.
• Optimal Parsing: To get better compression without expanding RAM, replace a greedy search with lazy evaluation (checking if a match starting at the next byte is longer than the current match). It is slightly slower but yields a much tighter compression ratio. [1]

2. Implementing BWT on 8-Bit
The Burrows-Wheeler Transform (BWT) is highly effective but famously memory-hungry because it requires sorting blocks of data. [1]

• Restrict Block Sizes to 256 Bytes: Do not try to use large 4KB or 900KB blocks standard on PCs. If you limit your BWT block size to exactly 256 bytes, every index in your suffix array fits into a single 8-bit register (like the X/Y registers on a 6502 or B/C on a Z80).
• In-Place Sorting: You can sort a 256-byte block using a lightweight insertion sort or counting sort. This requires only a 256-byte index array of RAM, and the resulting stream will be perfectly set up for your Move-to-Front (MTF) stage. [1]

3. Efficient BPE and Word Tokenization
Your current BPE method mimics LZ77 because it relies on dynamic, recent occurrences. For an 8-bit system, a static vocabulary approach is significantly more efficient:

Method RAM Cost Best Use Case How it Works
Static Digraph Coding 0 bytes (ROM only) Text and code Pre-calculate the 128 most common byte pairs (or words) on a PC. Assign them to unused byte values (e.g., 128–255). Decompression is a fast ROM table lookup.
Z-Machine Style Tokenization ~50–100 bytes Text-heavy data Used by classic Infocom text adventures. Pack text into fixed 5-bit character codes and maintain a small, high-frequency word table in ROM referenced by brief shift tokens.
Huffman-Coded Tokens < 256 bytes High-entropy streams Instead of a full byte-pair tree, run a fixed Huffman or Shannon-Fano tree over a hybrid alphabet of characters and pre-defined common words.

To help tailor the exact code architecture, could you let me know:

• Which 8-bit processor are you targeting (e.g., Z80, 6502, 8051)?
• Does the 8-bit system need to compress data in real-time, or is it only decompressing pre-packaged data?
• What type of data are you primarily trying to compress (text, graphics, binary code)?