title: Optimal pairing algorithm with few-value integer data
body: <p>I have to compare 2 strings, say, <code>CDABAB</code> and <code>EABACCCBB</code>. For me, the similarity is simply the amount of co-occurence of the same characters in both, regardless the position (i.e. the strings are "texts" not "sequences"). In addition, characters that form a co-occuring chain of characters, are given double weight.</p>
  
  <p>In my example, <code>A</code>, <code>A</code>, <code>B</code>, <code>B</code>, <code>C</code> are the instances of co-occurence. Also, <code>ABA</code> is a chain with 3 characters to double-weight. So, <code>A(2)</code>, <code>A(2)</code>, <code>B(2)</code>, <code>B(1)</code>, <code>C(1)</code> to sum, <code>2+2+2+1+1=8</code> is the similarity between the two strings for me. The example was too easy; in real life I have strings of a thousand+ lengths. So I need an algorithm.</p>
  
  <p>This is clearly a classic assignment problem. And I know it can be solved by, for example, <a href="http://en.wikipedia.org/wiki/Hungarian_algorithm" rel="nofollow noreferrer">Hungarian algorithm</a>. We should construct matrix of co-occurence (2 = double weight because of a chain):</p>
  
  <pre><code>   E A B A C C C B B
  C          1 1 1
  D
  A    2   1  
  B      2         1 1
  A    2   2
  B      2         1 1
  </code></pre>
  
  <p>and pair rows and columns one-to-one optimally so that the sum of within-pair similarities is maximized. It implies leaving only one positive value in each row and column, in a way giving the maximal matrix sum of values. Hungarian algorithm is a general approach that will give such maximal sum (the optimal solution). The left entries have the sum <code>8</code>, same to what is computed above:</p>
  
  <p><img src="https://i.stack.imgur.com/MkB3c.jpg" alt="enter image description here"></p>
  
  <p>However, Hungarian is not particularly fast (and not quite easy to program). I need another algorithm with my long strings. <strong>Can you suggest me another algorithm, faster and desirably easier</strong>? Note that my data are special case: it is <strong>similarity matrix with 3 integer values only - 0, 1, and 2</strong>.</p>
  
  <p>(With binary matrix, it is very easy to make the optimal pairing. With 3 values, I have an idea how to do, but it can give suboptimal, albeit "good" solution, in terms of exactness. Is there a way to always get the optimal one?)</p>
  
  <p><strong>P.S. Important.</strong> My elements in strings are actually not real characters from a limited alphabet, but are real words; so - they come from potentially unlimited alphabet which I don't know beforehand. I will not do preprocessing such as frequency counting. I'm rather inclined to start  with the rectangular matrix as shown above: I can make such a matrix with proper 0,1,2 values quite efficiently. My main question is about further algorithm.</p>
  
  <p>Thank you (for your patience, too).</p>
  
  <hr>
  
  <p><strong>Later update: a reply</strong> to @j_random_hacker's answer.</p>
  
  <p>I liked the proposed quick approach, it looked handsome. But I've found that it is problematic. The example below demonstrates it.</p>
  
  <pre><code>Two strings are
  S1= ABCACCDECF
  S2= BACBCCDA
  
  The matrix of co-occurences (where chains are given weight 2) is therefore:
     B  A  C  B  C  C  D  A
  A  0  1  0  0  0  0  0  1* 
  B  1  0  0  2* 0  0  0  0 
  C  0  0  1  0  2* 1  0  0 
  A  0  2* 0  0  0  0  0  1 
  C  0  0  2* 0  2  1  0  0 
  C  0  0  1  0  1  2* 0  0 
  D  0  0  0  0  0  0  2* 0 
  E  0  0  0  0  0  0  0  0 
  C  0  0  1  0  1  1  0  0 
  F  0* 0  0  0  0  0  0  0
  
  Hungarian algorithm of optimal pairing paired the rows and columns so as to maximize
  the sum of within-pair values. These values - which pair a row and a column - are shown starred
  in the matrix. And the sum is 13. It is the "similarity" between the strings.
  
  Let us compute now the similarity by the quick algorithm suggested by @j_random_hacker.
  
  Counts of individual characters (only occuring in both strings shown):
       A  B  C  D
  S1   2  1  4  1
  S2   2  2  3  1
  ---------------
  Min  2  1  3  1
  Sum1=7
  
  Counts of dyadic chains (only occuring in both strings shown):
       BC  AC  CC  CD
  S1    1   1   1   1
  S2    1   1   1   1
  -------------------
  Min   1   1   1   1
  Sum2=4
  
  Counts of triadic chains (only occuring in both strings shown):
       CCD
  S1    1
  S2    1
  --------
  Min   1
  Sum3=1
  
  Sum1 + 2Sum2 - Sum3 = 14. While I was expecting 13, as Hungarian algo gave.
  
  The cause of the discrepancy seems obvious enough.
  The second algorithm recognized 4 dyads: AC, BC, CD, and CC; and because CC and CD actually
  superimpose by C (they form a triad CCD), C should be counted only once as a member of a dyad.
  
  However, as seen from the starred elements in the matrix, Hungarian algorithm recognized
  only 3 dyads: AC, BC, CD. Because the first of the two C is shared by by AC and CC or by
  BC and CC, this character is (since it cannot be counted twice) is discarded altogether,
  and hence the dyad it is a member of, CC, does not exist. And that is correct for me.
  </code></pre>