어떤 n-gram일까? n-gram이 텍스트에 나타나기 전에는 모른다. 26개 알파벳으로 26 × 26 = 26² = 676개의 바이그램이 가능하고, 26³ = 17,576개의 트라이그램, 임의의 n으로는 26ⁿ의 n-gram이 가능하다. 우리는 이 중에서 일부인 작은 부분 집합을 선택할 수 있다. 구체적으로 압축하려는 텍스트를 훑어가며 n-gram을 찾을 것이다. 이는 텍스트를 처리해 가며 단계적으로 인코딩을 구성함을 의미한다.

어떻게 압축하는지 예를 들어 살펴보자. ‘MELLOW YELLOW FELLOW’를 압축한다고 해 보자. 앞에서 언급했듯이 모든 유니그램과 모든 단일 문자에 대해 8비트를 사용한다. 하위 7비트는 단일 문자들의 아스키 인코딩에 해당하고, 가장 왼쪽 비트는 0이 된다. 앞으로는 아이템을 수치로 매핑한 테이블을 사용한다.

그림 3-11 상단에 문자 매핑 테이블 t가 있다. 간단히 대문자 아스키코드 문자와 공백(␣)에 대한 매핑을 보여준다. 그 아래 그림의 각 줄은 어떻게 문자 단위로 구를 읽는지 보여준다. 현재 위치의 문자는 그 주변에 테두리가 처져 있다.

▲ 그림 3-11 LZW 압축