@prefix ns1: . @prefix ns2: . @prefix rdf: . @prefix rdfs: . @prefix xml: . @prefix xsd: . a ns1:Chapter ; ns1:about , ; ns1:author ( ) ; ns1:datePublished "2014" ; ns1:datePublishedReg "2014-01-01" ; ns1:description """We present a really 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, where N is the size of the input string and g the size of the optimal grammar generating this string. The algorithm works for arbitrary size alphabets, but the running time is linear when the alphabet Σ of the input string can be identified with numbers from {1,…, N}. Algorithms with such an approximation guarantee and running time are known, however all of them were non-trivial and their analyses involved. The here presented algorithm computes the LZ77 factorisation (of size l) and transforms it in phases to a grammar. In each phase it maintains an LZ77-like factorisation of the word with at most l factors as well as additional \\documentclass[12pt]{minimal} \\usepackage{amsmath} \\usepackage{wasysym} \\usepackage{amsfonts} \\usepackage{amssymb} \\usepackage{amsbsy} \\usepackage{mathrsfs} \\usepackage{upgreek} \\setlength{\\oddsidemargin}{-69pt} \\begin{document}$\\mathcal{O}(l)$\\end{document} letters. In one phase in a greedy way (by a left-to-right sweep) we choose a set of pairs of consecutive letters to be replaced with new symbols, i.e. nonterminals of the constructed grammar. We choose at least 2/3 of the letters in the word and there are \\documentclass[12pt]{minimal} \\usepackage{amsmath} \\usepackage{wasysym} \\usepackage{amsfonts} \\usepackage{amssymb} \\usepackage{amsbsy} \\usepackage{mathrsfs} \\usepackage{upgreek} \\setlength{\\oddsidemargin}{-69pt} \\begin{document}$\\mathcal{O}(l)$\\end{document} many different pairs among them. Hence there are \\documentclass[12pt]{minimal} \\usepackage{amsmath} \\usepackage{wasysym} \\usepackage{amsfonts} \\usepackage{amssymb} \\usepackage{amsbsy} \\usepackage{mathrsfs} \\usepackage{upgreek} \\setlength{\\oddsidemargin}{-69pt} \\begin{document}$\\mathcal{O}(log N)$\\end{document} phases, each introduces \\documentclass[12pt]{minimal} \\usepackage{amsmath} \\usepackage{wasysym} \\usepackage{amsfonts} \\usepackage{amssymb} \\usepackage{amsbsy} \\usepackage{mathrsfs} \\usepackage{upgreek} \\setlength{\\oddsidemargin}{-69pt} \\begin{document}$\\mathcal{O}(l)$\\end{document} nonterminals. A more precise analysis yields a bound \\documentclass[12pt]{minimal} \\usepackage{amsmath} \\usepackage{wasysym} \\usepackage{amsfonts} \\usepackage{amssymb} \\usepackage{amsbsy} \\usepackage{mathrsfs} \\usepackage{upgreek} \\setlength{\\oddsidemargin}{-69pt} \\begin{document}$\\mathcal{O}(l log(N/l))$\\end{document}. As l ≤ g, this yields \\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}.""" ; ns1:editor ( [ a ns1:Person ; ns1:familyName "Kulikov" ; ns1:givenName "Alexander S." ] [ a ns1:Person ; ns1:familyName "Kuznetsov" ; ns1:givenName "Sergei O." ] [ a ns1:Person ; ns1:familyName "Pevzner" ; ns1:givenName "Pavel" ] ) ; ns1:genre "chapter" ; ns1:inLanguage "en" ; ns1:isAccessibleForFree true ; ns1:isPartOf [ a ns1:Book ; ns1:isbn "978-3-319-07565-5", "978-3-319-07566-2" ; ns1:name "Combinatorial Pattern Matching" ] ; ns1:keywords "algorithm", "algorithm computes", "alphabet", "alphabet Σ", "analysis", "approximation", "approximation guarantee", "arbitrary size alphabets", "compute", "consecutive letters", "context-free grammars", "different pairs", "factorisation", "factors", "grammar", "greedy way", "guarantees", "input string", "introduces", "letter", "linear time algorithm", "new symbols", "nonterminals", "number", "optimal grammar", "pairs", "phase", "precise analysis", "running time", "set", "set of pairs", "simple approximation", "simple linear time algorithm", "size", "size alphabet", "strings", "symbols", "time", "way", "words", "yield" ; ns1:name "A really Simple Approximation of Smallest Grammar" ; ns1:pagination "182-191" ; ns1:productId [ a ns1:PropertyValue ; ns1:name "dimensions_id" ; ns1:value "pub.1035201050" ], [ a ns1:PropertyValue ; ns1:name "doi" ; ns1:value "10.1007/978-3-319-07566-2_19" ] ; ns1:publisher [ a ns1:Organisation ; ns1:name "Springer Nature" ] ; ns1:sameAs , ; ns1:sdDatePublished "2022-06-01T22:32" ; ns1:sdLicense "https://scigraph.springernature.com/explorer/license/" ; ns1:sdPublisher [ a ns1:Organization ; ns1:name "Springer Nature - SN SciGraph project" ] ; ns1:url "https://doi.org/10.1007/978-3-319-07566-2_19" ; ns2:license ; ns2:sdDataset "chapters" . a ns1:DefinedTerm ; ns1:inDefinedTermSet ; ns1:name "Mathematical Sciences" . a ns1:DefinedTerm ; ns1:inDefinedTermSet ; ns1:name "Pure Mathematics" . a ns1:Person ; ns1:affiliation ; ns1:familyName "Jeż" ; ns1:givenName "Artur" ; ns1:sameAs . a ns1:Organization ; ns1:alternateName "Institute of Computer Science, University of Wrocław, Poland" ; ns1:name "Institute of Computer Science, University of Wrocław, Poland", "Max Planck Institute für Informatik, Saarbrücken, Germany" .