I have written a C# class to perform LZ77 compression ( per RFC 1951 ), to incorporate in my RFC 1951 deflate implementation ( posted on Jan 2 ).
The usual method (per RFC 1951) is to use a 3-byte hash to get started, then iterate through a chain of earlier 3-byte matches. However this can be slow if the chains become long. ZLib has heuristics (which I don't fully understand!) to shorten the search, RFC 1951 suggests "To avoid a worst-case situation, very long hash chains are arbitrarily truncated at a certain length, determined by a run-time parameter."
That all seems a little messy, so I decided to see if a "re-hashing" approach would work : suppose the string ABC is already recorded, and we encounter a new ABC, the new position of ABC will in future be used in preference to the old (position) for coding ABC (as it's "closer") so we re-hash the old position as a 4-byte hash instead. If there is already a matching 4-byte entry, then the lesser position becomes a 5-byte hash, etc.
Example: given input string ABCABCDABC, the hash dictionary updates as follows ( each section delimited by ';' corresponds to the input position advancing by one byte ):
0(ABC); 1(BCA); 2(CAB); 0(ABCA), 3(ABC); 4(BCD); 5(CDA); 6(DAB); 3(ABCD), 7(ABC);
Here's the code:
class Matcher
{
public Matcher ( int n )
{
Hash = new Entry[ n * 5 ]; // A larger table reduces the number of hash collisions, but uses more memory.
}
private const int MinMatch = 3, MaxMatch = 258, MaxDistance = 32768; // RFC 1951 limits.
public int Match( byte [] input, int position, uint hash, out int matchDistance, bool look )
// Record the specified input string starting at position for future matching, and (if look=true)
// look for the longest prior match. hash is a function of MinMatch bytes of input starting at
// position ( can simply be the concatenated bytes ).
{
int matchPosition = InsertLook( input, position, hash, MinMatch );
matchDistance = position - matchPosition;
if ( ! look || matchPosition < 0 || matchDistance > MaxDistance ) return 0;
int match = MinMatch;
int bestMatch = ExtraMatch( input, position, matchPosition, match );
// Look for a match longer than MinMatch.
while ( bestMatch < MaxMatch && position + bestMatch < input.Length )
{
hash += hash * 4 + input[position+match];
match += 1;
matchPosition = Look( input, position, hash, match );
if ( matchPosition < 0 || position - matchPosition > MaxDistance ) break;
int newMatch = ExtraMatch( input, position, matchPosition, match );
if ( newMatch > bestMatch )
{
matchDistance = position - matchPosition;
bestMatch = newMatch;
}
}
return bestMatch;
}
private Entry [] Hash; // The Hash table used to find a matching string.
private class Entry // Alternatively make Hash an array of positions and also store Length and Next in arrays.
{
public int Position, Length; // Position and Length of input substring.
public Entry Next; // To handle hash collisions.
public Entry( int position, int length, Entry next ){ Position = position; Length = length; Next = next; }
}
private int Look( byte[] input, int position, uint hash, int length )
// Look in the hash table for a match of specified length.
{
uint hashindex = hash % (uint) Hash.Length;
for ( Entry e = Hash[ hashindex ]; e != null; e = e.Next )
{
if ( e.Length == length && Equal( input, position, e.Position, length ) ) return e.Position;
}
return -1;
}
private int InsertLook( byte[] input, int position, uint hash, int length )
// Look in the hash table for the specified string, and also insert the specified string into the table.
// If there is a match with an existing string, it's position is returned, and the existing string is re-hashed.
{
uint hashindex = hash % (uint) Hash.Length;
for ( Entry e = Hash[ hashindex ]; e != null; e = e.Next )
{
if ( e.Length == length && Equal( input, position, e.Position, length ) )
{
int result = e.Position;
e.Position = position;
hash += hash * 4 + input[ result + length ];
Rehash( input, result, hash, length + 1 );
return result;
}
}
Hash[ hashindex ] = new Entry( position, length, Hash[ hashindex ] );
return -1;
}
private void Rehash( byte[] input, int position, uint hash, int length )
{
while ( true )
{
uint hashIndex = hash % (uint) Hash.Length;
Entry e = Hash[ hashIndex ];
while ( true )
{
if ( e == null )
{
Hash[ hashIndex ] = new Entry( position, length, Hash[ hashIndex ] );
return;
}
else if ( e.Length == length && Equal( input, position, e.Position, length ) )
{
int eposition = e.Position;
if ( eposition < position ) // The smaller position is rehashed.
{
e.Position = position;
hash += hash * 4 + input[ eposition + length ];
position = eposition;
}
else
{
hash += hash * 4 + input[ position + length ];
}
length += 1;
break;
}
e = e.Next;
}
}
}
private static int ExtraMatch( byte [] input, int p, int q, int match )
{
int limit = input.Length;
if ( limit - p > MaxMatch ) limit = p + MaxMatch;
while ( p + match < limit && input[ p + match ] == input[ q + match ] ) match += 1;
return match;
}
private static bool Equal( byte [] input, int p, int q, int length )
{
for ( int i = 0; i < length; i+=1 ) if ( input[ p + i ] != input[ q + i ] ) return false;
return true;
}
}
ZLib (on default settings) seems to be faster ( although I have not tried to fully optimise my code yet), but at the expense of less compression ( since truncating the search means it doesn't always find the longest LZ77 match ).
For example, my code compresses the file FreeSans.ttf from 264,072 bytes to 146,542 bytes, the ZLib compressed length is 148,324 bytes.
Questions:
(1) What do you think of this approach compared to the 'standard' approach, are there any hidden issues I haven't foreseen?
(2) Re-hashing seems a fairly obvious and natural idea, have you seen it before?
(3) Would using arrays instead of the Entry record be a good idea?
(4) I am thinking of using two hash tables, "sliding" every 16kb of input, to reduce hash collisions when the input is more than 32kb long ( and also reduce memory usage), would that be a good idea?
(5) Any other suggestions?
(6) The algorithm as is performs poorly on long repeats ( for example 1,000 zeros ). How can I fix that? [ This question added later ]
p&qinExtraMatchandEqualok, and maybe theninMatcher;-) \$\endgroup\$