Grammar-based code
http://dbpedia.org/resource/Grammar-based_code
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.
rdf:langString
文法圧縮（ぶんぽうあっしゅく、grammar-based codes、grammar compression）とは、入力文字列データから文脈自由文法（context-free grammar、CFG）を構築する圧縮法の総称である。可逆圧縮。
rdf:langString
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).
rdf:langString
rdf:langString
Grammar-based code
rdf:langString
文法圧縮
rdf:langString
Kodowanie gramatykowe
xsd:integer
3136832
xsd:integer
1082091538
rdf:langString
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.
rdf:langString
文法圧縮（ぶんぽうあっしゅく、grammar-based codes、grammar compression）とは、入力文字列データから文脈自由文法（context-free grammar、CFG）を構築する圧縮法の総称である。可逆圧縮。
rdf:langString
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.
xsd:nonNegativeInteger
5631
