Firstly; I call the compression Haruhiko because (as Ombra noted), the LZSS compression was originally devised by Haruhiko Okumura, so far as I can tell. I don't call it LZSS compression because *all* the compression algorithms output LZSS files - Haruhiko's algorithm just outputs better compressed LZSS then ours do
So, since the algorithm Cosmo uses is essentially a direct port of Haruhiko's code, I call it LZSS/Haruhiko compression.
Qhimm: The Haruhiko code compresses very fast - it uses fixed trees, and so the speed seems *comparable* to your own. I haven't benchmarked it in any way, but for FF7 purposes, if it compresses a level in less than a second, you're happy enough, regardless of small differences...
M4v3r: Yes, the problem is that Cosmo is 'too clever'. If you change the length of a piece of text, it tries to rewrite all the pointers in the level to accomodate the new size. When it works, that's really funky. Unfortunately, when it doesn't, it corrupts the level file. Even worse, sometimes (I don't know why) it thinks you've changed the length when you haven't, which is obviously worse still...
The black dots: Yes, they're still a pain in the proverbial. Unfortunately, I've pretty much now decoded about 95%+ of the background (see latest LGP Tools for working-in-many-locations animations and transparencies) and they don't change a thing at all - quite a few of the black dots appear in locations that aren't covered by animations or transparencies at all, so it's a more basic problem than that.
I've developed one or two simple filters that try to eradicate them, but they're less than totally effective...LGP Tools has a checkbox to enable the filter; you can see the difference by loading a level with the filter off, turning it on then clicking 'Reload'. Sometimes it works really well and eliminates lots of the dots. Often it doesn't. If I were to actually pay attention to some of my lectures at uni, I might be able to develop a better filter...
(Actually, I really should see what's on my departments pages about this sort of application. There's a surprising amount of code and information available if you know where to look, although I'm not sure how useful it'd be for this. I suspect the format of having some sort of horrible quirks that you'd only discover by guesswork.)