diffっぽいもの

以前、•¶‘”äŠridiffjƒAƒ‹ƒSƒŠƒYƒ€のページを見てdiffに興味を持ったのだが、なかなか手をつける機会がなかった。
しかしこのたび、公的（？）な機会に巡り合えそうなのでとりあえず作ってみた（言語はJava）。
編集距離の導出方法はいくつか存在するが、今回はWu氏らの計算量O(NP)のアルゴリズムを用いた。
Wu氏らの論文An O(NP) Sequence Comparison Algorithm（PDF）に詳細が書かれているので説明は割愛するが、今回作成したプログラムは論文内のFigure 6をほぼそのまま適用している。
もっときちんとした実装を見たい場合は、言語は異なるが

• 2009-04-27 - エンジニアのソフトウェア的愛情
• 2007-03-15 - 当面C#と.NETな記録

などをみると参考になるかと。

以下、プログラム（長くて申し訳ない）

import java.util.Arrays;
import java.util.Iterator;
import java.util.Vector;

public class Diff<T> {
	
	private T a[];
	private T b[];
	private int M;
	private int N;
	private int editDistance;
	private Node current;
	public boolean exchanged;
	
	public Diff(T a[], T b[]) {
		
		this.a = a; this.b = b;
		M = this.a.length; N = this.b.length;
		editDistance = 0;
		exchanged = false;
		
		if (M > N) {
			T tmp[] = this.a; this.a = this.b; this.b = tmp;
			M = this.a.length; N = this.b.length;
			exchanged = true;
		}
	}
	
	public int getEditDistance () { return editDistance; }
	
	public void compose () {
		
		int p = -1;
		int size = M + N + 3;
		int delta = N - M;
		int offset = M + 1;
		int fp[] = new int[size];
		Arrays.fill(fp, -1);
		
		do {
			p++;
			for (int k=-p;k<=delta-1;k++) {
				fp[k+offset] = snake(k, fp[k-1+offset]+1, fp[k+1+offset]);
			}
			for (int k=delta+p;k>=delta+1;k--) {
				fp[k+offset] = snake(k, fp[k-1+offset]+1, fp[k+1+offset]);
			}
			fp[delta+offset] = snake(delta, fp[delta-1+offset]+1, fp[delta+1+offset]);
		} while(fp[delta+offset] != N);

		editDistance = delta + 2 * p;
		printDiff();
	}

	private int snake(int k, int p, int pp) {
		
		int y, x;
		
		if(p > pp) {
			y = p;
			x = y - k;
			current = new Node(x,y,Node.Type.DELETE,current);
		} else {
			y = pp;
			x = y - k;
			current = new Node(x,y,Node.Type.ADD,current);
		}
		
		while (x < M && y < N && a[x].equals(b[y])) {
			current = new Node(++x,++y,Node.Type.COMMON,current);
		}
		
		return y;
	}
	
	private void printDiff() {
		
		Node parent;
		Vector<Node> list = new Vector<Node>();
		
		while((parent = current.prev) != null) {
			if(current.type == Node.Type.DELETE && parent.x == current.x && parent.y == current.y-1) {}
			else if(current.type == Node.Type.ADD && parent.x == current.x-1 && parent.y == current.y) {}
			else if(current.type == Node.Type.COMMON && parent.x == current.x-1 && parent.y == current.y-1) {}
			else {
				current.prev = parent.prev;
				continue;
			}
			list.add(0,current);
			current = parent;
		}
		
		Iterator<Node> itr = list.iterator();
		while(itr.hasNext()) printNode(itr.next());
		System.out.println();
	}
	
	private void printNode(Node node) {
		if(node.type == Node.Type.COMMON) System.out.print("(C " + b[node.y-1] + ")");
		else if(node.type == Node.Type.DELETE){
			String type = (exchanged) ? "(A " : "(D ";
			System.out.print(type + b[node.y-1] + ")");
		}
		else if(node.type == Node.Type.ADD){
			String type = (exchanged)?"(D ":"(A ";
			System.out.print(type + a[node.x-1] + ")");
		}
	}
}

public class Node {
	public Node prev;
	public Type type;
	public int x;
	public int y;
	
	public Node(int x2, int y2, Type t, Node p) {
		x = x2; y = y2; type = t; prev = p;
	}
	
	enum Type { DELETE, COMMON, ADD};
}

都合によりインデントは無茶苦茶である。
ちなみに編集距離導出部分まではTDDを行っていたが、体力切れや場当たり的対応により差分導出部分あたりはかなりグダグダな実装なってしまった（私では2日だとこれくらいが限界ということか）。
しかし、テストによって何度も救われたので体力のある限りはTDDでがんばってみたいところである。

今回は通称O(NP)法を用いて実装したが、余裕があるときにビットパラレル法もやってみようと思う。