Improved Behaviour of Tries by the "Symmetrization" of the Source

Get BibTex-formatted data

Download

PDF

Author

Yuriy A. Reznik and Wojciech Szpankowski

Tech report number

CERIAS TR 2002-14

Entry type

inproceedings

Abstract

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

Download

PDF

Date

2002

URL

https://www.cerias.purdue.edu/papers/archive/2002-14.ps

Booktitle

Data Compression Conference

Institution

CERIAS, Purdue University

Key alpha

Reznik

Publication Date

1900-01-01

Location

A hard-copy of this is in the CERIAS Library

BibTex-formatted data

To refer to this entry, you may select and copy the text below and paste it into your BibTex document. Note that the text may not contain all macros that BibTex supports.

@Inproceedings{ Reznik,
	title = "Improved Behaviour of Tries by the "Symmetrization" of the Source",
	author = "Yuriy A. Reznik and Wojciech Szpankowski",
	year = "2002",
	booktitle = "Data Compression Conference",
	institution = "CERIAS, Purdue University",
	abstract = "In this paper, we propose and study a pre-processing technique for improving performance of digital tree (trie)-based search algorithms under asymmetric memory less sources. This technique (which we call a symmetrization of the source) bijectively maps the sequences of symbols from the original (asymmetric) source into symbols of an output alphabet resulting in a more uniform distribution. We introduce a criterion of efficiency for such a mapping, and demonstrate that a problem of finding an optimal for a given source (or universal) symmetrization transform is equivalent to a problem of constructing a minimum redundancy variable-length-to-block code for this source (or class of sources). Based on this result, we propose search algorithms that incorporate known (optimal for a given source and universal) variable-length-to-block codes and study their asymptotic behavior. We complement our analysis with a description of an efficient algorithm for universal symmetrization of binary memory less sources, and compare the performance of the resulting search structure with the standard tries.",
	url = "https://www.cerias.purdue.edu/papers/archive/2002-14.ps",
}