표 3-5의 인코딩은 여전히 모든 문자에 대해 같은 수의 비트를 사용한다. 문자의 빈도에 따라 다른 수의 비트를 사용하는 것이 목표라면 가변 길이 인코딩(variable-length encoding)은 어떨까? 표 3-6처럼 인코딩해 볼 수 있지만, 이것은 잘못되었다. 인코딩된 단어는 011011로 시작하는데, 이를 디코딩하면 E(0) 다음에 F(1과 1) 2개와 R(11) 1개 중 어느 것이 뒤에 올지 알 방법이 없다. 인코딩된 단어를 모호함 없이 확실히 디코딩하려면 어떤 문자도 다른 문자와 같은 비트열로 시작하지 않는, 즉 어떤 문자 코드도 다른 문자 코드의 접두어가 되지 않게 하는 가변 길이 인코딩을 해야 한다. 이러한 인코딩을 유일 접두어 인코딩(prefix-free encoding)이라 한다.

▼ 표 3-6 단어 effervescence의 가변 길이 인코딩: 오류

E: 0

F: 1

R: 11

V: 100

S: 101

C: 10

N: 110

 

표 3-7은 단어 effervescence의 가변 길이 유일 접두어 인코딩을 보여준다. 이 단어는 33비트의 010010001100111001111101011011010로 표현되며 이전보다 더 개선되었다. 3비트의 고정 길이 인코딩을 사용하던 일부 문자는 4비트를 사용해야 하지만, 이러한 오버헤드는 가장 일반적인 문자에 1비트, 그다음으로 빈번한 문자에 2비트를 사용하므로 상쇄된다.

▼ 표 3-7 단어 effervescence를 위한 유일 접두어 가변 길이 인코딩

E: 0

F: 100

R: 1100

V: 1110

S: 1111

C: 101

N: 1101

 

그러면 어떻게 표 3-7의 결과를 얻을 수 있을까? 물론 유일 접두어 인코딩을 위한 알고리즘이 있어야 한다. 이 알고리즘을 기술하기 전에 먼저 몇 가지 자료 구조에 익숙해져야 한다.