algorithm - 少值整数数据的最优配对算法

Question

我必须比较 2 个字符串，比如 CDABAB 和 EABACCCBB。对我来说，相似性只是相同字符在两者中同时出现的数量，无论位置如何(即字符串是“文本”而不​​是“序列”)。此外，形成同现字符链的字符被赋予双倍权重。

在我的示例中，A、A、B、B、C 是共现的实例。此外，ABA 是一个包含 3 个字符的双倍权重链。所以，A(2)，A(2)，B(2)，B(1)， C(1) 求和，2+2+2+1+1=8 对我来说就是两个字符串的相似度。这个例子太简单了；在现实生活中，我有一千多个长度的字符串。所以我需要一个算法。

这显然是一个经典的分配问题。我知道它可以通过例如 Hungarian algorithm 来解决.我们应该构建共现矩阵(2 = double weight because of a chain):

   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

并以最佳方式一对一地对行和列进行配对，以使对内相似度的总和最大化。它意味着在每一行和每一列中只留下一个正值，以一种给出最大矩阵值和的方式。匈牙利算法是一种通用方法，可以给出这样的最大和(最优解)。左侧条目的总和为 8，与上面的计算结果相同:

但是，匈牙利语并不是特别快(而且不太容易编程)。我的长字符串需要另一种算法。 你能给我推荐另一种算法吗，更快更简单？请注意，我的数据是特殊情况:它是仅具有 3 个整数值的相似矩阵 - 0、1 和 2。

(使用二进制矩阵，很容易做出最佳配对。有了 3 个值，我知道该怎么做，但就准确性而言，它可以给出次优的，尽管是“好”的解决方案。是否有始终获得最佳结果的方法？)

附言重要。 我在字符串中的元素实际上不是来自有限字母表的真实字符，而是真实的单词；所以-它们来 self 事先不知道的可能无限的字母表。我不会做频率计数等预处理。我更倾向于从如上所示的矩形矩阵开始:我可以非常有效地制作具有适当 0,1,2 值的矩阵。我的主要问题是关于进一步的算法。

谢谢您(也感谢您的耐心等待)。

---

稍后更新:回复@j_random_hacker 的回答。

我喜欢提议的快速方法，它看起来很帅。但是我发现这是有问题的。下面的示例对此进行了演示。

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.

Answer 1

[编辑 23/7/2014:此答案不正确——请参阅顶部的 OP 反例。]

实际上这根本不是分配问题。

如下预处理每个字符串S:

1. 对于每个字母X，计算X在S中出现的频率，并将其存储在f1[S][X]中。
2. 对于每对相邻的字母XY，统计XY在S中出现的频率，存入f2[S][XY]。
3. 对于相邻字母 XYZ 的每个三元组，计算 XYZ 在 S 中的频率并将其存储在 f3[S][XYZ] 中。

(请参阅下文了解可能的加速。)

[编辑:修复了下面的公式以计算共享字母对中的每个字母。]

任意一对字符串 S 和 T 的相似度由 A + 2B - C 给出，其中

A = sum(min(f1[S][X],   f1[T][X]))   over all letters X
B = sum(min(f2[S][XY],  f2[T][XY]))  over all letter pairs XY
C = sum(min(f3[S][XYZ], f3[T][XYZ])) over all letter triples XYZ

A 计算 S 和 T 共享的字母数，B 计算相邻字母对的数量，C 校正 2 个共享相邻对重叠 1 个字母的情况(例如，如果 S 和 T 都是 ABC ，则 A = 3，B = 2(因为 AB 和 BC 出现在两个字符串中)并且 C = 1，因此 B 由这两对共享的代码不会被计算两次。)

如果字母表很大，可能会有很多字母对甚至更多的三元组。在这种情况下，您可以将“在 S 中至少出现一次”或“在 T 中至少出现一次”添加到定义 A、B 和 C 的每一行的末尾——也就是说，向前扫描其中一个就足够了字符串，查看其中出现的每个(唯一)字母、字母对和字母三元组。这将比较算法从字母大小的立方体更改为较小字符串长度的线性体。同样，在预处理阶段，您可以使用哈希表而不是普通数组，仅将 S 中实际出现的字母、对和三元组存储在 f1[S]、f2[S] 和 f3[S] 中。