| 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
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 5631 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| 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
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
