Approximation of Grammar-Based Compression via Recompression View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2013

AUTHORS

Artur Jeż

ABSTRACT

We present a simple linear-time algorithm constructing a context-free grammar of size \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{O}(g \log (N/g))$\end{document} for the input string of size N, where g the size of the optimal grammar generating this string. The algorithm works for arbitrary size alphabets, but the running time is linear assuming that the alphabet Σ of the input string is a subset of {1,…, Nc } for some constant c. Algorithms with such an approximation guarantees and running time are known, the novelty of this paper is the particular simplicity of the algorithm as well as the analysis of the algorithm, which uses a general technique of recompression recently introduced by the author. Furthermore, contrary to the previous results, this work does not use the LZ representation of the input string in the construction, nor in the analysis. More... »

PAGES

165-176

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-38905-4_17

DOI

http://dx.doi.org/10.1007/978-3-642-38905-4_17

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1022417385


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Institute of Computer Science, University of Wroc\u0142aw, ul. Joliot-Curie\u00a015, 50-383, Wroc\u0142aw, Poland", 
          "id": "http://www.grid.ac/institutes/grid.8505.8", 
          "name": [
            "Max Planck Institute f\u00fcr Informatik, Campus E1 4, DE-66123, Saarbr\u00fccken, Germany", 
            "Institute of Computer Science, University of Wroc\u0142aw, ul. Joliot-Curie\u00a015, 50-383, Wroc\u0142aw, Poland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Je\u017c", 
        "givenName": "Artur", 
        "id": "sg:person.015252371751.76", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015252371751.76"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2013", 
    "datePublishedReg": "2013-01-01", 
    "description": "We present a simple linear-time algorithm constructing a\u00a0context-free grammar of size \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\mathcal{O}(g \\log (N/g))$\\end{document} for the input string of size N, where g the size of the optimal grammar generating this string. The algorithm works for arbitrary size alphabets, but the running time is linear assuming that the alphabet \u03a3 of the input string is a subset of {1,\u2026, Nc } for some constant c. Algorithms with such an approximation guarantees and running time are known, the novelty of this paper is the particular simplicity of the algorithm as well as the analysis of the algorithm, which uses a general technique of recompression recently introduced by the author. Furthermore, contrary to the previous results, this work does not use the LZ representation of the input string in the construction, nor in the analysis.", 
    "editor": [
      {
        "familyName": "Fischer", 
        "givenName": "Johannes", 
        "type": "Person"
      }, 
      {
        "familyName": "Sanders", 
        "givenName": "Peter", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-38905-4_17", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-38904-7", 
        "978-3-642-38905-4"
      ], 
      "name": "Combinatorial Pattern Matching", 
      "type": "Book"
    }, 
    "keywords": [
      "simple linear time algorithm", 
      "linear time algorithm", 
      "particular simplicity", 
      "size n", 
      "general technique", 
      "running time", 
      "approximation", 
      "size alphabet", 
      "arbitrary size alphabets", 
      "algorithm", 
      "strings", 
      "input string", 
      "previous results", 
      "alphabet \u03a3", 
      "context-free grammars", 
      "representation", 
      "optimal grammar", 
      "simplicity", 
      "alphabet", 
      "novelty", 
      "construction", 
      "size", 
      "technique", 
      "analysis", 
      "time", 
      "subset", 
      "work", 
      "results", 
      "NC", 
      "authors", 
      "recompression", 
      "compression", 
      "grammar", 
      "paper"
    ], 
    "name": "Approximation of Grammar-Based Compression via Recompression", 
    "pagination": "165-176", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1022417385"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-38905-4_17"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-38905-4_17", 
      "https://app.dimensions.ai/details/publication/pub.1022417385"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:45", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_31.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-38905-4_17"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-38905-4_17'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-38905-4_17'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-38905-4_17'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-38905-4_17'


 

This table displays all metadata directly associated to this object as RDF triples.

100 TRIPLES      23 PREDICATES      60 URIs      53 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-38905-4_17 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N2ad737f6029d4ad3b17fd1c8432654b1
4 schema:datePublished 2013
5 schema:datePublishedReg 2013-01-01
6 schema:description We present a simple linear-time algorithm constructing a context-free grammar of size \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{O}(g \log (N/g))$\end{document} for the input string of size N, where g the size of the optimal grammar generating this string. The algorithm works for arbitrary size alphabets, but the running time is linear assuming that the alphabet Σ of the input string is a subset of {1,…, Nc } for some constant c. Algorithms with such an approximation guarantees and running time are known, the novelty of this paper is the particular simplicity of the algorithm as well as the analysis of the algorithm, which uses a general technique of recompression recently introduced by the author. Furthermore, contrary to the previous results, this work does not use the LZ representation of the input string in the construction, nor in the analysis.
7 schema:editor N7316100587b149d9b30ce9ca04b0905f
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N9cd9a532527d48fd9e9da17ffaadbe73
12 schema:keywords NC
13 algorithm
14 alphabet
15 alphabet Σ
16 analysis
17 approximation
18 arbitrary size alphabets
19 authors
20 compression
21 construction
22 context-free grammars
23 general technique
24 grammar
25 input string
26 linear time algorithm
27 novelty
28 optimal grammar
29 paper
30 particular simplicity
31 previous results
32 recompression
33 representation
34 results
35 running time
36 simple linear time algorithm
37 simplicity
38 size
39 size alphabet
40 size n
41 strings
42 subset
43 technique
44 time
45 work
46 schema:name Approximation of Grammar-Based Compression via Recompression
47 schema:pagination 165-176
48 schema:productId N5a35f132ce214a7dbc9fd0a1880b24c0
49 Ndecdf9692a29405badb34ae6a3e6dbdd
50 schema:publisher N8562313abc3c452c8a4cbb2bee551a05
51 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022417385
52 https://doi.org/10.1007/978-3-642-38905-4_17
53 schema:sdDatePublished 2022-05-20T07:45
54 schema:sdLicense https://scigraph.springernature.com/explorer/license/
55 schema:sdPublisher N6894784627cc41329d0f450cffa4eb1a
56 schema:url https://doi.org/10.1007/978-3-642-38905-4_17
57 sgo:license sg:explorer/license/
58 sgo:sdDataset chapters
59 rdf:type schema:Chapter
60 N0ad4ea7177e145fea8bdcd9820c20a2a schema:familyName Sanders
61 schema:givenName Peter
62 rdf:type schema:Person
63 N2ad737f6029d4ad3b17fd1c8432654b1 rdf:first sg:person.015252371751.76
64 rdf:rest rdf:nil
65 N5a35f132ce214a7dbc9fd0a1880b24c0 schema:name dimensions_id
66 schema:value pub.1022417385
67 rdf:type schema:PropertyValue
68 N6894784627cc41329d0f450cffa4eb1a schema:name Springer Nature - SN SciGraph project
69 rdf:type schema:Organization
70 N7316100587b149d9b30ce9ca04b0905f rdf:first Nc162f854cb9d4b4286dac3cf186b0df2
71 rdf:rest Nbd70a77d776a41b2a9324536452d557c
72 N8562313abc3c452c8a4cbb2bee551a05 schema:name Springer Nature
73 rdf:type schema:Organisation
74 N9cd9a532527d48fd9e9da17ffaadbe73 schema:isbn 978-3-642-38904-7
75 978-3-642-38905-4
76 schema:name Combinatorial Pattern Matching
77 rdf:type schema:Book
78 Nbd70a77d776a41b2a9324536452d557c rdf:first N0ad4ea7177e145fea8bdcd9820c20a2a
79 rdf:rest rdf:nil
80 Nc162f854cb9d4b4286dac3cf186b0df2 schema:familyName Fischer
81 schema:givenName Johannes
82 rdf:type schema:Person
83 Ndecdf9692a29405badb34ae6a3e6dbdd schema:name doi
84 schema:value 10.1007/978-3-642-38905-4_17
85 rdf:type schema:PropertyValue
86 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
87 schema:name Information and Computing Sciences
88 rdf:type schema:DefinedTerm
89 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
90 schema:name Computation Theory and Mathematics
91 rdf:type schema:DefinedTerm
92 sg:person.015252371751.76 schema:affiliation grid-institutes:grid.8505.8
93 schema:familyName Jeż
94 schema:givenName Artur
95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015252371751.76
96 rdf:type schema:Person
97 grid-institutes:grid.8505.8 schema:alternateName Institute of Computer Science, University of Wrocław, ul. Joliot-Curie 15, 50-383, Wrocław, Poland
98 schema:name Institute of Computer Science, University of Wrocław, ul. Joliot-Curie 15, 50-383, Wrocław, Poland
99 Max Planck Institute für Informatik, Campus E1 4, DE-66123, Saarbrücken, Germany
100 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...