코드는 단어들의 집합이다. 어떤 단어도 다른 것의 Prefix가 아닌 단어들의 집합을 Prefix(-Free) Code라 부르고, 여기서 Prefix Coding이란, 주어진 수 n에 대하여, n개의 단어로 이루어진 Prefix 코드들 중에서 단어길이의 총합이 최소인 최적 Prefix 코드를 찾는 것을 말한다. 이 논문에서는 이의 특수한 경우로서, 특정 정규언어군에 속하는 임의의 정규언어 L에 대하여, L에 속하는 Prefix 코드들 중 최적의 코드를 찾는 방법을 제시한다. 또, 수 n이 변함에 따라 최적 Prefix 코드의 구조가 어떻게 변하는지, 그 성질을 트리구조를 이용해 밝힌다.
Code is a set of words. If, for any pair of words in the code, one is not prefix of another, the code is called "Prefix(-Free) Code". The prefix coding problem is, given n, to find an optimal code with the minimum-sum of lengths of n words. As a special case of this, we present a method to find, given language L in some specific classes of regular languages, an optimal code among prefix codes in L. We also show how the structure of optimal codes varies as n grows, using trees.
