This is my version of a LZ-77 lossless compression algorithm for text. It maintains a sliding window of 4095 characters and can pick up patterns up to 15 characters long. Basically, the compressed file is made of tuples (length, pos), with length on 4 bits and pos on 12 bits which makes 2 bytes each time. Besides, if I have to write a character that is not in the window, I set length=0, then I have 4 empty bits and the 8 bits left are used to encode the character.
I've spent a few hours on it correcting little bugs and it seems functional, although it appears not to work entirely for big files (size > window) but I'll correct this later. Anyway I'm not here for algorithm but for code design so tell me what's good or bad about this code, don't hesitate.
Also, I haven't implemented any file-manager system but the functions' names are quite explicit on how to use them.
#include <iostream>
#include <string>
#include <tuple>
#include <bitset>
#include <sstream>
#include <fstream>
using namespace std;
/**
Given two strings s1 and s2, find the longest prefix of s2 that is in s1
and returns the position of the prefix' first character in s1 and its length in a pair
If s1 = "lossless compression in opposition to " and s2 = "lossy compression", the longest prefix is "loss"
and the function returns (0, 4).
*/
pair<int, int> longest_prefix(string s1, string s2)
{
int pos {0};
int length {0};
for(int i = 0; i < s1.size(); i++)
{
int l {0};
while(i+l < s1.size() && l < s2.size() && s1[i+l] == s2[l])
l++;
if(l > length)
{
pos = i;
length = l;
}
if(i == s1.size() - length || length == s2.size())
return pair<int,int>(pos, length);
}
return pair<int,int>(pos, length);
}
/**
we have a sliding window of fixed size and instead of rewriting text that already is in the window,
we just refer to it with its position in the window and its size
*/
string lz77_compress(string s)
{
string compressed { "" };
int window_size { 4095 };
int pattern_size { 15 };
int i { 0 };
while(i < s.size())
{
string s1 { i >= window_size ? s.substr(i - window_size, window_size) : s.substr(0, i) };
string s2 { s.substr(i, min(pattern_size, (int)s.size() - i)) };
pair<int,int> match = longest_prefix(s1, s2); // fst = pos; snd = length
if(match.second == 0) // length = 0: no match, we just add a char (0, char)
{
compressed += (char)0;
compressed += s[i];
i++;
}
else // match, then we add (pos, length)
{
bitset<4> length(match.second);
bitset<12> pos(match.first);
bitset<16> concat(length.to_string() + pos.to_string()); // change a 4-bit and a 12-bit number into two 8-bits numbers
bitset<8> bit1(concat.to_string().substr(0,8));
bitset<8> bit2(concat.to_string().substr(8,8));
compressed += (char)bit1.to_ulong();
compressed += (char)bit2.to_ulong();
i += match.second;
}
}
return compressed;
}
string lz77_decompress(string compressed)
{
string s { "" };
int window_size { 4095 };
for(int i = 0; i < compressed.size(); i += 2)
{
bitset<8> bit1(compressed[i]);
bitset<8> bit2(compressed[i+1]);
bitset<16> concat(bit1.to_string() + bit2.to_string());
bitset<4> length_b(concat.to_string().substr(0,4));
int length = length_b.to_ulong();
if(length == 0)
{
bitset<8> c(concat.to_string().substr(8, 8));
s += (char)c.to_ulong();
}
else
{
bitset<12> pos(concat.to_string().substr(4, 12));
s += s.substr(max(0, i - window_size) + pos.to_ulong(), length);
}
}
return s;
}