[program] diffのアルゴリズム

Java5で

import java.util.*;
import java.io.*;

public class Diff {
    private String oldText;
    private String newText;
    private ArrayList matchList = new ArrayList();
    
    public Diff(String oldText, String newText) {
        this.newText = newText;
        this.oldText = oldText;
        this.doCalc();
    }
    
    public String diffText() {
        ArrayList result = new ArrayList();
        int oldLineNo = 0;
        int newLineNo = 0;
        for (MatchedLineNo matchedLineNo: matchList) {
            while (oldLineNo < matchedLineNo.getOldLineNo() && oldLineNo < oldText.length) {
                result.add("- " + oldText[oldLineNo]);
                oldLineNo++;
            }
            while (newLineNo < matchedLineNo.getNewLineNo() && newLineNo < newText.length) {
                result.add("+ " + newText[newLineNo]);
                newLineNo++;
            }
            if (oldLineNo >= oldText.length) break;
            result.add("= " + oldText[matchedLineNo.getOldLineNo()]);
            oldLineNo++;
            newLineNo++;
        }
        return (String) result.toArray(new String[result.size()]);
    }
    
    public MatchedLineNo machedLineNoPair() {
        return (MatchedLineNo) matchList.toArray(new MatchedLineNo[matchList.size()]);
    }
    
    private void doCalc() {
        int oldLineNo = 0;
        int newLineNo = 0;
        while (oldLineNo < oldText.length && newLineNo < newText.length) {
            // collection matched lines
            if (lineEquals(oldText[oldLineNo], newText[newLineNo])) {
                matchList.add(new MatchedLineNo(oldLineNo, newLineNo));
                //System.out.println("[matched] " + oldLineNo + ":" + newLineNo);
                oldLineNo++;
                newLineNo++;
                continue;
            }
            
            // find next matching line: cursor down each other
            boolean found = false;
            boolean cursorOldLine = true;
            int oldLineNoSearch = oldLineNo;
            int newLineNoSearch = newLineNo;
            while (oldLineNoSearch < oldText.length || newLineNoSearch < newText.length) {
                if (cursorOldLine) {
                    oldLineNoSearch++;
                    if (oldLineNoSearch < oldText.length) {
                        if (lineEquals(oldText[oldLineNoSearch], newText[newLineNo])) {
                            oldLineNo = oldLineNoSearch;
                            found = true;
                            break;
                        }
                    }
                } else {
                    newLineNoSearch++;
                    if (newLineNoSearch < newText.length) {
                        if (lineEquals(oldText[oldLineNo], newText[newLineNoSearch])) {
                            newLineNo = newLineNoSearch;
                            found = true;
                            break;
                        }
                    }
                }
                cursorOldLine = !cursorOldLine;
            }
            if (!found) {
                oldLineNo++;
                newLineNo++;
            }
        }
    }
    
    private boolean lineEquals(String oldLine, String newLine) {
        return oldLine != null ? oldLine.equals(newLine) : newLine == null;
    }
    
    // matched line pair container
    public static class MatchedLineNo {
        private int oldLineNo;
        private int newLineNo;
        public MatchedLineNo(int oldLineNo, int newLineNo) {
            this.newLineNo = newLineNo;
            this.oldLineNo = oldLineNo;
        }
        public int getOldLineNo() {
            return this.oldLineNo;
        }
        public int getNewLineNo() {
            return this.newLineNo;
        }
    }
    
    // test command line
    public static void main(String args) throws Exception {
        if (args.length != 2) {
            System.out.println("usage: java Diff oldFilename newFilename");
        }
        String oldText = readFile(args[0]);
        String newText = readFile(args[1]);
        Diff diff = new Diff(oldText, newText);
        String diffTexts = diff.diffText();
        for (String line: diffTexts) {
            System.out.println(line);
        }
    }
    
    private static String readFile(String fileName) throws Exception {
        BufferedReader reader = new BufferedReader(new FileReader(fileName));
        ArrayList result = new ArrayList();
        for (String line = reader.readLine(); line != null; line = reader.readLine()) {
            result.add(line);
        }
        return (String) result.toArray(new String[result.size()]);
    }
}

ポイントはdiffとは「なにを見つける」処理なのか。新旧テキストからdiffで探すのは「同じ行内容の行番号のペア」のリスト。それが気が付けばあとは自明。

doCalc()メソッドでは以下のことを行い、行番号ペアを集めています：

• 1. 現在行どおしが同じ行内容となるペアを逐次貯めていく。
• 2. 違う行にあたったら、同じ行内容を探す
  • 2.1. 片方を固定（現在行）したまま、片方を一時行として一時的に下げてみる。
  • 2.2. 一時行下げを交互に行い、先に同じ行内容が見つかったほうに現在行をあわせて1へ継続。
  • 2.3. 双方の一時行が末端まできて、見つからなければ双方の現在行を下げる。
• 3. 現在行がどちらかが末端に来たら終了。

簡単ですね。もちろん行番号を一旦集めなくても、ループ中に直接出力することも可能です。