Algorithm for measuring distance between disordered sequences

Question

The Levenshtein distance gives us a way to calculate the distance between two similar strings in terms of disordered individual characters:

quick brown fox
quikc brown fax

The Levenshtein distance = 3.

What is a similar algorithm for the distance between two strings with similar subsequences? For example, in

quickbrownfox
brownquickfox

the Levenshtein distance is 10, but this takes no account of the fact that the strings have two similar subsequences, which makes them more "similar" than completely disordered words like

quickbrownfox
qburiocwknfox

and yet this completely disordered version has a Levenshtein distance of eight.

What distance measures exist which take the length of subsequences into account, without assuming that the subsequences can be easily broken into distinct words?

Answer 1

Initial stab: use a diff algorithm and the count of the number of differences as your distance

Answer 2

I think that you can try shingles or some combinations of them with Levenshtein distance.

Answer 3

I have an impression that it's NP-complete problem.

At least, I cannot see how can we avoid an exhaustive search. Moreover, I cannot even see how can we verify given solution in polynomial time.

Answer 4

One simple metric would be to take all n*(n-1)/2 substrings in each string, and see how many overlap. There are some simple variations to this approach where you only look at substrings up to a certain length.

This would be similar to the BLEU score commonly used to evaluate machine translations. In the case of BLEU, they are comparing two sentences: they take all the unigrams, bigrams, trigrams, and 4-grams of words from each sentence. They calculate a version of precision and recall for each, and essentially use an average of those scores.

Answer 5

well the problem you're referring to falls under context sensitive grammar. You basically define a grammar, the english grammar in this case and then find the distance between a grammar and a mismatch. You'll need to parse your input first.