이 문서는 부캠위키의 문서 변화를 감지하는 문제를 풀어나가기 위해 생각을 정리한 문서입니다. 이론적으로 정확하지 않은 내용이 포함될 수 있습니다. 주의하고 읽으세요.

먼저 머리 부딪히기

두 개체의 다른점을 확인하는 연산을 수행하기 위해선 개체가 두개가 있어야한다. 두 개체는 비교가능한 데이터로 이루어진다고 가정한다.

• 문자열에서 어떠한 변화를 주면 다른 문자열이 된다.
• 바이너리에 어떠한 변화를 주면 다른 바이너리가 된다.
• 유전자 정보에 어떠한 변화를 주면 다른 유전자 정보가 된다.

문자열을 예로 들면, 가장 많이 일어나는 연산은 삽입과 삭제연산이다. 삽입과 삭제 를 통해 한 입력값에서 다른 입력값이 된다.

다른 문자열이란

문자열을 기준으로, 다른 문자열이란 의미론적으로 다른 것이 아닌 문자열을 구성하고 있는 문자가 다름을 의미한다.

<aside> 💡 A. 아빠가 방에 들어간다. B. 아버지가 방에 들어간다.

</aside>

A와 B는 의미상 같은 문장이더라도, 다른 문자열이다. 앞으로 다룰 주제들은, 다른 문자열을 기준으로 이야기하는 것이다.

알고리즘들

Edit Distance; Wagner-Fischer 알고리즘(1974)

Wagner-Fischer 알고리즘은 모든 diff 알고리즘의 신호탄이라 볼 수 있다. 두 문자열의 비교는 다음과 같은 문제로 바라 볼 수 있다. **두 문자열의 최소 편집 거리는 얼마인가?** 모든 문자열은 삽입과 삭제를 통해 변경한다. 그리고 편집거리란 **삽입 삭제의 최소 회수**이다.

Wagner-Fischer 알고리즘은 DP 전략을 통해 해결할 수 있다. Wagner-Fischer 알고리즘은 교체 비용도 같이 계산하는데, 그래서 dp 식이 다음과 같다 .

[i, j] := minimum(d[i-1, j] + 1,                   // deletion
                  d[i, j-1] + 1,                   // insertion
                   d[i-1, j-1] + substitutionCost) // substitution

Wiki https://en.wikipedia.org/wiki/Wagner–Fischer_algorithm

LeetCode https://leetcode.com/problems/edit-distance/description/

Edit Distance는 String-to-String correction problem 이라고도 불린다.