A unimodality property of optimal exhaustive prefix codes and retrieval trees over alphabets of varying size

摘要

For the case of a set of equally probable words to be encoded, by a coding alphabet in which each new symbol is more costly than the last, it is clear that the average word cost (equivalent to the total in this case) of an exhaustive prefix code varies with the subset chosen from the possible alphabet. The present paper establishes the nature of the variation and discovers the average work length is non-decreasing to a point, and then non-increasing beyond, thus making simple any search for a best alphabet. The above result is established first for an alphabet with costs {1,2,3,…}, which is important in information retrieval applications, then for arbitrary, but strictly increasing costs and for arbitrary, non-decreasing costs.