As it was explained to me by a patent attorney, what is colloquially known as a "software patent" really isn't. Rather, it's a patent on the resulting machine that software transforms a general purpose machine (computer) into.
If I had a black box wherein you fed in paper tape encoding data on one end and different paper tape with the data compressed came out the other end (thus taking less tape), that would be a data compression machine. Certainly, if the black box had no software at all but was instead a bunch of gears and such, i.e., totally mechanical, you'd have to agree that the machine would be patentable.
But it's still the type of machine that's being patented (a data compression machine). The preferred embodiment as described in the patent is just one way to do it.
Now if instead of gears you had a computer running software, well that doesn't change the functioning of the machine -- the tape output is the same for a given input. Therefore, the fact that a particular embodiment just might happen to use a computer and software rather than gears is irrelevant.