Lz77 Compression Technique: Applied Hash Tables, Code Still Too Slow!

Hi! In spite of some discouragement, I am still working on file compression. Right now, I'm working on optimizing my rendition of the lz77 technique, even though I'm not ready for it. Yesterday, I applied what I think is how hash tables work. It is still way too slow. I attached versions of the problem code. Main.c does the actual compression, while lz.c finds the lz77 block. In lz.c, the function GetLZ() finds the best match for the current input at location d in the input buffer lzdict, while ChkBlock() compares current input, whose address is writen into the pointer curaddr by GetLZ() to the offset specified in pos. The array lzhashtbl is to hold the matches found and put into the hash tables. The first subscript defines each entry, and the second the first 64 matches. lzhashsize defines the number of hash table entries so far. The function in main.c scans the input, compresses lz77 blocks and writes each literal directly. The calls to writeoutf() will write the number of bits specified in the second parameter to the output. If the name is followed by two numbers, the second number is the number of bits to write. You can ignore the call to WriteLast16(): it is part of another compression technique and not implemented here. lz77getused() and lz77setused() implement anther strategy to optimize lz77, where a value that has yet to be found will be skipped in the lz77 compare: lz77getused() returns true if found, and lz77setused() marks a word as found. InPos and lzoffs both represent the current location in the input. If you can identify the problem, I ask you to tell me it.

 

You may be better posting this type of question at Stack Exchange, for example: c++ - How can I make my LZ77 algorithm to compress faster or to .... https://codereview.stackexchange.co...orithm-to-compress-faster-or-to-compress-more

The following web pages may of use to you in resolving your question:

* The methods of improving the compression ratio of LZ77 family data .... https://ieeexplore.ieee.org/document/567359.
* [MS-WUSP]: LZ77 Compression Algorithm | Microsoft Learn. https://learn.microsoft.com/en-us/o.../ms-wusp/fb98aa28-5cd7-407f-8869-a6cef1ff1ccb.
* LNEE 140 - A BP-LZ77 Compression Algorithm Based on BP Network - Springer. https://link.springer.com/content/pdf/10.1007/978-3-642-27296-7_34.pdf.
* The DEFLATE specification. https://www.rfc-editor.org/rfc/rfc1951
* DEFLATE Wikipedia. https://en.wikipedia.org/wiki/Deflate​

 

Thank you. I plan to go to those sites soon.

 

Earlier today, I killed some of the code that tells me where I am in the file to compress and how it's compressing, and now, a 135k file takes just less than 2 seconds to compress.