1
iloahz 2013-09-14 10:49:17 +08:00
虽然不是很理解你说的差异,不过看起来像abs(a-b)的样子,直接减一下不就好了嘛
|
2
dragonszy OP @iloahz 好吧,这个就是同学原来的算法啊,效果不行啊。
与其说“差异性比较”不如说“相似度检测”,直接减的话00000000和00000111的差异不就很小了(还有很多此类情况),但他们差异应该要很大的。 这里相似指对应位的0,1只有1到2位的偏移或完全对齐,而且有偏移的位应当比较少。 而且“不同位占总位数百分比”这种算法也不成立,不能解决10000000和00000001这种情况,这里只有首末两位有差异,但相似度应该是很小。 |
3
txx 2013-09-14 11:04:24 +08:00
直接跑字符串模糊匹配 不好么....
|
4
binux 2013-09-14 11:15:56 +08:00
a,b异或,取1的最长距离
其实我完全不明白 111011101111 和 110110011110 凭什么就中等差异了 按最远距离算 001101110001 和 100000000001 就2位区别 按差异数量算 有6位差异 |
5
Mutoo 2013-09-14 11:32:43 +08:00
异或,代价记A
左右移位,代价记B 令B大于A,对N位数进行N次移位,统计代价合,然后评估。 |
6
Kabie 2013-09-14 13:08:37 +08:00
你连定义都定义不了怎么写算法啊……
|
7
dragonszy OP 好吧,这个是今年数学建模的B题,碎纸片拼接的题目。
碎纸片都是规则的矩形(bitmap图片),有些切在字上,所以分出矩形的左右边,然后按黑白换成1和0,比较各个图片的左右边的比特串,拼接。 关键就是一些图片的黑点比较少,传统比较难以区分相隔很远的黑点,也会认为相似度高。 毕竟不是我在做,学弟学妹在参加,我也不知道他们比较到底什么情况处理的不好,不然肯定可以针对这点优化,或取几个指数综合一下。 总之谢谢各位了! |
8
ddaii 2013-09-14 16:47:09 +08:00
有一些字是正好切在边上的,照你这种方法准确率不高啊。
|
9
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,应该可以比较好的度量两个串的差异度。 |
10
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]就是这两个串的差异度。 |
11
chemhack 2013-09-14 23:19:11 +08:00
Tanimoto coefficient
|