In search for the simplest example that proves Huffman coding overperforms Shannon-Fano coding
Authors
Macarie Breazu
Lucian Blaga University of Sibiu
Daniel Morariu
Lucian Blaga University of Sibiu
Radu G. Cretulescu
Lucian Blaga University of Sibiu
Antoniu Pitic
Lucian Blaga University of Sibiu
Adrian Bărglăzan
Lucian Blaga University of Sibiu
Abstract
Shannon-Fano coding (SFC) and Huffman coding (HC) are classic and well-known algorithms, but still in use today. The search for the simplest example that proves HC overperforms SFC is still of interest. The problem is not as trivial as it looks like at first view because of several decisions that must be considered. We perform a full-search of the stream data space for a maximum stream length of 100. Depending on additional requests we impose, the simplest solution we found is {1,1,1,1,3} when we accept to select a specific cutting, {2,3,3,3,7} when we accept only deterministic (unique) cuttings and {4,5,6,7,14} when we also ask for different frequencies for symbols as well.
Author Biographies
Macarie Breazu, Lucian Blaga University of Sibiu
Associate Professor, ComputerScience and Electrial Engineering Department
Daniel Morariu, Lucian Blaga University of Sibiu
Associate Professor, Computer Science and Electronic and Electrical Engineering Department
Antoniu Pitic, Lucian Blaga University of Sibiu
Lecturer, Computer Science and Electronical and Electrical Engineering Department
Adrian Bărglăzan, Lucian Blaga University of Sibiu
Assistant Professor, Computer Science and Electronical and Electrical Engineering Department
