V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
matepi
V2EX  ›  Java

Java 两有序列表内的差异节点的个数

  •  
  •   matepi · 2019-12-31 14:23:15 +08:00 · 2207 次点击
    这是一个创建于 1550 天前的主题,其中的信息可能已经有所发展或是发生改变。
    已知列表有序、内部节点可重复

    AA
    AA
    差异=0

    AA
    AB
    差异=1

    AAA
    ACA
    差异=1

    AA
    ACA
    差异=1 (一个缺少,但后续的要继续同步比较)

    AABBCC
    ABDCE
    差异=3

    这样的定义、尤其是在节点可重复时是否会有结果不确定性?
    该用什么样的算法?
    在 Java 里面已实现的轮子有吗?
    16 条回复    2020-01-01 13:48:40 +08:00
    chendy
        1
    chendy  
       2019-12-31 14:32:28 +08:00
    最…最小编辑距离?
    commons-text 里可能有现成的吧
    xxdd
        2
    xxdd  
       2019-12-31 14:46:47 +08:00
    先 sort
    然后 LCS
    matepi
        3
    matepi  
    OP
       2019-12-31 14:47:22 +08:00
    @chendy 恩,应该类似的了。不过问题可能表达的不太好,这里的 A,不是简单的文字 A,而是一个具体对象、或者说具体这个对象的 hash
    matepi
        4
    matepi  
    OP
       2019-12-31 14:47:49 +08:00
    @xxdd sort 会损失有序性
    xxdd
        5
    xxdd  
       2019-12-31 15:01:04 +08:00
    那就 LCS 就好了 长度减一下
    ffbh
        6
    ffbh  
       2019-12-31 17:28:08 +08:00
    差异节点个数是怎么定义的?
    比如
    ABC
    ACB
    差异=?
    matepi
        7
    matepi  
    OP
       2019-12-31 17:29:07 +08:00 via iPhone
    @ffbh 差异=2,因为有序
    ffbh
        8
    ffbh  
       2019-12-31 17:36:03 +08:00
    我还是不明白这个差异个数是怎么计算的,能给出详细的定义么
    比如这个
    AABBCC
    ABDCE
    差异=3
    为啥是 3
    ffbh
        9
    ffbh  
       2019-12-31 17:40:24 +08:00
    综合这么多测试例子,我唯一得出的结论
    差异个数=min(删除两个字符串字母的个数使得两个字符串长度相等 + 删除后两个字符串不相同位的数量)
    Sunyanzi
        10
    Sunyanzi  
       2019-12-31 17:41:05 +08:00
    @ffbh 关键字 Levenshtein distance ... 我觉得这么常见的算法肯定有现成的轮子 ...
    ffbh
        11
    ffbh  
       2019-12-31 17:44:05 +08:00
    @Sunyanzi
    是有点像这个,但是楼主也没给出具体的定义呀
    matepi
        12
    matepi  
    OP
       2019-12-31 17:49:39 +08:00 via iPhone
    @Sunyanzi
    @ffbh
    是的,就是 editing distance 或者说 Levenshtein distance,commons-text 有轮子
    但问题是是针对文字 character 的,没有对于对象或者 word 适用的轮子
    ffbh
        13
    ffbh  
       2019-12-31 17:51:20 +08:00
    @matepi
    你把==改成 equals 不可以么
    matepi
        14
    matepi  
    OP
       2019-12-31 17:55:00 +08:00 via iPhone
    @ffbh 也可以考虑,但比造轮子更难过的事情,就是改别人的轮子啊
    先凑活着放了个不考虑有序性的上去跑着了
    BiteTheDust
        15
    BiteTheDust  
       2020-01-01 12:07:15 +08:00
    看你这描述就是求一个最长公共子列 作为两列表的相同部分?
    srlp
        16
    srlp  
       2020-01-01 13:48:40 +08:00 via iPhone
    既然明确明确是 edit distance 了,那么网上搜搜针对 String 的源代码,改为 List<Object> 就可以了
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2764 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 12:27 · PVG 20:27 · LAX 05:27 · JFK 08:27
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.