V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
dragonszy
V2EX  ›  问与答

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

  •  
  •   dragonszy · 2013-09-14 10:44:24 +08:00 · 4348 次点击
    这是一个创建于 4077 天前的主题,其中的信息可能已经有所发展或是发生改变。
    其实这是帮同学问的

    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
        1
    iloahz  
       2013-09-14 10:49:17 +08:00
    虽然不是很理解你说的差异,不过看起来像abs(a-b)的样子,直接减一下不就好了嘛
    dragonszy
        2
    dragonszy  
    OP
       2013-09-14 11:03:10 +08:00
    @iloahz 好吧,这个就是同学原来的算法啊,效果不行啊。

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

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

    而且“不同位占总位数百分比”这种算法也不成立,不能解决10000000和00000001这种情况,这里只有首末两位有差异,但相似度应该是很小。
    txx
        3
    txx  
       2013-09-14 11:04:24 +08:00
    直接跑字符串模糊匹配 不好么....
    binux
        4
    binux  
       2013-09-14 11:15:56 +08:00
    a,b异或,取1的最长距离
    其实我完全不明白

    111011101111 和
    110110011110 凭什么就中等差异了
    按最远距离算
    001101110001 和
    100000000001 就2位区别
    按差异数量算 有6位差异
    Mutoo
        5
    Mutoo  
       2013-09-14 11:32:43 +08:00
    异或,代价记A
    左右移位,代价记B
    令B大于A,对N位数进行N次移位,统计代价合,然后评估。
    Kabie
        6
    Kabie  
       2013-09-14 13:08:37 +08:00
    你连定义都定义不了怎么写算法啊……
    dragonszy
        7
    dragonszy  
    OP
       2013-09-14 15:27:00 +08:00
    好吧,这个是今年数学建模的B题,碎纸片拼接的题目。

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

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

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

    总之谢谢各位了!
    ddaii
        8
    ddaii  
       2013-09-14 16:47:09 +08:00
    有一些字是正好切在边上的,照你这种方法准确率不高啊。
    deanguqiang
        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,应该可以比较好的度量两个串的差异度。
    deanguqiang
        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]就是这两个串的差异度。
    chemhack
        11
    chemhack  
       2013-09-14 23:19:11 +08:00
    Tanimoto coefficient
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1034 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 20:21 · PVG 04:21 · LAX 12:21 · JFK 15:21
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.