[Someone1234]

If you have both the old and new password in plain text you don't need to do a compression-based check, just a raw iterative approach would accomplish the same thing with very low overhead (in either CPU or memory accesses).

Compression systems typically need a lookup table of some kind and have more overhead than just the raw comparison.

[DoggettCK]

As mentioned in another comment, I'd probably do a Levenshtein distance between the old and new passwords, and reject if they crossed some threshold. However, only knowing the plaintext of the immediately-preceding password as they enter it to authorize the change, it wouldn't do much to stop them from doing:

PasswordA SomeOtherPassword1 PasswordB SomeOtherPassword2 PasswordC SomeOtherPassword3

Just iterate on every other change, and you've beaten the requirement.

[derefr]

That's assuming what you want is to find passwords that are "the same" in a literal sense, rather than "the same" as in sharing a common generation algorithm that biases certain outputs.

For example, if a user's first password is "first123!@#" and their second password is "second456$%^", there are no letters in common—but those two passwords, when joined together, are very intracompressible (by an ideal compressor)—and likewise, an attacker who knew that the first was a previously-used password would be very likely to try the second. That both properties apply is not a coincidence of this particular password; the intra-compressibility of a set of plaintexts, and the predictability of unknown plaintexts of the set from known ones, are equivalent measures of informational entropy.