Improved behaviour of tries by the "symmetrization" of the source

摘要: In this paper, we propose and study a pre-processing technique for improving performance of digital tree (trie)-based search algorithms under asymmetric memoryless sources. This (which call symmetrization the source) bijectively maps sequences symbols from original (asymmetric) source into an output alphabet resulting in more uniform distribution. We introduce criterion efficiency such mapping, demonstrate that problem finding optimal construction given (or universal) transform is equivalent to constructing minimum redundancy variable-length-to-block code class sources). Based on result, incorporate known (optimal codes their asymptotic behaviour. complement our analysis with description efficient algorithm universal binary sources, compare structure standard tries.