کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
428270 686627 2007 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the lexicographical generation of compressed codes
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 104, Issue 3, 31 October 2007, Pages 95-100