Restricted Hamming–Huffman trees

Lin, Min C.; Oliveira, Fabiano S.; Pinto, Paulo E. D.; Sampaio, Moysés S. Jr.; Szwarcfiter, Jayme L.

RAIRO. Operations Research, Tome 56 (2022) no. 3, pp. 1823-1839

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$$ of dimension n, we are interested in some aspects of its vertex neighborhoods. For a subset L of vertices of Q$$, 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$$. 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 .

Classification : 68P30, 94Bxx, 05C90
Keywords: Hamming–Huffman codes, hypercube graphs, minimum neighborhood

[1] L. Faria, F. S. Oliveira, P. E. D. Pinto and M. S. Sampaio Jr, On the minimum neighborhood of independent sets in the $n$-cube. Mat. Contemp. 44 (2016) 1–10. | MR | Zbl

[2] R. W. Hamming, Coding and Information Theory. Prentice-Hall (1986). | Zbl

[3] D. A. Huffman, A method for the construction of minimum redundancy codes. Proc. IRE 40 (1951) 1098–1101. | Zbl | DOI

[4] G. O. H. Katona, The Hamming sphere has minimum boundary. Stud. Sci. Math. Hung. 10 (1977) 131–140. | Zbl | MR

[5] D. E. Knuth. Art of Computer Programming. Vol. 1. Addison-Wesley (2005). | MR

[6] J. Körner and V. K. Wei, Odd and even Hamming spheres also have minimum boundary. Discrete Math. 51 (1984) 147–165. | MR | Zbl | DOI

[7] J. Körner and V. K. Wei, Addendum to “odd and even Hamming spheres also have minimum boundary”. Discrete Math. 62 (1986) 105–106. | MR | Zbl | DOI

[8] J. B. Kruskal, The number of simplices in a complex. In Mathematical Optimization Techniques, edited by R. Bellman. University of California Press (1963) 251–278. | MR | Zbl | DOI

[9] A. Pessoa, An approximation algorithm for constructing error detecting prefix codes. Optimization Online (2006).

[10] A. Pessoa, A note on the construction of error detecting/correcting prefix codes. Inf. Process. Lett. 107 (2008) 34–38. | MR | Zbl | DOI

[11] P. E. D. Pinto, F. Protti and J. L. Szwarcfiter, A Huffman-based error detecting code. In: Proc. of the Experimental and Efficient Algorithms (WEA’2004). Lecture Notes in Computer Science 3059 (2004) 446–457. | DOI

[12] P. E. D. Pinto, F. Protti and J. L. Szwarcfiter, Parity codes. RAIRO – Theor. Inf. Appl. 39 (2005) 263–278. | MR | Zbl | Numdam | DOI

[13] P. E. D. Pinto, F. Protti and J. L. Szwarcfiter, Exact and experimental algorithms for a huffman-based error detecting code. Lect. Notes Comput. Sci. 5532 (2009) 311–324. | MR | Zbl | DOI

[14] P. E. D. Pinto, F. Protti and J. L. Szwarcfiter, Exact and approximation algorithms for error-detecting even codes. Theor. Comput. Sci. 440,441 (2012) 60–72. | MR | Zbl | DOI

[15] T. Wenisch, P. F. Swaszek and A. K. Uht, Combined error correction and compression codes. In: IEEE International Symposium on Information Theorys (2001) 238.

[16] G. K. Zipf, Human Behaviour and the Principle of Least Effort. Addison-Wesley, (1949).

[17] https://github.com/moysessj/restricted-hamming-huffman-trees.git (Accessed: May 17, 2022).