Analysis of a heuristic for full trie minimization

Publisher Website
Google Scholar
Abstract
A trie is a distributed-key search tree in which records from a file correspond to leaves in the tree. Retrieval consists of following a path from one root to a leaf, where the choice of edge at each node is determined by attribute values of the key. For full tries, those in which all leaves lie at the same depth, the problem of finding an ordering of attributes which yields a minimum size trie is NP-complete. This paper considers a “greedy” heuristic for constructing low-cost tries. It presents simulation experiments which show that the greedy method tends to produce tries with small size, and analysis leading to a worst case bound on approximations produced by the heuristic. It also shows a class of files for which the greedy method may perform badly, producing tries of high cost.

This publication has 4 references indexed in Scilit: