{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:27:21Z","timestamp":1760239641476,"version":"build-2065373602"},"reference-count":43,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2020,12,25]],"date-time":"2020-12-25T00:00:00Z","timestamp":1608854400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP18F18120, 19K20213, 18K18111"],"award-info":[{"award-number":["JP18F18120, 19K20213, 18K18111"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"name":"JST CREST","award":["JPMJCR1402"],"award-info":[{"award-number":["JPMJCR1402"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Re-Pairis a grammar compression scheme with favorably good compression rates. The computation of Re-Pair comes with the cost of maintaining large frequency tables, which makes it hard to compute Re-Pair on large-scale data sets. As a solution for this problem, we present, given a text of length n whose characters are drawn from an integer alphabet with size \u03c3=nO(1), an O(min(n2,n2lglog\u03c4nlglglgn\/log\u03c4n)) time algorithm computing Re-Pair with max((n\/c)lgn,nlg\u03c4)+O(lgn) bits of working space including the text space, where c\u22651 is a fixed user-defined constant and \u03c4 is the sum of \u03c3 and the number of non-terminals. We give variants of our solution working in parallel or in the external memory model. Unfortunately, the algorithm seems not practical since a preliminary version already needs roughly one hour for computing Re-Pair on one megabyte of text.<\/jats:p>","DOI":"10.3390\/a14010005","type":"journal-article","created":{"date-parts":[[2020,12,27]],"date-time":"2020-12-27T20:04:58Z","timestamp":1609099498000},"page":"5","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Re-Pair in Small Space"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8721-4444","authenticated-orcid":false,"given":"Dominik","family":"K\u00f6ppl","sequence":"first","affiliation":[{"name":"M&amp;D Data Science Center, Tokyo Medical and Dental University, Tokyo 113-8510, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9106-6192","authenticated-orcid":false,"given":"Tomohiro","family":"I","sequence":"additional","affiliation":[{"name":"Kyushu Institute of Technology, Fukuoka 820-8502, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1918-5802","authenticated-orcid":false,"given":"Isamu","family":"Furuya","sequence":"additional","affiliation":[{"name":"Graduate School of IST, Hokkaido University, Hokkaido 060-0814, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4566-8974","authenticated-orcid":false,"given":"Yoshimasa","family":"Takabatake","sequence":"additional","affiliation":[{"name":"Kyushu Institute of Technology, Fukuoka 820-8502, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kensuke","family":"Sakai","sequence":"additional","affiliation":[{"name":"Kyushu Institute of Technology, Fukuoka 820-8502, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Keisuke","family":"Goto","sequence":"additional","affiliation":[{"name":"Fujitsu Laboratories Ltd., Kawasaki 211-8588, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,12,25]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Larsson, N.J., and Moffat, A. (1999, January 29\u201331). Offline Dictionary-Based Compression. Proceedings of the 1999 Data Compression Conference, Snowbird, UT, USA.","DOI":"10.1109\/DCC.1999.755679"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Navarro, G., and Russo, L.M.S. (2008, January 25\u201327). Re-Pair Achieves High-Order Entropy. Proceedings of the 2008 Data Compression Conference, Snowbird, UT, USA.","DOI":"10.1109\/DCC.2008.79"},{"key":"ref_3","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_4","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"},{"key":"ref_5","first-page":"11:1","article-title":"Entropy Lower Bounds for Dictionary Compression","volume":"128","author":"Ganczorz","year":"2019","journal-title":"Proc. CPM"},{"key":"ref_6","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_7","unstructured":"Bannai, H., Hirayama, M., Hucke, D., Inenaga, S., Jez, A., Lohrey, M., and Reh, C.P. (2019). The smallest grammar problem revisited. arXiv."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Yoshida, S., and Kida, T. (2013, January 20\u201322). Effective Variable-Length-to-Fixed-Length Coding via a Re-Pair Algorithm. Proceedings of the 2013 Data Compression Conference, Snowbird, UT, USA.","DOI":"10.1109\/DCC.2013.111"},{"key":"ref_9","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_10","doi-asserted-by":"crossref","unstructured":"Tabei, Y., Saigo, H., Yamanishi, Y., and Puglisi, S.J. (2016, January 13\u201317). Scalable Partial Least Squares Regression on Grammar-Compressed Data Matrices. Proceedings of the SIGKDD, San Francisco, CA, USA.","DOI":"10.1145\/2939672.2939864"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"de Luca, P., Russiello, V.M., Ciro-Sannino, R., and Valente, L. (2019). A study for Image compression using Re-Pair algorithm. arXiv.","DOI":"10.22606\/fsp.2019.33001"},{"key":"ref_12","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":"TWEB"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2670128","article-title":"Locally Compressed Suffix Arrays","volume":"19","author":"Navarro","year":"2014","journal-title":"ACM J. Exp. Algorithmics"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Sekine, K., Sasakawa, H., Yoshida, S., and Kida, T. (2014, January 26\u201328). Adaptive Dictionary Sharing Method for Re-Pair Algorithm. Proceedings of the 2014 Data Compression Conference, Snowbird, UT, USA.","DOI":"10.1109\/DCC.2014.73"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Masaki, T., and Kida, T. (April, January 30). Online Grammar Transformation Based on Re-Pair Algorithm. Proceedings of the 2016 Data Compression Conference (DCC), Snowbird, UT, USA.","DOI":"10.1109\/DCC.2016.69"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Ganczorz, M., and Jez, A. (2017, January 4\u20137). Improvements on Re-Pair Grammar Compressor. Proceedings of the 2017 Data Compression Conference (DCC), Snowbird, UT, USA.","DOI":"10.1109\/DCC.2017.52"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","article-title":"A universal algorithm for sequential data compression","volume":"23","author":"Ziv","year":"1977","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Furuya, I., Takagi, T., Nakashima, Y., Inenaga, S., Bannai, H., and Kida, T. (2019, January 26\u201329). MR-RePair: Grammar Compression based on Maximal Repeats. Proceedings of the 2019 Data Compression Conference (DCC), Snowbird, UT, USA.","DOI":"10.1109\/DCC.2019.00059"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"K\u00e4rkk\u00e4inen, J., Kempa, D., and Puglisi, S.J. (2013, January 5\u20137). Lightweight Lempel-Ziv Parsing. Proceedings of the International Symposium on Experimental Algorithms, Rome, Italy.","DOI":"10.1007\/978-3-642-38527-8_14"},{"key":"ref_20","unstructured":"Goto, K. (2019, January 26\u201328). Optimal Time and Space Construction of Suffix Arrays and LCP Arrays for Integer Alphabets. Proceedings of the Prague Stringology Conference 2019, Prague, Czech Republic."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1137\/0222058","article-title":"Suffix Arrays: A New Method for On-Line String Searches","volume":"22","author":"Manber","year":"1993","journal-title":"SIAM J. Comput."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Li, Z., Li, J., and Huo, H. (2018, January 9\u201311). Optimal In-Place Suffix Sorting. Proceedings of the International Symposium on String Processing and Information Retrieval, Lima, Peru.","DOI":"10.1007\/978-3-030-00479-8_22"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1016\/j.jda.2015.01.004","article-title":"Computing the Burrows-Wheeler transform in place and in small space","volume":"32","author":"Crochemore","year":"2015","journal-title":"J. Discret. Algorithms"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1016\/j.jda.2016.11.003","article-title":"Burrows-Wheeler transform and LCP array construction in constant space","volume":"42","author":"Gagie","year":"2017","journal-title":"J. Discret. Algorithms"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Kosolobov, D. (2015, January 24\u201328). Faster Lightweight Lempel-Ziv Parsing. Proceedings of the International Symposium on Mathematical Foundations of Computer Science, Milano, Italy.","DOI":"10.1007\/978-3-662-48054-0_36"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"1429","DOI":"10.3390\/a2041429","article-title":"Linear-Time Text Compression by Longest-First Substitution","volume":"2","author":"Nakamura","year":"2009","journal-title":"Algorithms"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Bille, P., G\u00f8rtz, I.L., and Prezza, N. (2017, January 4\u20137). Space-Efficient Re-Pair Compression. Proceedings of the 2017 Data Compression Conference (DCC), Snowbird, UT, USA.","DOI":"10.1109\/DCC.2017.24"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Bille, P., G\u00f8rtz, I.L., and Prezza, N. (2017). Practical and Effective Re-Pair Compression. arXiv.","DOI":"10.1109\/DCC.2017.24"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Sakai, K., Ohno, T., Goto, K., Takabatake, Y., I, T., and Sakamoto, H. (2019, January 26\u201329). RePair in Compressed Space and Time. Proceedings of the 2019 Data Compression Conference (DCC), Snowbird, UT, USA.","DOI":"10.1109\/DCC.2019.00060"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Carrascosa, R., Coste, F., Gall\u00e9, M., and L\u00f3pez, G.G.I. (2010, January 24\u201328). Choosing Word Occurrences for the Smallest Grammar Problem. Proceedings of the International Conference on Language and Automata Theory and Applications, Trier, Germany.","DOI":"10.1007\/978-3-642-13089-2_13"},{"key":"ref_31","first-page":"23","article-title":"A New Algorithm for Data Compression","volume":"12","author":"Gage","year":"1994","journal-title":"C Users J."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"11:1","DOI":"10.1145\/3168005","article-title":"Selection and Sorting in the \u201cRestore\u201d Model","volume":"14","author":"Chan","year":"2018","journal-title":"ACM Trans. Algorithms"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1145\/512274.512284","article-title":"Algorithm 232\u2014Heapsort","volume":"7","author":"Williams","year":"1964","journal-title":"Commun. ACM"},{"key":"ref_34","unstructured":"Vigna, S. (June, January 30). Broadword Implementation of Rank\/Select Queries. Proceedings of the International Workshop on Experimental and Efficient Algorithms, Provincetown, MA, USA."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"424","DOI":"10.1016\/0022-0000(93)90040-4","article-title":"Surpassing the Information Theoretic Bound with Fusion Trees","volume":"47","author":"Fredman","year":"1993","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_36","unstructured":"Knuth, D.E. (2009). The Art of Computer Programming, Volume 4, Fascicle 1: Bitwise Tricks & Techniques; Binary Decision Diagrams, Addison-Wesley. [12th ed.]."},{"key":"ref_37","unstructured":"Batcher, K.E. (May, January 30). Sorting Networks and Their Applications. Proceedings of the AFIPS Spring Joint Computer Conference, Atlantic City, NJ, USA."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"1116","DOI":"10.1145\/48529.48535","article-title":"The Input\/Output Complexity of Sorting and Related Problems","volume":"31","author":"Aggarwal","year":"1988","journal-title":"Commun. ACM"},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Jiang, S., and Larsen, K.G. (2019, January 6\u20139). A Faster External Memory Priority Queue with DecreaseKeys. Proceedings of the 2019 Annual ACM-SIAM Symposium on Discrete Algorithms, San Diego, CA, USA.","DOI":"10.1137\/1.9781611975482.81"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"1262","DOI":"10.1016\/j.aml.2009.01.040","article-title":"Jensen\u2019s inequality and new entropy bounds","volume":"22","author":"Simic","year":"2009","journal-title":"Appl. Math. Lett."},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Boyer, R.S., and Moore, J.S. (1991). MJRTY: A Fast Majority Vote Algorithm. Automated Reasoning: Essays in Honor of Woody Bledsoe, Springer.","DOI":"10.1007\/978-94-011-3488-0_5"},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"K\u00f6ppl, D., Furuya, I., Takabatake, Y., Sakai, K., and Goto, K. (September, January 31). Re-Pair in Small Space. Proceedings of the Prague Stringology Conference 2020, Prague, Czech Republic.","DOI":"10.1109\/DCC47342.2020.00092"},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"K\u00f6ppl, D., I, T., Furuya, I., Takabatake, Y., Sakai, K., and Goto, K. (2020, January 24\u201327). Re-Pair in Small Space (Poster). Proceedings of the 2020 Data Compression Conference, Snowbird, UT, USA.","DOI":"10.1109\/DCC47342.2020.00092"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/1\/5\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:46:20Z","timestamp":1760179580000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/1\/5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,25]]},"references-count":43,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2021,1]]}},"alternative-id":["a14010005"],"URL":"https:\/\/doi.org\/10.3390\/a14010005","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2020,12,25]]}}}