Grammar compression with probabilistic context-free grammar

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 \emph{straight-line progr...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2020-03
Main Authors: Naganuma, Hiroaki, Hendrian, Diptarama, Yoshinaka, Ryo, Shinohara, Ayumi, Kobayashi, Naoki
Format: Article
Language:English
Subjects:
Canonical forms
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites
container_end_page
container_issue
container_start_page
container_title arXiv.org
container_volume
creator Naganuma, Hiroaki
Hendrian, Diptarama
Yoshinaka, Ryo
Shinohara, Ayumi
Kobayashi, Naoki
description 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 \emph{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.
format article
fullrecord <record><control><sourceid>proquest</sourceid><recordid>TN_cdi_proquest_journals_2379276609</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2379276609</sourcerecordid><originalsourceid>FETCH-proquest_journals_23792766093</originalsourceid><addsrcrecordid>eNpjYuA0MjY21LUwMTLiYOAtLs4yMDAwMjM3MjU15mSwdi9KzM1NLFJIzs8tKEotLs7Mz1MozyzJUCgoyk9KTMrMySwuyUwGSueVpFaU6KYVpaYqpEP08DCwpiXmFKfyQmluBmU31xBnD12g1sLS1OKS-Kz80qI8oFS8kbG5pZG5mZmBpTFxqgBpAzgd</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2379276609</pqid></control><display><type>article</type><title>Grammar compression with probabilistic context-free grammar</title><source>Publicly Available Content Database</source><creator>Naganuma, Hiroaki ; Hendrian, Diptarama ; Yoshinaka, Ryo ; Shinohara, Ayumi ; Kobayashi, Naoki</creator><creatorcontrib>Naganuma, Hiroaki ; Hendrian, Diptarama ; Yoshinaka, Ryo ; Shinohara, Ayumi ; Kobayashi, Naoki</creatorcontrib><description>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 \emph{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.</description><identifier>EISSN: 2331-8422</identifier><language>eng</language><publisher>Ithaca: Cornell University Library, arXiv.org</publisher><subject>Canonical forms</subject><ispartof>arXiv.org, 2020-03</ispartof><rights>2020. This work is published under http://arxiv.org/licenses/nonexclusive-distrib/1.0/ (the “License”). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.</rights><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://www.proquest.com/docview/2379276609?pq-origsite=primo$$EHTML$$P50$$Gproquest$$Hfree_for_read</linktohtml><link.rule.ids>780,784,25753,37012,44590</link.rule.ids></links><search><creatorcontrib>Naganuma, Hiroaki</creatorcontrib><creatorcontrib>Hendrian, Diptarama</creatorcontrib><creatorcontrib>Yoshinaka, Ryo</creatorcontrib><creatorcontrib>Shinohara, Ayumi</creatorcontrib><creatorcontrib>Kobayashi, Naoki</creatorcontrib><title>Grammar compression with probabilistic context-free grammar</title><title>arXiv.org</title><description>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 \emph{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.</description><subject>Canonical forms</subject><issn>2331-8422</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2020</creationdate><recordtype>article</recordtype><sourceid>PIMPY</sourceid><recordid>eNpjYuA0MjY21LUwMTLiYOAtLs4yMDAwMjM3MjU15mSwdi9KzM1NLFJIzs8tKEotLs7Mz1MozyzJUCgoyk9KTMrMySwuyUwGSueVpFaU6KYVpaYqpEP08DCwpiXmFKfyQmluBmU31xBnD12g1sLS1OKS-Kz80qI8oFS8kbG5pZG5mZmBpTFxqgBpAzgd</recordid><startdate>20200318</startdate><enddate>20200318</enddate><creator>Naganuma, Hiroaki</creator><creator>Hendrian, Diptarama</creator><creator>Yoshinaka, Ryo</creator><creator>Shinohara, Ayumi</creator><creator>Kobayashi, Naoki</creator><general>Cornell University Library, arXiv.org</general><scope>8FE</scope><scope>8FG</scope><scope>ABJCF</scope><scope>ABUWG</scope><scope>AFKRA</scope><scope>AZQEC</scope><scope>BENPR</scope><scope>BGLVJ</scope><scope>CCPQU</scope><scope>DWQXO</scope><scope>HCIFZ</scope><scope>L6V</scope><scope>M7S</scope><scope>PIMPY</scope><scope>PQEST</scope><scope>PQQKQ</scope><scope>PQUKI</scope><scope>PRINS</scope><scope>PTHSS</scope></search><sort><creationdate>20200318</creationdate><title>Grammar compression with probabilistic context-free grammar</title><author>Naganuma, Hiroaki ; Hendrian, Diptarama ; Yoshinaka, Ryo ; Shinohara, Ayumi ; Kobayashi, Naoki</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-proquest_journals_23792766093</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2020</creationdate><topic>Canonical forms</topic><toplevel>online_resources</toplevel><creatorcontrib>Naganuma, Hiroaki</creatorcontrib><creatorcontrib>Hendrian, Diptarama</creatorcontrib><creatorcontrib>Yoshinaka, Ryo</creatorcontrib><creatorcontrib>Shinohara, Ayumi</creatorcontrib><creatorcontrib>Kobayashi, Naoki</creatorcontrib><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>Materials Science &amp; Engineering Collection</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central</collection><collection>ProQuest Central Essentials</collection><collection>AUTh Library subscriptions: ProQuest Central</collection><collection>Technology Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest Central</collection><collection>SciTech Premium Collection (Proquest) (PQ_SDU_P3)</collection><collection>ProQuest Engineering Collection</collection><collection>Engineering Database</collection><collection>Publicly Available Content Database</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><collection>ProQuest Central China</collection><collection>Engineering collection</collection></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Naganuma, Hiroaki</au><au>Hendrian, Diptarama</au><au>Yoshinaka, Ryo</au><au>Shinohara, Ayumi</au><au>Kobayashi, Naoki</au><format>book</format><genre>document</genre><ristype>GEN</ristype><atitle>Grammar compression with probabilistic context-free grammar</atitle><jtitle>arXiv.org</jtitle><date>2020-03-18</date><risdate>2020</risdate><eissn>2331-8422</eissn><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 \emph{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.</abstract><cop>Ithaca</cop><pub>Cornell University Library, arXiv.org</pub><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier EISSN: 2331-8422
ispartof arXiv.org, 2020-03
issn 2331-8422
language eng
recordid cdi_proquest_journals_2379276609
source Publicly Available Content Database
subjects Canonical forms
title Grammar compression with probabilistic context-free grammar
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-26T02%3A27%3A18IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest&rft_val_fmt=info:ofi/fmt:kev:mtx:book&rft.genre=document&rft.atitle=Grammar%20compression%20with%20probabilistic%20context-free%20grammar&rft.jtitle=arXiv.org&rft.au=Naganuma,%20Hiroaki&rft.date=2020-03-18&rft.eissn=2331-8422&rft_id=info:doi/&rft_dat=%3Cproquest%3E2379276609%3C/proquest%3E%3Cgrp_id%3Ecdi_FETCH-proquest_journals_23792766093%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2379276609&rft_id=info:pmid/&rfr_iscdi=true