Browse Prior Art Database

Bounding the Depth of Search Trees

IP.com Disclosure Number: IPCOM000148870D
Original Publication Date: 1986-Mar-31
Included in the Prior Art Database: 2007-Mar-30
Document File: 26 page(s) / 1M

Publishing Venue

Software Patent Institute

Related People

Fraenkel, A.S.: AUTHOR [+3]

Abstract

Aviezri S. Fraenkel and Shmuel T. Klein

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 8% of the total text.

Page 1 of 26

Bounding the Depth of Search Trees A.S. Fkaenkel g. Klein

CS86-07'

March 1986

[This page contains 1 picture or other non-text object]

Page 2 of 26

[This page contains 1 picture or other non-text object]

Page 3 of 26

Bounding the Depth of Search Trees

Aviezri S. Fraenkel and Shmuel T. Klein

Department of Applied Mathematics The Weizmann Institute of Science

Rehovot , Israel

March 1986

ABSTRACT

    For an ordered sequence of n weights, Huffman's algorithm con- structs in time and space O(n) a search tree with minimum average path length, or, which is equivalent, a minimum redundancy code. However, if an upper bound B is imposed on the length of the codewords, the best known algorithms for the construction of an optimal code have time and space complexities O(Bn2). A new algorithm is presented, which yields sub-optimal codes, but in time O(n1og n) and space O(n). Under certain conditions, these codes are shown to be close to optimal, and extensive experiments suggest that in many practical applications, the deviation from the optimum is negligible.

[This page contains 1 picture or other non-text object]

Page 4 of 26

1. Motivation and Introduction

   We consider the set B (n, b) of eztended binary trees with n leaves, labelled 1 to n, and with depth _< b, henceforth called b-restricted trees. An extended binary tree is a binary tree in which every internal node has two sons (here, and in what follows, we use the terminology of Knuth [14, pp. 399-4051). For a given set of weights wi, 1 _< i 5 n, and a given bound B ;1 [logz n], the problem is to find a tree in B (n, B) which minimizes the weighted path length C:=, wili, where li is the length (number of edges) of the path from the root to leaf i.

   A possible application is the construction of a binary prefix-code with minimal average codeword length and subject to the additional constraint that no codeword has length exceeding B. Here wi is the frequency of the element which will be encoded by the i-th codeword. Another application is the organization of a file of n records, which are stored at the leaves of a binary search tree; wi is the probability of record i being requested, and the problem is to minimize the average search time such that no search takes more than B comparisons.

   The approach is recommended by Gilbert (71 for the case of inaccurately known probabilities wi: if some of the wj are significantly underestimated, Huffman's well- known procedure (111 would assign long codewords to the corresponding elements and the code thus obtained may be fairly inefficient. Another possible application of bounding the depth of a tree is to reduce the external pth length L =

x:=,

quantity which appears in the complexity function of many algorithms. In the worst case, L is O(n2) and on the average (with all trees equally likely) O ( n m (see [14]), but imposing a bound B = 0...