문자열 대 문자열 수정 문제

String-to-string correction problem

컴퓨터 과학에서 문자열 대 문자열 수정 문제는 한 문자열을 다른 문자열로 바꾸는 데 필요한 편집 작업의 최소 비용 순서(즉, 최단 편집 거리 계산)를 결정하는 것을 말한다.편집 작업의 각 유형에는 고유한 비용 가치가 있다.[1]한 번의 편집 작업으로 문자열의 단일 기호를 다른 기호(비용C W)로 변경하거나, 기호를 삭제D(비용 W)하거나, 새 기호(비용I W)를 삽입할 수 있다.[2]

모든 편집 작업이 동일한 단위 비용(WC = WD = WI = W = 1)을 갖는 경우 문제는 두 문자열의 레벤스테인 거리를 계산하는 것과 동일하다.

문자열 거리를 결정하고 필요한 변환 작업의 최소 수를 지정하는 효율적인 방법을 제공하기 위해 여러 알고리즘이 존재한다.[3][4]그러한 알고리즘은 어떤 것이 기본 버전에 상대적인 차이의 집합으로 저장되는 델타 생성 작업에 특히 유용하다.이를 통해 단일 개체의 여러 버전을 별도로 저장하는 것보다 훨씬 효율적으로 저장할 수 있다.이는 여러 개체의 단일 버전이 크게 다르지 않거나 그 사이에 있는 경우에도 적용된다.특히, 그러한 차이 알고리즘은 분자 생물학에서 분자(단백질이나 DNA와 같은 분자)의 유사성에 기초하여 서로 다른 종류의 유기체들 사이의 친족 관계를 어느 정도 측정하기 위해 사용된다.

확장

문제의 확장된 변종에는 새로운 유형의 편집 작업이 포함된다. 즉, 두 개의 인접한 기호를 W 비용으로S 교환하는 것이다.

이 버전은 편집 운영 비용에 대한 특정 제한사항 하에서 다항 시간 내에 해결될 수 있다.[2][5]

로버트 A.바그너(1975)는 일반적인 문제가 NP-완전하다는 것을 보여주었다.특히 WI < WC = WD = ∞, 0S < W > ∞ (또는 동등하게, 변경 및 삭제는 허용되지 않는다)일 때 문제가 NP-완전하다는 것을 증명했다.[5]

참조

  1. ^ Wagner, Robert A.; Fischer, Michael J. (1974). "The String-to-String Correction Problem". Journal of the ACM. 21 (1): 168–173. doi:10.1145/321796.321811.
  2. ^ a b Lowrance, Roy; Wagner, Robert A. (April 1975). "An Extension of the String-to-String Correction Problem". Journal of the ACM. 22 (2): 177–183. doi:10.1145/321879.321880.
  3. ^ 거리 편집#컴퓨팅
  4. ^ Tichy, Walter F. (1984). "The string-to-string correction problem with block moves". ACM Transactions on Computer Systems. 2 (4): 309–321. doi:10.1145/357401.357404.
  5. ^ a b Wagner, Robert A. (May 1975). "On the complexity of the Extended String-to-String Correction Problem". STOC '75: Proceedings of the seventh annual ACM symposium on Theory of computing: 218–223. doi:10.1145/800116.803771.