문장 비교

최근에 받은 문제 중 하나가 이런 내용이 있었다.

두 문장의 차이점을 출력하는 프로그램을 작성하라. 두 문장은 동일한 문장을 조금 바꾼 것으로 아래와 같은 3개의 차이점이 있을 수 있다.
- Text could be deleted.
- Text could be inserted.
- Text could be changed.
원래 문장과 새로운 문장의 차이점을 모두 출력한다.

<Input>
텍스트 파일을 입력으로 한다.
비교할 두 개의 문장을 입력 받는다. 각 문장은 줄바꿈 문자로 구분하며, 각 문장을 text1, text2라 할 때 text1은 원래 문장, text2는 새로운 문장이 된다.

<Output>
다음과 같은 형태의 두 문장의 차이점을 모두 출력한다.
- deletion : 삭제된 문자와 그 위치 그리고 삭제된 문자의 개수

ex) pos 8 deleted 4 chars "not "

- insertion : 추가된 문자와 그 위치 그리고 추가된 문자의 개수
            ex) pos 8 inserted 4 chars "not "

- change : 변경된 원래 문자와 새로운 문자 그 위치 그리고 원래 문자의 개수
            ex) pos 46 changed 10 chars from "thoroughly" to "anyway"
위치는 원래 문장을 기준으로 출력한다. 첫 번째 문자의 위치는 0으로 시작한다.

 

<Sample Input>
This is not a joke. This is life. Consider it thoroughly...
This is a joke. This is not life. Don't consider it anyway

<Sample Output>
pos 8 deleted 4 chars "not "
pos 28 inserted 4 chars "not "
pos 34 inserted 6 chars "Don't "
pos 46 changed 10 chars from "thoroughly" to "anyway"
(sample output을 보면 대소문자를 구분하지 않는다.)

문제에서 요구하는 것은 문장에서 삽입, 삭제, 변경의 정보를 알고 싶어하는 것이다. 거기에 추가적인 몇몇 정보를 원하는 것이다.
X에서 Y로 변경할 때 삽입, 삭제, 변경은 항상 일어나게 마련이고, 이러한 정보를 알아보는 가장 좋은 알고리즘은 Edit Distance를 이용하는 것이다.

그러나, 우리가 알고 있듯이 Edit Distance는 문자간의 정보를 알아보는 것이다.
즉, 아래와 같은 예시가 될 것이다.

- p a r k
s p a k e

본 문제는 단어간의 삽입, 삭제, 변경의 정보를 알고 싶어 하는 것이다.
즉, 이런 식이 될 것이다.

This is not a joke. This is  -   life.
This is  -   a joke. This is not life.

위 예시와 아래 예시의 차이점은 무엇인가?
눈에 보이는 차이점을 말하는 것이 아니라, 구현 상의 차이점을 말하는 것이다.

그렇다. 위 예시는 1차원 배열로 쉽게 해결이 되지만, 아래 예시는 2차원 배열로 해결해야 쉽다.
하나의 단어를 하나의 문자로 간주한다는 것은 사람의 생각으로는 쉽게 되지만, 막상 컴퓨터에 주입시키기 위해서는 한 단계를 더 거쳐야 하는 수고로움을 해야한다.


** 관련 글 **
Edit Distance (Edit Operations) using Dynamic Programming

** 소스 **

setence compare.c