Listの編集距離（Java）

編集距離のList版。
Java17で簡単な動作確認しましたが、Java8でも動くと思います。

動機

集合（Set）での類似度（Jaccard係数、Dice係数、Simpson係数、など）のような感じで、順番を考慮した類似度を使用したかったため。

ソースコード

import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class EditDistance<T> {
	Map<Integer, Map<Integer, Integer>> memo;
	
	public EditDistance() {
		memo = new HashMap<Integer, Map<Integer, Integer>>();
	}
	
	public int distance(List<T> list1, List<T> list2) {
		if (list1.isEmpty()) return list2.size();
		if (list2.isEmpty()) return list1.size();
		
		// このフェーズでは一致している場合
		if (list1.get(0).equals(list2.get(0)))
			return distance(list1.subList(1, list1.size())
					, list2.subList(1, list2.size()));
		
		// 以下は一致していない場合
		int diff = -1;
		//メモで探す
		if (memo.containsKey(list1.hashCode()))
			if (memo.get(list1.hashCode()).containsKey(list2.hashCode())) {
				diff = memo.get(list1.hashCode()).get(list2.hashCode());
				System.out.println("get from memo " + diff);
			}
		
		//メモにない場合
		if (diff == -1) {
			int l1 = distance(list1, list2.subList(1, list2.size()));
			int l2 = distance(list1.subList(1, list1.size()), list2);
			int l3 = distance(list1.subList(1, list1.size())
					, list2.subList(1, list2.size()));
			
			// l1とl2とl3のうち最小の値を求め、+1する
            // （+1は、このフェーズでは一致していないため）
			diff = Math.min(l1, Math.min(l2, l3)) + 1;
			
			// メモする
			Map<Integer, Integer> m = new HashMap<Integer, Integer>();
			m.put(list2.hashCode(), diff);
			memo.put(list1.hashCode(), m);
		}
		
		return diff;
	}

	public void clearMemo() {
		memo.clear();
	}
	
	public void printMemo() {
		System.out.println("print memo");
		memo.entrySet().forEach(System.out::println);
	}

簡単な動作確認

	public static void main(String[] args) {
		EditDistance<String> test = new EditDistance<>();
		
		//一致するリスト
		// 0になることを期待
		List<String> list1 = Arrays.asList("test1", "test2", "test3");
		List<String> list2 = Arrays.asList("test1", "test2", "test3");
		
		System.out.println("--- ---");
		System.out.println("dist : " + test.distance(list1, list2));
		System.out.println("---");
		test.printMemo();
		test.clearMemo();
		test.printMemo();
		
		// 一致しないリスト
		// 操作1: list1の先頭のtest2を削除
		// 操作2: list1の２つ目の要素にtest2を追加
		// 操作3: list1の最後にtest4を追加
		// でlist1とlist2は一致するはずなので3が返るを期待
		list1 = Arrays.asList("test2", "test1", "test3", "test4");
		list2 = Arrays.asList("test1", "test2", "test3");
		System.out.println("--- ---");
		System.out.println("dist : " + test.distance(list1, list2));
		System.out.println("---");
		test.printMemo();
		test.clearMemo();
		test.printMemo();
	}
}

動いているっぽい。。

--- ---
dist : 0
---
print memo
print memo
--- ---
get from memo 2
get from memo 2
dist : 3
---
print memo
110251521={110251520=1}
958565345={2105574015=3}
-766918686={-766918718=2}
2105574047={-766918718=2}
print memo