<p>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. </p>

CC BY-SA 2.5
2011-02-06T22:01:13.577Z
that is neat. I had never heard of this problem before. As a bonus, here's a survey of the problem: http://kam.mff.cuni.cz/~kolman/papers/mcsphard.pdf
Suresh Venkat
CC BY-SA 2.5
2011-02-06T21:55:39.250Z
2011-02-06T21:55:39.250Z
Marek Chrobak
<p>For anyone interested:</p>

<p>I implemented <a href="http://dimacs.rutgers.edu/~graham/pubs/papers/editmovestalg.pdf" rel="nofollow noreferrer">The String Edit Distance Matching Problem with Moves by Graham Cormode and S. Muthukrishnan</a>. It essentially approximates the described metric in linear time.</p>

CC BY-SA 3.0
2017-07-05T08:52:02.150Z
2017-07-05T08:52:02.150Z
ybungalobill
<blockquote>
  <p>Migrated from <a href="https://stackoverflow.com/questions/4914162/how-to-calculate-this-string-dissimilarity-function-efficiently">stackoverflow</a>.</p>
</blockquote>

<p>Hello,</p>

<p>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).</p>

<p>[original research]</p>

<p>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:</p>

<pre><code>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
</code></pre>

<p>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.  </p>

<pre><code>f("computer", "combuter") = 3       // com uter -&gt; com uter, unmatched: p and b.
</code></pre>

<p>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:</p>

<pre><code>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
</code></pre>

<p>The problem is... guess what...</p>

<p>... that I'm not able to calculate this in polynomial time.</p>

<p>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?</p>

CC BY-SA 2.5
2011-02-06T18:15:44.837Z
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
Suresh Venkat
CC BY-SA 2.5
2011-02-06T18:56:27.790Z
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.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-06T20:12:01.930Z
@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.
Suresh Venkat
CC BY-SA 2.5
2011-02-06T20:15:50.317Z
@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.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-06T20:16:47.397Z
@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:”.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-06T20:16:51.783Z
@Tsuyoshi ah I see. so this is a time travelling application from the days of paper tape input :)
Suresh Venkat
CC BY-SA 2.5
2011-02-06T20:19:18.317Z
@Suresh: Yeah, I agree that my application is slightly dated.  Slightly. :)
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-06T20:47:43.603Z
@Suresh: "By your definition, f(computer,computeb) = 2, less than f(computer,combuter). Is that the desired outcome" yes, it's fine. If I really want to matchi 'whole strings' then I can add a terminating character at the end.
ybungalobill
CC BY-SA 2.5
2011-02-06T20:50:47.350Z
@Tsuyoshi: "because |A| and |B| are not sets", they are cardinals, that are sets in traditional axiomatic set-theory. "the definition ... not permutations of each other." it does. See formal definition of a function in any set-theory book. P:|A|→|B| doesn't mean that dom(P) = |A| nor rng(P) = |B|. Excuse me if that notation is not common among non-set-theorists.
ybungalobill
CC BY-SA 2.5
2011-02-06T20:59:30.897Z
I confess that I am a non-set-theorist.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-06T21:03:20.380Z
@Tsuyoshi: Actually I'm neither set-theorist (yet) nor a computer scientist. Anyway, I also think that probably there is no polynomial time algorithm for that. However, it has some similarities with max-flow graphs, so who knows... (edited the formal definition to be less ambiguous)
ybungalobill
CC BY-SA 2.5
2011-02-07T01:12:30.567Z
You might want to have a look at (local) string alignments. While not precisely what you want, they are computable in $\mathcal{O}(n^2)$, with $n$ the number of characters in the larger word.
Raphael
<ds.algorithms><metrics><string-matching>
How to calculate this string-dissimilarity function efficiently?
ybungalobill
# How to calculate this string-dissimilarity function efficiently?

(Asked by: username_0 on 2011-02-06)

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?

**Tags:** ds.algorithms, metrics, string-matching

> **Comments:**
> **username_1**: 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  
> **username_2**: 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.  
> **username_1**: @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.  
> **username_2**: @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.  
> **username_2**: @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:”.  
> **username_1**: @Tsuyoshi ah I see. so this is a time travelling application from the days of paper tape input :)  
> **username_2**: @Suresh: Yeah, I agree that my application is slightly dated.  Slightly. :)  
> **username_0**: @Suresh: "By your definition, f(computer,computeb) = 2, less than f(computer,combuter). Is that the desired outcome" yes, it's fine. If I really want to matchi 'whole strings' then I can add a terminating character at the end.  
> **username_0**: @Tsuyoshi: "because |A| and |B| are not sets", they are cardinals, that are sets in traditional axiomatic set-theory. "the definition ... not permutations of each other." it does. See formal definition of a function in any set-theory book. P:|A|→|B| doesn't mean that dom(P) = |A| nor rng(P) = |B|. Excuse me if that notation is not common among non-set-theorists.  
> **username_2**: I confess that I am a non-set-theorist.  
> **username_0**: @Tsuyoshi: Actually I'm neither set-theorist (yet) nor a computer scientist. Anyway, I also think that probably there is no polynomial time algorithm for that. However, it has some similarities with max-flow graphs, so who knows... (edited the formal definition to be less ambiguous)  
> **username_3**: You might want to have a look at (local) string alignments. While not precisely what you want, they are computable in $\mathcal{O}(n^2)$, with $n$ the number of characters in the larger word.  

---

## 2 answers

### Answer by username_4 on 2011-02-06. Score: 8 | Accepted answer

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.

> **Comments:**
> **username_1**: that is neat. I had never heard of this problem before. As a bonus, here's a survey of the problem: http://kam.mff.cuni.cz/~kolman/papers/mcsphard.pdf  

---

### Answer by username_0 on 2017-07-05. Score: 1

For anyone interested:

I implemented [The String Edit Distance Matching Problem with Moves by Graham Cormode and S. Muthukrishnan](http://dimacs.rutgers.edu/~graham/pubs/papers/editmovestalg.pdf). It essentially approximates the described metric in linear time.


---

