问一个“二进制序列差异性比较”的算法

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 4089 天前的主题，其中的信息可能已经有所发展或是发生改变。

其实这是帮同学问的

000000000001 和
100000000000 要有很大差异

000000100000 和
000001000000 差异很小

111011101111 和
110110011110 中等差异

完全一样差异为0

最好能度量差异性，二进制序列大概100位左右

我有两个想法：
第一个是每4位二进制按格雷码转换成10进制，然后逐位取差平方再平均。
第二个是借鉴Levenshtein Distance算法，看看能不能运用到这里。

因为不是我在做，所以也没编个程验证什么的。
感觉方法1在一些极端情况反映不了差异。

比如
000100000001 和
000000010000 这样应该差异大，可是因为转成格雷码十进制后，转换的数比较小，所以算差异时反而不大。

PS:各位大侠给个稍微简单一点的算法啊，同学编不了我就遭殃啦！

差异

二进制

算法

11 条回复 • 1970-01-01 08:00:00 +08:00

iloahz

2013-09-14 10:49:17 +08:00

虽然不是很理解你说的差异，不过看起来像abs(a-b)的样子，直接减一下不就好了嘛

dragonszy

2013-09-14 11:03:10 +08:00

@iloahz 好吧，这个就是同学原来的算法啊，效果不行啊。

与其说“差异性比较”不如说“相似度检测”，直接减的话00000000和00000111的差异不就很小了(还有很多此类情况)，但他们差异应该要很大的。

这里相似指对应位的0,1只有1到2位的偏移或完全对齐，而且有偏移的位应当比较少。

而且“不同位占总位数百分比”这种算法也不成立，不能解决10000000和00000001这种情况，这里只有首末两位有差异，但相似度应该是很小。

txx

2013-09-14 11:04:24 +08:00

直接跑字符串模糊匹配不好么....

binux

2013-09-14 11:15:56 +08:00

a,b异或，取1的最长距离
其实我完全不明白

111011101111 和
110110011110 凭什么就中等差异了
按最远距离算
001101110001 和
100000000001 就2位区别
按差异数量算有6位差异

Mutoo

2013-09-14 11:32:43 +08:00

异或，代价记A
左右移位，代价记B
令B大于A，对N位数进行N次移位，统计代价合，然后评估。

Kabie

2013-09-14 13:08:37 +08:00

你连定义都定义不了怎么写算法啊……

dragonszy

2013-09-14 15:27:00 +08:00

好吧，这个是今年数学建模的B题，碎纸片拼接的题目。

碎纸片都是规则的矩形(bitmap图片)，有些切在字上，所以分出矩形的左右边，然后按黑白换成1和0，比较各个图片的左右边的比特串，拼接。

关键就是一些图片的黑点比较少，传统比较难以区分相隔很远的黑点，也会认为相似度高。

毕竟不是我在做，学弟学妹在参加，我也不知道他们比较到底什么情况处理的不好，不然肯定可以针对这点优化，或取几个指数综合一下。

总之谢谢各位了！

ddaii

2013-09-14 16:47:09 +08:00

有一些字是正好切在边上的，照你这种方法准确率不高啊。

deanguqiang

2013-09-14 16:51:18 +08:00

@dragonszy
本质是还是求两个比特串的差异度，只要统计不相同的位置的多少就可以了，唯一特殊的地方是：
000000100000 和
000001000000 差异很小
这应该是考虑到两边的字有斜的笔画。，当计算a[k]和b[k]的差异度的时候还要考虑两个串周围的比特，在计算差异度的时候可以考虑：
1. 如果a[k]和b[k]都是1，那么认为这一位完全相同，差异度为0；
2. 如果其中有一位为0，那么在其周围搜索不为0的比特，找到最近的一个比特，假设相距 d，那么这一位的差异度为alpha^d，其中alpha>=1；
3. 如果两个都为零，那么两边都要做搜索，差异度应该未alpha^(d1+d2)
遍历所有的比特，应该就可以得到两个串的差异度。

alpha 应该是一个稍大于1的数，找一个合适的 alpha，应该可以比较好的度量两个串的差异度。

deanguqiang

2013-09-14 17:12:14 +08:00

貌似还有一些地方没考虑清楚，修改一下：
当计算a[k]和b[k]的差异度的时候，假设这一位的差异度为w[k]
1. 如果a[k]和b[k]都是1或者都是0，那么认为这一位完全相同，差异度为w[k]=0；
2. 如果其中有一位为1另一位为0，那么在0的周围搜索不为0的比特，找到最近的一个比特，假设相距 d，那么这一位的差异度为w[k]=alpha^d，其中 alpha>=1 是一个可调参数。
遍历后累加w[k]就是这两个串的差异度。

chemhack

2013-09-14 23:19:11 +08:00

Tanimoto coefficient