Grammar-based code (original) (raw)
Grammar-based codes or Grammar-based compression are compression algorithms based on the idea of constructing a context-free grammar (CFG) for the string to be compressed. Examples include universal lossless data compression algorithms. To compress a data sequence , a grammar-based code transforms into a context-free grammar .The problem of finding a smallest grammar for an input sequence (smallest grammar problem) is known to be NP-hard, so many grammar-transform algorithms are proposed from theoretical and practical viewpoints.Generally, the produced grammar is further compressed by statistical encoders like arithmetic coding.
| Property | Value |
|---|---|
| dbo:abstract | Grammar-based codes or Grammar-based compression are compression algorithms based on the idea of constructing a context-free grammar (CFG) for the string to be compressed. Examples include universal lossless data compression algorithms. To compress a data sequence , a grammar-based code transforms into a context-free grammar .The problem of finding a smallest grammar for an input sequence (smallest grammar problem) is known to be NP-hard, so many grammar-transform algorithms are proposed from theoretical and practical viewpoints.Generally, the produced grammar is further compressed by statistical encoders like arithmetic coding. (en) 文法圧縮（ぶんぽうあっしゅく、grammar-based codes、grammar compression）とは、入力文字列データから文脈自由文法（context-free grammar、CFG）を構築する圧縮法の総称である。可逆圧縮。 (ja) Kodowanie gramatykowe (ang. grammar-based coding) – nazwa grupy algorytmów kodowania stosowanych w bezstratnej kompresji danych, w których dane wejściowe opisuje się gramatyką bezkontekstową, dąży się przy tym do minimalizacji ilości reguł. Następnie gramatyka jest kompresowana innymi metodami. Kodowanie sprawdza się m.in. w kompresji DNA oraz tekstów naturalnych, w których powtarzają się ciągi liter, ale często też całe słowa, frazy czy zdania. Idea kodowania gramatykowego wykorzystuje powtórzenia ciągów liter, które są zastępowane specjalnymi symbolami (nieterminalnymi). Np. w tekście „aaabaaacaaadaaae” powtarza się ciąg „aaa”, stąd gramatyka która go opisuje może składać się z dwóch reguł: 1. * – reguła pomocnicza, zapamiętująca powtórzenie; 2. * – reguła główna, opisująca cały tekst (gdzie to symbol startowy). Istnieją dwa podejścia do budowania gramatyki: 1. * Kodowanie rozpoczyna się od pustego ciągu, do którego dopisywane są kolejne litery z tekstu i gdy zajdzie potrzeba, tworzone są nowe reguły pomocnicze. Metody działające według tego schematu: 2. * LZ78, LZW, 3. * Sequitur. 4. * Kodowanie rozpoczyna się od wejściowego tekstu i w wyniku jego całościowej analizy podejmowane są decyzje o dodaniu nowych reguł. Metody działające według tego schematu: 5. * Multilevel Pattern Matching (MPM), 6. * Byte Pair Encoding (BPE), 7. * Greedy. (pl) |
| dbo:thumbnail | wiki-commons:Special:FilePath/IndpGrm.gif?width=300 |
| dbo:wikiPageExternalLink | https://encode.su/threads/2427-GLZA http://www.dcc.uchile.cl/~gnavarro/software/index.html https://www.mit.edu/~6.454/www_fall_2002/emin/summary.pdf http://www.cbrc.jp/~rwan/en/restore.html http://sequitur.info https://github.com/GrammarViz2/grammarviz2_src |
| dbo:wikiPageID | 3136832 (xsd:integer) |
| dbo:wikiPageLength | 5631 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1082091538 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Entropy_rate dbr:Block_code dbc:Data_compression dbr:Context-free_grammar dbr:Grammar_induction dbr:Arithmetic_coding dbr:Data_compression dbc:Information_theory dbc:Coding_theory dbr:Ergodic dbr:Dictionary_coder dbr:Straight-line_grammar dbr:LZ77_and_LZ78 dbr:Smallest_grammar_problem dbr:Re-Pair dbr:SEQUITUR_algorithm dbr:Lossless_data_compression dbr:GLZA dbr:File:IndpGrm.gif |
| dbp:wikiPageUsesTemplate | dbt:Reflist dbt:Short_description dbt:Compression_methods |
| dcterms:subject | dbc:Data_compression dbc:Information_theory dbc:Coding_theory |
| rdfs:comment | Grammar-based codes or Grammar-based compression are compression algorithms based on the idea of constructing a context-free grammar (CFG) for the string to be compressed. Examples include universal lossless data compression algorithms. To compress a data sequence , a grammar-based code transforms into a context-free grammar .The problem of finding a smallest grammar for an input sequence (smallest grammar problem) is known to be NP-hard, so many grammar-transform algorithms are proposed from theoretical and practical viewpoints.Generally, the produced grammar is further compressed by statistical encoders like arithmetic coding. (en) 文法圧縮（ぶんぽうあっしゅく、grammar-based codes、grammar compression）とは、入力文字列データから文脈自由文法（context-free grammar、CFG）を構築する圧縮法の総称である。可逆圧縮。 (ja) Kodowanie gramatykowe (ang. grammar-based coding) – nazwa grupy algorytmów kodowania stosowanych w bezstratnej kompresji danych, w których dane wejściowe opisuje się gramatyką bezkontekstową, dąży się przy tym do minimalizacji ilości reguł. Następnie gramatyka jest kompresowana innymi metodami. Kodowanie sprawdza się m.in. w kompresji DNA oraz tekstów naturalnych, w których powtarzają się ciągi liter, ale często też całe słowa, frazy czy zdania. 1. * – reguła pomocnicza, zapamiętująca powtórzenie; 2. * – reguła główna, opisująca cały tekst (gdzie to symbol startowy). (pl) |
| rdfs:label | Grammar-based code (en) 文法圧縮 (ja) Kodowanie gramatykowe (pl) |
| owl:sameAs | freebase:Grammar-based code wikidata:Grammar-based code dbpedia-ja:Grammar-based code dbpedia-pl:Grammar-based code https://global.dbpedia.org/id/4nLve |
| prov:wasDerivedFrom | wikipedia-en:Grammar-based_code?oldid=1082091538&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/IndpGrm.gif |
| foaf:isPrimaryTopicOf | wikipedia-en:Grammar-based_code |
| is dbo:wikiPageRedirects of | dbr:Grammar-based_compression dbr:Grammar-based_codes dbr:GLZA |
| is dbo:wikiPageWikiLink of | dbr:Induction_of_regular_languages dbr:Grammar-based_compression dbr:Grammar_induction dbr:Lossless_compression dbr:John_Kieffer dbr:Heavy_path_decomposition dbr:Grammar-based_codes dbr:Dictionary_coder dbr:Smallest_grammar_problem dbr:Re-Pair dbr:GLZA |
| is foaf:primaryTopic of | wikipedia-en:Grammar-based_code |
