This task asks for an basic implementation of the the
Lempel-Ziv-Welch (LZW) compression/decompression algorithm. I am
keeping two D versions, the first one is minimal, and the second
is a little more optimized:
http://rosettacode.org/wiki/LZW_compression#More_Refined_Version
There are of course ways to implement a really efficient ZLW
compressor in D, and such implementation could be added as third
D entry if it manages to be not too much long, but for the first
two versions keeping the code very short is more important.
Despite the compressor in the second D entry is still not
efficient at all, I have tried to make it not terrible regarding
its efficiency, so I have defined a new kind of slice that can be
extended, unlike the D slices, to avoid the string appends
visible in the first D entry:
struct Slice {
size_t start, end;
@property opSlice() const pure nothrow @safe @nogc {
return original[start .. end];
}
alias opSlice this;
}
Slice w;
Tcomp[] result;
foreach (immutable i; 0 .. original.length) {
auto wc = Slice(w.start, w.end + 1); // Extend slice.
if (wc in dict) {
w = wc;
} else {
result ~= dict[w];
assert(dict.length < Tcomp.max); // Overflow guard.
dict[wc] = cast(Tcomp)dict.length;
w = Slice(i, i + 1);
}
}
Is this showing a limit (problem) of D slices, or is this design
better written in other ways?
Bye,
bearophile
