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

求一个算法:一个字符串变成另一个字符串的编辑过程

  •  
  •   hellogbk · 2015-06-07 09:34:54 +08:00 · 2509 次点击
    这是一个创建于 3446 天前的主题,其中的信息可能已经有所发展或是发生改变。

    我在寻找这个算法的过程中找到了 edit distance算法,不过跟我需要的东西不是太一样。
    具体的要求就是,给出两个字符串(当然这两个字符串都不会太长,而且一般都会有一定的相似性,当然也有可能完全不相似)

    比如:
    原始字符串:this is a strings.
    目标字符串:This is not a damn string.

    算法要求能够整理说从原始字符串到目标字符串所需要的编辑过程。
    比如说:
    1. 删掉原句开头小写的t
    2. 在开头插入大写的T
    3. 在某某位置处插入not
    4. 在某某位置插入damn
    5. 删掉某某位置的字母s

    求大神帮忙!!!当然最好是JAVA写的。
    多谢!

    15 条回复    2015-06-07 20:54:38 +08:00
    Kilerd
        1
    Kilerd  
       2015-06-07 09:45:43 +08:00
    - this is a strings.
    + This is not a damn string.

    Git 的做法 ←_←
    hellogbk
        2
    hellogbk  
    OP
       2015-06-07 09:48:21 +08:00
    @Kilerd 呃好吧, 我需要的是一个详细的编辑过程呀。。。
    Hyperion
        3
    Hyperion  
       2015-06-07 09:55:54 +08:00
    从收藏夹里翻出了这个:
    http://article.yeeyan.org/view/67953/33055
    Kilerd
        4
    Kilerd  
       2015-06-07 09:57:03 +08:00
    @hellogbk 详细算法,就是伸手党了。。。。。
    msg7086
        5
    msg7086  
       2015-06-07 10:03:00 +08:00
    https://leetcode.com/problems/edit-distance/

    其实就是Edit Distance,只不过原题是以字母为单位,而你这是可以把字母合并成词为单位。
    pimin
        6
    pimin  
       2015-06-07 10:04:00 +08:00
    1.原句拆分,str1="this is a strings.";str2="This is not a damn string.";
    拆分成单词词组,words1={"this","is","a","strings"}
    1.首字母强制大写转换,
    2.找到合适的位置插入你想要插入的单词,比如判断在is,are,之类be动词前后做处理.如果没有怎么处理.
    3.重新拼接
    binux
        7
    binux  
       2015-06-07 11:38:56 +08:00 via Android
    你没看懂 edit distance,这东西就是 edit distance
    aheadlead
        8
    aheadlead  
       2015-06-07 11:43:31 +08:00
    编辑距离+1
    可以从dp的结果上反推
    qiayue
        9
    qiayue  
       2015-06-07 12:18:16 +08:00
    知乎的编辑日志就是这样
    qiayue
        10
    qiayue  
       2015-06-07 12:20:02 +08:00
    @pimin 你不能仅仅根据楼主举的这个例子来写算法
    jsq2627
        11
    jsq2627  
       2015-06-07 13:53:24 +08:00 via iPhone
    就是编辑距离。基本的DP问题,建议好好理解下自己解决。
    zmj1316
        12
    zmj1316  
       2015-06-07 18:04:57 +08:00
    这个我们上数据结构课用过,记得是用LCS做的;好像是从后往前扫;反正是个DP问题
    shiye515
        13
    shiye515  
       2015-06-07 19:49:36 +08:00
    faceair
        14
    faceair  
       2015-06-07 20:29:05 +08:00 via iPhone
    不是叫 Operational Transformation 的么?
    jugelizi
        15
    jugelizi  
       2015-06-07 20:54:38 +08:00
    以前用最大公共子字符串比较的
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1033 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 20:30 · PVG 04:30 · LAX 12:30 · JFK 15:30
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.