Mastering Algorithms With C - Kyle Loudon [176]
* *
* Adjust the phrase length to account for the unmatched symbol. *
* *
***********************************************************************/
length++;
}
else {
/***********************************************************************
* *
* Handle processing a symbol token. *
* *
***********************************************************************/
next = 0x00;
for (i = 0; i < LZ77_NEXT_BITS; i++) {
tpos = (sizeof(unsigned char) * 8) - LZ77_NEXT_BITS + i;
bit_set((unsigned char *)&next, tpos, bit_get(compressed, ipos));
ipos++;
}
/***********************************************************************
* *
* Write the symbol to the buffer of original data. *
* *
***********************************************************************/
if (opos > 0) {
if ((temp = (unsigned char *)realloc(orig, opos + 1)) == NULL) {
free(orig);
return -1;
}
orig = temp;
}
else {
if ((orig = (unsigned char *)malloc(1)) == NULL)
return -1;
}
orig[opos] = next;
opos++;
/***********************************************************************
* *
* Record the symbol in the look-ahead buffer until ready to update *
* the sliding window. *
* *
***********************************************************************/
if (remaining > 0)
buffer[0] = next;
/***********************************************************************
* *
* Adjust the total symbols remaining to account for the unmatched *
* symbol. *
* *
***********************************************************************/
remaining--;
/***********************************************************************
* *
* Set the phrase length to account for the unmatched symbol. *
* *
***********************************************************************/
length = 1;
}
/**************************************************************************
* *
* Copy the look-ahead buffer into the sliding window. *
* *
**************************************************************************/
memmove(&window[0], &window[length], LZ77_WINDOW_SIZE - length);
memmove(&window[LZ77_WINDOW_SIZE - length], &buffer[0], length);
}
/*****************************************************************************
* *
* Point to the buffer of original data. *
* *
*****************************************************************************/
*original = orig;
/*****************************************************************************
* *
* Return the number of bytes in the original
data. *
* *
*****************************************************************************/
return
opos;
}
Questions and Answers
Q: There are certain cases where compressing data may generate poor results. When might we encounter this with Huffman coding?
A: Effective compression with Huffman coding depends on symbols occurring in the data at varying frequencies. If all possible symbols occur at nearly the same frequency, poor compression results. Huffman coding also performs poorly when used to compress small amounts of data. In this case, the space required by the table in the header negates the compression achieved in the data. Fortunately, these limitations are not normally a problem because the symbols in most data are not uniformly distributed, and we are usually not interested in compressing small amounts of data.
Q: Just as with Huffman coding, there are certain cases in which LZ77 achieves poor compression. What are some of these cases?
A: Effective compression with LZ77 depends on being able to encode many sequences of symbols using phrase tokens. If we generate a large number of symbol tokens and only a few phrase tokens representing predominantly short phrases, poor compression results. An excessive number of symbol tokens may even cause the compressed data to be larger than the original data itself. This occurs when the sliding window is made too small to take advantage of recurring phrases effectively.
Q: In the implementation of both Huffman coding and LZ77 presented