icanwin,
I am glad Text::LevenshteinXS looks promising. You have missed my other point though.

You have asked for helping optimizing your solution but have not provided enough information to do so. There are plenty of "what if" scenarios but you are holding all the cards. If you want more advice beyond faster edit distance checking, please provide more information.