So, I'm implementing LZ77 compression algorithm. To compress any file type, I use its binary representation and then read it as chars
(because 1 char
is equal to 1 byte, afaik) to a std::string
. Current program version compresses and decompresses files (.txt, .bmp, etc) just fine – size of raw file in bytes matches the size of uncompressed file. Though I started to wonder, if usage of byte representation instead of bits is optimal at all:
- Is it optimal to use
chars
(bytes) instead of single bits? No possible loss of bits?
Also, is there a way to compare file sizes in bits instead of bytes? (forgive me for stupid questions)
And now for the actual code part. Here's the short info on how LZ77 handles compression:
Below are 2 main functions: compress and findLongestMatch:
compress
moves char data between 2 buffers and saves encoded tuple ⟨offset, length, nextchar⟩findLongestMatch
finds the longest match of lookheadBuffer in historyBuffer
- Is there a more elegant and effective way of searching for longest match?
(also in theory algo should search right to left, but is there any complexity difference? even if the offset
is actually longer, it's still int and still 4 bytes – I convert every int
into 4 chars
(bytes) to save into output binary file)
LZ77::Triplet LZ77::slidingWindow::findLongestPrefix()
{
// Minimal tuple (if no match >1 is found)
Triplet n(0, 0, lookheadBuffer[0]);
size_t lookCurrLen = lookheadBuffer.length() - 1;
size_t histCurrLen = historyBuffer.length();
// Increasing the substring (match) length on every iteration
for (size_t i = 1; i <= std::min(lookCurrLen, histCurrLen); i++)
{
// Getting the substring
std::string s = lookheadBuffer.substr(0, i);
size_t pos = historyBuffer.find(s);
if (pos == std::string::npos)
break;
if ((historyBuffer.compare(histCurrLen - i, i, s) == 0) && (lookheadBuffer[0] == lookheadBuffer[i]))
pos = histCurrLen - i;
// If the longest match is found, check if there are any repeats
// following the of current longest substring in lookheadBuffer
int extra = 0;
if (histCurrLen == pos + i)
{
// Check for full following repeats
while ((lookCurrLen >= i + extra + i) && (lookheadBuffer.compare(i + extra, i, s) == 0))
extra += i;
// Check for partial following repeats
int extraextra = i - 1;
while (extraextra > 0)
{
if ((lookCurrLen >= i + extra + extraextra) && (lookheadBuffer.compare(i + extra, extraextra, s, 0, extraextra) == 0))
break;
extraextra--;
}
extra += extraextra;
}
// Compare the lengths of matches
if (n.length <= i + extra)
n = Triplet(histCurrLen - pos, i + extra, lookheadBuffer[i + extra]);
}
return n;
}
void LZ77::compress()
{
do
{
if ((window.lookheadBuffer.length() < window.lookBufferMax) && (byteDataString.length() != 0))
{
int len = window.lookBufferMax - window.lookheadBuffer.length();
window.lookheadBuffer.append(byteDataString, 0, len);
byteDataString.erase(0, len);
}
LZ77::Triplet tiplet = window.findLongestPrefix();
// Move the used part of lookheadBuffer to historyBuffer
window.historyBuffer.append(window.lookheadBuffer, 0, tiplet.length + 1);
window.lookheadBuffer.erase(0, tiplet.length + 1);
// If historyBuffer's size exceeds max, delete oldest part
if (window.historyBuffer.length() > window.histBufferMax)
window.historyBuffer.erase(0, window.historyBuffer.length() - window.histBufferMax);
encoded.push_back(tiplet);
} while (window.lookheadBuffer.length());
}
Accessory functions:
int intFromBytes(std::istream& is)
{
char bytes[4];
for (int i = 0; i < 4; ++i)
is.get(bytes[i]);
int integer;
std::memcpy(&integer, &bytes, 4);
return integer;
}
void intToBytes(std::ostream& os, int value)
{
char bytes[4];
std::memcpy(&bytes, &value, 4);
os.write(bytes, 4);
}
struct Triplet
{
int offset;
int length;
char next;
}