Compression systems typically need a lookup table of some kind and have more overhead than just the raw comparison.
Just iterate on every other change, and you've beaten the requirement.
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.
* not more than 2 identical characters in a row (e.g., 111 not allowed)
* Name/Username in password (Name: Chuck Norris, username: ChuckNorris, Password: ChuckNorris#1)
These are reasons why I don't look forward to doing this and also why I'm leaning towards G+/FB/twitter/etc authentication in an app I'm planning.
For the second, I'd probably just do something like compute the Levenshtein distance between the username and password, and reject it if it passed some threshold.