It's not obvious to me how Algorithm::Diff can be used to compute edit distances. Do you call diff() and then count up the number of insertions and deletions in the result?

Suppose you have several equidistant matches from a given element in A to several elements in B. Do you have to pick one of them such that the overall number of pairings is maximized? It might be an NP-complete problem.