views:

204

answers:

5
+2  Q: 

lz77 question

what is the minimum source length (in bytes) for LZ77. can anyone suggest a small and fast real time compression technique (preferable with c source). i need it to store compressed text and fast retrieval for excerpt generation in my search engine. thanks

+3  A: 

I long ago had need for a simple, fast compression algorithm, and found Predictor.

While it may not be the best in terms of compression ratio, Predictor is certainly fast (very fast), easy to implement, and has a good worst-case performance. You also don't need a license to implement it, which is goodness.

You can find a description and C source for Predictor in Internet RFC 1978: PPP Predictor Compression Protocol.

Chris W. Rea
thanks, really simple algorithm. im trying it. quick question, is there a limit to source length?
kar
I don't *think* so. It's been a good ten years since I used it, and I doubt we had to compress anything huge (>2GB) back then :-)
Chris W. Rea
+1  A: 

If you're looking for something more well known this is about the best compressor in terms of general compression you'll get. LZMA, the 7-zip encoder. http://www.7-zip.org/sdk.html

+2  A: 

The lzo compressor is noted for its smallness and high speed, making it suitable for real-time use. Decompression, which uses almost zero memory, is extremely fast and can even exceed memory-to-memory copy on modern CPUs due to the reduced number of memory reads. lzop is an open-source implementation; versions for several other languages are available.

j_random_hacker
A: 

thanks for all the response, im using D language for this project so it's kinda hard to port LZO to D codes. so im going with either LZ77 or Predictor. thanks again :)

kar
+1  A: 

There's also LZJB: http://src.opensolaris.org/source/xref/onnv/onnv-gate/usr/src/uts/common/os/compress.c

It's pretty simple, based on LZRW1, and is used as the basic compression algorithm for ZFS.

James Snyder