Zobrazeno 1 - 10
of 26
pro vyhledávání: '"Smallest grammar problem"'
Grammar-based compression is a loss-less data compression scheme that represents a given string w by a context-free grammar that generates only w. While computing the smallest grammar which generates a given string w is NP-hard in general, a number o
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b10a9523aede52f93ae266a7190ab2ac
Publikováno v:
Algorithms, Vol 4, Iss 4, Pp 262-284 (2011)
The smallest grammar problem—namely, finding a smallest context-free grammar that generates exactly one sequence—is of practical and theoretical importance in fields such as Kolmogorov complexity, data compression and pattern discovery. We propos
Externí odkaz:
https://doaj.org/article/67a87f6420214577a7b290ed7a2a4f18
Autor:
Artur Jeż, Danny Hucke, Hideo Bannai, Carl Philipp Reh, Markus Lohrey, Momoko Hirayama, Shunsuke Inenaga
In a seminal paper of Charikar et al. on the smallest grammar problem, the authors derive upper and lower bounds on the approximation ratios for several grammar-based compressors, but in all cases there is a gap between the lower and upper bound. Her
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::465a1382023f1235cd31b4aa0326c1d8
http://arxiv.org/abs/1908.06428
http://arxiv.org/abs/1908.06428
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Publikováno v:
KDD
Data represented as strings abounds in biology, linguistics, document mining, web search and many other fields. Such data often have a hierarchical structure, either because they were artificially designed and composed in a hierarchical manner or bec
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::f7732b4692049ee475ecd3a54fcbed99
https://doi.org/10.1145/2939672.2939741
https://doi.org/10.1145/2939672.2939741
Publikováno v:
String Processing and Information Retrieval ISBN: 9783319460482
SPIRE
SPIRE
In a seminal paper of Charikar et al. on the smallest grammar problem, the authors derive upper and lower bounds on the approximation ratios for several grammar-based compressors, but in all cases there is a gap between the lower and upper bound. Her
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::ed4f321f0a11fcb82ec94451c2c94263
https://doi.org/10.1007/978-3-319-46049-9_4
https://doi.org/10.1007/978-3-319-46049-9_4
Autor:
Abhi Shelat, Eric Lehman, Ding Liu, Moses Charikar, Rina Panigrahy, Amit Sahai, Manoj Prabhakaran
Publikováno v:
IEEE Transactions on Information Theory. 51:2554-2576
This paper addresses the smallest grammar problem: What is the smallest context-free grammar that generates exactly one given string /spl sigma/? This is a natural question about a fundamental object connected to many fields such as data compression,
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::326e84be4b49b54cda1e86eb382f4893
https://doi.org/10.1109/tit.2005.850116
https://doi.org/10.1109/tit.2005.850116
Publikováno v:
Algorithms
Algorithms, 2011, 4, pp.262-284. ⟨10.3390/a4040262⟩
Algorithms, MDPI, 2011, pp.262-284. ⟨10.3390/a4040262⟩
Algorithms, Vol 4, Iss 4, Pp 262-284 (2011)
Algorithms; Volume 4; Issue 4; Pages: 262-284
Algorithms, 2011, 4, pp.262-284. ⟨10.3390/a4040262⟩
Algorithms, MDPI, 2011, pp.262-284. ⟨10.3390/a4040262⟩
Algorithms, Vol 4, Iss 4, Pp 262-284 (2011)
Algorithms; Volume 4; Issue 4; Pages: 262-284
International audience; The smallest grammar problem--namely, finding a smallest context-free grammar that generates exactly one sequence--is of practical and theoretical importance in fields such as Kolmogorov complexity, data compression and patter
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d5b959fd3137ed7ab062fa72322c19a4
https://inria.hal.science/inria-00638445
https://inria.hal.science/inria-00638445
Autor:
Jim X. Chen, Yuan Li
Publikováno v:
2014 11th International Computer Conference on Wavelet Actiev Media Technology and Information Processing(ICCWAMTIP).
Grammar induction has received a lot of attention from researchers in the past decades because of its practical and theoretical impact on data compression, pattern discovery and computation theory. There are a bunch of grammar induction algorithms fo
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::ed43e85909cb61566645297246cd76be
https://doi.org/10.1109/iccwamtip.2014.7073350
https://doi.org/10.1109/iccwamtip.2014.7073350