Paper Info
Title
Grammar Compression with Probabilistic Context-Free Grammar
Abstract
We propose a new approach for universal lossless text compression, based on grammar compression. In the literature, a target string T has been compressed as a context-free grammar G in Chomsky normal form satisfying L(G) = T. Such a grammar is often called a straight-line program (SLP). In this paper, we consider a probabilistic grammar G that generates T, but not necessarily as a unique element of L(G). In order to recover the original text T unambiguously, we keep both the grammar G and the derivation tree of T from the start symbol in G, in compressed form. We show some simple evidence that our proposal is indeed more efficient than SLPs for certain texts, both from theoretical and practical points of view.
Year
DOI
Venue
2020
10.1109/DCC47342.2020.00093
2020 Data Compression Conference (DCC)
Keywords
DocType
ISSN
grammar compression,straight line grammar,probabilistic context free grammar,entropy compression
Conference
1068-0314
ISBN
Citations 
PageRank 
978-1-7281-6458-8
0
0.34
References 
Authors
2
5
Name
Order
Citations
PageRank
Naganuma Hiroaki100.34
Diptarama Hendrian202.70
Ryo Yoshinaka317226.19
Ayumi Shinohara493688.28
Naoki Kobayashi503.38