문서의 문장 단위 변경 추적 기능을 공부하고 구현하며 헷갈렸던 개념들을 간단하게 정리해보려고 한다.
Dynamic Programming : 동적 프로그래밍
문제를 여러 하위 문제로 분할하여 해결하는 알고리즘 설계 기법이다.
하위 문제의 해결 방식을 저장하고 재사용하여 중복 계산을 피하는 방식으로 동작한다.
이를 통해 계산 속도를 개선할 수 있다.
동적 프로그래밍은 피보나치 수열, 최장 공통 부분 수열, 최단 경로 문제 등 다양한 문제에 적용할 수 있다.
이러한 문제들은 최적 부분 구조와 중복 부분 문제의 성질을 가지고 있어
동적 프로그래밍을 사용하여 효율적으로 해결될 수 있다.
동적 프로그래밍의 세 가지 주요 요소
- Optimal Substructure : 최적 부분 구조
주어진 문제의 최적해가 하위 문제들의 최적해를 활용하여 구해질 수 있는 성질이다.
큰 문제를 작은 하위 문제들로 분할하여 해결하고, 이들 하위 문제들의 최적해를 결합하여
전체 문제의 최적해를 얻는다. - Overlapping Subproblems : 중복 부분 문제
동일한 하위 문제들이 반복적으로 발생하는 성질이다.
동적 프로그래밍은 이러한 하위 문제들의 해결 방식을 저장하여 재사용한다.
이를 통해 중복 계산을 피하고, 효율적인 알고리즘을 구현할 수 있다. - Memoization : 메모이제이션 혹은 Tabulation : 테이블 기반 접근
계산된 하위 문제들의 해결 방식을 저장하는 메모리 기법이다.
이를 통해 이후에 동일한 하위 문제가 발생할 때 저장된 결과를 가져와서 중복 계산을 피하고
속도를 향상시킨다.
메모이제이션은 일반적으로 재귀적인 방식으로 구현되며, 테이블 기반 접근은 반복적인 방식으로 구현된다.
동적 프로그래밍의 대표적인 알고리즘 : 피보나치 수열
아래 코드에서 fibonacci() 함수는 피보나치 수열의 n번째 항을 계산한다.
이때 이전에 계산한 결과를 저장하기 위한 memo 리스트를 활용하여 중복 계산을 피한다.
이미 계산된 값이 있는 경우 해당 값을 반환하고, 계산된 값이 없는 경우 재귀적으로 이전 항들을 계산하여 값을 구하고
memo 리스트에 저장한다.
# 피보나치 수열을 동적 프로그래밍으로 계산하는 함수
def fibonacci(n, memo):
if n <= 1:
return n
# 이미 계산된 값이 있는 경우 메모이제이션된 결과를 반환
if memo[n] is not None:
return memo[n]
# 계산된 값이 없는 경우 계산하여 메모이제이션
memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
return memo[n]
# 피보나치 수열의 n번째 항을 반환하는 함수
def get_fibonacci(n):
# 메모이제이션을 위한 리스트 초기화
memo = [None] * (n + 1)
return fibonacci(n, memo)
# 피보나치 수열의 10번째 항 계산 예시
n = 10
result = get_fibonacci(n)
print(f"The {n}th Fibonacci number is: {result}")
Longest Common Subsequence, LCS : 최장 공통 부분 수열
LCS는 두 개의 문자열에서 공통으로 나타나는 가장 긴 부분 수열을 의미한다.
부분 수열은 원래 문자열의 순서를 유지하면서 문자들을 선택한 부분으로 연속하지 않을 수 있다.
최장 공통 부분 수열 문제는 문자열 처리와 관련된 DNA 서열 분석, 문서 유사도 비교, 파일 비교 등
다양한 분야에서 활용될 수 있다.
LCS알고리즘은 DP의 특성을 활용하여 중복 계산을 피하고 효율적으로 최장 공통 부분 수열을 찾는 방법이다.
LCS를 구하는 알고리즘의 일반적인 동작 방식
- 두 개의 문자열을 입력
- 두 문자열의 길이에 따라 DP 테이블 초기화
(DP 테이블은 문자열1의 길이 + 1 x 문자열2의 길이 + 1의 크기를 가진다.) - DP 테이블을 채우기 위해 문자열을 순회하면서 각 셀의 값을 계산한다.
이때 문자가 일치하는 경우 이전 대각선 셀의 값에 1을 더하고 일치하지 않는 경우 이전 행 또는 열의 값 중 최댓값을 선택하여 채운다. - DP 테이블을 채우고 나면 최장 공통 부분 수열을 역추적한다.
DP 테이블 오른쪽 아래 셀부터 시작하여 문자가 일치하는 경우 해당 문자를 결과에 추가하고 대각선 위로 이동한다.
일치하지 않는 경우 이전 행 또는 열로 이동하여 진행한다. - 역추적을 마치면 최장 공통 부분 수열이 구해진다.
LCS를 DP 방식으로 해결하는 예시 코드
longest_common_subsequence() 함수는 두 문자열 str1과 str2의 최장 공통 부분 수열을 계산한다.
이때 DP 테이블을 활용하여 중복 계산을 피하고 최장 공통 부분 수열을 찾는다.
DP 테이블은 (m+1) x (n+1) 크기로 초기화되며 dp[i][j]는 str1[:i]와 str2[:j]까지의 최장 공통 부분 수열의 길이를 나타낸다.
각 셀의 값을 계산하기 위해 문자가 일치하는 경우 이전 대각선 셀의 값에 1을 더하고
일치하지 않는 경우 이전 행 또는 열의 값 중 최댓값을 선택하여 채운다.
DP 테이블을 채우고 난 후 최장 공통 부분 수열을 구하기 위해 역추적을 수행한다.
# 최장 공통 부분 수열을 동적 프로그래밍으로 계산하는 함수
def longest_common_subsequence(str1, str2):
m = len(str1)
n = len(str2)
# DP 테이블 초기화
dp = [[0] * (n + 1) for _ in range(m + 1)]
# DP 테이블 채우기
for i in range(1, m + 1):
for j in range(1, n + 1):
if str1[i - 1] == str2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
# 최장 공통 부분 수열 구하기
lcs = ""
i = m
j = n
while i > 0 and j > 0:
if str1[i - 1] == str2[j - 1]:
lcs = str1[i - 1] + lcs
i -= 1
j -= 1
elif dp[i - 1][j] > dp[i][j - 1]:
i -= 1
else:
j -= 1
return lcs
# 두 문자열의 최장 공통 부분 수열 계산 예시
str1 = "ABCDGH"
str2 = "AEDFHR"
lcs = longest_common_subsequence(str1, str2)
print(f"The Longest Common Subsequence is: {lcs}")
Minimum Edit Distance : 최소 편집 거리
두 개의 문자열을 서로 변환하기 위해 필요한 최소 편집 연산의 수를 나타내는 개념이다.
이때의 편집 연산은 문자열에 적용되는 삽입, 삭제, 대체 세 가지 종류의 연산을 말한다.
최소 편집 거리는 문자열 간의 유사도를 측정하거나 두 문자열 간의 차이를 계산하는 등
다양한 문제에서 활용될 수 있다.
편집 연산의 종류
- 삽입 (Insertion) : 한 문자열에 문자를 추가하는 연산
- 삭제 (Deletion) : 한 문자열에서 문자를 삭제하는 연산
- 대체 (Substitution) : 한 문자열의 문자를 다른 문자로 대체하는 연산
최소 편집 거리 계산 예시 코드
최소 편집 거리를 계산하기 위해 일반적으로 DP가 활용된다.
최종적으로 DP 테이블의 오른쪽 아래 셀에는 최소 편집 거리가 계산되며 이 값을 반환한다.
아래 코드에서는 두 문자열 사이의 최소 편집 거리인 3이 출력된다.
def minimum_edit_distance(str1, str2):
m = len(str1)
n = len(str2)
# DP 테이블 초기화
dp = [[0] * (n + 1) for _ in range(m + 1)]
# 첫 번째 행 초기화
for i in range(n + 1):
dp[0][i] = i
# 첫 번째 열 초기화
for i in range(m + 1):
dp[i][0] = i
# DP 테이블 채우기
for i in range(1, m + 1):
for j in range(1, n + 1):
if str1[i - 1] == str2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
return dp[m][n]
# 두 문자열의 최소 편집 거리 계산 예시
str1 = "kitten"
str2 = "sitting"
distance = minimum_edit_distance(str1, str2)
print(f"The minimum edit distance is: {distance}")
Shortest Edit Script : 최단 편집 스크립트
최소 편집 거리를 구성하는 편집 연산의 집합을 나타내는 개념이다.
최소 편집 거리는 두 문자열 같의 변환에 필요한 최소 연산 횟수를 의미하는 반면,
최단 편집 스크립트는 이러한 최소 연산을 구체적으로 나열한 것이다.
최단 편집 스크립트는 문자열의 삽입, 삭제, 대체 연산을 나타내는 기호들로 구성된다.
- 삽입 (Insertion) : I
- 삭제 (Deletion) : D
- 대체 (Substitution) : S
- 유지 (Match, 문자가 일치하는 경우) : M
예를 들어 문자열 kitten을 sitting로 변환하기 위한 최단 편집 스크립트는 SISMMDD이다.
| 인덱스 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 문자열1 | k | i | t | t | e | n | |
| 문자열2 | s | i | t | t | i | n | g |
| 연산기호 | S | M | M | M | S | M | I |
최단 편집 스크립트 예시 코드
DP를 사용하여 최소 편집 거리를 계산하고 그에 따라 최단 편집 스크립트를 구성한다.
위의 예시 코드를 실행하면 문자열 "kitten"을 "sitting"으로 변환하기 위한 최단 편집 스크립트 "SMMMSMI"가 출력된다.
이 코드는 동적 프로그래밍 알고리즘을 사용하여 최소 편집 거리를 계산하고,
DP 테이블을 기반으로 최단 편집 스크립트를 구성한다.
function shortestEditScript(str1: string, str2: string): string {
const m = str1.length;
const n = str2.length;
// DP 테이블 초기화
const dp: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
// DP 테이블 채우기
for (let i = 0; i <= m; i++) {
for (let j = 0; j <= n; j++) {
if (i === 0) {
dp[i][j] = j;
} else if (j === 0) {
dp[i][j] = i;
} else if (str1[i - 1] === str2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);
}
}
}
// 최단 편집 스크립트 구성
const script: string[] = [];
let i = m;
let j = n;
while (i > 0 && j > 0) {
if (str1[i - 1] === str2[j - 1]) {
script.push('M');
i--;
j--;
} else if (dp[i][j] === 1 + dp[i - 1][j - 1]) {
script.push('S');
i--;
j--;
} else if (dp[i][j] === 1 + dp[i][j - 1]) {
script.push('I');
j--;
} else {
script.push('D');
i--;
}
}
while (i > 0) {
script.push('D');
i--;
}
while (j > 0) {
script.push('I');
j--;
}
script.reverse();
return script.join('');
}
// 두 문자열의 최단 편집 스크립트 계산 예시
const str1 = "kitten";
const str2 = "sitting";
const editScript = shortestEditScript(str1, str2);
console.log(`The shortest edit script is: ${editScript}`);
현재 진행중인 무비위키 프로젝트의 문서의 변경 추적 기능은
DP를 기반으로 한 최소 편집거리와 최단 편집 스크립트를 사용하고 있다.
LCS는 두 문서의 공통 부분을 찾는데 적합한 알고리즘이기 때문에 배제한 것이다.
정리하면 원본 문서와 수정된 문서를 비교해서 최소 편집 거리를 계산하고
최단 편집 스크립트를 이용해 원본 문서와 수정된 문서의 차이 데이터를 저장한다.
앞의 저장된 데이터가 원본 문서를 수정된 문서로 변환시킬 때 필요한 최소한의 편집 과정 데이터가 되는 것이다.
이 데이터를 활용해 문서의 최신 수정 버전을 출력하고, 특정 버전으로 롤백도 가능하다.
참고 문서
https://galid1.tistory.com/507
알고리즘 - Dynamic Programming(동적프로그래밍)이란?
Dynamic Programming(동적계획법) 이란 1. Dynamic Programming(동적계획법)이란?큰 문제를 작은문제로 나누어 푸는 문제를 일컫는 말입니다. 동적 계획법이란 말 때문에 어떤 부분에서 동적으로 프로그래밍
galid1.tistory.com
[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence
LCS는 주로 최장 공통 부분수열(Longest Common Subsequence)을 말합니다만, 최장 공통 문자열(Longest Common Substring)을 말하기도 합니다.
velog.io
https://blog.naver.com/ndb796/220870218783
최소 편집 거리(Minimum Edit Distance) 알고리즘
( 문제 출제 : 류관희 교수님 ) 최소 편집 거리(Minimum Edit Distance) 알고리즘 이란 두 ...
blog.naver.com
'Development > TIL' 카테고리의 다른 글
| 비교 단위별 Diff 및 Patch 코드 동작 속도 측정 (0) | 2023.06.16 |
|---|---|
| patch 알고리즘 수정 (feat. </p> 태그 지옥) (0) | 2023.06.16 |
| 문서의 문장 단위 변경 추적 (0) | 2023.06.13 |
| git의 diff 알고리즘 (0) | 2023.06.10 |
| 데이터 형상 관리 (특정 버전으로 롤백) (0) | 2023.06.10 |
