Name says it all! ;)
© 2001 by Alain Brobecker (aka baah/Arm's Tech)

LouZy77 & LouZy77D are compression algorithms, a bit slow and giving average compression ratios (better than Huffman though), but the coders and decoder are very simple, have small memory needs (except for LouZy77D coder) and the decoder is very small & fast.

0. Introduction
1. LouZy77 packer & depacker
2. Optimality problem: Dijkstra algorithm
3. Results

Download LouZy77.zip with sources (C+Archimedes packer, ARM, 6502, 68000 depacker).

0. Introduction

While working on a simple Run Length Encoding pre-compressor, where ABCCCC is coded NoRept(2;AB)+Rept(4;C), i devised another way of coding the repetition of bytes: NoPk(3;ABC)+Copy(3;-1) with Copy(3;-1) meaning copy 3 bytes from current position-1 to current position.

In this example, and in all pure RLE cases, this new method will require more bytes to code the stream, but the depacker will remain as simple and fast as for RLE, and the method allows references to previously depacked strings as in dictionnary based compression (LZ77).

ABCDABCD will be packed as NoPk(4;ABCD)+Copy(4;-4)

This method is almost original, meaning i had already heard about dictionnary compression before, but i had only seen LZ78 algorithms which are far different and i made the first tries before looking in the litterature for exact references. I was pleased to learn it is in fact a LZ77 variation.

1. LouZy77 compressor & decompressor

For each byte in the source file and for every possible offset, the encoder searches for the longest string which matches the characters to come.

No compression at all: dest must contain SrcLen+INT(SrcLen/MaxNbNoPk)+1 bytes.File format:

       0 : End
  1..127 : NbNoPk followed with NbNoPk bytes
128..256 : NbCopy+128-Min followed by Offset-1

2. Optimality problem: Dijkstra algorithm

The greedy parsing technique used above is not always optimal.

3. Results

typesizeziphuffmanlz77+hufflz77d+huff
Nine img789043729557674615205250161125
Pulse0 img661041255524058186361615718534
enchlandst 8738 2070 4481 2620 2391 2605
ReadMe txt 7772 3292 4771 5199 4489 5150
SockZ arm 7308 3519 5556 4746 4272 4722
AngieSuXc64 5786 2634 3550 3333 3136 3292
lz77 bas 4703 2400 3587 3371 3131 3353
atari3k5prg 4697 2586 4221 3324 3261 3318
MrGland img 4672 1998 2790 2671 2404 2640
permute c 2119 697 1225 949 948 941
paranoidarm 1095 813 1093 883 954 880
adressestxt 1059 689 795 951 865 948