5
$\begingroup$

Migrated from stackoverflow.

Hello,

I was looking for a string metric that have the property that moving around large blocks in a string won't affect the distance so much. So "helloworld" is close to "worldhello". Obviously Levenshtein distance and Longest common subsequence don't fulfill this requirement. Using Jaccard distance on the set of n-grams gives good results but has other drawbacks (it's a pseudometric and higher n results in higher penalty for changing single character).

[original research]

As I thought about it, what I'm looking for is a function f(A,B) such that f(A,B)+1 equals the minimum number of blocks that one have to divide A into (A1 ... An), apply a permutation on the blocks and get B:

f("hello", "hello") = 0
f("helloworld", "worldhello") = 1   // hello world -> world hello
f("abba", "baba") = 2               // ab b a -> b ab a
f("computer", "copmuter") = 3       // co m p uter -> co p m uter

This can be extended for A and B that aren't necessarily permutations of each other: any additional character that can't be matched is considered as one additional block.

f("computer", "combuter") = 3       // com uter -> com uter, unmatched: p and b.

Observing that instead of counting blocks we can count the number of pairs of indices that are taken apart by a permutation, we can write f(A,B) formally as:

f(A,B) = min { C(P) | P ⊆ |A|×|B|, P is a bijective function, ∀i∈dom(P) A[P(i)]=B[P(i)] }
C(P) = |A| + |B| − |dom(P)| − |{ i | i,i+1∈dom(P) and P(i)+1=P(i+1) }| − 1

The problem is... guess what...

... that I'm not able to calculate this in polynomial time.

Can someone suggest a way to do this efficiently (possibly with minor modifications)? Or perhaps point me to already known metric that exhibits similar properties?

$\endgroup$
  • $\begingroup$ By your definition, f(computer,computeb) = 2, less than f(computer,combuter). Is that the desired outcome ? I ask because it seems like the two misspellings should be equidistant from the correct word $\endgroup$ – Suresh Venkat Feb 6 '11 at 18:15
  • $\begingroup$ I think that this is a nice question. (1) The formal definition has a few shortcomings. First, “P:|A|→|B|” does not make sense because |A| and |B| are not sets (I interpret it as P:{1,…,|A|}→{1,…,|B|}). Second, the definition does not seem to handle the case where A and B are not permutations of each other. (2) I would not expect that this function is computable in polynomial time, just because it sounds too good to be true. $\endgroup$ – Tsuyoshi Ito Feb 6 '11 at 18:56
  • $\begingroup$ @Tsuyoshi, the OP has addressed the non-permutation case in the question. Since it's ok to "match" dissimilar characters, there's an upper bound of n on the distance between two n-character strings in his model. $\endgroup$ – Suresh Venkat Feb 6 '11 at 20:12
  • $\begingroup$ @Suresh: I guess that whether it is desirable depends on the application, but I do not think that “the two misspellings should be equidistant from the correct word” for any fundamental reason. For example, one might be typing the string on a long tape and one may have to cut the tape with scissors to correct the mistake. In this case, “computeb” is easier to correct than “combuter” because the former needs only one cut whereas the latter needs two cuts. $\endgroup$ – Tsuyoshi Ito Feb 6 '11 at 20:15
  • $\begingroup$ @Suresh: The “formal definition” I referred to is the definition at the end of the question after “we can write f(A,B) formally as:”. $\endgroup$ – Tsuyoshi Ito Feb 6 '11 at 20:16
8
$\begingroup$

What you seem to be looking for is called the minimum common string partition, and it has been well studied. In particular, it's known to be NP-hard. There is also a closely related concept of edit distance with block moves, which would capture the extension you mention, where substitutions are allowed.

$\endgroup$
1
$\begingroup$

For anyone interested:

I implemented The String Edit Distance Matching Problem with Moves by Graham Cormode and S. Muthukrishnan. It essentially approximates the described metric in linear time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.