{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T01:51:22Z","timestamp":1760233882536,"version":"build-2065373602"},"reference-count":24,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2021,2,20]],"date-time":"2021-02-20T00:00:00Z","timestamp":1613779200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["LO 748\/10-2"],"award-info":[{"award-number":["LO 748\/10-2"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>A grammar-based compressor is an algorithm that receives a word and outputs a context-free grammar that only produces this word. The approximation ratio for a single input word is the size of the grammar produced for this word divided by the size of a smallest grammar for this word. The worst-case approximation ratio of a grammar-based compressor for a given word length is the largest approximation ratio over all input words of that length. In this work, we study the worst-case approximation ratio of the algorithms Greedy, RePair and LongestMatch on unary strings, i.e., strings that only make use of a single symbol. Our main contribution is to show the improved upper bound of O((logn)8\u00b7(loglogn)3) for the worst-case approximation ratio of Greedy. In addition, we also show the lower bound of 1.34847194\u22ef for the worst-case approximation ratio of Greedy, and that RePair and LongestMatch have a worst-case approximation ratio of log2(3).<\/jats:p>","DOI":"10.3390\/a14020065","type":"journal-article","created":{"date-parts":[[2021,2,21]],"date-time":"2021-02-21T21:15:01Z","timestamp":1613942101000},"page":"65","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Approximation Ratios of RePair, LongestMatch and Greedy on Unary Strings"],"prefix":"10.3390","volume":"14","author":[{"given":"Danny","family":"Hucke","sequence":"first","affiliation":[{"name":"Department Elektrotechnik und Informatik, Universit\u00e4t Siegen, D-57068 Siegen, Germany"}]},{"given":"Carl Philipp","family":"Reh","sequence":"additional","affiliation":[{"name":"Department Elektrotechnik und Informatik, Universit\u00e4t Siegen, D-57068 Siegen, Germany"}]}],"member":"1968","published-online":{"date-parts":[[2021,2,20]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"530","DOI":"10.1109\/TIT.1978.1055934","article-title":"Compression of individual sequences via variable-rate coding","volume":"24","author":"Ziv","year":"1978","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1227","DOI":"10.1109\/18.850665","article-title":"Universal lossless compression via multilevel pattern matching","volume":"46","author":"Kieffer","year":"2000","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_3","first-page":"67","article-title":"Identifying Hierarchical Structure in Sequences: A linear-time algorithm","volume":"7","author":"Witten","year":"1997","journal-title":"CoRR"},{"key":"ref_4","unstructured":"Apostolico, A., and Lonardi, S. (April, January 30). Some Theory and Practice of Greedy Off-Line Textual Substitution. Proceedings of the Data Compression Conference, DCC 1998, IEEE Computer Society, Snowbird, UH, USA."},{"key":"ref_5","unstructured":"Apostolico, A., and Lonardi, S. (2000, January 28\u201330). Compression of Biological Sequences by Greedy Off-Line Textual Substitution. Proceedings of the Data Compression Conference, DCC 2000, IEEE Computer Society, Snowbird, UH, USA."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"1733","DOI":"10.1109\/5.892709","article-title":"Off-line compression by greedy textual substitution","volume":"88","author":"Apostolico","year":"2000","journal-title":"Proc. IEEE"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Larsson, N.J., and Moffat, A. (1999, January 29\u201331). Offline Dictionary-Based Compression. Proceedings of the Data Compression Conference, DCC 1999, IEEE Computer Society, Snowbird, UH, USA.","DOI":"10.1109\/DCC.1999.755679"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"737","DOI":"10.1109\/18.841160","article-title":"Grammar-based codes: A new class of universal lossless source codes","volume":"46","author":"Kieffer","year":"2000","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"16:1","DOI":"10.1145\/1841909.1841913","article-title":"Fast and Compact Web Graph Representations","volume":"4","author":"Claude","year":"2010","journal-title":"ACM Trans. Web"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1016\/S0304-3975(02)00426-7","article-title":"Collage system: a unifying framework for compressed pattern matching","volume":"298","author":"Kida","year":"2003","journal-title":"Theor. Comput. Sci."},{"key":"ref_11","first-page":"216","article-title":"Compressed Text Indexes with Fast Locate","volume":"Volume 4580","author":"Ma","year":"2007","journal-title":"Proceedings of the Combinatorial Pattern Matching, 18th Annual Symposium, CPM 2007"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1150","DOI":"10.1016\/j.is.2013.06.006","article-title":"XML tree structure compression using RePair","volume":"38","author":"Lohrey","year":"2013","journal-title":"Inf. Syst."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"2554","DOI":"10.1109\/TIT.2005.850116","article-title":"The smallest grammar problem","volume":"51","author":"Charikar","year":"2005","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_14","first-page":"35","article-title":"The Smallest Grammar Problem Revisited","volume":"Volume 9954","author":"Inenaga","year":"2016","journal-title":"Proceedings of the String Processing and Information Retrieval\u201423rd International Symposium, SPIRE 2016"},{"key":"ref_15","unstructured":"Hucke, D., Jez, A., and Lohrey, M. (2017). Approximation ratio of RePair. arXiv."},{"key":"ref_16","unstructured":"Knuth, D.E. (1998). The Art of Computer Programming, Volume II: Seminumerical Algorithms, Addison-Wesley. [3rd ed.]."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"275","DOI":"10.3844\/jcssp.2017.275.289","article-title":"A Review on Heuristics for Addition Chain Problem: Towards Efficient Public Key Cryptosystems","volume":"13","author":"Noma","year":"2017","journal-title":"J. Comput. Sci."},{"key":"ref_18","first-page":"3","article-title":"Approximation Ratios of RePair, LongestMatch and Greedy on Unary Strings","volume":"Volume 11811","author":"Brisaboa","year":"2019","journal-title":"Proceedings of the String Processing and Information Retrieval\u201426th International Symposium, SPIRE 2019"},{"key":"ref_19","first-page":"429","article-title":"Some doubly exponential sequences","volume":"11","author":"Aho","year":"1973","journal-title":"Fibonacci Quart."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/0020-0190(87)90031-7","article-title":"On the Length of Word Chains","volume":"26","author":"Berstel","year":"1987","journal-title":"Inf. Process. Lett."},{"key":"ref_21","unstructured":"Diwan, A.A. (1986). A New Combinatorial Complexity Measure for Languages, Tata Institute."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"928","DOI":"10.1145\/322344.322346","article-title":"Data compression via textual substitution","volume":"29","author":"Storer","year":"1982","journal-title":"J. ACM"},{"key":"ref_23","first-page":"122","article-title":"On the Complexity of Grammar-Based Compression over Fixed Alphabets","volume":"Volume 55","author":"Chatzigiannakis","year":"2016","journal-title":"Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"3160","DOI":"10.1109\/TIT.2018.2871452","article-title":"RePair and All Irreducible Grammars are Upper Bounded by High-Order Empirical Entropy","volume":"65","author":"Ochoa","year":"2019","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/2\/65\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:26:46Z","timestamp":1760160406000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/2\/65"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,20]]},"references-count":24,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2021,2]]}},"alternative-id":["a14020065"],"URL":"https:\/\/doi.org\/10.3390\/a14020065","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2021,2,20]]}}}