Edit Distance - 편집 역사

Ahn9807: 봇: 자동으로 텍스트 교체 (-\[\[분류:컴퓨터 공학(\|[^\]]+)?\]\] +)

2026-01-15T15:20:35Z

봇: 자동으로 텍스트 교체 (-\[\[분류:컴퓨터 공학(\|[^\]]+)?\]\] +)

← 이전 판		2026년 1월 15일 (목) 15:20 판
1번째 줄:		1번째 줄:
	[[분류:알고리즘 설계와 분석]]		[[분류:알고리즘 설계와 분석]]
	~~[[분류:컴퓨터 공학]]~~
	상위 문서: [[Dynamic Programming]]		상위 문서: [[Dynamic Programming]]

2025년 12월 1일 (월) 16:44에 Pinkgo님의 편집

2025-12-01T16:44:35Z

← 이전 판		2025년 12월 1일 (월) 16:44 판
1번째 줄:		1번째 줄:
	[[분류:알고리즘 설계와 분석]]		[[분류:알고리즘 설계와 분석]]
	[[분류:컴퓨터 공학]]		[[분류:컴퓨터 공학]]
	상위 문서: [[Dynamic ~~Programming#문제\|Dynammic~~ Programming]]		상위 문서: [[Dynamic Programming]]

	==개요==		==개요==

2025년 12월 1일 (월) 16:44에 Pinkgo님의 편집

2025-12-01T16:44:20Z

← 이전 판		2025년 12월 1일 (월) 16:44 판
1번째 줄:		1번째 줄:
	[[분류:알고리즘 설계와 분석]]		[[분류:알고리즘 설계와 분석]]
	[[분류:컴퓨터 공학]]		[[분류:컴퓨터 공학]]
	상위 문서: [[Dynamic Programming]]		상위 문서: [[Dynamic Programming#문제\|Dynammic Programming]]

	==개요==		==개요==

Pinkgo: /* Example of Implementation */

2025-11-18T07:50:02Z

Example of Implementation

← 이전 판		2025년 11월 18일 (화) 07:50 판
122번째 줄:		122번째 줄:
	위 연산을 의식하면 DP 테이블에 대해 더욱 깊이 이해할 수 있다. 제시된 DP 테이블에는 색칠이 되어 있는데, 이는 각각의 원소들이 어떠한 연산을 통해 구해졌는지를 의미한다. 먼저, 빨간색은 일치(match)나 치환(substitution)을 의미한다. 즉, 이는 해당 원소의 부모가 되는 원소가 대각선에 일치함을 의미한다. 이때 부모 원소와 비교하여 값이 보존되었다면 일치(M), 값이 증가하였다면 치환(S) 연산을 통해 구해진 것이다. 두번째로, 초록색은 삽입 연산(Insertion)을 의미한다. 즉, 이는 해당 원소의 부모가 되는 원소가 왼쪽에 일치함을 의미한다. 마지막으로, 파란색은 삭제 연산(Deletion)을 의미한다. 즉, 이는 해당 원소의 부모가 되는 원소가 위쪽에 일치함을 의미한다.		위 연산을 의식하면 DP 테이블에 대해 더욱 깊이 이해할 수 있다. 제시된 DP 테이블에는 색칠이 되어 있는데, 이는 각각의 원소들이 어떠한 연산을 통해 구해졌는지를 의미한다. 먼저, 빨간색은 일치(match)나 치환(substitution)을 의미한다. 즉, 이는 해당 원소의 부모가 되는 원소가 대각선에 일치함을 의미한다. 이때 부모 원소와 비교하여 값이 보존되었다면 일치(M), 값이 증가하였다면 치환(S) 연산을 통해 구해진 것이다. 두번째로, 초록색은 삽입 연산(Insertion)을 의미한다. 즉, 이는 해당 원소의 부모가 되는 원소가 왼쪽에 일치함을 의미한다. 마지막으로, 파란색은 삭제 연산(Deletion)을 의미한다. 즉, 이는 해당 원소의 부모가 되는 원소가 위쪽에 일치함을 의미한다.

	이를 통하여 m[10, 10] 부터 연산을 역추적하면 Edit Distance를 5로 만들기 위한 Edit Sequence가 DSMMMMMISMS임을 알 수 있다. 이때 주어진 Edit Sequence에서 M을 제외한 편집 횟수는 5이며, 이는 m[10][10]을 통해 주어진 Edit Distance인 5와 일치한다.		이를 통하여 m[10, 10] 부터 연산을 역추적하면 Edit Distance를 5로 만들기 위한 Edit Sequence가 DSMMMMMISMS임을 알 수 있다. 이때 주어진 Edit Sequence에서 M을 제외한 편집 횟수는 5이며, 이는 m[10, 10]을 통해 주어진 Edit Distance인 5와 일치한다.

	===Reconstructing the Path===		===Reconstructing the Path===

Pinkgo: /* Simple Recursive Algorithm */

2025-11-18T05:18:27Z

Simple Recursive Algorithm

← 이전 판		2025년 11월 18일 (화) 05:18 판
10번째 줄:		10번째 줄:

	==Simple Recursive Algorithm==		==Simple Recursive Algorithm==
	Edit Distance 계산은 문자열 뒤에서부터 비교하면서 재귀적으로 해결할 수 있다. 이는 ~~두 문자열~~ 두 문자열 S[1..i], T[1..j]이 있을때 마지막 문자를 비교하여 해결할 수 있다. 만약 비교하는 두 문자가 같으면 비용 증가 없이 이전 문제로 이동한다.<ref>(s[1..i-1], t[1..j-1])에 해당한다.</ref> 반면 두 문자가 다른 경우에는 substitution을 통해 Edit Distance를 1 증가시킨다.<ref>혹은 S에 문자를 추가하거나 삭제하는 방식을 취할 수도 있다.</ref>		Edit Distance 계산은 문자열 뒤에서부터 비교하면서 재귀적으로 해결할 수 있다. 이는 두 문자열 S[1..i], T[1..j]이 있을때 마지막 문자를 비교하여 해결할 수 있다. 만약 비교하는 두 문자가 같으면 비용 증가 없이 이전 문제로 이동한다.<ref>(s[1..i-1], t[1..j-1])에 해당한다.</ref> 반면 두 문자가 다른 경우에는 substitution을 통해 Edit Distance를 1 증가시킨다.<ref>혹은 S에 문자를 추가하거나 삭제하는 방식을 취할 수도 있다.</ref>

	===Recurrence Relation===		===Recurrence Relation===

Pinkgo: /* Example of Implementation */

2025-11-16T06:50:36Z

Example of Implementation

← 이전 판		2025년 11월 16일 (일) 06:50 판
113번째 줄:		113번째 줄:

	===Example of Implementation===		===Example of Implementation===
			[[파일:Figure 1. Example of DP Table.png\|섬네일\|Figure 1. Example of DP Table\|가운데]]
	Figure 1은 "thou shalt"를 "you should"로 편집하기 위한 Edit Distance를 구한 결과 DP 테이블이다. 해당 DP 테이블의 값들은 해당 인덱스가 가리키는 부분문자열을 일치시키기 위해서 요구되는 Edit Distance(편집 횟수)를 의미한다. 예를 들어 m[3, 2]는 "tho"를 "so"로 편집하기 위해서 요구되는 편집 횟수를 의미한다. 이때 각각의 값들은 두 문자열의 마지막 문자를 서로 비교하며 결정되며 사용되는 식은 아래와 같다:		Figure 1은 "thou shalt"를 "you should"로 편집하기 위한 Edit Distance를 구한 결과 DP 테이블이다. 해당 DP 테이블의 값들은 해당 인덱스가 가리키는 부분문자열을 일치시키기 위해서 요구되는 Edit Distance(편집 횟수)를 의미한다. 예를 들어 m[3, 2]는 "tho"를 "so"로 편집하기 위해서 요구되는 편집 횟수를 의미한다. 이때 각각의 값들은 두 문자열의 마지막 문자를 서로 비교하며 결정되며 사용되는 식은 아래와 같다:
	<math>D[i, j]</math> is minimum of:		<math>D[i, j]</math> is minimum of:
119번째 줄:		120번째 줄:
	• <math>D[i, j - 1] + 1</math> for an insertion into <math>S</math>: T에서 문자를 하나 가져오는 경우(insertion)		• <math>D[i, j - 1] + 1</math> for an insertion into <math>S</math>: T에서 문자를 하나 가져오는 경우(insertion)
	• <math>D[i - 1, j] + 1</math> for a deletion from <math>S</math>: S에서 문자를 하나 버리는 경우(deletion)		• <math>D[i - 1, j] + 1</math> for a deletion from <math>S</math>: S에서 문자를 하나 버리는 경우(deletion)
	~~[[파일:Figure 1. Example of DP Table.png\|섬네일\|Figure 1. Example of DP Table]]~~
	위 연산을 의식하면 DP 테이블에 대해 더욱 깊이 이해할 수 있다. 제시된 DP 테이블에는 색칠이 되어 있는데, 이는 각각의 원소들이 어떠한 연산을 통해 구해졌는지를 의미한다. 먼저, 빨간색은 일치(match)나 치환(substitution)을 의미한다. 즉, 이는 해당 원소의 부모가 되는 원소가 대각선에 일치함을 의미한다. 이때 부모 원소와 비교하여 값이 보존되었다면 일치(M), 값이 증가하였다면 치환(S) 연산을 통해 구해진 것이다. 두번째로, 초록색은 삽입 연산(Insertion)을 의미한다. 즉, 이는 해당 원소의 부모가 되는 원소가 왼쪽에 일치함을 의미한다. 마지막으로, 파란색은 삭제 연산(Deletion)을 의미한다. 즉, 이는 해당 원소의 부모가 되는 원소가 위쪽에 일치함을 의미한다.		위 연산을 의식하면 DP 테이블에 대해 더욱 깊이 이해할 수 있다. 제시된 DP 테이블에는 색칠이 되어 있는데, 이는 각각의 원소들이 어떠한 연산을 통해 구해졌는지를 의미한다. 먼저, 빨간색은 일치(match)나 치환(substitution)을 의미한다. 즉, 이는 해당 원소의 부모가 되는 원소가 대각선에 일치함을 의미한다. 이때 부모 원소와 비교하여 값이 보존되었다면 일치(M), 값이 증가하였다면 치환(S) 연산을 통해 구해진 것이다. 두번째로, 초록색은 삽입 연산(Insertion)을 의미한다. 즉, 이는 해당 원소의 부모가 되는 원소가 왼쪽에 일치함을 의미한다. 마지막으로, 파란색은 삭제 연산(Deletion)을 의미한다. 즉, 이는 해당 원소의 부모가 되는 원소가 위쪽에 일치함을 의미한다.

Pinkgo: /* Example of Implementation */

2025-11-16T06:50:17Z

Example of Implementation

← 이전 판		2025년 11월 16일 (일) 06:50 판
113번째 줄:		113번째 줄:

	===Example of Implementation===		===Example of Implementation===
	Figure 는 "thou shalt"를 "you should"로 편집하기 위한 Edit Distance를 구한 결과 DP 테이블이다. 해당 DP 테이블의 값들은 해당 인덱스가 가리키는 부분문자열을 일치시키기 위해서 요구되는 Edit Distance(편집 횟수)를 의미한다. 예를 들어 m[3, 2]는 "tho"를 "so"로 편집하기 위해서 요구되는 편집 횟수를 의미한다. 이때 각각의 값들은 두 문자열의 마지막 문자를 서로 비교하며 결정되며 사용되는 식은 아래와 같다:		Figure 1은 "thou shalt"를 "you should"로 편집하기 위한 Edit Distance를 구한 결과 DP 테이블이다. 해당 DP 테이블의 값들은 해당 인덱스가 가리키는 부분문자열을 일치시키기 위해서 요구되는 Edit Distance(편집 횟수)를 의미한다. 예를 들어 m[3, 2]는 "tho"를 "so"로 편집하기 위해서 요구되는 편집 횟수를 의미한다. 이때 각각의 값들은 두 문자열의 마지막 문자를 서로 비교하며 결정되며 사용되는 식은 아래와 같다:
	<math>D[i, j]</math> is minimum of:		<math>D[i, j]</math> is minimum of:
	• <math>D[i - 1, j - 1]</math> if <math>S[i] = T [j]</math>: 둘이 같으면 비용 추가 안 됨(match)		• <math>D[i - 1, j - 1]</math> if <math>S[i] = T [j]</math>: 둘이 같으면 비용 추가 안 됨(match)
119번째 줄:		119번째 줄:
	• <math>D[i, j - 1] + 1</math> for an insertion into <math>S</math>: T에서 문자를 하나 가져오는 경우(insertion)		• <math>D[i, j - 1] + 1</math> for an insertion into <math>S</math>: T에서 문자를 하나 가져오는 경우(insertion)
	• <math>D[i - 1, j] + 1</math> for a deletion from <math>S</math>: S에서 문자를 하나 버리는 경우(deletion)		• <math>D[i - 1, j] + 1</math> for a deletion from <math>S</math>: S에서 문자를 하나 버리는 경우(deletion)
			[[파일:Figure 1. Example of DP Table.png\|섬네일\|Figure 1. Example of DP Table]]
	위 연산을 의식하면 DP 테이블에 대해 더욱 깊이 이해할 수 있다. 제시된 DP 테이블에는 색칠이 되어 있는데, 이는 각각의 원소들이 어떠한 연산을 통해 구해졌는지를 의미한다. 먼저, 빨간색은 일치(match)나 치환(substitution)을 의미한다. 즉, 이는 해당 원소의 부모가 되는 원소가 대각선에 일치함을 의미한다. 이때 부모 원소와 비교하여 값이 보존되었다면 일치(M), 값이 증가하였다면 치환(S) 연산을 통해 구해진 것이다. 두번째로, 초록색은 삽입 연산(Insertion)을 의미한다. 즉, 이는 해당 원소의 부모가 되는 원소가 왼쪽에 일치함을 의미한다. 마지막으로, 파란색은 삭제 연산(Deletion)을 의미한다. 즉, 이는 해당 원소의 부모가 되는 원소가 위쪽에 일치함을 의미한다.		위 연산을 의식하면 DP 테이블에 대해 더욱 깊이 이해할 수 있다. 제시된 DP 테이블에는 색칠이 되어 있는데, 이는 각각의 원소들이 어떠한 연산을 통해 구해졌는지를 의미한다. 먼저, 빨간색은 일치(match)나 치환(substitution)을 의미한다. 즉, 이는 해당 원소의 부모가 되는 원소가 대각선에 일치함을 의미한다. 이때 부모 원소와 비교하여 값이 보존되었다면 일치(M), 값이 증가하였다면 치환(S) 연산을 통해 구해진 것이다. 두번째로, 초록색은 삽입 연산(Insertion)을 의미한다. 즉, 이는 해당 원소의 부모가 되는 원소가 왼쪽에 일치함을 의미한다. 마지막으로, 파란색은 삭제 연산(Deletion)을 의미한다. 즉, 이는 해당 원소의 부모가 되는 원소가 위쪽에 일치함을 의미한다.

Pinkgo: /* Variant of Edit Distance */

2025-11-16T06:48:49Z

Variant of Edit Distance

@@ 152번째 줄: / 152번째 줄: @@
 ==Variant of Edit Distance==
 <syntaxhighlight lang="c">
 </syntaxhighlight>
 <syntaxhighlight lang="c">
 </syntaxhighlight>
 <syntaxhighlight lang="c">
 </syntaxhighlight>
-<syntaxhighlight lang="c">
+즉, 이를 통해서 DP는 문자가 같으면 match하고, 문자가 다르면 delete/insert로 스킵한다. 이를 통해 가장 많은 match 를 모으는 방향으로 DP가 움직이며, 그 match들의 집합이 바로 LCS가 된다.
-</syntaxhighlight>
 ==각주==

Pinkgo: /* Reconstructing the Path */

2025-11-16T06:15:42Z

Reconstructing the Path

@@ 125번째 줄: / 125번째 줄: @@
 ===Reconstructing the Path===
 DP 테이블을 기반으로 연산 경로를 복원하기 위해서는 DP 테이블의 m[|S|][|T|]에서 시작하여 parent를 따라가는 것이다. 즉, goal state인 m[i][j]에서 시작하여 parent 방향으로 (i-1, j), (i, j-1), (i-1, j-1) 중 하나로 이동하며, 이 과정에서 발생한 연산인 M/S/I/D를 기록하면 되는 것이다. 하지만 이는 뒤집혀진 순서이므로, 기록된 것을 reverse하여 출력해야 한다. 혹은 재귀(recursion)를 반대로 실행하면 자동으로 정방향 순서를 구할 수 있다. 아래는 주어진 DP 테이블을 바탕으로 경로를 복원하는 함수를 C언어로 구현한 예시이다:
 ==Variant of Edit Distance==

Pinkgo: /* Recursive Algorithm Using DP */

2025-11-16T06:13:25Z

Recursive Algorithm Using DP

← 이전 판		2025년 11월 16일 (일) 06:13 판
113번째 줄:		113번째 줄:

	===Example of Implementation===		===Example of Implementation===
	Figure 는 "thou shalt"를 "you should"로 편집하기 위한 Edit Distance를 구한 결과 DP 테이블이다. 해당 DP 테이블의 값들은 해당 인덱스가 가리키는 부분문자열을 일치시키기 위해서 요구되는 Edit Distance(편집 횟수)를 의미한다. 예를 들어 ~~테이블의 (~~3, 2)는 "tho"를 "so"로 편집하기 위해서 요구되는 편집 횟수를 의미한다. 이때 각각의 값들은 두 문자열의 마지막 문자를 서로 비교하며 결정되며 사용되는 식은 아래와 같다:		Figure 는 "thou shalt"를 "you should"로 편집하기 위한 Edit Distance를 구한 결과 DP 테이블이다. 해당 DP 테이블의 값들은 해당 인덱스가 가리키는 부분문자열을 일치시키기 위해서 요구되는 Edit Distance(편집 횟수)를 의미한다. 예를 들어 m[3, 2]는 "tho"를 "so"로 편집하기 위해서 요구되는 편집 횟수를 의미한다. 이때 각각의 값들은 두 문자열의 마지막 문자를 서로 비교하며 결정되며 사용되는 식은 아래와 같다:
	<math>D[i, j]</math> is minimum of:		<math>D[i, j]</math> is minimum of:
	• <math>D[i - 1, j - 1]</math> if <math>S[i] = T [j]</math>: 둘이 같으면 비용 추가 안 됨(match)		• <math>D[i - 1, j - 1]</math> if <math>S[i] = T [j]</math>: 둘이 같으면 비용 추가 안 됨(match)
121번째 줄:		121번째 줄:
	위 연산을 의식하면 DP 테이블에 대해 더욱 깊이 이해할 수 있다. 제시된 DP 테이블에는 색칠이 되어 있는데, 이는 각각의 원소들이 어떠한 연산을 통해 구해졌는지를 의미한다. 먼저, 빨간색은 일치(match)나 치환(substitution)을 의미한다. 즉, 이는 해당 원소의 부모가 되는 원소가 대각선에 일치함을 의미한다. 이때 부모 원소와 비교하여 값이 보존되었다면 일치(M), 값이 증가하였다면 치환(S) 연산을 통해 구해진 것이다. 두번째로, 초록색은 삽입 연산(Insertion)을 의미한다. 즉, 이는 해당 원소의 부모가 되는 원소가 왼쪽에 일치함을 의미한다. 마지막으로, 파란색은 삭제 연산(Deletion)을 의미한다. 즉, 이는 해당 원소의 부모가 되는 원소가 위쪽에 일치함을 의미한다.		위 연산을 의식하면 DP 테이블에 대해 더욱 깊이 이해할 수 있다. 제시된 DP 테이블에는 색칠이 되어 있는데, 이는 각각의 원소들이 어떠한 연산을 통해 구해졌는지를 의미한다. 먼저, 빨간색은 일치(match)나 치환(substitution)을 의미한다. 즉, 이는 해당 원소의 부모가 되는 원소가 대각선에 일치함을 의미한다. 이때 부모 원소와 비교하여 값이 보존되었다면 일치(M), 값이 증가하였다면 치환(S) 연산을 통해 구해진 것이다. 두번째로, 초록색은 삽입 연산(Insertion)을 의미한다. 즉, 이는 해당 원소의 부모가 되는 원소가 왼쪽에 일치함을 의미한다. 마지막으로, 파란색은 삭제 연산(Deletion)을 의미한다. 즉, 이는 해당 원소의 부모가 되는 원소가 위쪽에 일치함을 의미한다.

	이를 통하여 ~~테이블의 (~~10, 10) 부터 연산을 역추적하면 Edit Distance를 5로 만들기 위한 Edit Sequence가 DSMMMMMISMS임을 알 수 있다. 이때 주어진 Edit Sequence에서 M을 제외한 편집 횟수는 5이며, 이는 m[10][10]을 통해 주어진 Edit Distance인 5와 일치한다.		이를 통하여 m[10, 10] 부터 연산을 역추적하면 Edit Distance를 5로 만들기 위한 Edit Sequence가 DSMMMMMISMS임을 알 수 있다. 이때 주어진 Edit Sequence에서 M을 제외한 편집 횟수는 5이며, 이는 m[10][10]을 통해 주어진 Edit Distance인 5와 일치한다.

	===Reconstructing the Path===		===Reconstructing the Path===
	DP 테이블을 기반으로 연산 경로를 복원하기 위해서는 DP 테이블의		DP 테이블을 기반으로 연산 경로를 복원하기 위해서는 DP 테이블의 m[\|S\|][\|T\|]에서 시작하여 parent를 따라가는 것이다. 즉, goal state인 m[i][j]에서 시작하여 parent 방향으로 (i-1, j), (i, j-1), (i-1, j-1) 중 하나로 이동하며, 이 과정에서 발생한 연산인 M/S/I/D를 기록하면 되는 것이다. 하지만 이는 뒤집혀진 순서이므로, 기록된 것을 reverse하여 출력해야 한다. 혹은 재귀(recursion)를 반대로 실행하면 자동으로 정방향 순서를 구할 수 있다. 아래는 주어진 DP 테이블을 바탕으로 경로를 복원하는 함수를 C언어로 구현한 예시이다:

	==Variant of Edit Distance==		==Variant of Edit Distance==