现在的位置: 首页 > 综合 > 正文

java diff 及wiki相关

2013年10月01日 ⁄ 综合 ⁄ 共 2571字 ⁄ 字号 评论关闭

原理

diff的原理在于找两个字符串之间的最大相同子串(Longest Common Subsequence)以及编辑距离,比较有名的实现是UnixLinux上常用的diff(GNU Diff)。

实现

Java里Diff的实现我找了一下,主要是两个,java-diff 和bsmi上的Diff ,前者为LGPL,后一个为GPL。其实代码也都不多,都实现了LCS算法。前一个协议上对我们比较有利,而且文档、测试和例子多一些。

JavaDiff里主要有两个类,Diff和Difference类。前者是算法,后者是差异的表示类。下面讲一下例子:

Object[] a = new Object[] {
        
"a",
        
"b",
        
"c",
        
"d",
        
"e"
    }
;

    Object[] b 
= new Object[] {
        
"a",
        
"x",
        
"y",
        
"b",
        
"c",
        
"j",
        
"e",
    }
;

    Difference[] expected 
= new Difference[] {
        
new Difference(1-1,  1,  2),
        
new Difference(3,  3,  5,  5),
    }
;

    Diff diff 
= new Diff(a, b);
    List diffOut 
= diff.diff();


差别有三处,用两个Difference对象表示。一个Difference对象表示替换,增加,删除。Difference的构造函数:

public Difference(int delStart, int delEnd, int addStart, int addEnd)

如果delEnd或者addEnd为-1的话,就代表没有删除或者增加行为。

回到例子,两个字符串之间的差别在于,目标字符串在第1-2行(从0算起)增加了x,y,第3行的d被第5行的j替换。Difference虽然只说明了行号和动作,但我们可以推算出来增加了什么,删除了什么,替换了什么。下面是另一个更长的例子,来自测试用例:



public void testStrings1()
    
{
        Object[] a 
= new Object[] {
            
"a",
            
"b",
            
"c",
            
"e",
            
"h",
            
"j",
            
"l",
            
"m",
            
"n",
            
"p"
        }
;

        Object[] b 
= new Object[] {
            
"b",
            
"c",
            
"d",
            
"e",
            
"f",
            
"j",
            
"k",
            
"l",
            
"m",
            
"r",
            
"s",
            
"t"
        }
;

        Difference[] expected 
= new Difference[] {
            
new Difference(0,  0,  0-1),
            
new Difference(3-1,  2,  2),
            
new Difference(4,  4,  4,  4),
            
new Difference(6-1,  6,  6),
            
new Difference(8,  9,  911),
        }
;

        runDiff(a, b, expected);
    }

上面比较的都是一个个字符串的差异,推广一下,把每一行文本当作一个字母,就可以得到文件的差异。在java-diff的etc下有一个FileDiff.java,是一个很好的参考。得到之间的差异之后,我们要把这个差异表示出来,这个需要包装一下,不过难度不大。

版本保存

还有一个wiki版本的保存问题。大的维基引擎如MediaWiki(就是维基百科那个,顺便说一下,维基百科的英文版终于可以访问了)没时间研究,就是 JSPWiki也没来得及看)(JSPWiki连数据库也不用,Web用自己写的框架,可读性可能比较不行)。只研究了trac的wiki实现。trac 的wiki实现很简单,就是把每一个版本都保存在数据库,毕竟都是文本的,还可以接受。每次比较的时候就从数据库里取两个版本出来做一个diff,具体实 现在PYTHON/site-packages/trac/wiki/web_ui.py(_render_diff函数)。trac提供两种形式的 diff结果,一个是tabular的表格形式,就是很直观的对比,还有一个是Unified的形式,也就是经常看见的diff结果。这是通过页面上 javascript读table里的文字转换成Unified格式的diff文本,虽然个人不推荐这种方式。wiki的文本修改又有一个特点,就是每一 行其实内容可能比较多,只改了几个字,这样就要对这一行的两个版本再做一个diff,然后把删除的文本用<del>标签,增加的文本用 <ins>标签展示出来。

最后提一下JSR-170,一个用来管理仓库内容(主要是大型CMS)的API,支持版本控制,存储多元化,很复杂,有两个商业实现和一个Apache JackRabbit的开源实现,这里 是一个参考资料。JSR170也是里面的例子也是把每一个版本都存储下来。

参考资料

 

抱歉!评论已关闭.