On the lexicographical generation of compressed codes

A certain class of algorithms for the lexicographical generation of combinatorial objects can be considered as working on the code tree representation of the objects processed. Then the strategy used by the algorithms in order to find lexicographical successors corresponds to a special kind of tree traversal. If the encoding used is redundant in the sense that the code tree has nodes with only one successor, compression becomes possible which allows for a speed-up in the lexicographical generation. In this note we analyze the average running time saved when compression is applied. For this purpose we consider random code trees within the model of simply generated trees together with the compression as used for the trie and the PATRICIA data structure. We prove general results which quantify the average savings only depending on the generator Θ and the size of the family under consideration. As an example, those results are applied to consider random encodings over an s-ary alphabet. Finally, we comment on connections of our findings to the problem of ranking words of a given language.