我在寻找这个算法的过程中找到了 edit distance算法,不过跟我需要的东西不是太一样。
具体的要求就是,给出两个字符串(当然这两个字符串都不会太长,而且一般都会有一定的相似性,当然也有可能完全不相似)
比如:
原始字符串:this is a strings.
目标字符串:This is not a damn string.
算法要求能够整理说从原始字符串到目标字符串所需要的编辑过程。
比如说:
1. 删掉原句开头小写的t
2. 在开头插入大写的T
3. 在某某位置处插入not
4. 在某某位置插入damn
5. 删掉某某位置的字母s
求大神帮忙!!!当然最好是JAVA写的。
多谢!
1
Kilerd 2015-06-07 09:45:43 +08:00
- this is a strings.
+ This is not a damn string. Git 的做法 ←_← |
3
Hyperion 2015-06-07 09:55:54 +08:00
从收藏夹里翻出了这个:
http://article.yeeyan.org/view/67953/33055 |
5
msg7086 2015-06-07 10:03:00 +08:00
|
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.重新拼接 |
7
binux 2015-06-07 11:38:56 +08:00 via Android
你没看懂 edit distance,这东西就是 edit distance
|
8
aheadlead 2015-06-07 11:43:31 +08:00
编辑距离+1
可以从dp的结果上反推 |
9
qiayue 2015-06-07 12:18:16 +08:00
知乎的编辑日志就是这样
|
11
jsq2627 2015-06-07 13:53:24 +08:00 via iPhone
就是编辑距离。基本的DP问题,建议好好理解下自己解决。
|
12
zmj1316 2015-06-07 18:04:57 +08:00
这个我们上数据结构课用过,记得是用LCS做的;好像是从后往前扫;反正是个DP问题
|
13
shiye515 2015-06-07 19:49:36 +08:00
|
14
faceair 2015-06-07 20:29:05 +08:00 via iPhone
不是叫 Operational Transformation 的么?
|
15
jugelizi 2015-06-07 20:54:38 +08:00
以前用最大公共子字符串比较的
|