Restricted Hamming–Huffman trees

¹ Universidad de Buenos Aires, Buenos Aires, Argentina
² Universidade do Estado do Rio de Janeiro, Rio de Janeiro, Brazil
³ Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brazil

^* Corresponding author: moysessj@cos.ufrj.br

Received: 17 September 2021
Accepted: 6 May 2022

Abstract

We study a special case of Hamming–Huffman trees, in which both data compression and data error detection are tackled on the same structure. Given a hypercube Q_n of dimension n, we are interested in some aspects of its vertex neighborhoods. For a subset L of vertices of Q_n, the neighborhood of L is defined as the union of the neighborhoods of the vertices of L. The minimum neighborhood problem is that of determining the minimum neighborhood cardinality over all those sets L. This is a well-known problem that has already been solved. Our interest lies in determining optimal Hamming–Huffman trees, a problem that remains open and which is related to minimum neighborhoods in Q_n. In this work, we consider a restricted version of Hamming–Huffman trees, called [k]-HHT s, which admit symbol leaves in at most k different levels. We present an algorithm to build optimal [2]-HHT s. For uniform frequencies, we prove that an optimal HHT is always a [5]-HHT and that there exists an optimal HHT which is a [4]-HHT . Also, considering experimental results, we conjecture that there exists an optimal tree which is a [3]-HHT .