Bounding the Depth of Search Trees | Zendy

Abdul Qadir O.S. | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Bounding the Depth of Search Trees

Author(s) -

Abdul Qadir O.S.

Publication year - 1993

Publication title -

the computer journal

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.319

H-Index - 64

eISSN - 1460-2067

pISSN - 0010-4620

DOI - 10.1093/comjnl/36.7.668

Subject(s) - huffman coding , bounding overwatch , combinatorics , mathematics , upper and lower bounds , sequence (biology) , path length , algorithm , prefix code , redundancy (engineering) , code (set theory) , binary logarithm , path (computing) , search tree , discrete mathematics , search algorithm , computer science , linear code , block code , data compression , decoding methods , mathematical analysis , computer network , set (abstract data type) , artificial intelligence , biology , programming language , genetics , operating system

For an ordered sequence of n weights, Huffman's algorithm constructsin time and space O(n) a search tree with minimum average pathlength, or, which is equivalent, a minimum redundancy code. However,if an upper bound B is imposed on the length of the codewords, thebest known algorithms for the construction of an optimal code havetime and space complexities O(Bn2). A new algorithm is presented,which yields sub-optimal codes, but in time O(n log n) and space O(n).Under certain...

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research