2019/11/07 by Gańczorz, Michał
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1911.02889
We introduce the problem of computing a parsing where each phrase is of length at most m and which minimizes the zeroth order entropy of parsing. Based on the recent theoretical results we devise a heuristic for this problem. The solution has straightforward application in succinct text representations and gives practical improvements. Moreover the proposed heuristic yields structure whose size can be bounded both by |S|Hm-1(S) and by |S|/m(H0(S) + ⋯ + Hm-1), where Hk(S) is the k-th order empirical entropy of S. We also consider a similar problem in which the first-order entropy is minimized.