RFC 1951 compression LZ77 re-hashing approach

Question

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 ]

Answer 1

I apologize in advance that this answer does not contribute much to the actual functions of your code; However, I firmly believe that writing code that is easy for others to read/understand is an important element of feedback from any code review.

At first glance, I would note that there can be a little bit more adherence to C# Coding Conventions.

(Aside) I admit it is a bit of a discipline thing (think of setting a table for dinner... The fork and knife shouldn't be upside down with the handles faced away from the diner -- it's not functionally "wrong" but you'll get a weird face from people when they find out you were responsible -- it doesn't conform to conventions).

In particular here are a few bits that standout the most to me:

Exessive spacing.
Your "excessive" spacing (really just one too many)
makes the code a l i t t l e h a r d e r t o r e a d.

For example:

public Matcher ( int n )
public int Match( byte [] input, int position, uint hash, out int matchDistance, bool look )

Should look more like this:

public Matcher(int n)
public int Match(byte[] input, int position, uint hash, out int matchDistance, bool look)

Proper case and underscore for your private fields
Here we have a private field called Hash

private Entry [] Hash;

Which according to naming conventions should be

private readonly Entry[] _hash; // note the underscore and lower case

Note: I have also added a readonly to it which according to your code is what you should do. You could alternatively do a property, such as:

public Entry[] Hash { get; private set; } // note properties are capitalized

Note: Don't do this with your code "as-is", since your Hash object is currently a private one -- you will have an accessibility problem. I just added this as an example of a property declaration since I noticed you had none.

Validating arguments.
This is something that you may or may not require in every method as sometimes this can get a little out of hand. However, for the case of a constructor and key (usually every publicly exposed) methods, I will state that you MUST do it.

public Matcher(int n)
{
    // throw an error if passed zero or negative values
    if (n < 0) throw new ArgumentException("must be greater than zero", nameof(n));

    _hash = new Entry[n*5];
}

---

Hmmmm... smelly code.

I am not familiar with RFC 1951, so I hesitate to dive into the efficiencies or accuracy of your code. But asides from some of the coding convention related issues I noted earlier, there are a few sections that look like bad / smelly code (again, I cannot be certain about the results due to my lack of knowledge with RFC 1951).

Two infinite while loops.
Let's start here...

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 )  // <----!?
        {
            ...

I'm sure others will tend to agree that this doesn't sit right. It's quite unusual to see a while(true) at all. To be blunt, it feels like a lazy design attempt, but the reason it stands out to me is because it is inside a method which name suggests a singular task / operation (Rehash). If the method name was something like RehashForeverAndEver then I would probably have glossed over this and just assumed the infinite loop was intended.

Use of public fields.
I'm looking at this private nested class Entry, that you have...

private class Entry
{ 
    public int Position, Length;
    public Entry Next;
    public Entry( int position, int length, Entry next )
    {
        Position = position;
        Length = length;
        Next = next;
    }
}

I generally hesitate when I see the use of public fields. Due to the -- let's call it -- stigma behind the use of them. It throws off some heavy code smell. I would carefully reconsider the design of this class.

I was about to note areas of possible optimizations with how you are handling the byte[] operations, but I'm going to hold off, as I think that this post is plenty long now. I encourage you to break down your code into small concise methods and re-post just the methods that you feel need code review (it would very likely yield you a more focused review and profitable feedback).

Answer 2

To partially answer question (6), the Rehash function can be modified to start:

private void Rehash( byte[] input, int position, uint hash, int length )
{
  while ( true )
  {
    if ( length > MaxMatch ) return;

The logic is that since the limit on a match is MaxMatch (=258), there is no point hashing a string longer than that. This means it is now possible, albeit rather slow, to compress long repeat sequences ( which are quite common when compressing PDF images ).

I'm not very satisfied with this solution yet though, I think the algorithm could be modified to process long repeats efficiently and elegantly, but I haven't figured out how. Even with this fix, long repeats cause the processing to go much slower than normal - the outer loop of Rehash is executed nearly 258 times for each byte of input processed, when processing a long repeat.

Edit: I think skipping to the last MaxMatch bytes of a repeat sequence might work, as earlier potential matches will never be used ( again due to the MaxMatch limit ). I have not yet tried to code this.

Further Edit: After more investigation, my conclusion is that the re-hashing is not an effective approach. The cost appears to exceed any benefit, at least in the context of RFC 1951.

What seems to be more interesting is trying different block sizes, which seems to produce improved compression for relatively mimimal cost ( for example, for each block, starting with a small block size, and testing whether doubling the block size results in smaller output ).