태그 보관물: dynamic-algorithms

dynamic-algorithms

Levenshtein 편집 거리에 대한 최적의 문자열 정렬을 계산하기위한 공간 복잡성 거리 계산은 시간 복잡도

크기

n1

의 두 개의 스트링이 주어지면

n2

, 표준 레 벤슈 테인 편집 거리 계산은 시간 복잡도

O(n1n2)

와 공간 복잡도 가진 동적 알고리즘에 의해 계산됩니다

O(n1n2)

. (일부 개선 편집 거리의 함수로 만들 수 있습니다

d

, 그러나 우리는 아무런 가정도하지 않습니다

d

O(max(n1,n2))

그러나 최적의 편집 스크립트를 실제로 편집하려면 실행 시간을 희생하여 메모리 사용량 보다 더 나은 작업을 수행 할 수 있습니까?

O(n1n2)


답변

Yuval이 제안한 트레이드 오프가 필요하지 않습니다. Dan Hirschberg가 먼저 설명한 동적 프로그래밍과 분할 및 정복의 혼합을 사용하여 시간과 공간에서 전체 최적 편집 시퀀스를 계산할 수 있습니다 . ( 최대 공통 서브 시퀀스를 계산하기위한 선형 공간 알고리즘. Commun. ACM 18 (6) : 341-343, 1975.)

O(nm)

O(n+m)

직관적으로 Hirschberg의 아이디어는 최적의 편집 시퀀스를 통해 절반의 단일 편집 작업을 계산 한 다음 시퀀스의 두 절반을 재귀 적으로 계산하는 것입니다. 최적 편집 순서를 메모 테이블의 한 모서리에서 다른 모서리로의 경로로 생각하면이 경로가 테이블의 중간 행을 교차하는 위치를 기록하도록 수정 된 반복이 필요합니다. 작동하는 한 가지 재발은 다음과 같습니다.

Half(i,j)={∞if i<m/2jif i=m/2Half(i−1,j)if i>m/2 and Edit(i,j)=Edit(i−1,j)+1Half(i,j−1)if i>m/2 and Edit(i,j)=Edit(i,j−1)+1Half(i−1,j−1)otherwise

의 값은 시간을 사용하여 편집 거리 테이블 와 동시에 계산 될 수 있습니다 . 메모 테이블의 각 행은 위의 행에만 의존하므로 및 모두 계산 하려면 공간 만 있으면됩니다 .

Half(i,j)

Edit(i,j)

O(mn)

Edit(m,n)

Half(m,n)

O(m+n)

마지막으로 입력 문자열 을 으로 변환하는 최적의 편집 시퀀스 는 를 다음에 을 변환 최적의 서열이 이어진다 . 이 두 하위 시퀀스를 재귀 적으로 계산하면 전체 실행 시간은 다음 반복에 따릅니다.

임을 증명하는 것은 어렵지 않습니다

A[1..m]

B[1..n]

A[1..m/2]

B[1..Half(m,n)]

A[m/2+1..m]

B[Half(m,n)+1..n]

T(m,n)={O(n)if m≤1O(m)if n≤1O(mn)+maxh(T(m/2,h)+T(m/2,n−h))otherwise

T(m,n)=O(mn)

. 마찬가지로, 한 번에 하나의 동적 프로그래밍 패스를위한 공간 만 필요하므로 총 공간 한계는 여전히 입니다. 재귀 스택을위한 공간은 무시할 수 있습니다.

O(m+n)


답변

공간에서 실행되는 알고리즘은 실제로 최종 편집 및 최종 편집 직전의 상태를 복구합니다. 따라서이 알고리즘을 번 실행하면 런타임을 늘리는 대신 전체 편집 시퀀스를 복구 할 수 있습니다. 일반적으로 시간 공간 상충 관계는 시간에 유지하는 행 수에 의해 제어됩니다. 이 절충점의 두 가지 극단적 인 점은 공간 및 공간 이며, 그 사이에서 시간과 공간의 곱은 일정합니다 (최대 O).

O(n1+n2)

O(n1+n2)

O(n1n2)

O(n1+n2)

답변