Also, if your window size is greater than 2^8 and you can afford an extra 2 x window_size bytes, the optional indexing greatly increases the compression speed o

Also, if your window size is greater than 2^8 and you can afford an extra 2 x window_size bytes, the optional indexing greatly increases the compression speed over normal LZSS; the typical linear scan for every byte really hurts as the window gets larger. The index construction is O(N) in the window size for both time and space, which should be doable on many systems. It doesn't change the fundamental algorithm, just speeds up the compression's pattern detection.