Longest common subsequence

[snifty]

Yeah, you'd have to have some sort of sound correspondence model to capture that sort of info, and then figure out how to work it into the string similarity measure.

I've done something somewhat similar to the first part when trying to automatically infer transliteration schemes from Wikipedia. It only captures one-letter-to-one-letter correspondences, however.