시퀀스 비교 알고리즘 — LCS, 최소 편집 거리, diff

이 문서는 LCS(Longest Common Subsequence, 최장 공통 부분 수열), 최소 편집 거리(Minimum Edit Distance), 최단 편집 스크립트(Shortest Edit Script, SES)가 어떻게 연결되는지 설명하고, 고전적인 동적 계획법(Dynamic Programming) 표 채우기부터 Myers의 O(ND) diff 알고리즘, Git의 patience와 histogram까지 한 흐름으로 정리합니다. 알고리즘 강의처럼 수식만 나열하지 않고, 문자 단위 예제와 줄 단위 예제를 나란히 놓고 왜 실제 diff가 이런 형태의 출력으로 보이는지까지 연결합니다.

시퀀스 비교의 기본 관점

시퀀스(Sequence) 비교 문제는 "두 입력에서 무엇을 같다고 볼 것인가"를 정하는 순간 시작됩니다. 문자열 알고리즘 교과서에서는 보통 문자를 원소로 사용하지만, 실제 개발 도구는 줄, 토큰, AST 노드 같은 더 큰 단위를 원소로 삼기도 합니다. diff는 기본적으로 줄 단위 시퀀스를 입력으로 보고, Git의 다양한 diff 알고리즘도 이 줄 시퀀스를 어떻게 정렬하고 묶을지에 집중합니다.

여기서 중요한 점은 LCS는 연속 구간을 찾는 문제가 아니라 순서를 보존하는 공통 골격을 찾는 문제라는 사실입니다. 예를 들어 A B C D와 A E B D의 LCS는 A B D입니다. 가운데 원소가 끊겨 있어도 순서만 유지되면 같은 부분 수열로 인정합니다.

LCS 정의와 성질

LCS는 두 시퀀스에서 모두 등장하면서 상대 순서를 유지하는 부분 수열 중 가장 긴 것을 말합니다. 길이만 중요한 것이 아니라 어떤 원소를 공통 골격으로 남길지 결정하는 기준이라는 점이 핵심입니다. 이 골격을 기준으로 나머지 원소를 삭제와 추가로 해석하면, 사람이 읽는 diff와 기계가 적용하는 패치가 동시에 설명됩니다.

# 예제 1: 작은 문자열
A = "ABCD"
B = "AEBD"
LCS = "ABD"  # 길이 3

# 예제 2: 고전 교과서 예제
A = "ABCBDAB"
B = "BDCABA"
LCS 길이 = 4

이 점이 Git의 patience, histogram 같은 가독성 지향 알고리즘이 필요한 이유이기도 합니다. Myers는 최소 편집 길이를 잘 찾지만, 공통 줄이 너무 많거나 코드 이동이 큰 상황에서는 사람이 기대하는 경계와 다른 헝크를 만들 수 있습니다.

고전 예제 완전 전개

알고리즘 책에서 가장 자주 등장하는 예제는 A = ABCBDAB, B = BDCABA입니다. 이 예제가 좋은 이유는 최적 길이는 같지만 실제 LCS는 여러 개라는 점을 한 번에 보여 주기 때문입니다. 즉 "정답 길이 4"는 쉽게 말할 수 있지만, 어떤 4개 원소를 남길지는 선택 여지가 있습니다.

이 예제가 시사하는 바는 단순합니다. LCS 길이만 알아서는 실제 diff 모양을 완전히 예측할 수 없습니다. 어떤 공통 원소를 앵커로 삼는지에 따라 헝크가 나뉘는 방식이 달라지고, 그 차이가 리뷰 체감 품질로 이어집니다. Git이 Myers만이 아니라 patience, histogram을 제공하는 이유도 여기에 있습니다.

동적 계획법 표 채우기

고전적인 LCS 계산은 2차원 표를 채우는 방식입니다. L[i][j]를 "A의 앞 i개와 B의 앞 j개의 LCS 길이"로 정의하면, 더 작은 접두부 문제를 이용해 큰 문제를 해결할 수 있습니다. 교육용으로는 가장 직관적이지만, 큰 파일에서는 표가 너무 커져 실제 diff 도구의 기본 구현으로 쓰기에는 부담이 큽니다.

# L[i][j] = A 앞 i개와 B 앞 j개의 LCS 길이
if A[i - 1] == B[j - 1]:
    L[i][j] = L[i - 1][j - 1] + 1
else:
    L[i][j] = max(L[i - 1][j], L[i][j - 1])

이 방식의 시간 복잡도는 O(nm)이고, 표 전체를 저장하면 공간 복잡도도 O(nm)입니다. 문자 수가 몇십 개면 충분히 괜찮지만, 실제 소스 파일은 줄 수가 수천에서 수만까지 커질 수 있으므로 더 실용적인 방법이 필요합니다.

LCS 복원 절차

표의 오른쪽 아래에는 LCS 길이만 들어 있습니다. 실제로 어떤 공통 원소를 남길지 알아내려면 표를 거꾸로 따라 올라가야 합니다. 이 단계가 있어야 문자 예제에서는 실제 부분 수열을 복원할 수 있고, 줄 예제에서는 어떤 줄이 문맥 줄로 남고 어떤 줄이 추가/삭제 줄이 되는지 설명할 수 있습니다.

1. 문자가 같으면 대각선으로 이동
   현재 문자를 LCS 결과 앞에 붙이고 왼쪽 위 칸으로 이동합니다.
2. 문자가 다르면 더 큰 값을 준 방향으로 이동
   위와 왼쪽 중 LCS 길이가 유지되는 방향으로 이동합니다.
3. 행 또는 열이 0이 되면 종료
   접두부 한쪽이 비면 더 이상 공통 원소를 찾을 수 없습니다.

# 표를 거꾸로 따라 LCS 자체를 복원
result = []
while i > 0 and j > 0:
    if A[i - 1] == B[j - 1]:
        result.prepend(A[i - 1])
        i -= 1
        j -= 1
    elif L[i - 1][j] >= L[i][j - 1]:
        i -= 1
    else:
        j -= 1

이 절차를 방금 예제에 적용하면 ABD를 얻습니다. 하지만 이 방식은 여전히 전체 표가 필요합니다. 따라서 입력이 커질수록 길이를 설명하는 데는 좋지만 실전 구현으로는 무거운 방법이 됩니다.

공간 최적화와 선형 메모리

동적 계획법 표의 점화식은 현재 행을 계산할 때 바로 이전 행과 현재 행의 왼쪽 칸만 필요합니다. 따라서 LCS 길이만 구할 목적이라면 표 전체를 저장할 필요가 없습니다. 이때 공간 복잡도를 O(nm)에서 O(min(n,m)) 수준으로 줄일 수 있습니다.

실무에서는 이 차이가 큽니다. 문자열 두 개는 짧아 보여도, 줄 단위 입력으로 바꾸면 수만 행짜리 비교가 흔해집니다. 표 전체를 메모리에 두면 설명은 쉬워도 캐시(Cache) 친화성이 떨어지고 메모리 사용량이 급격히 커집니다. 반대로 한 행 또는 두 행만 유지하면 길이 계산 자체는 훨씬 가볍게 수행할 수 있습니다.

static int lcs_len_row(const char *a, size_t n,
                       const char *b, size_t m)
{
    int *prev = calloc(m + 1, sizeof(*prev));
    int *cur = calloc(m + 1, sizeof(*cur));
    size_t i, j;

    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            if (a[i - 1] == b[j - 1])
                cur[j] = prev[j - 1] + 1;
            else
                cur[j] = prev[j] > cur[j - 1] ? prev[j] : cur[j - 1];
        }

        memcpy(prev, cur, (m + 1) * sizeof(*prev));
        memset(cur, 0, (m + 1) * sizeof(*cur));
    }

    i = prev[m];
    free(cur);
    free(prev);
    return i;
}

Hirschberg는 전방 계산과 역방 계산을 결합해 어느 지점에서 문제를 둘로 나눌지 찾고, 이를 재귀적으로 반복해 실제 LCS를 복원합니다. 시간 복잡도는 여전히 O(nm)이지만, 공간 복잡도는 선형 수준으로 줄일 수 있어 메모리 제약이 큰 환경에서 유용합니다.

구현 예제: DP로 LCS 자체 복원하기

길이만 구하는 예제는 원리를 설명하기에 좋지만, 실제로는 "공통 부분 수열 자체"를 얻고 싶은 경우가 많습니다. 아래 예제는 가장 직관적인 방식으로 전체 표를 채운 뒤 역추적(Backtrace)해 LCS 문자열을 복원합니다. 문자 비교 예제로 작성했지만, 비교 단위를 한 줄로 바꾸면 줄 시퀀스에도 같은 구조를 적용할 수 있습니다.

#include <stdlib.h>
#include <string.h>

static char *lcs_build(const char *a, const char *b)
{
    size_t n = strlen(a);
    size_t m = strlen(b);
    size_t i, j, pos;
    unsigned int *dp;
    char *out;

    dp = calloc((n + 1) * (m + 1), sizeof(*dp));
    if (!dp)
        return NULL;

#define DP(x, y) dp[(x) * (m + 1) + (y)]

    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            if (a[i - 1] == b[j - 1])
                DP(i, j) = DP(i - 1, j - 1) + 1;
            else if (DP(i - 1, j) >= DP(i, j - 1))
                DP(i, j) = DP(i - 1, j);
            else
                DP(i, j) = DP(i, j - 1);
        }
    }

    out = malloc(DP(n, m) + 1);
    if (!out) {
        free(dp);
        return NULL;
    }

    pos = DP(n, m);
    out[pos] = '\\0';
    i = n;
    j = m;

    while (i > 0 && j > 0) {
        if (a[i - 1] == b[j - 1]) {
            out[--pos] = a[i - 1];
            i--;
            j--;
        } else if (DP(i - 1, j) >= DP(i, j - 1)) {
            i--;
        } else {
            j--;
        }
    }

    free(dp);
    return out;
}

이 구현의 장점은 이해하기 쉽고 디버깅(Debugging)이 단순하다는 점입니다. 반면 표 전체를 유지하므로 메모리 사용량이 큽니다. 예를 들어 두 입력 길이가 각각 10,000이면 표 원소 수는 1억 개가 되어, 원소 타입을 4바이트로 잡을 경우 표만 약 400MB가 필요합니다. 이 때문에 실제 diff 구현은 같은 정확성을 더 경제적으로 얻는 방향으로 진화했습니다.

최소 편집 거리와 SES 관계

diff에서 더 직접적인 결과는 LCS 그 자체보다 SES입니다. 전통적인 diff 모델은 치환을 독립 연산으로 두지 않고, 삭제 + 추가의 조합으로 해석합니다. 그러면 원본 길이를 n, 수정본 길이를 m, LCS 길이를 L이라 할 때 다음 관계가 바로 나옵니다.

# 공통 골격에 남는 원소 수 = L
삭제 수 = n - L
추가 수 = m - L
SES 길이 D = (n - L) + (m - L) = n + m - 2L

즉 LCS와 SES는 서로 다른 문제처럼 보이지만, 실제로는 같은 정보를 다른 관점에서 보는 것입니다. LCS는 "무엇을 남길 것인가"를 말하고, SES는 "무엇을 지우고 넣을 것인가"를 말합니다.

편집 그래프와 Myers O(ND)

Myers의 핵심 아이디어는 LCS 표를 전부 채우는 대신, 편집 그래프(Edit Graph)에서 짧은 편집 경로를 직접 찾는 것입니다. x축은 원본 위치, y축은 수정본 위치를 나타내고, 오른쪽 이동은 삭제, 아래 이동은 추가, 대각선 이동은 공통 원소 소비를 뜻합니다. 논문은 두 시퀀스 길이 합을 N으로 두고 복잡도를 O(ND)로 표기합니다.

이 방식이 실전에서 강력한 이유는 대부분의 소스 수정이 "전체를 새로 쓰는 작업"이 아니라 "대부분 비슷하고 일부만 달라지는 작업"이기 때문입니다. 차이가 작을수록 D가 작아지고, Myers는 이 특성을 활용해 큰 파일도 실용적으로 처리합니다.

Myers 탐색 추적

Myers를 처음 접할 때 가장 어려운 부분은 D와 대각선 k = x - y가 실제로 어떻게 움직이는지입니다. 아래 표는 앞서 사용한 A = ABCD, B = AEBD 예제를 대상으로, 각 편집 거리 단계에서 가장 멀리 전진한 좌표를 요약한 것입니다.

이 표에서 중요한 것은 Myers가 모든 좌표를 다 살피지 않는다는 점입니다. 각 D마다 "각 대각선에서 가장 멀리 간 지점"만 유지하면 되므로, 완전한 n × m 표를 유지하는 동적 계획법보다 훨씬 경제적입니다.

# Myers 사고방식 요약
D = 0부터 증가시키며
    각 대각선 k에서
        가장 멀리 도달한 x를 기록
        가능한 만큼 대각선으로 미끄러져 전진
도착점 (n, m)에 처음 닿는 순간 종료

즉 Myers는 "최단 편집 경로를 먼저 찾는다"는 점에서 BFS와 비슷한 감각을 줍니다. 다만 실제 구현은 대각선별 최원점 추적을 통해 매우 압축된 상태만 저장합니다. 이 설계 덕분에 입력이 비슷한 일반적인 소스 비교에서 강한 성능을 보입니다.

구현 예제: Myers로 SES 길이 계산하기

아래 코드는 Myers의 핵심 루프만 남긴 축약 구현입니다. 목적은 편집 스크립트 전체를 복원하는 것이 아니라 SES 길이를 계산하는 것입니다. 실제 diff는 여기에 trace 저장과 헝크 조립, 공백/함수 경계 같은 후처리를 더합니다.

#include <stdlib.h>
#include <string.h>

static int ses_len_myers(const char **a, int n,
                         const char **b, int m)
{
    int max = n + m;
    int offset = max;
    int *v = calloc(2 * max + 1, sizeof(*v));
    int d, k;

    if (!v)
        return -1;

    v[offset + 1] = 0;

    for (d = 0; d <= max; d++) {
        for (k = -d; k <= d; k += 2) {
            int x;
            int y;

            if (k == -d || (k != d && v[offset + k - 1] < v[offset + k + 1]))
                x = v[offset + k + 1];
            else
                x = v[offset + k - 1] + 1;

            y = x - k;

            while (x < n && y < m && strcmp(a[x], b[y]) == 0) {
                x++;
                y++;
            }

            v[offset + k] = x;

            if (x >= n && y >= m) {
                free(v);
                return d;
            }
        }
    }

    free(v);
    return max;
}

이 축약 구현은 핵심 아이디어를 보여 주기에는 충분하지만, 실제 도구에 그대로 쓰기에는 부족합니다. 실제 diff는 다음 정보를 추가로 관리해야 합니다.

• trace 저장 — 어느 k에서 어떤 선택을 했는지 기록해야 실제 삭제/추가 목록을 복원할 수 있습니다.
• 입력 전처리 — 줄 해시(Hash), 공백 규칙, 바이너리 감지, 인코딩 처리 같은 단계가 필요합니다.
• 출력 후처리 — unified diff 헝크 묶기, 문맥 줄 수 조절, 함수명 추출 같은 작업이 들어갑니다.
• 가독성 보정 규칙 — 최소 길이만으로는 읽기 좋은 결과가 보장되지 않으므로 경계 이동, 앵커 선택 같은 보정이 필요합니다.

줄 단위 diff와의 연결

이제 문자 대신 코드 한 줄을 원소로 보겠습니다. 그러면 LCS는 "원본과 수정본에서 그대로 남는 줄들"이 되고, SES는 "어떤 줄을 삭제하고 어떤 줄을 추가할지"가 됩니다. unified diff에서 앞에 공백이 붙은 줄은 LCS에 남은 문맥 줄, -가 붙은 줄은 삭제, +가 붙은 줄은 추가입니다.

--- old.c
+++ new.c
@@ -1,4 +1,5 @@
 #include <stdio.h>
+#include <stdlib.h>
-printf("Hello")
+printf("Hello, %s")
 return 0;
 }

따라서 unified diff는 단순한 표시 형식이 아니라, 시퀀스 비교 결과를 사람이 읽기 쉬운 형태로 직렬화(Serialization)한 표현입니다. 더 자세한 명령 사용법은 diff & patch 문서를 참조하면 됩니다.

알고리즘 비교

LCS 자체를 계산하는 방법과 diff 도구가 실제로 쓰는 방법은 목적이 조금 다릅니다. 아래 표는 교육용 이해, 메모리 효율, 실무 가독성이라는 세 관점을 한 번에 비교한 것입니다. 큰 입력에서는 메모리 접근 지연(Latency)도 체감 성능에 직접 영향을 줍니다.

Git 공식 문서는 histogram을 "low-occurrence common elements를 지원하도록 확장한 patience"라고 설명합니다. 즉 최소 편집 길이만이 아니라 리뷰어가 읽기 좋은 경계도 알고리즘 선택의 중요한 기준입니다.

성능 분석과 선택 기준

알고리즘 선택은 Big-O 표기만으로 끝나지 않습니다. 실제 체감 성능은 입력 유사도, 반복 줄 비율, 메모리 배치, 후처리 보정 규칙 유무에 크게 영향을 받습니다. 아래 그림은 입력 특성에 따라 어떤 접근이 더 자연스러운지 요약한 것입니다.

정리하면, 알고리즘 수업에서는 DP가 가장 설명력이 좋고, 실제 도구 기본 구현은 Myers가 가장 경제적이며, 리뷰 경험 개선은 Patience/Histogram이 담당한다고 보면 됩니다. 이 셋은 경쟁 관계라기보다 서로 다른 층위를 담당하는 도구들입니다.

커널 개발 실전 시나리오

커널 개발에서는 단순한 문자열 비교보다 "리뷰어가 의도를 얼마나 빨리 읽을 수 있는가"가 더 중요합니다. 특히 에러 처리 경로, 반복 로그, 조건부 컴파일, 대규모 리팩터링에서는 같은 최소 편집 길이여도 패치 모양이 크게 달라집니다.

# 함수 이동이 섞인 리팩터링은 histogram으로 먼저 확인
git diff --histogram --color-moved=zebra HEAD~1

# 코드 블록 경계를 최대한 보존하며 읽고 싶을 때
git diff --patience HEAD~1

# .config는 전용 도구가 훨씬 읽기 쉽습니다
scripts/diffconfig .config.old .config

# 같은 패치를 여러 알고리즘으로 나란히 비교
git diff --diff-algorithm=myers HEAD~1
git diff --diff-algorithm=histogram HEAD~1

한계와 실전 해석

• 여러 LCS가 가능할 수 있습니다. 따라서 같은 입력이라도 diff 구현 세부 사항에 따라 헝크 경계가 달라질 수 있습니다.
• 블록 이동은 기본 LCS 문제에 직접 드러나지 않습니다. 한 함수가 다른 위치로 통째로 이동하면 삭제 + 추가처럼 보일 수 있습니다.
• 반복 줄이 많으면 공통 골격 선택이 애매합니다. 중괄호, 빈 줄, 로그 문장처럼 흔한 줄은 좋은 앵커가 아닙니다.
• 사람이 읽기 좋은 결과와 최소 편집 길이는 다를 수 있습니다. Git이 여러 알고리즘을 제공하는 이유가 여기에 있습니다.
• 의미적 변화는 별도 계층 문제입니다. 변수 이름 바꾸기, 코드 이동, 구문 트리 수준 변경은 LCS만으로 충분히 설명되지 않습니다.

여기에 한 가지를 더 덧붙이면, LCS 계열 알고리즘은 텍스트 수준의 구조 보존에는 강하지만 의미 수준 해석까지 해 주지는 않습니다. 예를 들어 조건식이 논리적으로 동등하게 바뀌었는지, 함수 분할이 성능 회귀를 부르는지, 잠금(Lock) 순서가 바뀌었는지 같은 문제는 별도의 정적 분석과 도메인 지식이 필요합니다. 즉 LCS는 리뷰의 시작점을 정리해 주는 도구이지, 최종 의미 판정을 대신하는 도구는 아닙니다.

AST/구조적 diff로의 진화

2020년대 중반부터 전통적인 줄 단위 LCS 기반 diff를 넘어서는 구조적 diff(Structural diff) 접근이 부상했습니다. 핵심 발상은 "텍스트 그 자체가 아닌, 파서가 이해한 구문 트리(Abstract Syntax Tree)를 비교하자"는 것입니다. 코드 포매터 변경, 주석만 수정, 변수명 일괄 치환과 같은 케이스에서 라인 기반 diff가 과장되게 보이는 문제를 완화합니다.

difftastic의 Dijkstra 기반 접근

difftastic은 두 AST를 동시에 탐색하는 그래프를 구성하고, "동일 노드는 비용 0, 추가/삭제/이동은 비용 1"로 가중치를 부여한 뒤 Dijkstra 최단경로를 계산합니다. 이 방식은 LCS 계열과 달리 노드 이동(Move)과 부분 일치(Partial Match)를 자연스럽게 모델링합니다.

• 장점: 들여쓰기/공백/주석만 바뀐 변경이 그대로 "무시됨"으로 표시, 문법 구조가 그대로 유지되면 diff가 최소화됩니다.
• 단점: 그래프 크기가 AST 노드 수의 제곱 수준으로 증가해 대용량 파일(수천 줄 이상)에서 느립니다. difftastic은 임계치를 넘으면 자동으로 line-diff로 fallback합니다.
• 파서 오류 시: tree-sitter가 파싱에 실패한 영역은 구조적 비교를 포기하고 라인 기반 비교를 사용합니다 — 오탐 회피를 위한 보수적 선택입니다.

언제 구조적 diff를 쓸까

참고자료

• An O(ND) Difference Algorithm and Its Variations — Eugene W. Myers 1986 논문
• An Algorithm for Differential File Comparison — Hunt-McIlroy 원논문
• git-diff 공식 문서 — Git diff 알고리즘과 옵션
• GNU Diffutils 매뉴얼 — diff, diff3, sdiff, cmp 공식 문서

관련 문서

• diff & patch — 출력 형식, patch 적용, 실전 워크플로를 다룹니다.
• Git — Git의 diff 알고리즘 선택과 패치 리뷰 흐름을 다룹니다.
• 정규표현식 (Regular Expression) — 텍스트 처리와 패턴 매칭 관점의 보조 배경 지식입니다.