Diff 알고리즘 활용

실제 프로젝트에서 Diff 알고리즘을 활용한 예를 보도록 하겠습니다.
아래와 같은 목록을 가지고 3D로 알아서? 모델링하는 경우를 생각해 봅시다.

CONCENTRIC, FLEXIBLE HOSE, CHECK, BUTTERFLY, GATE, FLANGE

사용자가 요구 사항으로
목록의 항목을 더블 클릭했을때 해당하는 모델을 하이라이트하는 기능을 만들고자 합니다.

항목은 아래와 같은 Class로 정의됩니다.

class Item
{
	public string UID{get;set;}
	public string Type{get;set;}
}

쉽게 생각해보면 모델을 생성할 때 해당 Item의 UID를 속성을 넣어 준다면, 위 기능을 구현할 수 있습니다.

하지만 외부에서 만들어진 모델(Type은 알고 있지만 UID 값을 가지지 않음)을 가지고 위 기능을 만들려면 어떻게 해야 할까요?
먼저 모델의 UID를 대응하는 Item의 UID로 업데이트하여 동기화 시켜야 합니다.
순차적으로 나타나는 Type으로 유추하면 되지 않을까 생각할지도 모르겠지만 동일한 Type이 여러개 나올 수 있다고 생각하면 올바른 방법이 아닌것 같습니다.




이때 Diff 알고리즘을 활용할 수 있을것 같습니다. 여기서 코드를 다운받을 수 있습니다.
Type을 NewLine으로 연결하여 lhstr, rhstr를 생성합니다.

그리고 나서 DiffText 함수를 호출하면

var diffs = Diff.DiffText(lhstr, rhstr, true, true, true).Reverse();

나중에 추가, 삭제된 부분을 제거하기 위해 결과 값을 역 정렬했습니다.
lhs에서는 추가된 정보를, rhs에서는 삭제된 정보를 리턴하고 있습니다.

위 예에서 lhs에서는 2개 항목이 삭제되었고, rhs에서는 4개 항목이 추가되었다고 합니다.
변경된 항목을 제거하면 즉 lhs에서 2개 항목을 삭제하고, rhs에서 4개 항목을 삭제하면, lhs, rhs의 항목의 수는 동일하게 됩니다.

foreach (var diff in diffs)
{
    if (diff.deletedA > 0) lhs.RemoveRange(diff.StartA, diff.deletedA);
    if (diff.insertedB > 0) rhs.RemoveRange(diff.StartB, diff.insertedB);
}

이후에 rhs의 UID를 lhs의 UID로 업데이트해주면 됩니다.

if (lhs.Count == rhs.Count)
{
    for (int i = 0; i < lhs.Count; i++)
    {
        rhs[i].UID = lhs[i].UID;
    }
}

위 로직으로 두 그룹에서 최대한 많은 동일한 항목들을 찾아낼 수 있습니다.
Diff 알고리즘에 대해서는 이 글을 참조하시면 됩니다.