一个无聊的算法优化：找出有最多相同tag的主题。

爱的奉献

过去我做的课题是蛋白质折叠，其中用到一个算法，前不久在做一个论文库的tag系统的时候意识到这两者其实是同一个问题，于是就把原来的优化算法改进了一下，不过想了一下，估计也没有什么系统会用吧，但是基于不想浪费的原则，就把这个优化写一下。
/ O- M. h; d+ J
这个算法是用来计算两个主题在tag上面的相似度。假如一个主题的tag的数目是有限的（用在论文库上，还有一个限制就是主题词数目是一样多的），那么我们可以找出所有和它有至少一个tag相同的主题，然后在里面找出tag相同数目最多的那个主题作为最相似主题。

* j* W+ j. w% S) u  |( S8 ~# G最简单的想法是做一个二叉树，第一级是有没有tag a，第二级是有没有tag b，但是这个和二叉树不同，二叉树的不同级优先级是不一样的，而这个问题里面优先级是一样的。
) h( C0 }  s0 u( O3 o0 s0 i3 R' P) ~$ w0 L9 t然后的想法是仍然做一个二叉树，不过使用贪恋法找一个尝试解，然后其实根本不必算到最后就可以砍掉很多分支。因为假如最优解是5个相同，你现在得分只有1，然后下面只剩3层，可想最优情况也只能得到4，所以整个分支都可以砍掉。当找到更优解的时候就替换掉暂时的尝试最优解。
& v- J' z- ?# J' L
这在速度上当然是最优解法，不过有没有空间上花费较少，而效率上下降不多的解法呢？
0 b' l& K# `( r+ X- g我想了一下，使用这种方法：
1 L, P) }* R2 S0 C1 q1 b把每种tag按照有无，把一个主题的tag编码成一个二进制串，第n位为1则表示拥有第n个tag。里面的1的数目是固定的。然后把两个主题的二进制表示进行按位and操作，结果字节用查表法就可以查出里面1的数目，最后相加，可以节省一点if操作。

+ _2 A; H/ [6 _( D/ g; S然后，我们把二进制表示为这样一种排序，最低位是0110,0110,0110重复，第二位是0011,1100,0011,1100重复，第三位是0000,1111,1111,0000，重复，简单说就是呈现一种回文的结构。这种排序表示为数字，就是0,1,3,2,6,7,5,4的顺序……
000
001
9 C3 @6 b# m0 b2 {( c011
010
: e1 ?  m2 `8 }% I: ^110
7 ?, t* G. d7 x1 K3 |, E7 r+ L0 O111
" i- l. w+ b& W  [101
' O$ g0 A- B3 ]7 Z$ N3 L" `100
, {* h$ X" M3 n
可以看到，任意相邻数字的二进制表示永远只相差一位，而且相邻的高位几乎总是相同的（用数学归纳法可以简单证明）。这就保证了，如果我找到一个优质解，那么很大概率在它的附近找到另外一个优质解（但只有一定概率，不是肯定保证）。我们把tag的二进制数表示按照这种方法排序后，我们就知道了所有相邻位置相同到第几位。一旦知道一个条目的二进制表示到倒数第四个字节得分1，那么肯定不会超过最高得分6，然后接下来所有和前一个位置的前四位相同的一系列条目都可以跳过。 由于每个条目和前一个条目相同到第几位是可以预先算好的，所以这个算法几乎不用存储中间结果。

其实不按回文排列排序也可以，但是在密集区域这样可能更好，特别是可以用普通的对半分解排序函数更有效地找到试探解，这使得新数据的插入，删除都可以使用传统技术而不必把效率下降太多。
8 J/ V+ k- |; S3 h  U7 d
这种表虽然效率不是最高，不过考虑到tag往往是幂数分形分布的（也就是最大类有1000个，次大类100个，次次大类10个），这种算法和二叉树只有常数倍的差距，即理论上是平均情况为O(log_2 N) 和O(N^[1/m]，实际都退化到O(N^[1/m]。程序的复杂度更小，空间占用为O(1)，而数据的插入，排序都可以用传统的线性排序技术，属于一种值得推荐的算法。


1 l) Z, l% l+ o$ m1 W. R可惜的是，由于限定了条件是tag数有限，所以应用范围不广。这种算法不知道有没有人发明过（我觉得应该有，但是不会是这个领域），在基于关键词的倒排表里面可能有一些用处。

, P5 h% w9 R% E8 t