동적 사전 부호화

흔히 쓰이는 데이터 압축 기법 중 하나인 사전 부호화(dictionary coding)는 글에 등장하는 단어를 사전에서의 위치를 나타내는 번호로 바꾸는 방식이다. 사전을 미리 정해 두는 정적 사전 부호화는 압축된 글을 해독하려면 그 사전을 반드시 갖고 있어야 하므로 불편할 수 있다. 동적 사전 부호화는 압축할 글 자체로부터 사전을 만들어 감으로써 이 문제를 피한다.

글은 처음부터 끝까지 순서대로 처리하며, 사전은 비어 있는 상태에서 시작한다. 각 단어는 다음과 같이 처리한다.

• 이미 사전에 있는 단어라면, 사전에서의 위치를 나타내는 번호로 바꾼다. 위치 번호는 단어가 추가된 순서대로 1부터 매긴다.
• 아직 사전에 없는 단어라면, 압축 결과에 그대로 출력하고 사전의 맨 끝에 추가한다.

동적 사전 부호화를 구현하여라.

첫째 줄에는 압축할 텍스트 묶음의 개수를 나타내는 양의 정수가 주어진다.

각 텍스트 묶음은 소문자와 공백만으로 이루어진 한 줄 이상의 텍스트로 구성된다. 한 단어의 길이는 20글자를 넘지 않고, 한 줄의 길이는 80자를 넘지 않으며, 한 묶음의 줄 수는 100줄을 넘지 않는다. 서로 다른 텍스트 묶음은 하나의 빈 줄로 구분되며, 각 묶음은 (비어 있는 사전에서 시작하여) 독립적으로 압축한다.

각 텍스트 묶음을 동적 사전 부호화로 압축한 결과를 출력한다. 줄 바꿈과 공백은 입력과 완전히 똑같이 유지하고, 압축된 묶음들 사이는 하나의 빈 줄로 구분한다.

어떤 단어가 처음 등장했을 때, 그 단어를 사전에 추가하면서도 새로 부여된 위치 번호로 부호화하지 않고 그대로 출력하는 이유는 무엇일까?

만약 입력에 단어뿐 아니라 숫자도 들어올 수 있다면 어떤 문제가 생기는지 설명하고, 그 문제를 해결할 수 있도록 이 방법을 어떻게 바꾸면 좋을지 제안해 보아라.