gbadev.org forum archive

This is a read-only mirror of the content originally found on forum.gbadev.org (now offline), salvaged from Wayback machine copies. A new forum can be found here.

Coding > What "threshold" means in Lempel-Ziv algorithm?

#45647 - Pinczakko - Mon Jun 13, 2005 10:25 am

I'm trying to tinker with some compression algorithm to be used in my GBA program and needs some help. Most of the implementations I've read were based on C language. So, I planned to use C as well. But I'm not very well versed yet of the terms in this new world (compression).

I've google'd for this stuff and already found some info. But, I want to ensure that my interpretation is right.
To my understanding, the threshold word used by LZH or other dictionary compression algorithm explanation/specification means the minimum number of match-length in bytes, i.e. the minimum number of bytes that match within the dictionary and the bytes in the current look-ahead buffer that have to be "surpassed" to carry-out the "encoding". So, if the match-length is less than the threshold, the phrase in the look-ahead buffer won't be encoded, but will stay as literal in the compression result. Is this correct?

There must be some compression guru around here to help me ;)

PS: sorry for the bad english
_________________
- Human knowledge belongs to the world -
- Знания людей принадлежат миру -

#45660 - strager - Mon Jun 13, 2005 2:43 pm

This simply means, if the reference and the byte length take up more than the actual data, why bother? Just write the data as-is.

Bold terms in your post:
  • Threshold - minimum number of bytes that can be encoded to the dictionary
  • Match-length - the length of a phase matching to the dictionary
  • Dictionary - a list of phases that are used more than once
  • Look-ahead buffer - A buffer than holds threshold+ bytes after the current byte; holds a phase
  • Phase - a sequence of bytes
  • Literal - a phase from the origional file

That should be it.

#45723 - Pinczakko - Tue Jun 14, 2005 3:33 am

Thanks for the explanation. I've quite understood the terms, but I want to ensure that I've done it in the right way. Now I'm very sure about it :).
_________________
- Human knowledge belongs to the world -
- Знания людей принадлежат миру -