On nonlinear compression costs: when Shannon meets Rényi

Andrea Somazzi, Paolo Ferragina, Diego Garlaschelli

Shannon entropy is the shortest average codeword length a lossless compressor can achieve by encoding i.i.d. symbols. However, there are cases in which the objective is to minimize…