How to calculate this string-dissimilarity function efficiently? 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 -&gt; world hello
f("abba", "baba") = 2               // ab b a -&gt; b ab a
f("computer", "copmuter") = 3       // co m p uter -&gt; 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 -&gt; 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?
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.