LZW 압축 timer 1s memory 128MB

LZW 압축은 다음 과정을 거친다.

1. 길이가 1인 모든 단어를 가지는 사전을 생성한다.

2. 현재 위치에서 사전과 가장 길게 일치하는 문자열 s를 찾는다.

3. 문자열 s의 사전 색인 번호를 출력한다.

4. 다음 글자가 없으면 종료한다.

5. s+다음 글자를 사전에 등록한다.

6. 현재 위치를 다음 글자로 바꾼다.

7. 2번 작업으로 돌아간다.

압축 알고리즘이 영문 대문자만 처리한다고 할 때, 사전은 다음과 같이 초기화된다. 사전의 색인 번호는 정수값으로 주어지며, 1부터 시작한다고 하자.

예를 들어 입력으로 a = "BANANA"가 들어온다고 하자.

1. 현재 위치 a[0]='B'에서부터 사전에서 가장 길게 일치하는 문자열 s는 "B"이고 이에 해당하는 색인 번호 2를 출력한다. 이후 s+다음글자인 "BA"를 사전에 27번째로 등록한다.

2. 현재 위치 a[1]='A'에서부터 사전에서 가장 길게 일치하는 문자열 s는 "A"이고 이에 해당하는 색인 번호 1을 출력한다. 이후 s+다음글자인 "AN"를 사전에 28번째로 등록한다.

3. 현재 위치 a[2]='N'에서부터 사전에서 가장 길게 일치하는 문자열 s는 "N"이고 이에 해당하는 색인 번호 14를 출력한다. 이후 s+다음글자인 "NA"를 사전에 29번째로 등록한다.

4. 현재 위치 a[3]='A'에서부터 사전에서 가장 길게 일치하는 문자열 s는 "AN"이고 이에 해당하는 색인 번호 28을 출력한다. 이후 s+다음글자인 "ANA"을 사전에 30번째로 등록하고, 현재 위치를 다음 글자 s[5]=A로 바꾼다.

5. 현재 위치 a[5]='A'에서부터 사전에서 가장 길게 일치하는 문자열 s는 "A"이고 이에 해당하는 색인 번호 1을 출력한다. 이후 다음글자는 없으므로 끝낸다.