6

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?

  • 1
    How is this off-topic? Maybe one could just improve the title. – Dario May 18 '10 at 11:26
  • Was asked many times under better name :o) http://stackoverflow.com/questions/451884/similar-string-algorithm or http://stackoverflow.com/questions/653157/a-better-similarity-ranking-algorithm-for-variable-length-strings or http://stackoverflow.com/questions/246961/algorithm-to-find-similar-text Btw: I especially like the idea with compression based distance. – MaR May 18 '10 at 11:27
  • @Dario: What title would you suggest? –  May 18 '10 at 11:28
  • @MaR: those questions are not the same as this question. The point is that there is no obvious way to break the string into words. –  May 18 '10 at 11:30
  • Also interesting page comparing different string similarity metrics: http://www.dcs.shef.ac.uk/~sam/stringmetrics.html Best seems to be SmithWatermanGotoh metric in this comparison. – MaR May 18 '10 at 11:32
  • @Kinopiko: E.g. something with "measuring distance" in it. – Dario May 18 '10 at 11:40

5 Answers5

1

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

Manvel
  • 84
  • 1
  • 3
1

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.

mathmike
  • 1,014
  • 5
  • 10
0

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

jk.
  • 13,817
  • 5
  • 37
  • 50
0

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.

Roman
  • 64,384
  • 92
  • 238
  • 332
0

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.

Laz
  • 6,036
  • 10
  • 41
  • 54