{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,3]],"date-time":"2026-06-03T12:28:02Z","timestamp":1780489682079,"version":"3.54.1"},"reference-count":21,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2016,4,15]],"date-time":"2016-04-15T00:00:00Z","timestamp":1460678400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Although several self-indexes for highly repetitive text collections exist, developing an index and search algorithm with editing operations remains a challenge. Edit distance with moves (EDM) is a string-to-string distance measure that includes substring moves in addition to ordinal editing operations to turn one string into another. Although the problem of computing EDM is intractable, it has a wide range of potential applications, especially in approximate string retrieval. Despite the importance of computing EDM, there has been no efficient method for indexing and searching large text collections based on the EDM measure. We propose the first algorithm, named string index for edit distance with moves (siEDM), for indexing and searching strings with EDM. The siEDM algorithm builds an index structure by leveraging the idea behind the edit sensitive parsing (ESP), an efficient algorithm enabling approximately computing EDM with guarantees of upper and lower bounds for the exact EDM. siEDM efficiently prunes the space for searching query strings by the proposed method, which enables fast query searches with the same guarantee as ESP. We experimentally tested the ability of siEDM to index and search strings on benchmark datasets, and we showed siEDM\u2019s efficiency.<\/jats:p>","DOI":"10.3390\/a9020026","type":"journal-article","created":{"date-parts":[[2016,4,15]],"date-time":"2016-04-15T11:36:02Z","timestamp":1460720162000},"page":"26","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["siEDM: An Efficient String Index and Search Algorithm for Edit Distance with Moves"],"prefix":"10.3390","volume":"9","author":[{"given":"Yoshimasa","family":"Takabatake","sequence":"first","affiliation":[{"name":"Graduate School of Computer Science and Systems Engineering, Kyushu Institute of Technology, 680-4 Kawazu, Iizuka-shi, Fukuoka 820-8502, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kenta","family":"Nakashima","sequence":"additional","affiliation":[{"name":"Graduate School of Computer Science and Systems Engineering, Kyushu Institute of Technology, 680-4 Kawazu, Iizuka-shi, Fukuoka 820-8502, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tetsuji","family":"Kuboyama","sequence":"additional","affiliation":[{"name":"Computer Centre, Gakushuin University, 1-5-1 Mejiro, Toshima-ku, Tokyo 171-8588, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yasuo","family":"Tabei","sequence":"additional","affiliation":[{"name":"PRESTO, Japan Science and Technology Agency, 4-1-8 Honcho, Kawaguchi-shi, Saitama 332-0012, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3470-9187","authenticated-orcid":false,"given":"Hiroshi","family":"Sakamoto","sequence":"additional","affiliation":[{"name":"Graduate School of Computer Science and Systems Engineering, Kyushu Institute of Technology, 680-4 Kawazu, Iizuka-shi, Fukuoka 820-8502, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2016,4,15]]},"reference":[{"key":"ref_1","unstructured":"Takabatake, Y., Tabei, Y., and Sakamoto, H. (July, January 29). Improved ESP-index: A Practical Self-Index for Highly Repetitive Texts. Proceedings of the 13th International Symposium on Experimental Algorithms (SEA), Copenhargen, Denmark."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"313","DOI":"10.3233\/FI-2011-565","article-title":"Self-indexed grammar-based compression","volume":"111","author":"Claude","year":"2011","journal-title":"Fundam. Inform."},{"key":"ref_3","unstructured":"Gagie, T., Gawrychowski, P., K\u00e4rkk\u00e4inen, J., Nekrich, Y., and Puglisi, S.J. (April, January 31). LZ77-Based Self-Indexing with Faster Pattern Matching. Proceedings of the 11th Latin American Theretical Informatics Symposium (LATIN), Montevideo, Uruguay."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"12","DOI":"10.3389\/fbioe.2015.00012","article-title":"Searching and Indexing Genomic Databases via Kernelization","volume":"3","author":"Gagie","year":"2015","journal-title":"Front. Bioeng. Biotechnol."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Durbin, R., Eddy, S., Krogh, A., and Mitchison, G. (1998). Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids, Cambridge University Press.","DOI":"10.1017\/CBO9780511790492"},{"key":"ref_6","unstructured":"Crochemore, M., and Rytter, W. (1994). Text Algorithms, Oxford University Press."},{"key":"ref_7","first-page":"707","article-title":"Binary codes capable of correcting deletions, insertions and reversals","volume":"10","author":"Levenshtein","year":"1996","journal-title":"Sov. phys. dokl."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1186810.1186812","article-title":"The String Edit Distance Matching Problem with Moves","volume":"3","author":"Cormode","year":"2007","journal-title":"ACM Trans. Algor."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"380","DOI":"10.1016\/j.jda.2005.01.010","article-title":"Edit distance with move operations","volume":"5","author":"Shapira","year":"2007","journal-title":"J. Discret. Algorithms"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1587\/transinf.E92.D.158","article-title":"A Space-Saving Approximation Algorithm for Grammar-Based Compression","volume":"92-D","author":"Sakamoto","year":"2009","journal-title":"IEICE Trans. Inf. Syst."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"213","DOI":"10.3390\/a5020214","article-title":"An Online Algorithm for Lightweight Grammar-Based Compression","volume":"5","author":"Maruyama","year":"2012","journal-title":"Algorithms"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Maruyama, S., Tabei, Y., Sakamoto, H., and Sadakane, K. (2013, January 7\u20139). Fully-online grammar compression. Proceedings of the 20th International Symposium on String Processing and Information Retrieval Symposium (SPIRE), Jerusalem, Israel.","DOI":"10.1007\/978-3-319-02432-5_25"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Maruyama, S., and Tabei, Y. (2014, January 26\u201328). Fully-online grammar compression in constant space. Proceedings of the Data Compression Conference (DCC), Snowbird, UT, USA.","DOI":"10.1109\/DCC.2014.69"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1016\/j.jda.2012.07.009","article-title":"ESP-Index: A Compressed Index Based on Edit-Sensitive Parsing","volume":"18","author":"Maruyama","year":"2013","journal-title":"J. Discrete Alogrithms"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Takabatake, Y., Tabei, Y., and Sakamoto, H. (2015, January 1\u20134). Online Self-Indexed Grammar Compression. Proceedings of the 22nd International Symposium on String Processing and Information Retrieval (SPIRE), London, UK.","DOI":"10.1007\/978-3-319-23826-5_25"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1587\/transinf.E96.D.457","article-title":"Scalable Detection of Frequent Substrings by Grammar-Based Compression","volume":"96-D","author":"Nakahara","year":"2013","journal-title":"IEICE Trans. Inf. Syst."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Takabatake, Y., Tabei, Y., and Sakamoto, H. (2014, January 20\u201322). Online Pattern Matching for String Edit Distance with Moves. Proceedings of the 21st International Symposium on String Processing and Information Retrieva (SPIRE), Ouro Preto, Brazil.","DOI":"10.1007\/978-3-319-11918-2_20"},{"key":"ref_18","first-page":"172","article-title":"An efficient pattern-matching algorithm for strings with short descriptions","volume":"4","author":"Karpinski","year":"1997","journal-title":"Nord. J. Comput."},{"key":"ref_19","unstructured":"Jacobson, G. (November, January 30). Space-Efficient Static Trees and Graphs. Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS), Research Triangle Park, NC, USA."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Raman, R., Raman, V., and Rao, S.S. (2007). Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Trans. Algor., 3.","DOI":"10.1145\/1290672.1290680"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Golynski, A., Munro, J.I., and Rao, S.S. (2006, January 22\u201326). Rank\/select operations on large alphabets: A tool for text indexing. Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Miami, FL, USA.","DOI":"10.1145\/1109557.1109599"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/9\/2\/26\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T19:22:17Z","timestamp":1760210537000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/9\/2\/26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,4,15]]},"references-count":21,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2016,6]]}},"alternative-id":["a9020026"],"URL":"https:\/\/doi.org\/10.3390\/a9020026","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,4,15]]}}}