{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,8,15]],"date-time":"2022-08-15T03:40:26Z","timestamp":1660534826074},"reference-count":29,"publisher":"Institute of Electronics, Information and Communications Engineers (IEICE)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEICE Trans. Inf. & Syst."],"published-print":{"date-parts":[[2018]]},"DOI":"10.1587\/transinf.2017fcp0010","type":"journal-article","created":{"date-parts":[[2018,3,1]],"date-time":"2018-03-01T22:25:06Z","timestamp":1519943106000},"page":"593-601","source":"Crossref","is-referenced-by-count":0,"title":["Approximate Frequent Pattern Discovery in Compressed Space"],"prefix":"10.1587","volume":"E101.D","author":[{"given":"Shouhei","family":"FUKUNAGA","sequence":"first","affiliation":[{"name":"Department of Artificial Intelligence, Kyushu Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yoshimasa","family":"TAKABATAKE","sequence":"additional","affiliation":[{"name":"Department of Artificial Intelligence, Kyushu Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tomohiro","family":"I","sequence":"additional","affiliation":[{"name":"Department of Artificial Intelligence, Kyushu Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hiroshi","family":"SAKAMOTO","sequence":"additional","affiliation":[{"name":"Department of Artificial Intelligence, Kyushu Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"532","reference":[{"key":"1","unstructured":"[1] S. Fukunaga, Y. Takabatake, T.I, and H. Sakamoto, \u201cOnline grammar compression for frequent pattern discovery,\u201d ICGI2016, pp.93-104. 2016."},{"key":"2","doi-asserted-by":"publisher","unstructured":"[2] N.J. Larsson and A. Moffat, \u201cOff-line dictionary-based compression,\u201d Proc. IEEE, vol.88, no.11, pp.1722-1732, 2000. 10.1109\/5.892708","DOI":"10.1109\/5.892708"},{"key":"3","unstructured":"[3] E. Lehman and A. Shelat, \u201cApproximation algorithms for grammar-based compression,\u201d SODA, pp.205-212, 2002."},{"key":"4","doi-asserted-by":"publisher","unstructured":"[4] E.-H. Yang and D.-K. He, \u201cEfficient universal lossless data compression algorithms based on a greedy sequential grammar transform-part two: with context models,\u201d IEEE Trans. Inf. Theory, vol.49, no.11, pp.2874-2894, 2003. 10.1109\/tit.2003.818411","DOI":"10.1109\/TIT.2003.818411"},{"key":"5","doi-asserted-by":"publisher","unstructured":"[5] W. Rytter, \u201cApplication of Lempel \u2014 Ziv factorization to the approximation of grammar-based compression,\u201d Theor. Comput. Sci., vol.302, no.1-3, pp.211-222, 2003. 10.1016\/s0304-3975(02)00777-6","DOI":"10.1016\/S0304-3975(02)00777-6"},{"key":"6","doi-asserted-by":"publisher","unstructured":"[6] H. Sakamoto, \u201cA fully linear-time approximation algorithm for grammar-based compression,\u201d J. Discrete Algorithms, vol.3, no.2-4, pp.416-430, 2005. 10.1016\/j.jda.2004.08.016","DOI":"10.1016\/j.jda.2004.08.016"},{"key":"7","doi-asserted-by":"publisher","unstructured":"[7] M. Charikar, E. Lehman, D. Liu, R. Panigrahy, M. Prabhakaran, A. Sahai, and A. Shelat, \u201cThe smallest grammar problem,\u201d IEEE Trans. Inf. Theory, vol.51, no.7, pp.2554-2576, 2005. 10.1109\/tit.2005.850116","DOI":"10.1109\/TIT.2005.850116"},{"key":"8","doi-asserted-by":"publisher","unstructured":"[8] S. Maruyama, H. Sakamoto, and M. Takeda, \u201cAn online algorithm for lightweight grammar-based compression,\u201d Algorithms, vol.5, no.4, pp.213-235, 2012. 10.3390\/a5020214","DOI":"10.3390\/a5020214"},{"key":"9","doi-asserted-by":"publisher","unstructured":"[9] S. Maruyama, Y. Tabei, H. Sakamoto, and K. Sadakane, \u201cFully-online grammar compression,\u201d SPIRE, vol.8214, pp.218-229, 2013. 10.1007\/978-3-319-02432-5_25","DOI":"10.1007\/978-3-319-02432-5_25"},{"key":"10","doi-asserted-by":"crossref","unstructured":"[10] Y. Tabei, Y. Takabatake, and H. Sakamoto, \u201cA succinct grammar compression,\u201d CPM, vol.7922, pp.218-229, 2013. 10.1007\/978-3-642-38905-4_23","DOI":"10.1007\/978-3-642-38905-4_23"},{"key":"11","doi-asserted-by":"crossref","unstructured":"[11] S. Maruyama and Y. Tabei, \u201cFully online grammar compression in constant space,\u201d DCC, pp.218-229, 2014. 10.1109\/dcc.2014.69","DOI":"10.1007\/978-3-319-02432-5_25"},{"key":"12","doi-asserted-by":"crossref","unstructured":"[12] C. Aggarwal and J. Han, eds., Frequent Pattern Mining, Springer, 2014.","DOI":"10.1007\/978-3-319-07821-2"},{"key":"13","doi-asserted-by":"crossref","unstructured":"[13] K. Sadakane, \u201cCompressed text databases with efficient query algorithms based on the compressed suffix array,\u201d ISAAC, vol.1969, pp.410-421, 2000. 10.1007\/3-540-40996-3_35","DOI":"10.1007\/3-540-40996-3_35"},{"key":"14","doi-asserted-by":"publisher","unstructured":"[14] G. Cormode and S. Muthukrishnan, \u201cThe string edit distance matching problem with moves,\u201d ACM Trans. Algorithms, vol.3, no.1, pp.1-19, 2007. 10.1145\/1186810.1186812","DOI":"10.1145\/1186810.1186812"},{"key":"15","doi-asserted-by":"crossref","unstructured":"[15] F. Hach, I. Numanagi\u0107, C. Alkan, and S.C. Sahinalp, \u201cScalce: boosting sequence compression algorithms using locally consistent encoding,\u201d Bioinformatics, vol.28, no.23, pp.3051-3057, 2012. 10.1093\/bioinformatics\/bts593","DOI":"10.1093\/bioinformatics\/bts593"},{"key":"16","doi-asserted-by":"publisher","unstructured":"[16] S. Maruyama, M. Nakahara, N. Kishiue, and H. Sakamoto, \u201cESP-Index: A compressed index based on edit-sensitive parsing,\u201d J. Discrete Alogrithms, vol.18, pp.100-112, 2013. 10.1016\/j.jda.2012.07.009","DOI":"10.1016\/j.jda.2012.07.009"},{"key":"17","doi-asserted-by":"crossref","unstructured":"[17] Y. Takabatake, Y. Tabei, and H. Sakamoto, \u201cOnline pattern matching for string edit distance with moves,\u201d SPIRE, vol.8799, pp.203-214, 2014. 10.1007\/978-3-319-11918-2_20","DOI":"10.1007\/978-3-319-11918-2_20"},{"key":"18","doi-asserted-by":"crossref","unstructured":"[18] Y. Takabatake, Y. Tabei, and H. Sakamoto, \u201cOnline self-indexed grammar compression,\u201d SPIRE, vol.9309, pp.258-269, 2015. 10.1007\/978-3-319-23826-5_25","DOI":"10.1007\/978-3-319-23826-5_25"},{"key":"19","doi-asserted-by":"publisher","unstructured":"[19] Y. Takabatake, K. Nakashima, T. Kuboyama, Y. Tabei, and H. Sakamoto, \u201csiEDM: an efficient string index and search algorithm for edit distance with moves,\u201d Algorithms, vol.9, no.2, p.Article 26, 2016. 10.3390\/a9020026","DOI":"10.3390\/a9020026"},{"key":"20","unstructured":"[20] T. Nishimoto, T. I, S. Inenaga, H. Bannai, and M. Takeda, \u201cDynamic index, lz factorization, and lcequeries in compressed space,\u201d arXiv: CoRR abs\/1504.06954, 2015."},{"key":"21","doi-asserted-by":"publisher","unstructured":"[21] M. Nakahara, S. Maruyama, T. Kuboyama, and H. Sakamoto, \u201cScalable detection of frequent substrings by grammar-based compression,\u201d IEICE Trans. Inf. Syst, vol.E96-D, no.3, pp.457-464, 2013. 10.1587\/transinf.e96.d.457","DOI":"10.1587\/transinf.E96.D.457"},{"key":"22","unstructured":"[22] M. Karpinski, W. Rytter, and A. Shinohara, \u201cAn efficient pattern-matching algorithm for strings with short descriptions,\u201d Nord. J. Comput., vol.4, pp.172-186, 1997."},{"key":"23","doi-asserted-by":"crossref","unstructured":"[23] G. Jacobson, \u201cSpace-efficient static trees and graphs,\u201d Proc. 30th Annual Symposium on Foundations of Computer Science (FOCS), Research Triangle Park, North Carolina, USA, 30 October-1 November, pp.549-554, 1989. 10.1109\/sfcs.1989.63533","DOI":"10.1109\/SFCS.1989.63533"},{"key":"24","doi-asserted-by":"publisher","unstructured":"[24] R. Raman, V. Raman, and S.R. Satti, \u201cSuccinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets,\u201d ACM Trans. Algor., vol.3, no.4, p.43, 2007. 10.1145\/1290672.1290680","DOI":"10.1145\/1290672.1290680"},{"key":"25","unstructured":"[25] R. Grossi, A. Gupta, and J. Vitter, \u201cHigh-order entropy-compressed text indexes,\u201d SODA, pp.636-645, 2003."},{"key":"26","doi-asserted-by":"crossref","unstructured":"[26] A. Golynski, J.I. Munro, and S.S. Rao, \u201cRank\/select operations on large alphabets: A tool for text indexing,\u201d Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Miami, Florida, USA, pp.368-373, 22-26 January, 2006. 10.1145\/1109557.1109599","DOI":"10.1145\/1109557.1109599"},{"key":"27","doi-asserted-by":"publisher","unstructured":"[27] G. Navarro and K. Sadakane, \u201cFully-functional static and dynamic succinct trees,\u201d ACM Trans. Algorithms, vol.10, no.3, pp.1-39, 2014. 10.1145\/2601073","DOI":"10.1145\/2601073"},{"key":"28","doi-asserted-by":"crossref","unstructured":"[28] V. M\u00e4kinen, D. Belazzougui, F. Cunial, and A.I. Tomescu, Genome-Scale Algorithm Design, Cambridge University Press, 2015.","DOI":"10.1017\/CBO9781139940023"},{"key":"29","unstructured":"[29] https:\/\/github.com\/nicolaprezza\/slz-rlbwt\/tree\/master\/extern\/DYNAMIC."}],"container-title":["IEICE Transactions on Information and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transinf\/E101.D\/3\/E101.D_2017FCP0010\/_pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,15]],"date-time":"2022-08-15T03:20:21Z","timestamp":1660533621000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transinf\/E101.D\/3\/E101.D_2017FCP0010\/_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018]]}},"URL":"https:\/\/doi.org\/10.1587\/transinf.2017fcp0010","relation":{},"ISSN":["0916-8532","1745-1361"],"issn-type":[{"value":"0916-8532","type":"print"},{"value":"1745-1361","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018]]}}}