이 시리즈의 1부에서는 두 문자열 간의 차이를 그래프 검색 문제로 모델링하는 방법을 살펴보았습니다. 두 문자열 사이의 최단 편집 스크립트를 살펴봤습니다:
- a = ABCABBA
- b = CBABAC
이 문자열에 대한 편집 그래프는 다음과 같습니다:
A B C A B B A
o-----o-----o-----o-----o-----o-----o-----o 0
| | | \ | | | | |
C | | | \ | | | | |
| | | \ | | | | |
o-----o-----o-----o-----o-----o-----o-----o 1
| | \ | | | \ | \ | |
B | | \ | | | \ | \ | |
| | \ | | | \ | \ | |
o-----o-----o-----o-----o-----o-----o-----o 2
| \ | | | \ | | | \ |
A | \ | | | \ | | | \ |
| \ | | | \ | | | \ |
o-----o-----o-----o-----o-----o-----o-----o 3
| | \ | | | \ | \ | |
B | | \ | | | \ | \ | |
| | \ | | | \ | \ | |
o-----o-----o-----o-----o-----o-----o-----o 4
| \ | | | \ | | | \ |
A | \ | | | \ | | | \ |
| \ | | | \ | | | \ |
o-----o-----o-----o-----o-----o-----o-----o 5
| | | \ | | | | |
C | | | \ | | | | |
| | | \ | | | | |
o-----o-----o-----o-----o-----o-----o-----o 6
0 1 2 3 4 5 6 7그리고 그래프를 추적하여 (0,0)에서 오른쪽 하단 모서리(7,6)까지의 최단 경로를 찾았습니다.
0,0 --- 1,0 --- 3,1 --- 5,2 --- 7,3
| | |
| | |
0,1 2,2 5,4 --- 7,5
| | |
| | |
2,4 --- 4,5 5,5 7,6
| | |
| | |
3,6 4,6 5,6이제 그래프 검색이 어떻게 작동하는지 살펴봤으니, 마이어스 알고리즘이 실제로 어떻게 작동하는지 알아보기 위해 표현을 약간 변경해 보겠습니다. 위의 그래프를 걸어가는 그래프를 45도 회전하여 렌더링한다고 가정해 보겠습니다.
| 0 1 2 3 4 5
----+--------------------------------------
|
4 | 7,3
| /
3 | 5,2
| /
2 | 3,1 7,5
| / \ / \
1 | 1,0 5,4 7,6
| / \ \
0 | 0,0 2,2 5,5
| \ \
-1 | 0,1 4,5 5,6
| \ / \
-2 | 2,4 4,6
| \
-3 | 3,6가로축의 숫자 d는 그래프에서 우리가 도달한 깊이, 즉 지금까지 얼마나 많은 이동을 했는지를 나타내며, 대각선 이동은 자유롭다는 점을 기억하세요. 세로축의 숫자를 k라고 하며, 그래프에서 한 행을 이동할 때마다 k = x - y라는 것을 알 수 있습니다.
오른쪽으로 이동하면 x가 증가하므로 k가 1씩 증가하고, 아래로 이동하면 y가 증가하므로 k가 1씩 감소합니다. 대각선으로 이동하면 x와 y가 모두 증가하므로 k는 동일하게 유지됩니다. 따라서 오른쪽으로 또는 아래쪽으로 이동한 후 대각선을 따라 이동할 때마다 k를 1씩 증가시키거나 감소시킵니다. 우리가 기록하는 것은 각 단계에서 k의 각 값에 대해 도달할 수 있는 편집 그래프를 통해 가장 먼 거리입니다.
이제 알고리즘은 다음과 같이 진행됩니다. 0으로 시작하는 각 d에 대해 -d에서 +d까지 k에 대한 각 이동을 2단계로 채웁니다. 각 (d, k) 위치에서 우리의 목표는 이전 위치에서 할 수 있는 최선의 이동을 결정하는 것입니다. 최상의 이동은 가장 높은 x 값을 제공하는 이동이며, y가 아닌 x를 최대화한다는 것은 삽입보다 삭제에 우선순위를 둔다는 의미입니다.
최적의 이동을 찾으려면 (d - 1, k + 1)에서 아래쪽 이동을 선택할지, 아니면 (d - 1, k - 1)에서 오른쪽 이동을 선택할지 결정해야 합니다. k가 -d이면 아래쪽으로 이동해야 하고, 마찬가지로 k가 +d이면 오른쪽으로 이동해야 합니다. 다른 모든 k 값의 경우, 이전 열의 인접한 두 k 값에서 가장 높은 x를 가진 위치를 선택하고 해당 이동이 어디로 향하는지 결정합니다.
예를 들어 (d, k) = (2,0)에서 이동한다고 가정해 보겠습니다. (x, y) = (0,1)인 (d, k) = (1,-1)에서 오른쪽으로 이동하거나 (x, y) = (1,0)인 (d, k) = (1,1)에서 아래쪽으로 이동할 수 있습니다.
| 0 1 2
----+----------------------
|
1 | 1,0
| / \
0 | 0,0 ( 2,2 )
| \
-1 | 0,1(1,0)은 (0,1)보다 x 값이 더 크므로 (1,0)에서 (1,1)로 아래쪽으로 이동하면 대각선으로 (2,2)가 됩니다. 따라서 (d, k) = (2,0)에 대해 (x, y) = (2,2)를 기록합니다. (0,1)에서 오른쪽으로 이동하면 (2,0)에 도달할 수 있는데도 이 경로를 통해 이동을 기록한 이유를 설명합니다. x 값이 가장 높은 이전 위치를 선택한다는 것은 삽입을 시도하기 전에 삭제 횟수를 최대화한다는 의미입니다.
어떤 상황에서는 이전 두 위치의 x 값이 같을 수도 있습니다. 예를 들어 (d, k) = (3,-1)에서 이동하는 경우, (x, y) = (2,2)에서 아래쪽으로 이동하거나 (x, y) = (2,4)에서 오른쪽으로 이동할 수 있다고 가정해 보겠습니다. 오른쪽으로 이동하면 x가 증가하므로 (2,4)에서 (3,4)로 이동한 다음 대각선으로 (4,5)로 이동합니다.
| 0 1 2 3
----+----------------------------
|
2 | 3,1
| /
1 | 1,0
| / \
0 | 0,0 2,2
| \
-1 | 0,1 ( 4,5 )
| \ /
-2 | 2,4논문에 제시된 알고리즘에 도달하기 위한 몇 가지 마지막 단순화가 있습니다. 첫 번째는 각 (x, y) 위치를 k에 대해 인덱싱하여 저장하고, k = x - y이므로 y는 k와 x의 값으로 계산할 수 있으므로 저장할 필요가 없다는 것입니다. 두 번째는 각 단계에서 이동한 방향을 저장할 필요가 없으며 각 지점에서 얻을 수 있는 최상의 x 값을 저장하면 된다는 것입니다. 이 과정을 완료한 후 경로를 도출하여 오른쪽 하단 위치로 이동하는 가장 작은 d를 찾고, 최종 위치가 어디에 표시되는지 알면 역추적하여 탐색한 여러 경로 중 어떤 경로가 그 위치로 연결되는지 찾을 수 있습니다.
이러한 세부 정보를 제거하면 이 정보가 남습니다:
| 0 1 2 3 4 5
----+--------------------------------------
|
4 | 7
|
3 | 5
|
2 | 3 7
|
1 | 1 5 7
|
0 | 0 2 5
|
-1 | 0 4 5
|
-2 | 2 4
|
-3 | 3마지막으로 단순화하면 d번째 라운드의 x 값은 (d-1)번째 라운드의 값에만 의존하며, 각 라운드가 홀수 또는 짝수 k 위치를 번갈아 수정하기 때문에 각 라운드가 이전 라운드에서 의존하는 값을 수정하지 않는다는 것입니다. 따라서 x 값은 k로 인덱싱된 단일 평면 배열에 저장할 수 있습니다. 이 예제에서 이 배열은 d의 각 값에 따라 다음과 같이 진화합니다:
k | -3 -2 -1 0 1 2 3 4
--------+-----------------------------------------------
|
d = 0 | 0
|
d = 1 | 0 0 1
|
d = 2 | 2 0 2 1 3
|
d = 3 | 3 2 4 2 5 3 5
|
d = 4 | 3 4 4 5 5 7 5 7
|
d = 5 | 3 4 5 5 7 7 5 7반복은 (d, k) = (5,1)에서 (x, y) = (7,6)에 도달할 수 있다는 것을 발견하면 중지됩니다.
이제 알고리즘에 사용된 문제의 표현에 도달했으며, 이를 실행 코드로 변환할 수 있습니다. 파일에서 줄을 나타내는 Diff::Line 객체를 포함하는 두 개의 목록 a와 b를 받는 함수를 만듭니다:
module Diff
Line = Struct.new(:number, :text)
def self.lines(document)
document = document.lines if document.is_a?(String)
document.map.with_index { |text, i| Line.new(i + 1, text) }
end
endDiff 코드는 대부분 이러한 객체의 텍스트 필드에만 의존하지만, 나중에 인쇄 및 기타 작업을 더 쉽게 할 수 있으므로 원래 줄 번호를 저장하는 것이 유용합니다. 앞으로 살펴볼 모든 알고리즘은 문자열을 줄로 나누어야 하므로 이를 수행하는 유틸리티 함수를 만든 다음 선택한 diff 알고리즘을 통해 결과 목록을 실행해 보겠습니다.
module Diff
def self.diff(a, b, differ: Myers)
differ.diff(lines(a), lines(b))
end
end이제 지금까지 논의한 알고리즘을 구현할 Myers 클래스를 작성해 보겠습니다. 우선, 두 문자열을 인스턴스 변수로 저장하기 위한 상용구 몇 개를 diff 메서드를 구현하는 객체에 만들 것이며, 모든 빌딩 블록이 준비되면 나중에 정의할 것입니다.
class Myers
def self.diff(a, b)
new(a, b).diff
end
def initialize(a, b)
@a, @b = a, b
end
def diff
# TODO
end
end차이를 반환하려면 가장 짧은 편집 경로를 찾아야 합니다. 먼저 n을 @a의 크기로, m을 @b의 크기로 저장하고 최대값을 이 둘의 합으로 저장하여 필요한 이동 횟수를 구합니다.
def shortest_edit
n, m = @a.size, @b.size
max = n + m그런 다음 각 k에 대해 x의 최신 값을 저장하는 배열을 설정합니다. k는 -최대부터 최대까지의 값을 취할 수 있으며, Ruby에서 음수 배열 인덱스는 배열의 끝에서 읽는 것으로 해석됩니다. 요소의 실제 순서는 중요하지 않으며, 배열이 양수 및 음수 k 값을 위한 공간을 확보할 수 있을 만큼 충분히 커야 합니다.
d = 0에 대한 반복이 x = 0을 선택하도록 v[1] = 0을 설정합니다. 대각선으로 즉시 이동할 수 있으므로 d = 0 반복을 이후 반복과 동일하게 처리해야 합니다. v[1] = 0으로 설정하면 알고리즘이 (x, y) = (0,-1)에서 가상으로 아래쪽으로 이동하는 것으로 시작하는 것처럼 동작합니다.
v = Array.new(2 * max + 1)
v[1] = 0다음으로 중첩 루프를 시작합니다. 외부 루프에서는 0에서 최대까지 d를 반복하고, 내부 루프에서는 -d에서 d까지 2단계로 k를 반복합니다.
(0 .. max).step do |d|
(-d .. d).step(2) do |k|루프 내에서 이전 라운드에서 아래쪽으로 이동할지 오른쪽으로 이동할지 선택하는 것으로 시작합니다. k가 -d이거나 d가 아니고 k + 1 값이 k - 1 값보다 큰 경우, 아래쪽으로 이동합니다. 즉, x 값을 이전 라운드의 k + 1 값과 같은 값으로 간주합니다. 그렇지 않으면 오른쪽으로 이동하여 x를 이전 k - 1 값보다 큰 값으로 취합니다. 이렇게 선택된 x 값과 현재 k에서 y를 계산합니다.
if k == -d or (k != d and v[k - 1] < v[k + 1])
x = v[k + 1]
else
x = v[k - 1] + 1
end
y = x - k오른쪽 또는 아래쪽으로 한 걸음씩 이동한 후 대각선 방향으로 이동할 수 있는지 확인합니다. 전체 @a 문자열을 삭제하거나 전체 @b 문자열을 추가하지 않았고 현재 위치에서 각 문자열의 요소가 동일하다면 x와 y를 모두 증가시킬 수 있습니다. 이동이 끝나면 현재 k에 도달한 x의 값을 저장합니다.
while x < n and y < m and @a[x].text == @b[y].text
x, y = x + 1, y + 1
end
v[k] = x마지막으로 오른쪽 하단 위치에 도달한 경우 현재 값인 d를 반환하여 호출자에게 a에서 b로 변환하는 데 필요한 최소 편집 횟수를 알려줍니다.
return d if x >= n and y >= m
end
end
end이 최소한의 알고리즘 버전은 필요한 최소한의 편집 횟수를 계산하지만, 그 편집 내용이 무엇인지 계산하지는 않습니다. 이를 위해서는 알고리즘에 의해 생성된 x 값의 기록을 역추적해야 합니다. 이 시리즈의 다음 글과 마지막 글에서 이 작업을 수행하는 방법을 살펴보겠습니다.